Projekter pr. år
Abstrakt
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.
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/Område | Polen |
By | Warsaw |
Periode | 10/07/2017 → 14/07/2017 |
Internetadresse |
Fingeraftryk
Dyk ned i forskningsemnerne om 'On the Metric-Based Approximate Minimization of Markov Chains'. Sammen danner de et unikt fingeraftryk.Projekter
- 5 Afsluttet
-
Approximate Reasoning for Stochastic Markovian Systems
Mardare, R. & Larsen, K. G.
01/11/2015 → 31/10/2019
Projekter: Projekt › Forskning
-
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
Projekter: Projekt › Forskning
-
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
Projekter: Projekt › Forskning