Projekter pr. år
Abstrakt
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(n^2 (f(l) + k) + mn^7), 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(n^2 (f(l) + k) + mn^7), 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.
Originalsprog  Engelsk 

Titel  Quantitative Evaluation of Systems : 15th International Conference, QEST 2018, Beijing, China, September 47, 2018, Proceedings 
Redaktører  Anabelle McIver, Andras Horvath 
Antal sider  17 
Forlag  Springer 
Publikationsdato  4 sep. 2018 
Sider  339355 
ISBN (Trykt)  9783319991535 
ISBN (Elektronisk)  9783319991542 
DOI  
Status  Udgivet  4 sep. 2018 
Begivenhed  Quantitative Evaluation of Systems 2018  Beijing, Kina Varighed: 4 sep. 2018 → 7 sep. 2018 http://www.qest.org/qest2018/ 
Konference
Konference  Quantitative Evaluation of Systems 2018 

Land  Kina 
By  Beijing 
Periode  04/09/2018 → 07/09/2018 
Internetadresse 
Navn  Lecture Notes in Computer Science 

Vol/bind  11024 
ISSN  03029743 
Emneord
 semimarkov process
 markov decision process
 simulation
 hemimetric
Fingeraftryk Dyk ned i forskningsemnerne om 'A Hemimetric Extension of Simulation for SemiMarkov Decision Processes'. Sammen danner de et unikt fingeraftryk.
Projekter
 2 Afsluttet

Approximate Reasoning for Stochastic Markovian Systems
01/11/2015 → 31/10/2019
Projekter: Projekt › Forskning

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
Projekter: Projekt › Forskning