Projects per year
Abstract
We study the strong and strutter trace distances on Markov chains (MCs). Our interest in these metrics is motivated by their relation to the probabilistic LTL-model checking problem: we prove that they correspond to the maximal differences in the probability of satisfying the same LTL and LTL-헑 ( LTL without next operator) formulas, respectively. The threshold problem for these distances (whether their value exceeds a given threshold) is NP-hard and not known to be decidable. Nevertheless, we provide an approximation schema where each lower and upper-approximant is computable in polynomial time in the size of the MC.
The upper-approximants are Kantorovich-like pseudometrics, i.e. branching-time distances, that converge point-wise to the linear-time metrics. This convergence is interesting in itself, since it reveals a nontrivial relation between branching and linear-time metric-based semantics that does not hold in the case of equivalence-based semantics.
The upper-approximants are Kantorovich-like pseudometrics, i.e. branching-time distances, that converge point-wise to the linear-time metrics. This convergence is interesting in itself, since it reveals a nontrivial relation between branching and linear-time metric-based semantics that does not hold in the case of equivalence-based semantics.
Original language | English |
---|---|
Title of host publication | Theoretical Aspects of Computing - ICTAC 2015 : 12th International Colloquium, Cali, Colombia, October 29-31, 2015, Proceedings |
Editors | Martin Leucker, Camilo Rueda, Frank D. Valencia |
Number of pages | 18 |
Publisher | Springer |
Publication date | 2015 |
Pages | 349-367 |
ISBN (Print) | 978-3-319-25149-3 |
ISBN (Electronic) | 978-3-319-25150-9 |
DOIs | |
Publication status | Published - 2015 |
Event | 12th International Colloquium on Theoretical Aspects of Computing - Cali, Colombia Duration: 29 Oct 2015 → 1 Nov 2015 Conference number: 12 |
Conference
Conference | 12th International Colloquium on Theoretical Aspects of Computing |
---|---|
Number | 12 |
Country/Territory | Colombia |
City | Cali |
Period | 29/10/2015 → 01/11/2015 |
Series | Lecture Notes in Computer Science |
---|---|
Number | 9399 |
ISSN | 0302-9743 |
Fingerprint
Dive into the research topics of 'Converging from Branching to Linear Metrics on Markov Chains'. Together they form a unique fingerprint.Projects
- 3 Finished
-
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
-
SENSATION: Self Energy-Supporting Autonomous Computation
Larsen, K. G., Hansen, R. R., Koch, P., Nielsen, B. & Skou, A.
01/10/2012 → 30/09/2015
Project: Research
-
IDEA4CPS: Foundations for Cyber-Physical Sytems
Larsen, K. G., Skou, A., Nielsen, B., Bulychev, P., Ravn, A. P. & Poulsen, D. B.
01/04/2011 → 30/04/2015
Project: Research