Introduction to Probabilistic Automata - 1st Edition - ISBN: 9780125476508, 9781483268576

Introduction to Probabilistic Automata

1st Edition

Authors: Azaria Paz
Editors: Werner Rheinboldt
eBook ISBN: 9781483268576
Imprint: Academic Press
Published Date: 1st January 1971
Page Count: 254
Sales tax will be calculated at check-out Price includes VAT/GST
15% off
15% off
15% off
Price includes VAT/GST
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


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.

Table of Contents






A. Notations

B. Some Analytical Lemmas

C. Some Algebraic Preliminaries

D. Probabilistic Preliminaries

Chapter I. Stochastic Sequential Machines


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 Notes

Chapter II. Markov Chains


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 Notes

Chapter III. Events, Languages, And Acceptors


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 Results

Chapter IV. Applications and Generalizations


A. Information Theory

B. Reliability

C. Learning Theory and Pattern Recongnition

D. Control

E. Other Applications

F. Extensions and Connections to Other Theories


Answers and Hints to Selected Exercises

Author Index

Subject Index


No. of pages:
© Academic Press 1971
Academic Press
eBook ISBN:

About the Author

Azaria Paz

About the Editor

Werner Rheinboldt

Ratings and Reviews