Handbook of Automata Theory Volume II Automata in Mathematics and Selected Applications

Dedicatory
Preface
Contents
List of contributors
Part IV. Automata in mathematics
23. Rational subsets of groups
1. Introduction
2. Finitely generated groups
3. Inverse automata and Stallings' construction
4. Rational and recognisable subsets
References
24. Groups defined by automata
1. Introduction
2. The geometry of the Cayley graph
3. Groups generated by automata
References
25. Automata in number theory
1. Introduction
2. Automatic sequences and automatic sets of integers
3. Prime numbers and finite automata
4. Expansions of algebraic numbers in integer bases
5. The Skolem–Mahler–Lech theorem in positive characteristic
6. The algebraic closure of F_p(t)
7. Update
References
26. On Cobham's theorem
1. Introduction
2. Numeration basis
3. Automatic sequences
4. Multidimensional extension and first-order logic
5. Numeration systems and substitutions
6. Cobham's theorem in various contexts
7. Decidability issues
References
27. Symbolic dynamics
1. Introduction
2. Shift spaces
3. Automata
4. Minimal automata
5. Symbolic conjugacy
6. Special families of automata
7. Syntactic invariants
References
28. Automatic structures
1. Introduction
2. Automatic Structures
3. The connection with MSOL
4. Operations on automatic structures
5. Proving a structure has no automatic presentation
6. Equivalent automatic presentations
7. Automatic-like structures
8. Outlook
References
29. Automata and finite model theory
1. Introduction
2. Definitions
3. Finite model theory of strings and trees
4. Automata and finite model theory of arbitrary structures
References
30. Finite automata, image manipulation, and automatic real functions
1. Introduction
2. Definitions and notation
3. Normal forms, minimality, and decidability
4. Examples
5. Image manipulation
6. A monster function
References
Part V. Selected applications
31. Communicating automata
1. Introduction
2. Communicating automata
3. Reachability problems
4. Specifications and model-checking
5. Realisability
References
32. Symbolic methods and automata
1. Introduction
2. Integer domain
3. Real domain
4. Conclusions and perspectives
References
33. Synthesis with finite automata
1. Introduction
2. Church problem
3. Control of discrete event systems
4. Distributed synthesis: synchronous architectures
5. Distributed synthesis: Zielonka automata
References
34. Timed automata
1. Introduction
2. Timed automata
3. The emptiness problem, why and how?
4. The region abstraction: a key for decidability
5. Applications of the region automaton construction
6. The language-theoretic perspective
7. Conclusion and current developments
References
35. Higher-order recursion schemes and their automata models
1. Introduction
2. Preliminaries
3. From CPDA to recursion schemes
4. From recursion schemes to collapsible pushdown automata
5. Safe higher-order recursion schemes
References
36. Analysis of probabilistic processes and automata theory
1. Introduction
2. Definitions and Background
3. Analysis of finite-state Markov chains
4. Analysis of finite-state MDPs
5. Adding recursion to MCs and MDPs
References
37. Natural language parsing
1. Introduction to natural language parsing
2. Preliminaries
3. Tabulation
4. LR recognition
5. Earley's algorithm
6. Cocke–Younger–Kasami algorithm
7. Bibliographic notes
References
38. Verification
1. Introduction
2. Linear-time logics
3. Applications
4. Branching-time logics
5. Applications
References
39. Automata and quantum computing
1. Introduction
2. Mathematical background
3. Preliminaries
4. One-way QFAs
5. Two-way QFAs
6. Other models and results
7. Concluding remarks
References
Index