Algebraic Theory of Automata

PrefaceChapter 1. Algebraic Prelimmaries 1.1 Sets 1.2 Relations and Mappings 1.3 Groupoids, Semigroups 1.4 Identity, Monoid 1.5 Isomorphism. Representation of Monoids by Right Translations 1.6 Groups 1.7 Reflexivity, Symmetry, Transitivity 1.8 Equivalence Relations, Partitions 1.9 Properties of Partitions 1.10 Congruences, Admissible Partitions 1.11 Homomorphism 1.12 Homomorphisms of Semigroups 1.13 Subgroups of a Group 1.14 Normal Subgroups. Simple Groups 1.15 Direct Product of Groups. Homomorphisms onto Simple Groups 1.16 Some Properties of Semigroups 1.17 Universal AlgebrasChapter 2. Semiautomata 2.1 Definition and Representation of a Semiautomaton 2.2 The Semigroup of a Semiautomaton 2.3 Right Congruences Over Σ* and the Corresponding Semiautomata 2.4 Subsemiautomata. Homomorphism 2.5 Homomorphisms of One-Input Semiautomata 2.6 Semiautomata and the Corresponding Congruences Over Σ* 2.7 The Homomorphism of Semigroups of Homomorphic Semiautomata 2.8 Nondeterministic SemiautomataChapter 3. Recognizers (Rabin-Scott Automata) 3.1 Automata 3.2 The Characterization of Regular Sets 3.3 Examples of Regular and Nonregular Sets 3.4 Reduction and Homomorphism of an Automaton 3.5 A Reduction ProcedureChapter 4. Regular Expressions 4.1 Definitions and the Basic Theorem 4.2 Properties of the Operations 4.3 Algebraic Manipulations with Regular Expressions 4.4 Transition Graphs 4.5 Sets of Words Corresponding to Transition Graphs 4.6 Proof of Kleene's Theorem 4.7 A Procedure for Checking Equality of Regular Expressions 4.8 Computation of Ax 4.9 Axiomatic Approach to Regular Expressions 4.10 The Nonsufficiency of a Finite System of Axioms 4.11 A Complete Finite Axiom System 4.12 Closure Properties of Regular Sets. A Canonical Form of a Regular ExpressionChapter 5. Coverings of Automata 5.1 Moore and Mealy Machines 5.2 Coverings of Automata 5.3 Homomorphisms of Automata 5.4 Homomorphism and Covering 5.5 Admissible Output-Consistent Decompositions 5.6 Reduction of Covering of an Automaton to Covering of a Semiautomaton 5.7 Properties of Coverings of Semiautomata 5.8 Construction of an Auxiliary Semiautomaton 5.9 Direct Product of Semiautomata 5.10 Cascade Product of Semiautomata 5.11 Covering with Cascade Product (The Partition Case) 5.12 Covering with Cascade Product (The Decomposition Case)Chapter 6. Covering by Permutation and Reset Semiautomata 6.1 Permutation-Reset Semiautomata 6.2 Permutation and Reset Semiautomata 6.3 Covering of Reset Semiautomata 6.4 Grouplike Semiautomata 6.5 Covering of Grouplike Semiautomata 6.6 Covering by Simple Grouplike and Two-State Reset SemiautomataChapter 7. The Theory of Krohn and Rhodes 7.1 The Main Theorem 7.2 Construction of Special Admissible Decompositions 7.3 Properties of the Constructed Decomposition 7.4 The Corresponding Semiautomaton 7.5 Covering of the Constructed Semiautomaton 7.6 The Properties of the Constructed Covering 7.7 The Proof of the Main Theorem 7.8 Example 7.9 The Necessity of Certain Components in a Cascade Product Covering of a Semiautomaton 7.10 The Simple Group Case 7.11 The Reset Case 7.12 Group-Free Regular Sets 7.13 Concluding RemarksBibliographyIndex