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

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.

---

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.

---

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.
Content:
Front Matter....Pages I-XXX
Front Matter....Pages 1-1
Semilattices of Fault Semiautomata....Pages 3-15
Thompson Languages....Pages 16-24
On Some Special Classes of Regular Languages....Pages 25-34
Synchronized Shuffle and Regular Languages....Pages 35-44
Synchronization Expressions: Characterization Results and Implementation....Pages 45-56
Front Matter....Pages 57-57
Uniformization of Rational Relations....Pages 59-71
Tree-Walking Pebble Automata....Pages 72-83
Counter Machines: Decision Problems and Applications....Pages 84-96
On the Equivalence of Finite Substitutions and Transducers....Pages 97-108
Complementation of B?chi Automata Revisited....Pages 109-120
Front Matter....Pages 121-121
Languages Accepted by Integer Weighted Finite Automata....Pages 123-134
A Power Series Approach to Bounded Languages....Pages 135-144
Full Abstract Families of Tree Series I....Pages 145-156
Linear Automata, Rational Series and a Theorem of Fine and Wilf....Pages 157-168
Front Matter....Pages 169-169
Numerical Parameters of Evolutionary Grammars....Pages 171-181
Iterated GSM Mappings: A Collapsing Hierarchy....Pages 182-193
On the Length of Words....Pages 194-203
An Insertion into the Chomsky Hierarchy?....Pages 204-212
Word Length Controlled DT0L Systems and Slender Languages....Pages 213-221
Front Matter....Pages 223-223
Program-Size Complexity of Initial Segments and Domination Reducibility....Pages 225-237
Front Matter....Pages 223-223
Stability of Approximation Algorithms and the Knapsack Problem....Pages 238-249
Some Examples of Average-case Analysis by the Incompressibility Method....Pages 250-261
Complexity of Language Recognition Problems for Compressed Words....Pages 262-272
Algorithms on Continued Fractions....Pages 273-284
Front Matter....Pages 285-285
On the Index of Sturmian Words....Pages 287-294
Repetitions and Boxes in Words and Pictures....Pages 295-306
Small Aperiodic Sets of Triangular and Hexagonal Tiles....Pages 307-313
Quadratic Word Equations....Pages 314-326
Fair and Associative Infinite Trajectories....Pages 327-338
Forbidden Factors in Finite and Infinite Words....Pages 339-350
Front Matter....Pages 354-354
Reversible Molecular Computation in Ciliates....Pages 353-363
Logic, Probability, and Rough Sets....Pages 364-373
Back Matter....Pages 375-379

---

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.
Content:
Front Matter....Pages I-XXX
Front Matter....Pages 1-1
Semilattices of Fault Semiautomata....Pages 3-15
Thompson Languages....Pages 16-24
On Some Special Classes of Regular Languages....Pages 25-34
Synchronized Shuffle and Regular Languages....Pages 35-44
Synchronization Expressions: Characterization Results and Implementation....Pages 45-56
Front Matter....Pages 57-57
Uniformization of Rational Relations....Pages 59-71
Tree-Walking Pebble Automata....Pages 72-83
Counter Machines: Decision Problems and Applications....Pages 84-96
On the Equivalence of Finite Substitutions and Transducers....Pages 97-108
Complementation of B?chi Automata Revisited....Pages 109-120
Front Matter....Pages 121-121
Languages Accepted by Integer Weighted Finite Automata....Pages 123-134
A Power Series Approach to Bounded Languages....Pages 135-144
Full Abstract Families of Tree Series I....Pages 145-156
Linear Automata, Rational Series and a Theorem of Fine and Wilf....Pages 157-168
Front Matter....Pages 169-169
Numerical Parameters of Evolutionary Grammars....Pages 171-181
Iterated GSM Mappings: A Collapsing Hierarchy....Pages 182-193
On the Length of Words....Pages 194-203
An Insertion into the Chomsky Hierarchy?....Pages 204-212
Word Length Controlled DT0L Systems and Slender Languages....Pages 213-221
Front Matter....Pages 223-223
Program-Size Complexity of Initial Segments and Domination Reducibility....Pages 225-237
Front Matter....Pages 223-223
Stability of Approximation Algorithms and the Knapsack Problem....Pages 238-249
Some Examples of Average-case Analysis by the Incompressibility Method....Pages 250-261
Complexity of Language Recognition Problems for Compressed Words....Pages 262-272
Algorithms on Continued Fractions....Pages 273-284
Front Matter....Pages 285-285
On the Index of Sturmian Words....Pages 287-294
Repetitions and Boxes in Words and Pictures....Pages 295-306
Small Aperiodic Sets of Triangular and Hexagonal Tiles....Pages 307-313
Quadratic Word Equations....Pages 314-326
Fair and Associative Infinite Trajectories....Pages 327-338
Forbidden Factors in Finite and Infinite Words....Pages 339-350
Front Matter....Pages 354-354
Reversible Molecular Computation in Ciliates....Pages 353-363
Logic, Probability, and Rough Sets....Pages 364-373
Back Matter....Pages 375-379
....