Qualitative logics and equivalences for probabilistic systems

L. De Alfaro, K. Chatterjee, M. Faella, A. Legay, in:, IEEE, 2007, pp. 237–248.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ;
Abstract
We present Qualitative Randomized CTL (QRCTL), a qualitative version of pCTL, for specifying properties of Markov Decision Processes (MDPs). QRCTL formulas can express the fact that certain temporal properties hold with probability 0 or 1, but they do not distinguish other probabilities values. We present a symbolic, polynomial time model-checking algorithm for QRCTL on MDPs. Then, we study the equivalence relation induced by QRCTL, called qualitative equivalence. We show that for finite alternating MDPs, where nondeterministic and probabilistic choice occur in different states, qualitative equivalence coincides with alternating bisimulation, and can thus be computed via efficient partition-refinement algorithms. Surprisingly, the result does not hold for non-alternating MDPs. Indeed, we show that no local partition refinement algorithm can compute qualitative equivalence on non-alternating MDPs. Finally, we consider QRCTL*, that is the “star extension” of QRCTL. We show that QRCTL and QRCTL* induce the same qualitative equivalence on alternating MDPs, while on non-alternating MDPs, the equivalence, arising from QRCTL* can be strictly finer We also provide a full characterization of the relation between qualitative equivalence, bisimulation, and alternating bisimulation, according to whether the MDPs are finite, and to whether their transition relations are finite-branching.
Publishing Year
Date Published
2007-10-08
Page
237 - 248
Conference
QEST: Quantitative Evaluation of Systems
IST-REx-ID

Cite this

De Alfaro L, Chatterjee K, Faella M, Legay A. Qualitative logics and equivalences for probabilistic systems. In: IEEE; 2007:237-248. doi:10.1109/QEST.2007.15
De Alfaro, L., Chatterjee, K., Faella, M., & Legay, A. (2007). Qualitative logics and equivalences for probabilistic systems (pp. 237–248). Presented at the QEST: Quantitative Evaluation of Systems, IEEE. https://doi.org/10.1109/QEST.2007.15
De Alfaro, Luca, Krishnendu Chatterjee, Marco Faella, and Axel Legay. “Qualitative Logics and Equivalences for Probabilistic Systems,” 237–48. IEEE, 2007. https://doi.org/10.1109/QEST.2007.15.
L. De Alfaro, K. Chatterjee, M. Faella, and A. Legay, “Qualitative logics and equivalences for probabilistic systems,” presented at the QEST: Quantitative Evaluation of Systems, 2007, pp. 237–248.
De Alfaro L, Chatterjee K, Faella M, Legay A. 2007. Qualitative logics and equivalences for probabilistic systems. QEST: Quantitative Evaluation of Systems 237–248.
De Alfaro, Luca, et al. Qualitative Logics and Equivalences for Probabilistic Systems. IEEE, 2007, pp. 237–48, doi:10.1109/QEST.2007.15.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar