Conference item
On computing the total variation distance of hidden Markov models
- Abstract:
- We prove results on the decidability and complexity of computing the total variation distance (equivalently, the L1-distance) of hidden Markov models (equivalently, labelled Markov chains). This distance measures the difference between the distributions on words that two hidden Markov models induce. The main results are: (1) it is undecidable whether the distance is greater than a given threshold; (2) approximation is #P-hard and in PSPACE.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, pdf, 416.2KB)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2018.130
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Host title:
- 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
- Series:
- Leibniz International Proceedings in Informatics
- Journal:
- 45th International Colloquium on Automata, Languages, and Programming (ICALP) Journal website
- Volume:
- 107
- Pages:
- 130:1--130:13
- Publication date:
- 2018-06-29
- Acceptance date:
- 2018-04-16
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959770767
Item Description
- Keywords:
- Pubs id:
-
pubs:842301
- UUID:
-
uuid:89098f10-5958-4807-9f07-5238c27fd263
- Local pid:
- pubs:842301
- Source identifiers:
-
842301
- Deposit date:
- 2018-04-19
Terms of use
- Copyright holder:
- Stefan Kiefer
- Copyright date:
- 2018
- Notes:
-
Copyright © Stefan Kiefer;
licensed under Creative Commons License CC-BY.
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record