EQUIVALENT STOCHASTIC SEQUENTIAL MACHINES
Jack W. Carlyle · Defense Technical Information Center (DTIC) · 1961
This analysis is concerned with some structural properties of the probabilistic finite-state machines which were introduced as models for noisy communication channels. Procedures are given for the detection and elimination of superfluous states in machine descriptions. The point of view can be regarded as a probabilistic analog of deterministic finite-state machines. The equivalent states of a stochastic machine can be merged, as in the deterministic case, to yield a reduced form. Deterministic machines have unique reduced forms, but stochastic machines may possess a family of distinct reduced forms; a computational procedure for the determination of this family is discussed and some examples are given. (Author)