On the metric-based approximate minimization of Markov chains

Bacci, Giovanni and Bacci, Giorgio and Larsen, Kim G. and Mardare, Radu; Muscholl, Anca and Indyk, Piotr and Kuhn, Fabian and Chatzigiannakis, Ioannis, eds. (2017) On the metric-based approximate minimization of Markov chains. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, POL. ISBN 9783959770415

Text (Bacci-etal-ICALP2017-On-metric-based-approximate-minimization-Markov-chains)
Final Published Version
License: Creative Commons Attribution 4.0 logo

Download (620kB)| Preview


    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.