UID:
almafu_9958090987102883
Format:
1 online resource (469 p.)
ISBN:
1-281-76345-4
,
9786611763459
,
0-08-087374-X
Series Statement:
Pure and applied mathematics; a series of monographs and text books, 58A [i.e. 59A]
Content:
Automata, languages, and machines
Note:
Description based upon print version of 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
,
English
Additional Edition:
ISBN 0-12-234001-9
Language:
English
