
Automata, Languages, and Machines
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions
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
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.