The decomposition of stochastic automata

Abstract

Finite-state stochastic sequential systems which are interconnections of two or more component systems exhibit a special structural property in their transition matrices as a consequence of the statistical independence of the next states of the component systems given the present states and the input to the interconnection. Along with the concept of a "lumpable" stochastic matrix, this structural property is of central importance to the decomposition theory presented. These ideas allow a generalization to the stochastic case of the definitions used by Hartmanis in his study of the decomposition of conventional switching circuits. With these definitions we are able to prove decomposition theorems for stochastic automata which reduce to those of Hartmanis in the deterministic case. © 1964 Academic Press Inc.