State Minimization for Concurrent System Analysis Based on State Space Exploration

A fundamental issue in the automated analysis of concurrent systems is the efficient generation of the reachable state space. Since it is not possible to explore all the reachable states of a system if the number of states is very large or infinite, we need to develop techniques for minimizing the state space. This paper presents our approach to cluster subsets of states into equivalent classes. We assume that concurrent systems are specified as communicating state machines with arbitrary data space. We describe a procedure for constructing a minimal reachability state graph from communicating state machines. As an illustration of our approach, we analyze a producer-consumer program written in Ada. 1 Introduction One of the most prohibitive barriers in automatic analysis based on state space exploration of a concurrent system is state explosion [4, 13]. Two major sources of state explosion are process composition and data space size. The state space of a system grows exponentially wit..