Finding Minimal Siphons in General Petri Nets

Shinji TANIMOTO  Masahiro YAMAUCHI  Toshimasa WATANABE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A    No.11    pp.1817-1824
Publication Date: 1996/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Description Models for Concurrent Systems and Their Applications)
general Petri nets,  minimal siphons,  polynomial-time algorithms,  strongly connectedness,  NP-completeness,  

Full Text: PDF(616.4KB)>>
Buy this Article

A siphon (or alternatively a structutal 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 any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.