1. Bisimulation and Logical Preservation for Continuous-Time Markov Decision Processes
- Author
-
Martin R. Neuhäußer and Joost-Pieter Katoen
- Subjects
Bisimulation ,Theoretical computer science ,Markov chain ,Variable-order Markov model ,Markov process ,Partially observable Markov decision process ,Markov model ,symbols.namesake ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Computer Science::Logic in Computer Science ,symbols ,Continuous-time Markov decision process (CTMDP) ,Markov property ,Markov decision process ,Algorithm ,Computer Science::Formal Languages and Automata Theory ,Mathematics - Abstract
This paper introduces strong bisimulation for continuous-time Markov decision processes (CTMDPs), a stochastic model which allows for a nondeterministic choice between exponential distributions, and shows that bisimulation preserves the validity of CSL. To that end, we interpret the semantics of CSL - a stochastic variant of CTL for continuous-time Markov chains - on CTMDPs and show its measure theoretic soundness. The main challenge faced in this paper is the proof of logical preservation that is substantially based on measure theory.
- Published
- 2007