Overview

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.

Full Product Details

Author:   Juhani Karhumäki ,  Hermann Maurer ,  Gheorghe Paun ,  Grzegorz Rozenberg
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   Softcover reprint of the original 1st ed. 1999
Dimensions:   Width: 15.50cm , Height: 2.10cm , Length: 23.50cm
Weight:   0.633kg
ISBN:  

9783642643040

ISBN 10:   3642643043
Pages:   379
Publication Date:   16 September 2011
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions