Finite Automata

?Preface
Chapter 0. Introduction
0.1. The Concept of an Automaton
0.2. Types of Automata
0.3. Automata and Graphs
0.4. Terminological Clarifications
0.5. Survey of the Contents of Chapters I to V
Notes
Chapter I. Behavior of Outputless Automata
I.1. Representation of Languages and ?-Languages in Automata
I.2. Interchangeability
I.3. Distinguishability of Words and ?-Words
I.4. Decidability of Properties of Finite Automata
I.5. Projections, Sources, Macrosources
I.6. Operations on Sources (Macrosources) and on the Languages (?-Languages) Represented by them
I.7. Determinization of Sources. Operations Preserving Representability of Languages in Finite Automata
I.8. Determinization of Macrosources. Operations Preserving Representability of ?-Languages in Finite Automata
I.9. Proof of the Concatenation Theorem (Theorem 1.11)
I.10. Proof of the Strong Iteration Theorem (Theorem 1.12)
I.11. Probabilistic Automata
I.12. Grammars and Automata
Supplementary Material, Problems, Examples
Notes
Chapter II. Behavior of Automata with Output
II.1. Anticipation
II.2. Memory (Weight)
II.3. Equivalent Automata
II.4. Comparison of the Weight of an Operator with the Weight of an Automaton Realizing it
II.5. Representation of Languages (?-Languages) and Realization of Operators. The Uniformization Problem
II.6. More About Decision Problems of Finite Automata
II.7. Games, Strategies and Nonanticipatory Operators
II.8. Game-Theoretic Interpretation of the Uniformization Problem
II.9. Proof of the Fundamental Theorem on Finite-State Games-Intuitive Outline
II.10. Proof of the Fundamental Theorem on Finite-State Games
II.11. Spectra of Accessibility and Distinguishabihty
II.12. Spectra of Operators and of Automata Defining them
II.13. Parameters of a Finite Automaton and its Behavior
Supplementary Material, Problems
Notes
Chapter III. Metalanguages
III.1. Preliminary Examples and Problems
III.2. Discussion of the Examples. Statement of the Problem
III.3. The Metalanguages of Sources (Macrosources), Trees and Grammars
III.4. The Metalanguage of Regular Expressions
III.5. The Metalanguage of ?-Regular Expressions
III.6. The Logical Metalanguage I
III.7. Expressive Power of the Logical Metalanguage I
III.8. Normal Form
III.9. Synthesis of an Automaton Representing the ?-Language Defined by an I-Formula
III.10. Synthesis of an Automaton According to Conditions Imposed on an Operator or a Language
III.11. Cases without a Synthesis Algorithm
Supplementary Material, Problems
Notes
Chapter IV. Automaton Identification
IV.1. Introduction
IV.2. Identification of Relative Black Boxes
IV.3. Frequency Criteria. Complexity of Identification of Almost All Relative Black Boxes
IV.4. General Remarks on Identification of Absolute Black Boxes
IV.5. Iterative Algorithms
IV.6. Identification of Absolute Black Boxes by Multiple Algorithms, with Arbitrary Preassigned Frequency
IV.7. Bound on the Complexity of Uniform Identification
IV.8. Bound on the Complexity of (Nonuniform) Identification. Statement of the Fundamental Results
IV.9. Proof of Theorem 4.8
IV.10. Identification of Absolute Black Boxes by Simple Algorithms with Arbitrary Preassigned Frequency
IV.11. Bounds on the Complexity of (Nonuniform) Identification by Simple Algorithms
Supplementary Material, Problems
Notes
Chapter V. Statistical Estimates for Parameters and Spectra of Automata
V.1. Uniform Statistical Estimate of Degree of distinguishability
V.2. Uniform Statistical Estimate of the Saturation Spectrum
V.3. Stochastic Procedure Generating Automaton Graphs
V.4. Statistical Estimate of the Accessibility Spectrum for Automaton Graphs
V.5. Statistical Estimate of the Diameter. Statement of the Fundamental Result
V.6. Auxiliary Propositions from Probability Theory
V.7. Proof of the Fundamental Lemma
V.8. Statistical Estimate from Below for the Height of Automaton Graphs
V.9. Statistical Estimate for Accessibility Spectrum, Degree of Accessibility and Degree of Reconstructibility of Automata
Notes
References
Subject Index