Can Stubborn Sets Be Optimal?

Issue title: Applications and Theory of Petri Nets and Other Models of Concurrency, 2010

Article type: Research Article

Authors: Valmari, Antti | Hansen, Henri

Affiliations: Tampere University of Technology, Department of Software Systems, PO Box 553, FI-33101 Tampere, Finland. {antti.valmari,henri.hansen}@tut.fi

Note: [] Address for correspondence: Tampere University of Technology, Department of Software Systems, PO Box 553, FI-33101 Tampere, Finland

Abstract: Literature on the stubborn set and similar state space reduction methods presents numerous seemingly ad-hoc conditions for selecting the transitions that are investigated in the current state. There are good reasons to believe that the choice between them has a significant effect on reduction results, but not much has been published on this topic. This article presents theoretical results and examples that aim at shedding light on the issue. Because the topic is extensive, we only consider the detection of deadlocks. We distinguish between different places where choices can be made and investigate their effects. It is usually impractical to aim at choices that are “best” in some sense. However, one non-trivial practical optimality result is proven.

DOI: 10.3233/FI-2011-613

Journal: Fundamenta Informaticae, vol. 113, no. 3-4, pp. 377-397, 2011