TY - JOUR

T1 - A State-Equation-Based Backward Approach to a Legal Firing Sequence Existence Problem in Petri Nets

AU - Qi, Liang

AU - Su, Yue

AU - Zhou, Meng Chu

AU - Abusorrah, Abdullah

N1 - Funding Information:
This work was supported in part by the National Natural Science Foundation of China under Grant 61903229, Grant 61973180, Grant 62072287, and Grant 62072288; and in part by the Natural Science Foundation of Shandong Province under Grant ZR2022MF270.
Publisher Copyright:
© 2022 IEEE.

PY - 2023/8/1

Y1 - 2023/8/1

N2 - Reachability is the basis for studying other dynamic properties of Petri nets (PNs). When a state equation is used to determine the reachability of a marking, we need to judge whether there is a corresponding legal firing sequence (LFS) for a non-negative integer solution (NIS), i.e., a firing count vector, of the state equation. The search for an LFS is an NP-hard problem, and previous work cannot always find an LFS for any NISs. This article proposes that transition-dependent circuits or firing-dependent circuits are the root cause that a state equation has an NIS but the marking is nonreachable, i.e., there is no LFS corresponding to an NIS in PNs. Based on this, we propose a state-equation-based backward algorithm (SBA) to determine whether there is an LFS corresponding to an NIS of the state equation in a PN. The correctness and effectiveness of SBA are verified by a case study on a PN-based flexible manufacturing system and through simulation on an S 4PR net. The experimental results show that the time required for SBA to determine the existence of an LFS increases linearly with the transition firing count in NISs. When the number of NISs of a state equation is finite, we can efficiently determine the reachability of a marking. This represents an important result in theory and applications of PNs.

AB - Reachability is the basis for studying other dynamic properties of Petri nets (PNs). When a state equation is used to determine the reachability of a marking, we need to judge whether there is a corresponding legal firing sequence (LFS) for a non-negative integer solution (NIS), i.e., a firing count vector, of the state equation. The search for an LFS is an NP-hard problem, and previous work cannot always find an LFS for any NISs. This article proposes that transition-dependent circuits or firing-dependent circuits are the root cause that a state equation has an NIS but the marking is nonreachable, i.e., there is no LFS corresponding to an NIS in PNs. Based on this, we propose a state-equation-based backward algorithm (SBA) to determine whether there is an LFS corresponding to an NIS of the state equation in a PN. The correctness and effectiveness of SBA are verified by a case study on a PN-based flexible manufacturing system and through simulation on an S 4PR net. The experimental results show that the time required for SBA to determine the existence of an LFS increases linearly with the transition firing count in NISs. When the number of NISs of a state equation is finite, we can efficiently determine the reachability of a marking. This represents an important result in theory and applications of PNs.

KW - Legal firing sequence (LFS) existence

KW - Petri nets (PNs)

KW - manufacturing systems

KW - reachability

KW - state equation

UR - http://www.scopus.com/inward/record.url?scp=85153513260&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85153513260&partnerID=8YFLogxK

U2 - 10.1109/TSMC.2023.3241101

DO - 10.1109/TSMC.2023.3241101

M3 - Article

AN - SCOPUS:85153513260

SN - 2168-2216

VL - 53

SP - 4968

EP - 4979

JO - IEEE Transactions on Systems, Man, and Cybernetics: Systems

JF - IEEE Transactions on Systems, Man, and Cybernetics: Systems

IS - 8

ER -