Jewels are Forever
Contributions on Theoretical Computer Science in Honor of Arto Salomaa
Published on 16. September 2011
Book
Paperback/Softback
XXX, 379 pages
978-3-642-64304-0 (ISBN)
Description
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.
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.
More details
Edition
Softcover reprint of the original 1st ed. 1999
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XXX, 379 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 23 mm
Weight
633 gr
ISBN-13
978-3-642-64304-0 (9783642643040)
DOI
10.1007/978-3-642-60207-8
Schweitzer Classification
Other editions
Additional editions
Juhani Karhumäki | Hermann Maurer | Gheorghe Paun
Jewels are Forever
Contributions on Theoretical Computer Science in Honor of Arto Salomaa
Book
06/1999
Springer
€85.55
Article exhausted; check different version
Content
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.