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

by Salomaa, Arto; Maurer, Hermann; Paun, Gheorghe; Rozenberg, Grzegorz; Karhumaki, Juhani

• ISBN13: 9783540659846
• ISBN10: 3540659846
• Edition: 1st
• Format: Hardcover
• Copyright: 1999-07-01
• Publisher: Springer Verlag

Summary

Presents a collection of contributions on the cutting edge trends in theoretical computer science on the occasion of Arto Salomaa's 65th birthday. Constitutes a comprehensive state-of- the-art survey in central areas as automata theory, algorithms and complexity, and combinatorics of words from internationally known scientists.

Table of Contents

Laudation for Arto Salomaa	xi
Bibliography of Arto Salomaa	xiii
Part I. Automata I: Finite State Machines
Semilattices of Fault Semiautomata	3	(13)
Jonusz A. Brzozowski
Helmut Jurgensen
Thompson Languages	16	(9)
Dora Giammarresi
Jean-Luc Ponty
Derick Wood
On Some Special Classes of Regular Languages	25	(10)
Balazes Imreh
Masami Ito
Synchronized Shuffle and Regular Languages	35	(10)
Michel Latteux
Yves Roos
Synchronization Expressions: Characterization Results and Implementation	45	(14)
Kai Salomaa
Sheng Yu
Part II. Automata II: More General Devices
Uniformization of Rational Relations	59	(13)
Christian Choffrut
Serge Grigorieff
Tree-Walking Pebble Automata	72	(12)
Joost Engelfriet
Hendrik Jan Hoogeboom
Counter Machines: Decision Problems and Applications	84	(13)
Oscar H. Ibarra
Jianwen Su
On the Equivalence of Finite Substitutions and Transducers	97	(12)
Juhani Karhumaki
Leonid P. Lisovik
Complementation of Buchi Automata Revisited	109	(14)
Wolfgang Thomas
Part III. Automata with Multiplicities
Languages Accepted by Integer Weighted Finite Automata	123	(12)
Vesa Halava
Tero Harju
A Power Series Approach to Bounded Languages	135	(10)
Juha Honkala
Full Abstract Families of Tree Series I	145	(12)
Werner Kuich
Linear Automata, Rational Series and a Theorem of Fine and Wilf	157	(14)
Giovanna Melideo
Cesidia Pasquarelli
Stefano Varricchio
Part IV. Formal Languages
Numerical Parameters of Evolutionary Grammars	171	(11)
Jurgen Dassow
Iterated GSM Mappings: A Collapsing Hierarchy	182	(12)
Vincenzo Manco
Carlos Martin-Vide
Gheorghe Paun
On the Length of Words	194	(10)
Solomon Marcus
An Insertion into the Chomsky Hierarchy?	204	(9)
Robert McNaughton
Word Length Controlled DTOL Systems and Slender Languages	213	(12)
Taishin Yasunobu Nishida
Part V. Algorithms and Complexity
Program-Size Complexity of Initial Segments and Domination Reducibility	225	(13)
Cristian S. Calude
Richard J. Coles
Stability of Approximation Algorithms and the Knapsack Problem	238	(12)
Juraj Hromkovic
Some Examples of Average-case Analysis by the Incompressibility Method	250	(12)
Tao Jiang
Ming Li
Paul Vitanyi
Complexity of Language Recognition Problems for Compressed Words	262	(11)
Wojciech Plandowski
Wojciech Rytter
Algorithms on Continued Fractions	273	(14)
Octavian Soldea
Azaria Paz
Part VI. Combinatorics of Words
On the Index of Sturmian Words	287	(8)
Jean Berstel
Repetitions and Boxes in Words and Pictures	295	(12)
Arturo Carpi
Aldo de Luca
Small Aperiodic Sets of Triangular and Hexagonal Tiles	307	(7)
Karel Culik II
Quadratic Word Equations	314	(13)
Volker Diekert
John Michael Robson
Fair and Associative Infinite Trajectories	327	(12)
Alexandru Mateescu
George Daniel Mateescu
Forbidden Factors in Finite and Infinite Words	339	(14)
Filippo Mignosi
Antonio Restivo
Marinella Sciortino
Part VII. Novel Directions
Reversible Molecular Computation in Ciliates	353	(11)
Lila Kari
Jarkko Kari
Laura F. Landweber
Logic, Probability, and Rough Sets	364	(11)
Zdzislaw Pawlak
List of Contributors	375