Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm

David N. Jansen; Flemming Nielson; Lijun Zhang

doi:10.1007/978-3-642-28891-3_31

Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm

David N. Jansen
, Flemming Nielson
, Lijun Zhang

Radboud University Nijmegen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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.

Original language	English
Title of host publication	NASA Formal Methods : 4th International Symposium, NFM 2012, Norfolk, VA, USA, April 3-5, 2012. Proceedings
Publisher	Springer
Publication date	2012
Pages	326-340
ISBN (Print)	978-3-642-28890-6
ISBN (Electronic)	978-3-642-28891-3
DOIs	https://doi.org/10.1007/978-3-642-28891-3_31
Publication status	Published - 2012
Event	4th NASA Formal Methods Symposium (NFM 2012) - Norfolk, Virginia, United States Duration: 3 Apr 2012 → 5 Apr 2012 http://shemesh.larc.nasa.gov/nfm2012/

Conference

Conference	4th NASA Formal Methods Symposium (NFM 2012)
Country/Territory	United States
City	Norfolk, Virginia
Period	03/04/2012 → 05/04/2012
Internet address	http://shemesh.larc.nasa.gov/nfm2012/

Series	Lecture Notes in Computer Science
Volume	7226
ISSN	0302-9743

Access to Document

10.1007/978-3-642-28891-3_31

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{317dcd7022e2493791855e011c1cd441,

title = "Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm",

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.",

author = "Jansen, \{David N.\} and Flemming Nielson and Lijun Zhang",

year = "2012",

doi = "10.1007/978-3-642-28891-3\_31",

language = "English",

isbn = "978-3-642-28890-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "326--340",

booktitle = "NASA Formal Methods",

note = "4th NASA Formal Methods Symposium (NFM 2012) ; Conference date: 03-04-2012 Through 05-04-2012",

url = "http://shemesh.larc.nasa.gov/nfm2012/",

}

Jansen, DN, Nielson, F & Zhang, L 2012, Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm. in NASA Formal Methods: 4th International Symposium, NFM 2012, Norfolk, VA, USA, April 3-5, 2012. Proceedings. Springer, Lecture Notes in Computer Science, vol. 7226, pp. 326-340, 4th NASA Formal Methods Symposium (NFM 2012), Norfolk, Virginia, United States, 03/04/2012. https://doi.org/10.1007/978-3-642-28891-3_31

Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm. / Jansen, David N.; Nielson, Flemming; Zhang, Lijun.
NASA Formal Methods: 4th International Symposium, NFM 2012, Norfolk, VA, USA, April 3-5, 2012. Proceedings. Springer, 2012. p. 326-340 (Lecture Notes in Computer Science, Vol. 7226).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm

AU - Jansen, David N.

AU - Nielson, Flemming

AU - Zhang, Lijun

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-28891-3_31

DO - 10.1007/978-3-642-28891-3_31

M3 - Article in proceedings

SN - 978-3-642-28890-6

T3 - Lecture Notes in Computer Science

SP - 326

EP - 340

BT - NASA Formal Methods

PB - Springer

T2 - 4th NASA Formal Methods Symposium (NFM 2012)

Y2 - 3 April 2012 through 5 April 2012

ER -

Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this