Automata, Languages, and Machines
Published on 28. June 1974
450 pages
978-0-08-087374-9 (ISBN)
Description
Automata, Languages, and Machines
More details
Other editions
Additional editions
Samuel Eilenberg
Automata, Languages and Machines: v. A
Book
01/1974
Academic Press
€84.18
Article exhausted; check different version
Content
- Front Cover
- Automata, Languages, and Machines
- Copyright Page
- Contents
- Preface
- Chapter I. Preliminaries
- 1. Functions
- 2. Relations and Partial Functions
- 3. Monoids
- 4. Categories
- 5. Equivalences and Congruences
- 6. Miscellaneous Conventions
- References
- Chapter II. Automata and Recognizable Sets
- 1. Basic Definitions
- 2. Examples
- 3. Operations on Automata
- 4. Accessibility
- 5. Finiteness and Iteration
- 6. Local Sets
- References
- Chapter III. Deterministic Automata
- 1. Basic Definitions
- 2. The Subset Construction
- 3. The Division Calculus
- 4. State-Mappings
- 5. Minimal Automata
- 6. A Decision Problem
- 7. Examples
- 8. The Quotient Criterion
- 9. Right Congruences
- 10. The Syntactic Monoid
- 11. Examples of Syntactic Monoids
- 12. Generalization to Arbitrary Monoids
- 13. Automata of Type ( p , r)
- References
- Chapter IV. Structure of Recognizable Sets
- 1. Unitary Sets
- 2. Prefixes
- 3. Unitary Monoids
- 4. The Decomposition Algorithm
- 5. Bases of Unitary Monoids
- 6. Iterated Up-Decomposition
- 7. Maximal Prefixes
- 8. Recurrent States
- References
- Chapter V. The Integers
- 1. The Monoid N
- 2. Integers at Base k
- 3. k-Recognizable Sets
- 4. Iteration
- 5. Gap Theorems
- 6. Other Interpretations
- 7. Coding
- References
- Chapter VI. Multiplicity
- 1. Multiplicity in Automata
- 2. Semirings
- 3. K-Subsets
- 4. Relations and Functions
- 5. Monoids and Matrices
- 6. K-S-Automata
- 7. Recognizable K-Subsets
- 8. The Equality Theorem
- 9. The Case K = N
- 10. The Division Theorem
- 11. The Subtraction Theorem
- 12. Undecidable Propositions
- References
- Chapter VII. Rational Sets
- 1. + -Algebras
- 2. Rational K-Subsets
- 3. Rational Expressions and Identities
- 4. Locally Finite Monoids
- 5. Kleene's Theorem
- 6. Linear Equations
- 7. Examples
- 8. Unambiguous Rational Sets
- 9. The Semirings N and N
- 10. Generalized Automata
- References
- Chapter VIII. An Excursion into Analysis
- 1. Generating Functions
- 2. K-Recognizable Power Series
- 3. The Case When k Is a Ring
- 4. The Case K = Z
- 5. Positive Analytic Functions
- 6. R+-Recognizable Functions
- 7. Behavior of Coefficients
- 8. Bernouili Distributions
- 9. Prefixes and Bases
- References
- Chapter IX. Rational Relations
- 1. Definitions and Examples
- 2. First Factorization Theorem
- 3. Evaluation Theorem
- 4. Composition Theorem
- 5. Second Factorization Theorem
- 6. Length-Preserving Relations
- 7. A Cross-Section Theorem
- 8. Rational Partial Functions
- 9. Iteration
- References
- Chapter X. Machines
- 1. Basic Definitions
- 2. Automata as Machines
- 3. Transducers and Rational Relations
- 4. Accelerated Transducers
- 5. Positive Rational Relations and Transducers
- 6. Two-way Automata
- 7. Other Machines
- 8. Deterministic Machines
- 9. A Conversion Theorem
- References
- Chapter XI. Sequential Machines
- 1. Basic Definitions
- 2. Notation and Interpretation
- 3. Properties of Sequential Functions
- 4. Digital Computation
- 5. State-Dependent Sequential Machines
- 6. Recognition of gsp-Functions
- 7. Sequential Bimachines
- 8. Examples of Bimachines
- 9. Proof of Theorem 7.1
- Chapter XII. Operations on Sequential Machines
- 1. State-Mappings
- 2. Accessibility
- 3. Reduction
- 4. Minimal gs-Machines
- 5. Decision Problems
- 6. The Strong Minimization Problem
- 7. The Synthesis Probleml
- 8. Composition of Sequential Llachines
- 9. 2-Categories
- 10. Parallel Products
- References
- Chapter XIII. Infinite Words
- 1. The Sets SN
- 2. Ultimately Periodic Sequences
- 3. Expansion of Real Numbers
- 4. Infinite Digital Computation
- 5. The Peano Curve
- 6. The Hilbert Curve
- References
- Chapter XIV. Infinite Behavior of Finite Automata
- 1. Main Definitions and Results
- 2. An Auxiliary Proposition
- 3. Proof of Theorem
- 4. Examples and Exercises
- References
- Chapter XV. k-Recognizable Sequences
- 1. k-Recognizable Sequences
- 2. k-Generic Sequences
- 3. Examples and Exercises
- 4. k-Recognizable Sequences and Sequential Functions
- References
- Chapter XVI. Linear Sequential Machines
- 1. Algebraic Preliminaries
- 2. Linear Sequential Machines
- 3. The Free Case
- Comparison with Automata
- 4. Quality
- 5. Minimization
- 6. Parallel Composition
- 7. Series Composition
- 8. The Case When K Is a Field
- 9. Rationality and Recurrence
- 10. Sequential Functions and Rationality
- 11. Integral Closure and Entire Rings
- 12. The Main Rationality Theorems
- 13. Proof of Theorems 12.1 and 12.2
- References
- Index
