On Choosing a Scapegoat in the Stubborn Set Method

Reference:

Kimmo Varpaaniemi. On choosing a scapegoat in the stubborn set method. In Hans-Dieter Burkhard, Peter H. Starke, and Ludwik Czaja, editors, Workshop: Concurrency, Specification & Programming, November 19–21, 1992, pages 163–171. Informatik-Preprint 22, Fachbereich Informatik der Humboldt-Universität zu Berlin, Germany, 1993.

Abstract:

The incremental algorithm for computing stubborn sets for Petri nets produces a stubborn set that may contain unnecessarily many enabled transitions since the algorithm contains nondeterministic choices. These choices involve choosing the starting transition and the choice of a disabling place (the scapegoat). The need for the first choice can be eliminated without affecting the complexity of the algorithm by visiting all the enabled transitions, but the latter choice remains. This paper compares different ways of choosing the scapegoat.

Keywords:

Petri nets, reachability analysis, stubborn set method

Suggested BibTeX entry:

@inproceedings{VarpaaniemiKimmo-Vrp92,
    author = {Kimmo Varpaaniemi},
    booktitle = {{W}orkshop: {C}oncurrency, Specification \& Programming, {N}ovember 19--21, 1992},
    editor = {Hans-Dieter Burkhard and Peter H. Starke and Ludwik Czaja},
    pages = {163--171},
    publisher = {Informatik-Preprint 22, Fachbereich Informatik der Humboldt-Universit{\"{a}}t zu Berlin, Germany},
    title = {{O}n Choosing a Scapegoat in the Stubborn Set Method},
    year = {1993},
}