Analysis of Unbounded Petri Net With Lean Reachability Trees

Jun Li, Xiaolong Yu, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

Abstract

At present, no efficient method is proposed for the liveness analysis of general unbounded Petri nets (UPNs) except some of their subclasses. Our previous work presents a non-Karp-Miller finite reachability tree, i.e., lean reachability tree (LRT) to represent their markings. It faithfully expresses and folds the reachability set of an unbounded net. It can totally avoid the efforts made by the existing modified Karp-Miller trees on the expression of potentially unbounded nodes and elimination of all fake markings. By exploiting it, this paper presents a method for comprehensively analyzing the properties of general UPNs. Particularly, we reveal the repeatability of deadlock with the unfolding of some unbounded leaves in LRT and present a sufficient and necessary condition of deadlock existence. Then, LRT and some partial trees generated from it, instead of entire reachability graphs, are utilized to analyze the liveness and reversibility of general UPNs rather than some special ones. The related theoretical results are proven. A unified algorithm based on LRT for analysis of boundedness, liveness, deadlock, and reversibility of general UPNs is developed for the first time. The results of a case study show that the presented method is effective for general UPNs.

Original languageEnglish (US)
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
DOIs
StateAccepted/In press - Feb 6 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Analysis of Unbounded Petri Net With Lean Reachability Trees'. Together they form a unique fingerprint.

Cite this