Volume 9 Number 8 (Aug. 2014)
Home > Archive > 2014 > Volume 9 Number 8 (Aug. 2014) >
JSW 2014 Vol.9(8): 2148-2153 ISSN: 1796-217X
doi: 10.4304/jsw.9.8.2148-2153

A Method Based on Depth-first Search to Compute All Minimal Siphons

Fan Ning1, Xingxing Li2, 3, Shouguang Wang2, 3, Qiaoli Zhuang2, 3
1Hangzhou Vocational & Technical College, Hangzhou 310018, China
2School of Information & Electronic Engineering, Zhejiang Gongshang University, Hangzhou, 310018, China
3School 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


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.

General Information

ISSN: 1796-217X (Online)
Frequency:  Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Apr 26, 2021 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Sep 13, 2021 News!

    The papers published in Vol 16, No 6 have all received dois from Crossref    [Click]

  • Jan 28, 2021 News!

    [CFP] 2021 the annual meeting of JSW Editorial Board, ICCSM 2021, will be held in Rome, Italy, July 21-23, 2021   [Click]

  • Sep 13, 2021 News!

    Vol 16, No 6 has been published with online version     [Click]