On probabilistic automata with structural restrictions

Results on two distinct aspects of the theory of probabilistic automata (PA) are presented. Part I is devoted to two generalizations of the theory of loop-free decomposition of stochastic finite-state systems formulated by G. Bacon. The first generalization consists of making a modification in the decomposition scheme of Bacon to allow for the decomposition of a larger class of systems. The second generalization subsumes the first; it is shown that there exist stochastic finite-state systems which admit a loop-free decomposition for a proper subset of the set of all initial distributions on their state set, while both Bacon´s theory and our first generalization hold for the set of all initial distributions. Sufficient conditions are given in both cases. In Part II linear probabilistic automata (LPA) are introduced. These are PA which can be realized by linear sequential circuits some of whose inputs are multinomial stochastic processes. It is shown that if a mod-2 LPA is driven by a single binomial process, then it will define regular languages only, and that this is not true for mod´3 LPA. The stability problem is discussed for mod-2 and mod-3 LPA driven by single binomial and trinomial processes respectively and different results are obtained in either case. Finally it is shown that if a mod-2 LPA has a critical cut-point, then this cutpoint is unique.