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