Relationships Among Distinct Models and Notions of Equivalence for Stochastic Finite-State Systems

In an effort to relate various existent schools of thought, this paper describes four models of probabilistic finite-state systems, giving necessary and sufficient conditions for reciprocal describability. An algorithm for the realization (synthesis) of a stochastic sequential machine by a deterministic machine and additive noise is presented. Different definitions of equivalence are listed and related by theorems, the most important of which states that "behavioral equivalence" with the same cutpoints for sequence recognizers is identical to "stochastic equivalence" (indistinguishability) for sequence transducers. Corollaries show the import of these results to the state minimization problem. The paper composes a strong case in favor of the adoption of J. W. Carlyle's model as a unifying one.