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
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;
Conference_Titel :
Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference on
Print_ISBN :
0-7803-4778-1
DOI :
10.1109/ICSMC.1998.725399
