A polynomial algorithm to find a set of elementary siphons in a class of Petri Nets

Zhi Wu Li, Yun An Zhi, Mengchu Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

The concept of siphons plays an important role in the analysis of Petri nets. In particular, criteria for liveness and reachability of some subclasses of Petri nets can be stated in terms of siphons. However, the computation of these structural components can be time-consuming or even impossible. Recently, a variety of deadlock control policies that rely on partial siphon computation and enumeration have been developed. In this paper we propose a polynomial algorithm to find a set of elementary siphons in a class of Petri nets called systems of simple sequential processes with resources, S3 PR for short. Based on them, other siphons, called dependent ones, can be composed by simple set operations. Case studies show that the proposed algorithm is more computationally efficient than INA, Integrated Net Analyzer, a widely used Petri net analysis tool.

Original languageEnglish (US)
Title of host publication2004 IEEE International Conference on Systems, Man and Cybernetics, SMC 2004
Pages4861-4866
Number of pages6
DOIs
StatePublished - Dec 1 2004
Event2004 IEEE International Conference on Systems, Man and Cybernetics, SMC 2004 - The Hague, Netherlands
Duration: Oct 10 2004Oct 13 2004

Publication series

NameConference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
Volume5
ISSN (Print)1062-922X

Other

Other2004 IEEE International Conference on Systems, Man and Cybernetics, SMC 2004
CountryNetherlands
CityThe Hague
Period10/10/0410/13/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • Deadlock control
  • Elementary siphon
  • Petri net
  • Siphon

Fingerprint Dive into the research topics of 'A polynomial algorithm to find a set of elementary siphons in a class of Petri Nets'. Together they form a unique fingerprint.

Cite this