Equivalence of state representations for hidden Markov models (Q2427474)

An example of an open problem for hidden Markov models (HMM) is the realization problem: given the string probabilities of finite length strings, find all HMM that realize these string probabilities. The realization problem can be split up into three subproblems. The first is the realizability problem: derive conditions for string probabilities to be realizable by an HMM. The second subproblem is the realization problem itself: given realizable string probabilities, find a corresponding HMM. The third subproblem concerns the question of finding all possible realizations that are equivalent to a given realization. The paper considers the equivalence problem for HMM. Section 2 introduces Moore and Mealy HMM and their quasi-forms and also describes a procedure to find a minimal quasi-Mealy model equivalent to a given positive model. Section 3 describes the complete set of equivalent Mealy models. Section 4 shows, that under certain conditions, the class of equivalent quasi-Moore HMM consists of only one element up to a permutation of the states and subsequently gives a description of the set of equivalent positive Moore models. Section 5 summarizes the results concerning the equivalence sets, and Section 6 compares the results with the linear Gaussian case. Section 7 draws some conclusions.