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 BibTeX

@proceedings{DBLP:conf/birthday/1999salomaa,
  editor    = {Juhani Karhum{\"a}ki and
               Hermann A. Maurer and
               Gheorghe Paun and
               Grzegorz Rozenberg},
  title     = {Jewels are Forever, Contributions on Theoretical Computer Science
               in Honor of Arto Salomaa},
  booktitle = {Jewels are Forever},
  publisher = {Springer},
  year      = {1999},
  isbn      = {3-540-65984-6},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Automata I: Finite State Machines

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

Automata II: More General Devices

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

Automata with Multiplicities

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

Formal Languages

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

Algorithms and Complexity

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

Combinatorics of Words

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

Novel Directions

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