Complex Reachability Trees and Their Application to Deadlock Detection for Unbounded Petri Nets

Faming Lu, Qingtian Zeng, Meng Chu Zhou, Yunxia Bao, Hua Duan

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

Deadlock detection plays an important role in the analysis of system behavior. Several kinds of reachability trees have been proposed to analyze Petri net properties including deadlock freedom. However, existing reachability trees can only solve the deadlock detection problem of bounded or some special kinds of unbounded Petri nets. To increase the applicable scope of reachability trees in the deadlock detection field, this paper presents a new type of reachability trees called complex reachability tree (CRT). Different from others, transition sequences corresponding to root-started paths of cyclic CRTs are always firable from the initial marking. The proposed trees can completely solve the deadlock detection problem of ω -gone node-free Petri nets, but cannot guarantee to detect all the deadlocks for the other kinds of unbounded Petri nets. Their construction method and applications are presented.

Original languageEnglish (US)
Article number7920387
Pages (from-to)1164-1174
Number of pages11
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume49
Issue number6
DOIs
StatePublished - Jun 2019

All Science Journal Classification (ASJC) codes

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

Keywords

  • Complex reachability tree (CRT)
  • Petri nets
  • deadlock detection
  • reachability tree

Fingerprint

Dive into the research topics of 'Complex Reachability Trees and Their Application to Deadlock Detection for Unbounded Petri Nets'. Together they form a unique fingerprint.

Cite this