Partial-Order Methods for the Verification of Concurrent Systems - An Approach to the State-Explosion Problem
(1995)Abstract
State-space exploration techniques are increasingly being used for debugging and proving correct finite-state concurrent reactive systems. The reason for this success is mainly the simplicity of these techniques. Indeed, they are easy to understand, easy to implement and, last but not least, easy to use: they are fully automatic. Moreover, the range of properties that they can verify has been substantially broadened thanks to the development of model-checking methods for various temporal logics. The main limit of state-space exploration verification techniques is the often excessive size of the state space due, among other causes, to the modeling of concurrency by interleaving. However, exploring all interleavings of concurrent events is not a priori necessary for verification: interleavings corresponding to the same concurrent execution contain related information. One can thus hope to be able to verify properties of a concurrent system without exploring all interleavings of its concu...
Description
Partial-Order Methods for the Verification of Concurrent Systems - An Approach to the State-Explosion Problem