Decomposition Theorems for Probabilistic Automata over Infinite Objects
Robert D. Reisz · 1999
Abstract. A probabilistic Büchi automaton PBA is defined. The probabilistic language (L; p) as defined by the PBA is defined. A decomposition theorem similar to the classical Krohn-Rhodes theorem, but for PBA is proved. Key words: probabilistic automata, Büchi automata, mathematical modelling, infinite processes. The theory of classical (non stochastic) finite automata over infinite objects was fun-damented as early as the 60s by such mathematicians as J.R. Büchi, R. McNaughton and M.O. Rabin (Büchi, 1960a, 1960b; McNaughton, 1966; Rabin, 1969). Their results gave birth to a theory that is now fundamental to those domains of theoretical computer science that deal with infinite processes or computations, and constitutes an adequate starting point for models in diverse domains of human knowledge. The theory of stochastic automata, also named random automata relies, on the other hand, on another extension of Mealy’s definition. The length of the input object is finite, but the evolution of the automaton is not simply non-deterministic, having a probabilis-tic character. The first definition of such an automaton is as old as 1963 and was put by J.W. Carlyle (1965). The denomination he used was that of stochastic sequential ma-chine. During the same year, an article by M.O. Rabin gives a more complete form of the same object. The romanian mathematicians O. Onicescu and S. Guiaşu define in 1965 the random abstract finite automaton (Farcaş, 1987). Important results are presented in Paz (1970). A probabilistic Büchi automata, short PBA was defined by Reisz (1997) and studied in previous articles (Reisz, 1998; Reisz, 1999). In the present article we will continue to investigate the properties of these automata, and in particular the possibility to separate their probabilistic and classical behaviour. A form of the classical Krohn-Rhosed theorem for PBA will be given. 1. Notations and Definitions During this article, A is a finite set, named alphabet. The elements x; y; : : : 2 A, are named letters. We define as follows: 428 R.D. Reisz the empty word is and A0 = fg, A1 = A; A2 = AA = fxyjx; y 2 Ag;