65. Birthday: Arto Salomaa, 1999

Juhani Karhumäki, Hermann A. Maurer, Gheorghe Paun, Grzegorz Rozenberg (Eds.): Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa. Springer 1999, ISBN 3-540-65984-6

Automata I: Finite State Machines

Janusz A. Brzozowski, Helmut Jürgensen: Semilattices of Fault Semiautomata. 3-15
Dora Giammarresi, Jean-Luc Ponty, Derick Wood: Thompson Languages. 16-24
Balázs Imreh, Masami Ito: On Some Special Classes of Regular Languages. 25-34
Michel Latteux, Yves Roos: Synchronized Shuffle and Regular Languages. 35-44
Kai Salomaa, Sheng Yu: Synchronization Expressions: Characterization Results and Implementation. 45-56

Christian Choffrut, Serge Grigorieff: Uniformization of Rational Relations. 59-71
Joost Engelfriet, Hendrik Jan Hoogeboom: Tree-Walking Pebble Automata. 72-83
Oscar H. Ibarra, Jianwen Su: Counter Machines: Decision Problems and Applications. 84-96
Juhani Karhumäki, Leonid P. Lisovik: On the Equivalence of Finite Substitutions and Transducers. 97-108
Wolfgang Thomas: Complementation of Büchi Automata Revised. 109-120

Vesa Halava, Tero Harju: Languages Accepted by Integer Weighted Finite Automata. 123-134
Juha Honkala: A Power Series Approach to Bounded Languages. 135-144
Werner Kuich: Full Abstract Families of Tree Series I. 145-156
Giovanna Melideo, Cesidia Pasquarelli, Stefano Varricchio: Linear Automata, Rational Series and a Theorem of Fine and Wilf. 157-168

Jürgen Dassow: Numerical Parameters of Evolutionary Grammars. 171-181
Vincenzo Manca, Carlos Martín-Vide, Gheorghe Paun: Iterated GSM Mappings: A Collapsing Hierarchy. 182-193
Solomon Marcus: On the Length of Words. 194-203
Robert McNaughton: An Insertion into the Chomsky Hierarchy? 204-212
Taishin Y. Nishida: Word Length Controlled DT0L Systems and Slender Languages. 213-221

Cristian Calude, Richard J. Coles: Program-Size Complexity of Initial Segments and Domination Reducibility. 225-237
Juraj Hromkovic: Stability of Approximation Algorithms and the Knapsack Problem. 238-249
Tao Jiang, Ming Li, Paul M. B. Vitányi: Some Examples of Average-case Analysis by the Imcompressibility Method. 250-261
Wojciech Plandowski, Wojciech Rytter: Complexity of Language Recognition Problems for Compressed Words. 262-272
Octavian Soldea, Azaria Paz: Algorithms on Continued Fractions. 273-284

Jean Berstel: On the Index of Sturmian Words. 287-294
Arturo Carpi, Aldo de Luca: Repetitions and Boxes in Words and Pictures. 295-306
Karel Culik II: Small Aperiodic Sets of Triangular and Hexagonal Tiles. 307-313
Volker Diekert, John Michael Robson: Quadratic Word Equations. 314-326
Alexandru Mateescu, George Daniel Mateescu: Fair and Associative Infinite Trajectories. 327-338
Filippo Mignosi, Antonio Restivo, Marinella Sciortino: Forbidden Factors in Finite and Infinite Words. 339-350

Lila Kari, Jarkko Kari, Laura F. Landweber: Reversible Molecular Computation in Ciliates. 353-363
Zdzislaw Pawlak: Logic, Probability, and Rough Sets. 364-373