Three-valued abstraction for probabilistic systems

TitleThree-valued abstraction for probabilistic systems
Publication TypeJournal Article
Year of Publication2012
AuthorsJoost-Pieter Katoen, Klink, D, Leucker, M, Wolf, V
JournalJournal of Algebraic and Logic Programming (JLAP)
Volume81
Issue4
Start Page356
Pagination34
Abstract

This paper proposes a novel abstraction technique for fully probabilistic systems. The models of our study are classical discrete-time and continuous-time Markov chains (DTMCs and CTMCs, for short). A DTMC is a Kripke structure in which each transition is equipped with a discrete probability; in a CTMC, in addition, state residence times are governed by negative exponential distributions. Our abstraction technique fits within the realm of three-valued abstraction methods that have been used successfully for traditional model checking. The key ingredients of our technique are a partitioning of the state space combined with an abstraction of transition probabilities by intervals. It is shown that this provides a conservative abstraction for both negative and affirmative verification results for a three-valued semantics of PCTL (Probabilistic Computation Tree Logic). In the continuous-time setting, the key idea is to apply abstraction on uniform CTMCs which are readily obtained from general CTMCs. In a similar way as for the discrete case, this is shown to yield a conservative abstraction for a three-valued semantics of CSL (Continuous Stochastic Logic). Abstract CTMCs can be verified by computing time-bounded reachability probabilities in continuous-time MDPs.

URLhttp://dx.doi.org/10.1016/j.jlap.2012.03.007
DOI10.1016/j.jlap.2012.03.007
Bibtex: 
@article {749,
	title = {Three-valued abstraction for probabilistic systems},
	journal = {Journal of Algebraic and Logic Programming (JLAP)},
	volume = {81},
	year = {2012},
	pages = {34},
	chapter = {356},
	abstract = {This paper proposes a novel abstraction technique for fully probabilistic systems. The models of our study are classical discrete-time and continuous-time Markov chains (DTMCs and CTMCs, for short). A DTMC is a Kripke structure in which each transition is equipped with a discrete probability; in a CTMC, in addition, state residence times are governed by negative exponential distributions. Our abstraction technique fits within the realm of three-valued abstraction methods that have been used successfully for traditional model checking. The key ingredients of our technique are a partitioning of the state space combined with an abstraction of transition probabilities by intervals. It is shown that this provides a conservative abstraction for both negative and affirmative verification results for a three-valued semantics of PCTL (Probabilistic Computation Tree Logic). In the continuous-time setting, the key idea is to apply abstraction on uniform CTMCs which are readily obtained from general CTMCs. In a similar way as for the discrete case, this is shown to yield a conservative abstraction for a three-valued semantics of CSL (Continuous Stochastic Logic). Abstract CTMCs can be verified by computing time-bounded reachability probabilities in continuous-time MDPs.},
	doi = {http://dx.doi.org/10.1016/j.jlap.2012.03.007},
	url = {http://dx.doi.org/10.1016/j.jlap.2012.03.007},
	author = {Joost-Pieter Katoen and Daniel Klink and Martin Leucker and Verena Wolf}
}