A Backward Algorithm to Determine the Existence of Legal Firing Sequences in Ordinary Petri Nets

Yue Su, Liang Qi, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Petri nets (PNs) are a graphical and mathematical tool to model various event-driven automated systems. Reachability is a fundamental property of PNs. The existence of a non-negative integer solution (NIS) to a state equation is a necessary but not sufficient condition for determining the reachability of PNs, i.e., there may be no legal firing sequence (LFS) corresponding to an NIS of a state equation. Finding an LFS for an NIS of a state equation is an NP-hard problem. However, we determine the reachability of a marking by determining the existence of LFSs rather than finding them. We find that the existence of idling circuits (ICs) or idling-dependent circuits (IDCs) is the root cause that there is an NIS satisfying the state equation but the marking is non-reachable in ordinary PNs. Based on this, a Backward Algorithm is presented to determine the existence of an LFS for an NIS. It reversely finds paths from the destination marking to the initial one and determines whether there is always an intermediate marking with ICs or IDCs. When the state equation has a finite number of NISs, only the polynomial time is needed to analyze the reachability of ordinary PNs. Experimental results verify the effectiveness and efficiency of the approach. This work represents an important advance in the theory and applications of PNs to automated system design.

Original languageEnglish (US)
Pages (from-to)3190-3197
Number of pages8
JournalIEEE Robotics and Automation Letters
Volume8
Issue number6
DOIs
StatePublished - Jun 1 2023

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence

Keywords

  • Automated manufacturing systems
  • Petri nets
  • backward algorithm
  • discrete event systems
  • intelligent automation
  • reachability

Fingerprint

Dive into the research topics of 'A Backward Algorithm to Determine the Existence of Legal Firing Sequences in Ordinary Petri Nets'. Together they form a unique fingerprint.

Cite this