?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
Ask a Question About this Product More... |