2026-07-19T22:40:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7367 2024-03-06T10:40:29Z ddc:004 open_access

On the Metric-Based Approximate Minimization of Markov Chains Bacci, Giovanni Bacci, Giorgio Larsen, Kim G. Mardare, Radu Behavioral distances Probabilistic Models Automata Minimization We address the behavioral metric-based approximate minimization problem of Markov Chains (MCs), i.e., given a finite MC and a positive integer k, we are interested in finding a k-state MC of minimal distance to the original. By considering as metric the bisimilarity distance of Desharnais at al., we show that optimal approximations always exist; show that the problem can be solved as a bilinear program; and prove that its threshold problem is in PSPACE and NP-hard. Finally, we present an approach inspired by expectation maximization techniques that provides suboptimal solutions. Experiments suggest that our method gives a practical approach that outperforms the bilinear program implementation run on state-of-the-art bilinear solvers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giovanni Bacci and Giorgio Bacci and Kim G. Larsen and Radu Mardare 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.104 urn:nbn:de:0030-drops-73675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.104 eng https://creativecommons.org/licenses/by/3.0/legalcode