Three-valued abstraction for probabilistic systems

Joost Pieter Katoen*, Daniel Klink, Martin Leucker, Verena Wolf

*Corresponding author for this work
26 Citations (Scopus)

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.

Original languageEnglish
JournalJournal of Logic and Algebraic Programming
Volume81
Issue number4
Pages (from-to)356-389
Number of pages34
ISSN1567-8326
DOIs
Publication statusPublished - 01.05.2012

Fingerprint

Dive into the research topics of 'Three-valued abstraction for probabilistic systems'. Together they form a unique fingerprint.

Cite this