Projects per year
Abstract
SemiMarkov decision processes (SMDPs) are continuoustime Markov decision processes where the residencetime on states is governed by generic distributions on the positive real line.
In this paper we consider the problem of comparing two SMDPs with respect to their timedependent behaviour. We propose a hemimetric between processes, which we call simulation distance, measuring the least acceleration factor by which a process needs to speed up its actions in order to behave at least as fast as another process. We show that this distance can be computed in time O(n2(f(l)+k)+mn7) , where n is the number of states, m the number of actions, k the number of atomic propositions, and f(l) the complexity of comparing the residencetime between states. The theoretical relevance and applicability of this distance is further argued by showing that (i) it is suitable for compositional reasoning with respect to CSPlike parallel composition and (ii) has a logical characterisation in terms of a simple Markovian logic.
In this paper we consider the problem of comparing two SMDPs with respect to their timedependent behaviour. We propose a hemimetric between processes, which we call simulation distance, measuring the least acceleration factor by which a process needs to speed up its actions in order to behave at least as fast as another process. We show that this distance can be computed in time O(n2(f(l)+k)+mn7) , where n is the number of states, m the number of actions, k the number of atomic propositions, and f(l) the complexity of comparing the residencetime between states. The theoretical relevance and applicability of this distance is further argued by showing that (i) it is suitable for compositional reasoning with respect to CSPlike parallel composition and (ii) has a logical characterisation in terms of a simple Markovian logic.
Original language  English 

Title of host publication  Quantitative Evaluation of Systems : 15th International Conference, QEST 2018, Beijing, China, September 47, 2018, Proceedings 
Editors  Anabelle McIver, Andras Horvath 
Number of pages  17 
Publisher  Springer 
Publication date  4 Sep 2018 
Pages  339355 
ISBN (Print)  9783319991535 
ISBN (Electronic)  9783319991542 
DOIs  
Publication status  Published  4 Sep 2018 
Event  Quantitative Evaluation of Systems 2018  Beijing, China Duration: 4 Sep 2018 → 7 Sep 2018 http://www.qest.org/qest2018/ 
Conference
Conference  Quantitative Evaluation of Systems 2018 

Country  China 
City  Beijing 
Period  04/09/2018 → 07/09/2018 
Internet address 
Series  Lecture Notes in Computer Science 

Volume  11024 
ISSN  03029743 
Fingerprint Dive into the research topics of 'A Hemimetric Extension of Simulation for SemiMarkov Decision Processes'. Together they form a unique fingerprint.
Projects
 2 Finished


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