Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes

Share/Save/Bookmark

Baier, Christel and Hermanns, Holger and Katoen, Joost-Pieter and Haverkort, Boudewijn R. (2005) Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes. Theoretical Computer Science, 345 (1). pp. 2-26. ISSN 0304-3975

[img]
Preview
PDF
281Kb
Abstract:A continuous-time Markov decision process (CTMDP) is a generalization of a continuous-time Markov chain in which both probabilistic and nondeterministic choices co-exist. This paper presents an efficient algorithm to compute the maximum
(or minimum) probability to reach a set of goal states within a given time bound in a uniform CTMDP, i.e., a CTMDP in which the delay time distribution per state visit is the same for all states. It furthermore proves that these probabilities coincide for (time-abstract) history-dependent and Markovian schedulers that
resolve nondeterminism either deterministically or in a randomized way.
Item Type:Article
Copyright:© 2005 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/54792
Official URL:http://dx.doi.org/10.1016/j.tcs.2005.07.022
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 229281