Finite Automata

Finite Automata

Behavior and Synthesis

1st Edition - January 1, 1981

Write a review

  • Author: A. de Vries
  • eBook ISBN: 9781483297293

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


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


    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


    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


    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


    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


    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



    Subject Index

Product details

  • No. of pages: 532
  • Language: English
  • Copyright: © Elsevier Science 1984
  • Published: January 1, 1981
  • Imprint: Elsevier Science
  • eBook ISBN: 9781483297293

About the Author

A. de Vries

Ratings and Reviews

Write a review

There are currently no reviews for "Finite Automata"