On Choosing a Scapegoat in the Stubborn Set Method (1993)
AUTHORS:
Varpaaniemi Kimmo
BOOKTITLE:
Workshop: Concurrency, Specification & Programming, November 19--21, 1992
PAGES:
163--171
PDF:
pdf/kvacsp92.pdf
@inproceedings{ Vrp92, editor = "Burkhard, Hans-Dieter and Starke, Peter H. and Czaja, Ludwik", author = "Varpaaniemi, Kimmo", 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", booktitle = "{W}orkshop: {C}oncurrency, Specification \& Programming, {N}ovember 19--21, 1992", ps = "kvacsp92.ps", pages = "163--171", flags = "public", year = "1993", keywords = "Petri nets, reachability analysis, stubborn set method", pdf = "kvacsp92.pdf", 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." }