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 language | English (US) |
---|---|
Article number | 7920387 |
Pages (from-to) | 1164-1174 |
Number of pages | 11 |
Journal | IEEE Transactions on Systems, Man, and Cybernetics: Systems |
Volume | 49 |
Issue number | 6 |
DOIs | |
State | Published - 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