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