Handbook of Automata Theory Volume I Theoretical Foundations

Preface
Contents
List of contributors
Part I. Foundations
1. Finite automata
1. Basic algebraic structures
2. Words, languages and automata
3. Operations on recognisable languages
4. Minimal automaton and syntactic monoid
5. Rational versus recognisable
6. Algebraic approach
References
2. Automata and rational expressions
1. A new look at Kleene's theorem
2. Rationality and recognisability
3. From automata to expressions: the AtEs-maps
4. From expressions to automata: the EtAs-maps
5. Changing the monoid
6. Introducing weights
7. Notes
References
3. Finite transducers and rational transductions
1. Introduction
2. Basic definitions
3. Morphic representations
4. Applications
5. Undecidability in transductions
6. Further reading
References
4. Weighted automata
1. Introduction
2. Weighted automata and their behaviour
3. Linear representations
4. The Kleene–Schützenberger theorem
5. Semimodules
6. Nivat's theorem
7. Weighted monadic second-order logic
8. Decidability of "r_1=r_2"?
9. Characteristic series and supports
10. Further results
References
5. Max-plus automata
1. Introduction
2. Preliminaries
3. One-letter max-plus automata
4. General max-plus automata
5. Bibliographic notes
References
6. ω-Automata
1. Introduction
2. Types of omega-automata
3. Basic properties of Büchi automata
4. Basic constructions
5. Run DAG’s of Büchi automata
6. Run trees of Büchi automata
7. Congruence relations
8. Loop structure
9. Alternation
10. Applications in logic
11. More complex recurrence conditions
References
7. Automata on finite trees
1. Introduction
2. Fundamentals on tree automata
3. Ground-tree rewriting
4. Tree-walking automata
5. Automata on unranked trees
6. Classification of regular tree languages
7. Conclusion
References
8. Automata on infinite trees
1. Introduction
2. Automata on infinite trees
3. Constructions for complementation and simulation
4. Decision problems
5. Applications in logic
References
9. Two-dimensional models
1. Introduction
2. Basic concepts for picture definition
3. Tiling recognition
4. Grammars
5. Comparison of language families
6. Conclusion
References
Part II. Complexity issues
10. Minimisation of automata
1. Introduction
2. Definitions and notation
3. Brzozowski's algorithm
4. Moore's algorithm
5. Hopcroft's algorithm
6. Slow automata
7. Minimisation by fusion
8. Dynamic minimisation
9. Extensions and special cases
References
11. Learning algorithms
1. Introduction
2. Preliminaries
3. Classical results
4. Learning from given data
5. Learning non-deterministic finite automata
6. Learning regular tree languages
7. PAC learning
8. Applications and further material
References
12. Descriptional complexity of regular languages
1. Introduction
2. Descriptional complexity and lower bound techniques
3. Transformation between models for regular languages
4. Operations on regular languages
5. Some recent developments
References
13. Enumerating regular expressions and their languages
1. Introduction and overview
2. On measuring the size of a regular expression
3. A simple grammar for valid regular expressions
4. Unambiguous context-free grammars and the Chomsky–Schützenberger theorem
5. Solving algebraic equations using Gröbner bases
6. Asymptotic bounds via singularity analysis
7. Lower bounds on enumeration of regular languages by regular expressions
8. Upper bounds on enumeration of regular languages by regular expressions
9. Exact enumerations
10. Conclusion and open problems
References
14. Circuit complexity of regular languages
1. Introduction
2. Circuits
3. Syntactic monoid
4. Regular expressions
5. Circuit complexity of regular languages
6. Circuit size of regular languages
7. Final remarks
References
15. Černý's conjecture and the road colouring problem
1. Synchronising automata, their origins and importance
2. Algorithmic and complexity issues
3. Around the Černý's conjecture
4. The road colouring problem
References
Part III. Algebraic and topological theory of automata
16. Varieties
1. Motivation and examples
2. Equations, identities and families of languages
3. Connections with logic
4. Operations on classes of languages
5. Varieties in other algebraic frameworks
References
17. Profinite topologies
1. Introduction
2. Profinite topologies for general algebras
3. The case of semigroups
4. Relatively free profinite semigroups
References
18. The factorisation forest theorem
1. Introduction
2. Some definitions
3. The factorisation forest theorem
4. Algebraic applications
5. Variants of the factorisation forest theorem
6. Applications as an accelerating structure
References
19. Wadge–Wagner hierarchies
1. The Wadge hierarchy
2. The Wagner hierarchy
References
20. Equational theories for automata
1. Introduction
2. Conway semirings
3. Automata in Conway semirings
4. Iteration semirings
5. Complete semirings
6. Continuous semirings
7. Completeness
8. Inductive *-semirings and Kleene algebras
9. Residuation
10. Some extensions
References
21. Language equations
1. Introduction
2. General properties of operations
3. Equations with one-sided concatenation
4. Resolved systems of equations
5. Equations with constant sides
6. Equations of the general form
7. Equations with erasing operations
References
22. Algebra for trees
1. Introduction
2. Trees as ground terms
3. A recipe for designing an algebra
4. Preclones
5. Forest algebra
6. Seminearring
7. Nesting algebras
8. Recent developments
References
Index