License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.43
URN: urn:nbn:de:0030-drops-132845
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13284/
Go to the corresponding LIPIcs Volume Portal

Darwin, Oscar ; Kiefer, Stefan

Equivalence of Hidden Markov Models with Continuous Observations

pdf-format:
LIPIcs-FSTTCS-2020-43.pdf (0.4 MB)

Abstract

We consider Hidden Markov Models that emit sequences of observations that are drawn from continuous distributions. For example, such a model may emit a sequence of numbers, each of which is drawn from a uniform distribution, but the support of the uniform distribution depends on the state of the Hidden Markov Model. Such models generalise the more common version where each observation is drawn from a finite alphabet. We prove that one can determine in polynomial time whether two Hidden Markov Models with continuous observations are equivalent.

BibTeX - Entry

@InProceedings{darwin_et_al:LIPIcs:2020:13284,
  author =	{Oscar Darwin and Stefan Kiefer},
  title =	{{Equivalence of Hidden Markov Models with Continuous Observations}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13284},
  URN =		{urn:nbn:de:0030-drops-132845},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.43},
  annote =	{Keywords: Markov chains, equivalence, probabilistic systems, verification}
}

Keywords: Markov chains, equivalence, probabilistic systems, verification
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI