Conference paper
Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm
Radboud University Nijmegen1
Department of Informatics and Mathematical Modeling, Technical University of Denmark2
Computer Science and Engineering, Department of Informatics and Mathematical Modeling, Technical University of Denmark3
Language-Based Technology, Department of Informatics and Mathematical Modeling, Technical University of Denmark4
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.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2012 |
Pages: | 326-340 |
Proceedings: | 4th NASA Formal Methods Symposium (NFM 2012)NASA Formal Methods Symposium |
Series: | Lecture Notes in Computer Science |
Journal subtitle: | 4th International Symposium, Nfm 2012, Norfolk, Va, Usa, April 3-5, 2012. Proceedings |
ISBN: | 3642288901 , 364228891X , 364228891x , 9783642288906 and 9783642288913 |
ISSN: | 03029743 |
Types: | Conference paper |
DOI: | 10.1007/978-3-642-28891-3_31 |
ORCIDs: | Nielson, Flemming |