[JansenNZ12] Belief Bisimulation for Hidden Markov Models - Logical Characterisation and Decision Algorithm Jansen, D. N.; Nielson, F. and Zhang, L. In NASA Formal Methods - 4th International Symposium (NFM), pages 326-340, Springer, Lecture Notes in Computer Science 7226, 2012.
Downloads: pdf, bibURL: Abstract. This paper establishes connections between logical equivalences and bisimulation relations for hidden Markov models (HMM). Both standard and belief state bisimulations are considered.
We also present decision algorithms for the bisimilarities. For standard bisimilarity, an extension of the usual partition refinement algorithm is enough. Belief bisimilarity, being a relation on the continuous space of belief states, cannot be described directly. Instead, we show how to generate a linear equation system in time cubic in the number of states.