Dynamically Stubborn Sets and the Sleep Set Method

Reference:

Kimmo Varpaaniemi. Dynamically stubborn sets and the sleep set method. In Hans-Dieter Burkhard, Ludwik Czaja, and Peter H. Starke, editors, Concurrency, Specification and Programming: Proceedings of the CS&P'93 Workshop, Nieborów near Warsaw, Poland, 14–16 October 1993, pages 230–246. Zakład Graficzny UW, zam. 261/94, Warsaw, Poland, 1994.

Abstract:

Reachability analysis is a powerful formal method for analysis of concurrent and distributed finite state systems. It suffers from the state space explosion problem, however: the state space of a system can be far too large to be completely generated. This paper considers two promising methods, Valmari's stubborn set method and Godefroid's sleep set method, to avoid generating all of the state space when searching for undesirable reachable terminal states, also called deadlocks. What makes deadlocks especially interesting is the fact that the verification of a safety property can often be reduced to deadlock detection. The considered methods utilize the independence of transitions to cut down on the number of states inspected during the search. These methods have been combined by Godefroid, Pirottin, and Wolper to further reduce the number of inspected states.

Petri nets are a widely used model for concurrent and distributed systems. This paper shows that the stubborn set method and the sleep set method can be combined without any of the assumptions previously placed on the stubborn sets as far as the detection of reachable terminal states in place/transition nets, a class of Petri nets, is concerned. The obtained result is actually more general and gives a sufficient condition for a method to be compatible with the sleep set method in the detection of reachable terminal states in place/transition nets.

This paper emphasizes the value of dynamically stubborn sets as a useful generalization of stubborn sets and presents some results that improve the understanding of the stubborn set method.

Keywords:

reachability analysis, Petri nets, deadlocks, stubborn set method, sleep set method

Suggested BibTeX entry:

@inproceedings{VarpaaniemiKimmo-Vrp93c,
    author = {Kimmo Varpaaniemi},
    booktitle = {{C}oncurrency, Specification and Programming: Proceedings of the {C}{S}\&{P}'93 Workshop, {N}iebor{\'{o}}w near {W}arsaw, {P}oland, 14--16 {O}ctober 1993},
    editor = {Hans-Dieter Burkhard and Ludwik Czaja and Peter H. Starke},
    pages = {230--246},
    publisher = {Zak{\l}ad Graficzny UW, zam. 261/94, Warsaw, Poland},
    title = {{D}ynamically Stubborn Sets and the Sleep Set Method},
    year = {1994},
}