Jewels are Forever

Contributions on Theoretical Computer Science in Honor of Arto Salomaa

Juhani Karhumäki, Hermann Maurer, Gheorghe Paun, Grzegorz Rozenberg (Herausgeber)

Buch | Softcover

XXX, 379 Seiten

2011 | 1. Softcover reprint of the original 1st ed. 1999
Springer Berlin (Verlag)
978-3-642-64304-0 (ISBN)

Artikel merken

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.

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.

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.

Erscheint lt. Verlag	16.9.2011
Zusatzinfo	XXX, 379 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	632 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
	Informatik ► Weitere Themen ► Bioinformatik
	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
Schlagworte	Algorithm analysis and problem complexity • Algorithmics • algorithms • Automata • Automata Theory • Calculus • combinatorics • combinatorics of words • Complexity • Formal Language Theory • grammar • lattice • mapping
ISBN-10	3-642-64304-3 / 3642643043
ISBN-13	978-3-642-64304-0 / 9783642643040
Zustand	Neuware