Jewels Are Forever: Contributions on Theoretical Computer Science in Honor of Arto Salomaa

ISBN-13: 9783642643040 / Angielski / Miękka / 2011 / 379 str.

Juhani Karhum Ki; Hermann Maurer; Gheorghe Paun

Opis

Dedicated to Arto Salomaa, a towering figure of theoretical computer science, on the occasion of his 65th birthday, this book is a tribute to him on behalf of the theoretical computer science community. The contributions are written by internationally recognized scientists and cover most of Salomaa's many research areas. Due to its representative selection of classic and cutting edge trends in theoretical computer science, the book constitutes a comprehensive state-of-the-art survey. The contributions are in such central areas as automata theory, algorithms and complexity, and combinatorics of words. But not only that, they take up new areas such as regular sets and biocomputing. While some are survey articles of fundamental topics, most are original research papers.

Spis treści

I. Automata I: Finite State Machines.- Semilattices of Fault Semiautomata.- Thompson Languages.- On Some Special Classes of Regular Languages.- Synchronized Shuffle and Regular Languages.- Synchronization Expressions:Characterization Results and Implementation.- II. Automata II: More General Devices.- Uniformization of Rational Relations.- Tree-Walking Pebble Automata.- Counter Machines: Decision Problems and Applications.- On the Equivalence of Finite Substitutions and Transducers.- Complementation of Büchi Automata Revisited.- III. Automata with Multiplicities.- Languages Accepted by Integer Weighted Finite Automata.- A Power Series Approach to Bounded Languages.- Full Abstract Families of Tree Series I.- Linear Automata, Rational Series and a Theorem of Fine and Wilf.- IV. Formal Languages.- Numerical Parameters of Evolutionary Grammars.- Iterated GSM Mappings: A Collapsing Hierarchy.- On the Length of Words.- An Insertion into the Chomsky Hierarchy?.- Word Length Controlled DT0L Systems and Slender Languages.- V. Algorithms and Complexity.- Program-Size Complexity of Initial Segments and Domination Reducibility.- Stability of Approximation Algorithms and the Knapsack Problem.- Some Examples of Average-case Analysis by the Incompressibility Method.- Complexity of Language Recognition Problems for Compressed Words.- Algorithms on Continued Fractions.- VI. Combinatorics of Words.- On the Index of Sturmian Words.- Repetitions and Boxes in Words and Pictures.- Small Aperiodic Sets of Triangular and Hexagonal Tiles.- Quadratic Word Equations.- Fair and Associative Infinite Trajectories.- Forbidden Factors in Finite and Infinite Words.- VII. Novel Directions.- Reversible Molecular Computation in Ciliates.- Logic, Probability, and Rough Sets.- List of Contributors.

O autorze

Hermann Maurer studierte Mathematik und Physik in Österreich, Informatik in Kanada. Er war einige Jahre in der Industrie tätig, aber ist nun seit mehr als 30 Jahren Universitätsprofessor für Informatik an Universitäten in Kanada, USA, Deutschland, Brasilien, Australien, Neuseeland und vor allem an der Technischen Universität Graz in Österreich. Er ist mit zahlreichen wissenschaftlichen Büchern und über 500 wissenschaftlichen Publikationen in seinem Bereich der Informatik aktiv tätig, ist aber auch seit vielen Jahren schriftstellerisch aktiv, oft unter einem Pseudonym.