Model checking discounted temporal properties

L. De Alfaro, M. Faella, T.A. Henzinger, R. Majumdar, M. Stoelinga, Theoretical Computer Science 345 (2005) 139–170.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ;
Abstract
Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We present a generalization of the branching-time logic CTL which achieves robustness with respect to model perturbations by giving a quantitative interpretation to predicates and logical operators, and by discounting the importance of events according to how late they occur. In every state, the value of a formula is a real number in the interval [0,1], where 1 corresponds to truth and 0 to falsehood. The boolean operators and and or are replaced by min and max, the path quantifiers ∃ and ∀ determine sup and inf over all paths from a given state, and the temporal operators ⋄ and □ specify sup and inf over a given path; a new operator averages all values along a path. Furthermore, all path operators are discounted by a parameter that can be chosen to give more weight to states that are closer to the beginning of the path. We interpret the resulting logic DCTL over transition systems, Markov chains, and Markov decision processes. We present two semantics for DCTL: a path semantics, inspired by the standard interpretation of state and path formulas in CTL, and a fixpoint semantics, inspired by the μ-calculus evaluation of CTL formulas. We show that, while these semantics coincide for CTL, they differ for DCTL, and we provide model-checking algorithms for both semantics.
Publishing Year
Date Published
2005-11-21
Journal Title
Theoretical Computer Science
Volume
345
Issue
1
Page
139 - 170
IST-REx-ID

Cite this

De Alfaro L, Faella M, Henzinger TA, Majumdar R, Stoelinga M. Model checking discounted temporal properties. Theoretical Computer Science. 2005;345(1):139-170. doi:10.1016/j.tcs.2005.07.033
De Alfaro, L., Faella, M., Henzinger, T. A., Majumdar, R., & Stoelinga, M. (2005). Model checking discounted temporal properties. Theoretical Computer Science, 345(1), 139–170. https://doi.org/10.1016/j.tcs.2005.07.033
De Alfaro, Luca, Marco Faella, Thomas A Henzinger, Ritankar Majumdar, and Mariëlle Stoelinga. “Model Checking Discounted Temporal Properties.” Theoretical Computer Science 345, no. 1 (2005): 139–70. https://doi.org/10.1016/j.tcs.2005.07.033.
L. De Alfaro, M. Faella, T. A. Henzinger, R. Majumdar, and M. Stoelinga, “Model checking discounted temporal properties,” Theoretical Computer Science, vol. 345, no. 1, pp. 139–170, 2005.
De Alfaro L, Faella M, Henzinger TA, Majumdar R, Stoelinga M. 2005. Model checking discounted temporal properties. Theoretical Computer Science. 345(1), 139–170.
De Alfaro, Luca, et al. “Model Checking Discounted Temporal Properties.” Theoretical Computer Science, vol. 345, no. 1, Elsevier, 2005, pp. 139–70, doi:10.1016/j.tcs.2005.07.033.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar