On the Metric-Based Approximate Minimization of Markov Chains

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

8 Citationer (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.
OriginalsprogEngelsk
TidsskriftLeibniz International Proceedings in Informatics
Vol/bind80
Udgave nummer44
Sider (fra-til)1
Antal sider14
ISSN1868-8969
DOI
StatusUdgivet - 2017
Begivenhed44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) - Warsaw, Polen
Varighed: 10 jul. 201714 jul. 2017
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=59138

Konference

Konference44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Land/OmrådePolen
ByWarsaw
Periode10/07/201714/07/2017
Internetadresse

Fingeraftryk

Dyk ned i forskningsemnerne om 'On the Metric-Based Approximate Minimization of Markov Chains'. Sammen danner de et unikt fingeraftryk.

Citationsformater