Projects per year
Abstract
SemiMarkov chains (SMCs) are continuoustime probabilistic transition systems where the residence time on states is governed by generic distributions on the positive real line. This paper shows the tight relation between the total variation distance on SMCs and their model checking problem over linear realtime specifications. Specifically, we prove that the total variation between two SMCs coincides with the maximal difference w.r.t. the likelihood of satisfying arbitrary MTL formulas or omegalanguages recognized by timed automata. Computing this distance (i.e., solving its threshold problem) is NPhard and its decidability is an open problem. Nevertheless, we propose an algorithm for approximating it with arbitrary precision.
Original language  English 

Title of host publication  Foundations of Software Science and Computation Structures : 18th International Conference, FOSSACS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 1118, 2015, Proceedings 
Editors  Andrew Pitts 
Number of pages  15 
Volume  9034 
Publisher  Springer 
Publication date  2015 
Pages  185199 
ISBN (Print)  9783662466773 
ISBN (Electronic)  9783662466780 
DOIs  
Publication status  Published  2015 
Event  18th International Conference on Foundations of Software Science and Computation Structures  Queen Mary University, London, United Kingdom Duration: 11 Apr 2015 → 18 Apr 2015 Conference number: 18 
Conference
Conference  18th International Conference on Foundations of Software Science and Computation Structures 

Number  18 
Location  Queen Mary University 
Country/Territory  United Kingdom 
City  London 
Period  11/04/2015 → 18/04/2015 
Series  Lecture Notes in Computer Science 

ISSN  03029743 
Fingerprint
Dive into the research topics of 'On the Total Variation Distance of SemiMarkov 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