Bisimulations and Logical Characterizations on Continuous-Time Markov Decision Processes
In Verification, Model Checking, and Abstract Interpretation
- 15th International Conference (VMCAI)
, pages 98-117, Springer
, Lecture Notes in Computer Science 8318, 2014.Downloads: pdf, bibURL: http://dx.doi.org/10.1007/978-3-642-54013-4_6
Abstract. In this paper we study strong and weak bisimulation equivalences for continuous-time Markov decision processes (CTMDPs) and the logical characterizations of these relations with respect to the continuous-time stochastic logic (CSL). For strong bisimulation, it is well known that it is strictly finer than the CSL equivalence. In this paper we propose strong and weak bisimulations for CTMDPs and show that for a subclass of CTMDPs, strong and weak bisimulations are both sound and complete with respect to the equivalences induced by CSL and the sub-logic of CSL without next operator respectively. We then consider a standard extension of CSL, and show that it and its sub-logic without X can be fully characterized by strong and weak bisimulations respectively over arbitrary CTMDPs.