For the most recent entries see the Petri Nets Newsletter.

The State Explosion Problem.

Valmari, Antti

In: Reisig, W.; Rozenberg, G.: Lecture Notes in Computer Science, Vol. 1491: Lectures on Petri Nets I: Basic Models, pages 429-528. Springer-Verlag, 1998.

Abstract: State space methods are one of the most important approaches to computer-aided analysis and verification of the behaviour of concurrent systems. In their basic form, they consist of enumerating and analysing the set of the states of system can ever reach. Unfortunately, the number of states of even a relatively small system is often far greater than can be handled in a realistic computer. The goal of this article is to analyse this state explosion problem from several perspectives. Many advanced state space methods alleviate the problem by using a subset or an abstraction of the set of states. Unfortunately, their use tends to restrict the set of analysis or verification questions that can be answered, making it impossible to discuss the methods without some taxonomy of the questions. Therefore, the article contains a lengthy discussion on alternative ways of stating analysis and verification questions, and algorithms for answering them. After that, many advanced state space methods are briefly described. The state explosion problem is investigated also from the computational complexity point of view.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography