Probabilistic automata

Probabilistic automata (p.a.) are a generalization of finite deterministic automata. We follow the formulation of finite automata in Rabin and Scott (1959) where the automata %plane1D;504; have two-valued output and thus can be viewed as defining the set T(%plane1D;504;) of all tapes accepted by %plane1D;504;. This involves no loss of generality. A p.a. is an automaton which, when in state s and when input is σ, has a probability pi(s, σ)} of going into any state si. With any cut-point 0 ≤ λ < 1, there is associated the set T(%plane1D;504;,λ) of tapes accepted by %plane1D;504; with cut-point λ.Here we develop a general theory of p.a. and solve some of the basic problems. Aside from the mathematical interest in pursuing this natural generalization of finite automata, the results also bear on questions of reliability of sequential circuits.P.a. are, in general, stronger than deterministic automata (Theorem 2). By studying the way we may want to use p.a. we are led to introduce the concept of isolated cut-point. It turns out that every p.a. with isolated cut-point is equivalent to a suitable deterministic automaton (the Reduction Theorem 3). It is interesting to note that in passing from a minimal deterministic automaton to an equivalent p.a. we can sometimes save states (Section VII).The Reduction Theorem is applied to prove the existence of an approximate calculation procedure for a calculation problem involving products of stochastic matrices (Section VIII). The problem is of a new kind in that there is no a-priori bound on the number of operations (matrix multiplications) which we may have to perform and therefore classical numerical estimates of round-off errors do not apply.Actual automata (Definition 9) have the property, often existing in actual unreliable circuits, that all transition probabilities are strictly positive. Actual automata are proved to give only definite events. This points to the restrictions we may have to impose on a probabilistic sequential circuit if we want it to perform general tasks, namely, some transitions should be prohibited.Finally we treat the important problem of stability. Is the operation of a p.a. stable (unchanged) under small enough perturbations of the transition probabilities? We have an affirmative answer to this question in the case of actual automata (Theorem 11) and we discuss the problem for the general case