Finding a Minimal Siphon Containing Specified Places in a General Petri Net

Masahiro YAMAUCHI  Shinji TANIMOTO  Toshimasa WATANABE  

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

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

A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal 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. The subject of the paper is to find a minimal siphon containing a given set of specified places of a general Petri net.