Algebraic Theory of Automata
- 1st Edition - September 20, 2014
- Imprint: Academic Press
- Author: Abraham Ginzburg
- Editor: Robert L. Ashenhurst
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 2 - 1 1 7 3 - 2
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 2 5 1 6 - 6
Algebraic Theory of Automata provides information pertinent to the methods and results of algebraic theory of automata. This book covers a variety of topics, including sets,… Read more
Purchase options
Algebraic Theory of Automata provides information pertinent to the methods and results of algebraic theory of automata. This book covers a variety of topics, including sets, semigroup, groupoids, isomorphism, semiautomata, proof of Kleene's theorem, and algebraic manipulations. Organized into seven chapters, this book begins with an overview of the fundamental properties of groups and semigroups. This text then examines the notion of semiautomaton, which serves as a basis for a rich and interesting theory. Other chapters consider algebraic notions and methods that are very useful in dealing with semiautomata. This book discusses as well some properties of the notion of covering of semiautomata. The final chapter deals with the theory of Krohn and Rhodes. This book is a valuable resource for graduate students.
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
- Edition: 1
- Published: September 20, 2014
- Imprint: Academic Press
- Language: English
Read Algebraic Theory of Automata on ScienceDirect