## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

Automata theory lies at the foundation of computer science, and is vital to a theoretical understanding of how computers work and what constitutes formal methods. This treatise gives a rigorous account of the topic and illuminates its real meaning by looking at the subject in a variety of ways. The first part of the book is organised around notions of rationality and recognisability. The second part deals with relations between words realised by finite automata, which not only exemplifies the automata theory but also illustrates the variety of its methods and its fields of application. Many exercises are included, ranging from those that test the reader, to those that are technical results, to those that extend ideas presented in the text. Solutions or answers to many of these are included in the book.

1. Cover
2. Title
5. Preface to the English Edition
6. Preface
7. M. Pascal’s Division Machine
8. 0 Fundamental Structures
9. The three stages of rationality
1. I The Simplest Possible Machine. . .
1. 1 What is an ‘automaton’?
1. 1.1 First definitions – first examples
2. 1.2 Basic constructions, basic properties
3. 1.3 The graph perspective
4. 1.4 Some supplementary definitions
2. 2 Rational languages
1. 2.1 Rational operations
2. 2.2 Rational languages
3. 2.3 Rational is recognisable
4. 2.4 Recognisable is rational
3. 3 The functional perspective
1. 3.1 From transitions to the transition function
2. 3.2 Deterministic automata
3. 3.3 Minimisation
4. 4 Rational expressions
1. 4.1 Rational expressions and languages
2. 4.2 Rational identities
3. 4.3 Expressions for the behaviour of a finite automaton
4. 4.4 Derivation of expressions
5. 5 From expressions to automata
1. 5.1 The standard automaton of an expression
2. 5.2 The derived term automaton
3. 5.3 String matching
6. 6 Star height
1. 6.1 Two heights and a degree
2. 6.2 Eggan’s Theorem
3. 6.3 An infinite hierarchy
4. 6.4 Generalised star height
7. 7 A field of automata
8. 8 A crop of properties
9. Solutions to the exercises
10. Notes & references
2. II The Power of Algebra
1. 1 Automata and rational sets
1. 1.1 Automata over a monoid
2. 1.2 Rational sets
3. 1.3 Behaviour of finite automata
4. 1.4 Unambiguous rational sets
2. 2 Actions and recognisable sets
1. 2.1 Actions on a set
2. 2.2 Recognisable here, recognisable there
3. 2.3 Elementary operations on recognisable subsets
4. 2.4 Minimisation
5. 2.5 Algebra at work
3. 3 Morphisms and coverings
1. 3.1 Automata morphisms
2. 3.2 Quotients of automata
3. 3.3 Automata coverings
4. 3.4 The Schützenberger covering
4. 4 Universal automaton
1. 4.1 Factorisations
2. 4.2 Universal automata of a subset
3. 4.3 Construction of the universal automaton
4. 4.4 Language approximations
5. 5 The importance of being well ordered
1. 5.1 Well quasi-orderings
2. 5.2 Derivations
6. 6 Rationals in the free group
1. 6.1 Recognisable and rational in groups
2. 6.2 Description of the free group
3. 6.3 Rationals of the free group
4. 6.4 Büchi systems
7. 7 Rationals in commutative monoids
1. 7.1 The natural order on A⊕
2. 7.2 The lexicographic order on nk
3. 7.3 Subtractive submonoids and affine sets
4. 7.4 Semi-linear and semi-simple sets
5. 7.5 Rationals of nk
6. 7.6 Rationals of commutative monoids
8. 8 Star height of group languages
9. Solutions to the exercises
10. Notes & references
3. III The Pertinence of Enumeration
1. 1 Formal power series on a graded monoid
1. 1.1 Formal power series over M with coefficients in z
3. 1.3 Topology on km
2. 2 k-automata and k-rational power series
1. 2.1 Star of a power series
2. 2.2 k-rational series
3. 2.3 Weighted automaton in a semiring
4. 2.4 The Fundamental Theorem of finite automata
5. 2.5 k-coverings k-quotients
3. 3 k-recognisable series
1. 3.1 k-representations
2. 3.2 Products
3. 3.3 The Kleene-Schützenberger Theorem
4. 4 Series on a free monoid
1. 4.1 A characterisation of recognisable series
2. 4.2 Derivation of rational k-expressions
3. 4.3 Series on a field
4. 4.4 Rational series and their supports
5. 5 Series on an arbitrary monoid
6. 6 Rational subsets in free products
7. 7 A non-commutative linear algebra primer
8. Solutions to the exercises
9. Notes & references
10. Rationality in relations
1. IV The Richness of Transducers
1. 1 Rational relations: an introduction
1. 1.1 Rational relations
2. 1.2 Realisation by automata
3. 1.3 Realisation by morphisms
4. 1.4 Recognisable relations
5. 1.5 Realisation by representation
6. 1.6 The Rabin–Scott model
2. 2 k-relations
1. 2.1 Definitions
2. 2.2 Composition
3. 2.3 Multiplicative k-relations
3. 3 Rational k-relations
1. 3.1 Reasonable semirings.
2. 3.2 Realisation of rational k-relations
3. 3.3 Evaluation and Composition Theorems
4. 4 Equivalence of finite k-transducers
5. 5 Deterministic rational relations
1. 5.1 Transducers with an endmarker
2. 5.2 Deterministic transducers
3. 5.3 Deterministic relations
4. 5.4 Geography of Rat A* × B* I
5. 5.5 Matrix representations
6. 5.6 An example: the map equivalence of a morphism
6. 6 Synchronisation of transducers
1. 6.1 Rational relations of bounded length discrepancy
2. 6.2 Transducers of bounded lag
3. 6.3 Synchronous relations
7. 7 Malcev-Neumann series
1. 7.1 Order on the free group
2. 7.2 Series on an ordered group
8. Solutions to the exercises
9. Notes & references
2. V The Simplicity of Functional Transducers
1. 1 Functionary
1. 1.1 Deciding functionality
2. 1.2 Sequential functions
3. 1.3 Pure sequential functions
4. 1.4 Local functions
2. 2 Uniformisation of rational relations
1. 2.1 Proof of Theorem 2.1 (transducer version)
2. 2.2 Proof of Theorem 2.1 (representation version)
3. 2.3 Decomposition of rational functions
4. 2.4 The Rational Skimming Theorem II
3. 3 Cross-section of rational functions
1. 3.1 The rational cross-section property
2. 3.2 Choosing the uniformisation (or the cross-section)
4. 4 Sequential functions
1. 4.1 Two characterisations
2. 4.2 Deciding sequentiality
3. 4.3 Minimisation
4. 4.4 The (Great) Sequentiality Theorem
5. 4.5 Pure sequential functions and local functions
6. Solutions to the exercises
7. Notes & references
11. Bibliography
12. Index