Title :
Insufficiently marked siphon of Petri nets - extension of token-free siphon
Author :
Ohta, Atsushi ; Tsuji, Kohkichi
Author_Institution :
Fac. of Inf. Sci. & Technol., Aichi Prefectural Univ., Japan
Abstract :
Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. A live Petri net exhibits no local deadlocks. Siphon is a subset of places useful for liveness analysis. Token-free siphon implies non-liveness of Petri net. In this report, we suggest an insufficiently marked siphon as an extended token-free siphon. More general necessary condition for liveness is obtained using this new status of siphons. Two methods are proposed to obtain an insufficiently marked siphon.
Keywords :
Petri nets; computational complexity; integer programming; NP-hard problem; concurrent systems; extended token-free siphon; graph oriented method; insufficiently marked siphon; live Petri net; liveness analysis; mathematical model; mathematical programming method; mixed integer programming problem; Bars; Computational complexity; Information science; Mathematical model; Mathematical programming; Petri nets; System recovery;
Conference_Titel :
Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on
Print_ISBN :
0-7803-7761-3
DOI :
10.1109/ISCAS.2003.1205001
