TCS / Research / Publications / On Choosing a Scapegoat in the Stubborn Set Method
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

On Choosing a Scapegoat in the Stubborn Set Method


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.


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.


Petri nets, reachability analysis, stubborn set method

Suggested BibTeX entry:

    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},

This work is not available online here.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.