Automata, Languages, and Machines
Academic Press
Published on 16. June 1976
386 pages
978-0-08-087375-6 (ISBN)
Description
Automata, Languages, and Machines
More details
Other editions
Additional editions
Samuel Eilenberg
Automata, Languages and Machines: v. B
Book
01/1976
Academic Press
€66.85
Article exhausted; check different version
Persons
Content
- Front Cover
- Automata, Languages, and Machines
- Copyright Page
- Contents
- Preface
- Chapter I. Transformation Semigroups
- 1. Semigroups, Monoids, and Groups
- 2. Transformation Semigroups
- 3. Examples of Transformation Semigroups
- 4. Coverings
- 5. Coverings of Semigroups
- 6. Inclusions and Restrictions
- 7. Isomorphisms and Equivalences
- 8. Join, Sum, and Direct Product
- 9. Some Simple Inequalities
- 10. The Wreath Product
- References
- Chapter II. Decomposition Theorems
- 1. Decompositions
- 2. Decomposition of Groups
- 3. Some UsefuI Decompositions
- 4. The Krohn-Rhodes Decomposition
- 5. Comments on the Proof
- 6. Height, Pavings, and Holonomy
- 7. The Holonomy Decomposition Theorem
- 8. Proof of Proposition 7.3
- 9. Examples
- References
- Chapter III. Transformation Semigroups (continued)
- 1. Classes and Closed Classes
- 2. Sinks in a ts
- 3. Transitivity Classes
- 4. Idempotents in Semigroups
- 5. Idempotents in a ts
- 6. Localization
- 7. Closed Classes Containing 2
- 8. The Derived ts and the Trace of a Covering
- 9. The Delay Covering
- References
- Chapter IV. Primes
- 1. The Exclusion Operator
- 2. Primes
- 3. Proof of Theorem 2.1
- 4. The Low Primes
- 5. The Primes C and C?
- 6. The Primes F, 2, F?, and 2?
- 7. Switching Rules
- 8. Summary and Open Problems
- References
- Chapter V Semigroups and Varieties
- 1. Varieties of Semigroups and Monoids
- 2. Varieties Defined by Equations
- 3. Examples of Ultimately Equational Varieties
- 4. Semidirect Products
- 5. Varieties V.W
- 6. Varieties vs. Weakly Closed Classes
- 7. Closed Varieties
- 8. Examples of Closed Varieties
- 9. Triple Products
- 10. G-Varieties
- 11. Primes
- 12. A Tabulation
- References
- Chapter VI. Decomposition of Sequential Functions
- 1. Syntactic Invariants of Sequential Functions
- 2. Composition
- 3. Decomposition
- 4. Parallel Composition
- 5. Examples of Decompositions
- 6. The Function S
- 7. Varieties of Sequential Functions
- Chapter VII. Varieties of Sets
- 1. Syntactic Semigroups
- 2. Syntactic Semigroups and Recognizable Sets
- 3. Varieties of Sets
- 4. Proof of Theorems 3.2 and 3.2s
- 5. Operations on Varieties
- 6. The Syntactic tm and ts of a Set
- Chapter VIII. Examples of Varieties of Sets
- 1. General Comments
- 2. Finite and Cofinite Sets
- 3. Finitely Generated Varieties
- 4. The Variety D
- 5. The Variety D
- 6. Locally Testable Sets
- 7. A Theorem on Graphs
- 8. Proof of Theorem 6.5
- 9. The *-Variety j
- 10. p-Groups
- References
- Chapter IX. Aperiodicity
- 1. Recognizable Sets and Sequential Functions
- 2. The Concatenation Product
- 3. Schützenberger's Theorem
- 4. The Brzozowski Hierarchy
- 5. Bn,1 Are +-Varieties
- 6. The Variety B2
- 7. The Variety A1
- References
- Chapter X. Unitary-Prefix Decompositions
- 1. Unitary-Prefix Decompositions
- 2. A Decomposition
- 3. Two Examples
- 4. Iterated Decomposition
- 5. Periods of Monoids
- 6. Proof of Theorem 5.2
- References
- Chapter XI. Depth Decomposition Theorem
- 1. Basic Orderings in Semigroups
- 2. The Depth Decomposition Theorem
- 3. The Rees Matrix Semigroup
- 4. The Reduction Theorem
- 5. Proof of Proposition 2.2
- 6. Comparison with Holonomy Decomposition
- References
- Chapter XII. Complexity of Semigroups and Morphisms
- 1. Definition and Basic Properties
- 2. The Standard Complexity
- 3. Complexity of Morphisms
- 4. Morphism Classes Defined by S-Varieties
- 5. The Main Theorems of Complexity
- 6. Examples
- 7. Complexity of Projections
- 8. The Derived Semigroup of a Morphism
- 9. The Rhodes Expansion
- 10. Proof of the Ideal Theorem
- 11. Construction of the Rhodes Expansion
- 12. S Is Fine
- 13. Proof of Property (9.6)
- 14. Problems, Conjectures, and Further Results
- References
- Index
