DocumentCode
2198789
Title
Extracting siphons containing a specified set of places in a Petri net
Author
Yamauchi, Masahiro ; Tanimoto, Shinji ; Watanabe, Toshio
Author_Institution
Dept. of Circuits & Syst., Hiroshima Univ., Japan
Volume
1
fYear
1998
fDate
11-14 Oct 1998
Firstpage
142
Abstract
Given a Petri net PN=(P, T, E), 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 minimal siphons containing a specified set of places, the paper shows several NP-completeness results of and a branch-and-bound method of extracting such one minimal siphon, as well as a method of enumerating all such ones containing a given place.
Keywords
Petri nets; computational complexity; tree searching; NP-completeness results; Petri net; branch-and-bound method; input transitions; minimal siphons; output transitions; siphon extraction; Circuits and systems; Fires; Petri nets; Polynomials; System recovery; Systems engineering and theory;
fLanguage
English
Publisher
ieee
Conference_Titel
Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference on
ISSN
1062-922X
Print_ISBN
0-7803-4778-1
Type
conf
DOI
10.1109/ICSMC.1998.725399
Filename
725399
Link To Document