In: IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E82-A, No. 11, pages 2558-2565. 1999.
Abstract: Given a Petri net, a siphon is a set S of places such that the set of input transitions to S is included in the set of output transitions from S. Concerning extraction of one or more minimal siphons containing a given specified set Q of places, the paper shows several results on polynomial time solvability and NP-completeness, mainly for the case card(Q) greater than or equal to 1.
Keywords: NP-completeness, Petri nets, minimal siphons, polynomial time algorithms, strong connectedness.