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 LTLmodel 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 NPhard and not known to be decidable. Nevertheless, we provide an approximation schema where each lower and upperapproximant is computable in polynomial time in the size of the MC.
The upperapproximants are Kantorovichlike pseudometrics, i.e. branchingtime distances, that converge pointwise to the lineartime metrics. This convergence is interesting in itself, since it reveals a nontrivial relation between branching and lineartime metricbased semantics that does not hold in the case of equivalencebased semantics.
The upperapproximants are Kantorovichlike pseudometrics, i.e. branchingtime distances, that converge pointwise to the lineartime metrics. This convergence is interesting in itself, since it reveals a nontrivial relation between branching and lineartime metricbased semantics that does not hold in the case of equivalencebased semantics.
Original language  English 

Title of host publication  Theoretical Aspects of Computing  ICTAC 2015 : 12th International Colloquium, Cali, Colombia, October 2931, 2015, Proceedings 
Editors  Martin Leucker, Camilo Rueda, Frank D. Valencia 
Number of pages  18 
Publisher  Springer 
Publication date  2015 
Pages  349367 
ISBN (Print)  9783319251493 
ISBN (Electronic)  9783319251509 
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  03029743 
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 Nonzerosum Games
Larsen, K. G., Skou, A., David, A. & Srba, J.
01/04/2013 → 31/03/2016
Project: Research

SENSATION: Self EnergySupporting 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 CyberPhysical Sytems
Larsen, K. G., Skou, A., Nielsen, B., Bulychev, P., Ravn, A. P. & Poulsen, D. B.
01/04/2011 → 30/04/2015
Project: Research