Introduction to Probabilistic Automata

1st Edition - January 1, 1971
Author: Azaria Paz
Editor: Werner Rheinboldt
Language: English
eBook ISBN:
9 7 8 - 1 - 4 8 3 2 - 6 8 5 7 - 6

Introduction to Probabilistic Automata deals with stochastic sequential machines, Markov chains, events, languages, acceptors, and applications. The book describes mathematical… Read more

Purchase options

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Institutional subscription on ScienceDirect

Request a sales quote

Introduction to Probabilistic Automata deals with stochastic sequential machines, Markov chains, events, languages, acceptors, and applications. The book describes mathematical models of stochastic sequential machines (SSMs), stochastic input-output relations, and their representation by SSMs. The text also investigates decision problems and minimization-of-states problems arising from concepts of equivalence and coverings for SSMs. The book presents the theory of nonhomogeneous Markov chains and systems in mathematical terms, particularly in relation to asymptotic behavior, composition (direct sum or product), and decomposition. "Word functions," induced by Markov chains and valued Markov systems, involve characterization, equivalence, and representability by an underlying Markov chain or system. The text also discusses the closure properties of probabilistic languages, events and their relation to regular events, particularly with reference to definite, quasidefinite, and exclusive events. Probabilistic automata theory has applications in information theory, control, learning theory, pattern recognition, and time sharing in computer programming. Programmers, computer engineers, computer instructors, and students of computer science will find the collection highly valuable.

PrefaceAcknowledgmentsAbbreviationsNotationPreliminariesA. NotationsB. Some Analytical LemmasC. Some Algebraic PreliminariesD. Probabilistic PreliminariesChapter I. Stochastic Sequential Machines Introduction A. The Model 1. Definitions and Basic Relations 2. Moore, Mealy, and Other Types of SSMs 3. Synthesis of Stochastic Machines 4. Bibliographical Notes B. State Theory and Equivalence 1. Set KM and Matrix HM 2. Equivalence and Minimization of States 3. Covering Relations 4. Decision Problems 5. Minimization of States by Covering-Problem I 6. Minimization of States by Covering-Problem II 7. Minimization of States by Covering-Problem III 8. Bibliographical Notes C. Input-Output Relations 1. Definitions and Basic Properties 2. Compound Sequence Matrix 3. Representability of Relations by Machines 4. Bibliographical NotesChapter II. Markov Chains Introduction A. Nonhomogeneous Markov Chains and Systems 1. Functionals over Stochastic Matrices 2. Nonhomogenous Markov Chains 3. Nonhomogeneous Markov Systems 4. Graph Properties and Decision Problems 5. Eigenvalues of Stochastic Matrices and Particular Cases 6. Bibliographical Notes B. Operation on Markov Systems 1. The Direct Sum and Product 2. Decomposition 3. Bibliographical Notes C. Word Functions 1. Functions of Markov Chains 2. Function Induced by Valued Markov Systems 3. Bibliographical NotesChapter III. Events, Languages, And Acceptors Introduction A. Events 1. Probabilistic Events 2. Pseudo Probabilistic Events 3. Bibliographical Notes B. Cut-Point Events 1. Closure Properties 2. Regular Events and Probabilistic Cut-Point Events 3. The Cardinality of PCEs and Saving of States 4. Particular Cases C. Quasidefinite PCEs 5. Approximations 6. Some Nonclosure and Unsolvability ResultsChapter IV. Applications and Generalizations Introduction A. Information Theory B. Reliability C. Learning Theory and Pattern Recongnition D. Control E. Other Applications F. Extensions and Connections to Other Theories ReferencesAnswers and Hints to Selected ExercisesAuthor IndexSubject Index