¹Hangzhou Vocational & Technical College, Hangzhou 310018, China
²School of Information & Electronic Engineering, Zhejiang Gongshang University, Hangzhou, 310018, China
³School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China

---

Abstract—Minimal siphons play an important role in the development of deadlock control policies for discrete event system modeled by Petri net. A new algorithm based on depth-first search of problem decomposition process is proposed to compute all minimal siphons in an ordinary Petri net. The algorithm can reduce the number of problems in the problem list. The proposed algorithm can solve the problem of high requirement for computer memory in computing all minimal siphons and decrease the memory consumption because the computer memory size is closely related to the number of problems in the problem list. Some examples are used to illustrate the superiority of the proposed algorithm.

Index Terms—Petri nets, Minimal siphons, Deadlock

[PDF]

Cite: Fan Ning, Xingxing Li, Shouguang Wang, Qiaoli Zhuang, "A Method Based on Depth-first Search to Compute All Minimal Siphons," Journal of Software vol. 9, no. 8, pp. 2148-2153, 2014.