Model Checking for a Probabilistic Branching Time Logic with Fairness
From International Center for Computational Logic
Model Checking for a Probabilistic Branching Time Logic with Fairness
Christel BaierChristel Baier, Marta Z. KwiatkowskaMarta Z. Kwiatkowska
Christel Baier, Marta Z. Kwiatkowska
Model Checking for a Probabilistic Branching Time Logic with Fairness
Distributed Computing, 11(3):125--155, 1998
Model Checking for a Probabilistic Branching Time Logic with Fairness
Distributed Computing, 11(3):125--155, 1998
- KurzfassungAbstract
We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL* [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems. - Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science
@article{BK1998,
author = {Christel Baier and Marta Z. Kwiatkowska},
title = {Model Checking for a Probabilistic Branching Time Logic with
Fairness},
journal = {Distributed Computing},
volume = {11},
number = {3},
year = {1998},
pages = {125--155},
doi = {10.1007/s004460050046}
}