On the metric-based approximate minimization of Markov chains

Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, Radu Mardare

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

5 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
EditorsAnca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis
Number of pages14
Volume80
ISBN (Electronic)9783959770415
DOIs
Publication statusPublished - 1 Jul 2017
Event44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland
Duration: 10 Jul 201714 Jul 2017

Conference

Conference44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
CountryPoland
CityWarsaw
Period10/07/1714/07/17

Keywords

  • automata minimization
  • behavioral distances
  • probabilistic models

Fingerprint Dive into the research topics of 'On the metric-based approximate minimization of Markov chains'. Together they form a unique fingerprint.

  • Cite this

    Bacci, G., Bacci, G., Larsen, K. G., & Mardare, R. (2017). On the metric-based approximate minimization of Markov chains. In A. Muscholl, P. Indyk, F. Kuhn, & I. Chatzigiannakis (Eds.), 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (Vol. 80). [104] https://doi.org/10.4230/LIPIcs.ICALP.2017.104