Belief Bisimulation for Hidden Markov Models Logical Characterisation and Decision Algorithm

David N. Jansen, Flemming Nielson, Lijun Zhang

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
    Title of host publicationNASA Formal Methods : 4th International Symposium, NFM 2012, Norfolk, VA, USA, April 3-5, 2012. Proceedings
    PublisherSpringer
    Publication date2012
    Pages326-340
    ISBN (Print)978-3-642-28890-6
    ISBN (Electronic)978-3-642-28891-3
    DOIs
    Publication statusPublished - 2012
    Event4th NASA Formal Methods Symposium (NFM 2012) - Norfolk, Virginia, United States
    Duration: 3 Apr 20125 Apr 2012
    http://shemesh.larc.nasa.gov/nfm2012/

    Conference

    Conference4th NASA Formal Methods Symposium (NFM 2012)
    CountryUnited States
    CityNorfolk, Virginia
    Period03/04/201205/04/2012
    Internet address
    SeriesLecture Notes in Computer Science
    Volume7226
    ISSN0302-9743

    Cite this

    Jansen, D. N., 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 (pp. 326-340). Springer. Lecture Notes in Computer Science, Vol.. 7226 https://doi.org/10.1007/978-3-642-28891-3_31