Finite automata : behavior and synthesis

Author(s)

• Trakhtenbrot, B. A. (Boris Avraamovich)
• Barzdinʹ, I︠A︡. M. (I︠A︡n Martynovich)

Bibliographic Information

Finite automata : behavior and synthesis

B.A. Trakhtenbrot and Ya. M. Barzdinʹ ; translated from the Russian by D. Louvish ; English translation edited by E. Shamir and L.H. Landweber

（Fundamental studies in computer science, v. 1）

North-Holland Pub. Co , American Elsevier, 1973

• : North-Holland
• : American Elsevier

Other Title

Konechnye avtomaty

Note

Translation of Konechnye avtomaty

Bibliography: p. 310-315

Description and Table of Contents

Description

This dictionary supplies associations which have been evoked by certain words, signs, etc. in Western civilization in the past, and which may float to the surface again tomorrow; for however 'daringly new' a modern use of imagery may look, it generally appears to have roots in what has been said and done in the past. No fine distinctions have been made between symbols (in the limited sense), allegories, metaphors, signs, types, images, etc. (not to mention 'ascending' and 'descending' symbols), since such subtle distinctions, however sensible from a scientific point of view, are useless to a person struggling with the deeper comprehension (and thus appreciation) of a particular 'symbol'.

Table of Contents

?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

by "Nielsen BookData"

Details

• NCID: BA12368734
• ISBN:
  • 0720480213
  • 0444104186
• LCCN: 72088504
• Country Code: ne
• Title Language Code: eng
• Text Language Code: eng
• Original Language Code: rus
• Place of Publication: Amsterdam,New York
• Pages/Volumes: xi, 321 p.
• Size: 23 cm
• Classification:
  • LCC : QA267.5.S4
  • DC : 629.8/91
• Subject Headings:
  • LCSH : Sequential machine theory
• Parent Bibliography ID:
  • BA00634477