Computer Science – Logic in Computer Science
Scientific paper
2012-04-09
Computer Science
Logic in Computer Science
Scientific paper
This paper studies the logical characterization problem for Continuous-time Markov Decision Processes (CTMDP) with respect to the Continuous-time Stochastic Logic (CSL). For strong bisimulation, it is well known that bisimulation is strictly finer than CSL equivalence. In this paper, we propose the notion of weak bisimulation for CTMDPs and show that for a subclass of CTMDPs, weak bisimulation is both sound and complete with respect to the equivalence induced by the sub-logic of CSL without next operator. We then propose a sequence of i-depth bisimulation relations characterizing a sequence of sub-logics with bounded until. The i-depth bisimulation equivalences converge to the CSL equivalence for arbitrary CTMDPs. We also extend the work to simulations as well as their characterizations. Another contribution of the paper is the novel definition of a parallel composition operator for CTMDPs, moreover, we show that both strong and weak bisimulations are congruence relations with respect to it.
Godskesen Jens Chr.
Song Lei
Zhang Lijun
No associations
LandOfFree
The Branching Time Spectrum for Continuous-time MDPs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Branching Time Spectrum for Continuous-time MDPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Branching Time Spectrum for Continuous-time MDPs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-648770