doi: 10.4304/jsw.9.8.2148-2153
A Method Based on Depth-first Search to Compute All Minimal Siphons
- 1 Hangzhou Vocational & Technical College, Hangzhou 310018, China
- 2 School of Information & Electronic Engineering, Zhejiang Gongshang University, Hangzhou, 310018, China
- 3 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.
Keywords
- Petri nets
- Minimal siphons
- Deadlock
How to Cite
Fan Ning, Xingxing Li, Shouguang Wang, and 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. https://doi.org/ 10.4304/jsw.9.8.2148-2153
Copyright & License
Copyright © 2014 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).