LIMITED OFFER

## Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Skip to main content# Algebraic Theory of Automata

## Purchase options

## Save 50% on book bundles

## Institutional subscription on ScienceDirect

Request a sales quote

Save up to 30% on Elsevier print and eBooks with free shipping. No promo code needed.

Save up to 30% on print and eBooks.

1st Edition - January 1, 1968

Author: Abraham Ginzburg

Editor: Robert L. Ashenhurst

Language: EnglisheBook 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

LIMITED OFFER

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

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

- No. of pages: 176
- Language: English
- Edition: 1
- Published: January 1, 1968
- Imprint: Academic Press
- eBook ISBN: 9781483225166

Read *Algebraic Theory of Automata* on ScienceDirect