Algebraic Theory of Automata

Algebraic Theory of Automata

1st Edition - January 1, 1968

Write a review

  • Author: Abraham Ginzburg
  • eBook ISBN: 9781483225166

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


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.

Table of Contents

  • Preface

    Chapter 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 Algebras

    Chapter 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 Semiautomata

    Chapter 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 Procedure

    Chapter 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 Expression

    Chapter 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 Semiautomata

    Chapter 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 Remarks



Product details

  • No. of pages: 176
  • Language: English
  • Copyright: © Academic Press 1968
  • Published: January 1, 1968
  • Imprint: Academic Press
  • eBook ISBN: 9781483225166

About the Author

Abraham Ginzburg

About the Editor

Robert L. Ashenhurst

Ratings and Reviews

Write a review

There are currently no reviews for "Algebraic Theory of Automata"