Format:
Online Ressource (451 pages)
Edition:
Online-Ausg.
ISBN:
0122340019
,
9780122340017
Series Statement:
Pure and applied mathematics v. 59, pt. 1
Content:
Automata, languages, and machines
Content:
Automata, languages, and machines
Note:
Includes bibliographical references. - Print version record
,
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 Problem7. 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 Interpretations7. 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 N10. 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 Functions9. 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
Additional Edition:
ISBN 0122340019
Additional Edition:
Erscheint auch als Druck-Ausgabe Automata, languages and machines. Volume A New York : Academic Press, 1974
Language:
English
Keywords:
Electronic books
;
Electronic books
Author information:
Eilenberg, Samuel 1913-1998
Bookmarklink