2026-08-17T22:54:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9134 2024-03-06T10:43:26Z ddc:004 open_access

On Computing the Total Variation Distance of Hidden Markov Models Kiefer, Stefan Labelled Markov Chains Hidden Markov Models Distance Decidability Complexity We prove results on the decidability and complexity of computing the total variation distance (equivalently, the L_1-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kiefer 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.130 urn:nbn:de:0030-drops-91344 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.130 eng https://creativecommons.org/licenses/by/3.0/legalcode