Resumé
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Leibniz International Proceedings in Informatics |
| Vol/bind | 80 |
| Udgave nummer | 44 |
| Sider (fra-til) | 1 |
| Antal sider | 14 |
| ISSN | 1868-8969 |
| DOI | |
| Status | Udgivet - 2017 |
| Begivenhed | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) - Warsaw, Polen Varighed: 10 jul. 2017 → 14 jul. 2017 http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=59138 |
Konference
| Konference | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|---|---|
| Land | Polen |
| By | Warsaw |
| Periode | 10/07/2017 → 14/07/2017 |
| Internetadresse |
Fingerprint
Citer dette
}
On the Metric-Based Approximate Minimization of Markov Chains. / Bacci, Giovanni; Bacci, Giorgio; Larsen, Kim Guldstrand; Mardare, Radu.
I: Leibniz International Proceedings in Informatics, Bind 80, Nr. 44, 2017, s. 1.Publikation: Bidrag til tidsskrift › Konferenceartikel i tidsskrift › Forskning › peer review
TY - GEN
T1 - On the Metric-Based Approximate Minimization of Markov Chains
AU - Bacci, Giovanni
AU - Bacci, Giorgio
AU - Larsen, Kim Guldstrand
AU - Mardare, Radu
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Behavioral distances
KW - Probabilistic Models
KW - Automata Minimization
U2 - 10.4230/LIPIcs.ICALP.2017.104
DO - 10.4230/LIPIcs.ICALP.2017.104
M3 - Conference article in Journal
VL - 80
SP - 1
JO - Leibniz International Proceedings in Informatics
JF - Leibniz International Proceedings in Informatics
SN - 1868-8969
IS - 44
ER -