Projects per year
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 language | English |
---|---|
Journal | Leibniz International Proceedings in Informatics |
Volume | 80 |
Issue number | 44 |
Pages (from-to) | 1 |
Number of pages | 14 |
ISSN | 1868-8969 |
DOIs | |
Publication status | Published - 2017 |
Event | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) - Warsaw, Poland Duration: 10 Jul 2017 → 14 Jul 2017 http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=59138 |
Conference
Conference | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
---|---|
Country/Territory | Poland |
City | Warsaw |
Period | 10/07/2017 → 14/07/2017 |
Internet address |
Keywords
- Behavioral distances
- Probabilistic Models
- Automata Minimization
Fingerprint
Dive into the research topics of 'On the Metric-Based Approximate Minimization of Markov Chains'. Together they form a unique fingerprint.Projects
- 5 Finished
-
Approximate Reasoning for Stochastic Markovian Systems
Mardare, R. & Larsen, K. G.
01/11/2015 → 31/10/2019
Project: Research
-
DiCyPS: Center for Data-Intensive Cyber-Physical Systems
Larsen, K. G., Skou, A., Pedersen, T. B., Jensen, C. S., Kjeldskov, J., Skov, M. B., Nielsen, B., Lahrmann, H., Bak-Jensen, B., Guerrero, J. M. & Raptis, D.
01/01/2015 → 31/12/2020
Project: Research
-
CASSTING: Collective Adaptive System SynThesIs using Non-zero-sum Games
Larsen, K. G., Skou, A., David, A. & Srba, J.
01/04/2013 → 31/03/2016
Project: Research