In: IEICE Trans. on Fundamentals in Electronics, Communications and Computer Science, Vol. E79-A, No. 11, pages 1817-1824. 1996.
Abstract: A siphon (or a structural deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that its any proper subset of is not a siphon. The results of the paper are: (i) the problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality siphon) is NP-complete, (ii) a polynomial-time algorithm to find a minimal siphon, if any, or even a maximal class of mutually disjoint minimal siphons of a general Petri net is proposed.
Keywords: NP-completeness, general Petri nets, minimal siphons, strong connectedness, structural deadlocks.