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

K Jensen (Editor), Christel Baier, Boudewijn R.H.M. Haverkort, A. Podelski (Editor), H. Hermanns, Joost P. Katoen

    Research output: Contribution to conferencePaper

    6 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. This work is supported by the NWO-DFG bilateral project Validation of Stochastic Systems.
    Original languageUndefined
    Pages61-76
    Number of pages16
    DOIs
    Publication statusPublished - 2004
    Event10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2004 - Barcelona, Spain
    Duration: 29 Mar 20042 Apr 2004
    Conference number: 10

    Conference

    Conference10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2004
    Abbreviated titleTACAS
    CountrySpain
    CityBarcelona
    Period29/03/042/04/04

    Keywords

    • FMT-PM: PROBABILISTIC METHODS
    • FMT-MC: MODEL CHECKING
    • IR-63329
    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS
    • EWI-6539

    Cite this

    Jensen, K. (Ed.), Baier, C., Haverkort, B. R. H. M., Podelski, A. (Ed.), Hermanns, H., & Katoen, J. P. (2004). Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes. 61-76. Paper presented at 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2004, Barcelona, Spain. https://doi.org/10.1007/b96393, https://doi.org/10.1007/978-3-540-24730-2_5