Partial model checking
Author:
- H.R. AndersenHAH.R. Andersen
- 1 January 1995
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 398-407
Abstract
A major obstacle in applying finite-state model checking to the verification of large systems is the combinatorial explosion of the state space arising when many loosely coupled parallel processes are considered. The problem also known as the *state- explosion problem* has been attacked from various sides. This paper presents a new approach based on *partial model checking*: Parts of the concurrent system are gradually removed while transforming the specification accordingly. When the intermediate specifications constructed in this manner can be kept small, the state-explosion problem is avoided. Experimental results with a prototype implemented in Standard ML, shows that for Milner's Scheduler - an often used benchmark - this approach improves on the published results on Binary Decision Diagrams and is comparable to results obtained using generalized Decision Diagrams. Specifications are expressed in a variant of the modal mu- calculus.Keywords
This publication has 13 references indexed in Scilit:
- Efficient checking of behavioural relations and modal assertions using fixed-point inversion1995
- Model checking and boolean graphsTheoretical Computer Science, 1994
- Symbolic model checking and constraint logic programming: A cross-fertilization1994
- A compositional proof system for the modal μ-calculus1994
- Compositional checking of satisfactionFormal Methods in System Design, 1992
- Model checking and abstraction1992
- A linear algorithm for solving fixed-point equations on transition systems1992
- A linear algorithm to solve fixed-point equations on transition systemsInformation Processing Letters, 1988
- Data Structures and Network Algorithms1983
- A lattice-theoretical fixpoint theorem and its applicationsPacific Journal of Mathematics, 1955