COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Algebraic Theory of Automata - 1st Edition - ISBN: 9781483200132, 9781483225166

Algebraic Theory of Automata

1st Edition

0.0 star rating Write a review
Author: Abraham Ginzburg
Editor: Robert L. Ashenhurst
eBook ISBN: 9781483225166
Imprint: Academic Press
Published Date: 1st January 1968
Page Count: 176
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

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


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




No. of pages:
© Academic Press 1968
1st January 1968
Academic Press
eBook ISBN:

About the Author

Abraham Ginzburg

About the Editor

Robert L. Ashenhurst

Ratings and Reviews