Symbolic Model Checking of Concurrent Probabilistic Systems using MTBDDs and Simplex

[KNPS99] M. Kwiatkowska, G. Norman, D. Parker and R. Segala. Symbolic Model Checking of Concurrent Probabilistic Systems using MTBDDs and Simplex. Technical report CSR-99-01, School of Computer Science, University of Birmingham. January 1999. ps.gz pdf bib

Downloads
PostScript 113 KBPDF 269 KBBibTeX
Notes
This paper is superceded by [dAKN+00].
Search for this paper
Google · Google Scholar

Abstract

Symbolic model checking for purely probabilistic processes using MTBDDs [12] was introduced in [4] and further developed in [20, 3]. In this paper we consider models for concurrent probabilistic systems similar to those of [28, 7, 5] and the concurrent Markov chains of [35, 13], which extend the purely probabilistic processes through the addition of nondeterministic choice. As a specification formalism we use probabilistic branching-time temporal logic PBTL of [5, 7], which allows to express properties such as "under any scheduling of nondeterministic choices, the probability of phi holding until psi is true is at least 0.78". In [5, 7] it is shown that the verification of "until" properties can be reduced to a linear programming problem and solved with the help of e.g. the simplex algorithm, but no symbolic model checking is considered. Based on the algorithms of [5, 7], we derive symbolic model checking procedure for PBTL over concurrent probabilistic systems using MTBDDs. We furthermore implement an experimental model checker using the Colorado University Decision Diagrams (CUDD) package [32]. Our key contribution is an implementation of the simplex algorithm in terms of MTBDDs.