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

Christel Baier, Boudewijn Haverkort, Holger Hermanns, Joost P. Katoen

    Research output: Book/ReportReportProfessional

    7 Citations (Scopus)
    15 Downloads (Pure)

    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. We prove that these probabilities coincide for (time-abstract) history-dependent and Markovian schedulers that resolve nondeterminism either deterministically or in a randomized way.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages30
    Publication statusPublished - Oct 2003

    Publication series

    NameCTIT technical report series
    PublisherCentre for Telematics and Information Technology, University of Twente
    No.03-50
    ISSN (Print)1381-3625

    Fingerprint Dive into the research topics of 'Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes'. Together they form a unique fingerprint.

    Cite this