Back to Search
Start Over
Comparative branching-time semantics for Markov chains
- Source :
-
Information & Computation . Aug2005, Vol. 200 Issue 2, p149-214. 66p. - Publication Year :
- 2005
-
Abstract
- Abstract: This paper presents various semantics in the branching-time spectrum of discrete-time and continuous-time Markov chains (DTMCs and CTMCs). Strong and weak bisimulation equivalence and simulation pre-orders are covered and are logically characterized in terms of the temporal logics Probabilistic Computation Tree Logic (PCTL) and Continuous Stochastic Logic (CSL). Apart from presenting various existing branching-time relations in a uniform manner, this paper presents the following new results: (i) strong simulation for CTMCs, (ii) weak simulation for CTMCs and DTMCs, (iii) logical characterizations thereof (including weak bisimulation for DTMCs), (iv) a relation between weak bisimulation and weak simulation equivalence, and (v) various connections between equivalences and pre-orders in the continuous- and discrete-time setting. The results are summarized in a branching-time spectrum for DTMCs and CTMCs elucidating their semantics as well as their relationship. [Copyright &y& Elsevier]
- Subjects :
- *MARKOV processes
*SEMANTICS
*PSYCHOLOGY
*SCIENTIFIC method
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 200
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 18091001
- Full Text :
- https://doi.org/10.1016/j.ic.2005.03.001