TY - JOUR
T1 - On Liveness Enforcing Supervisory Policies for Arbitrary Petri Nets
AU - Chen, Chen
AU - Raman, Arun
AU - Hu, Hesuan
AU - Sreenivas, Ramavarapu S.
N1 - Funding Information:
Manuscript received October 21, 2018; revised July 5, 2019 and October 29, 2019; accepted January 22, 2020. Date of publication January 28, 2020; date of current version December 3, 2020. The work of C. Chen and H. Hu was supported in part by the Natural Science Foundation of China under Grant 61973242, Grant 61573265, Grant 61203037, and Grant 51305321, in part by the Fundamental Research Funds for the Central Universities under Grant K7215581201, Grant K5051304004, and Grant K5051304021, in part by the New Century Excellent Talents in University under Grant NCET-12-0921, in part by the Academic Research Fund Tier 1 by Ministry of Education in Singapore under Grant 2014-T1-001-147, in part by the Academic Research Fund Tier 2 by Ministry of Education in Singapore under Grant MOE2015-T2-2-049, and in part by the Major Fundamental Research Program of the Natural Science Foundation of Shaanxi Province under Grant 2017ZDJC-34. The work of A. Raman and R. S. Sreenivas was supported by the Arthur Davis Faculty Scholar Endowment at the University of Illinois at Urbana-Champaign. Recommended by Associate Editor C. Seatzu. (Chen Chen and Arun Raman are co-first authors.) (Corresponding author: Ramavarapu S. Sreenivas.) C. Chen and H. Hu are with the School of Electromechanical Engineering, Xidian University, Xi’an 710071, China (e-mail: chenchen0@xidian.edu.cn; huhesuan@gmail.com).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2020/12
Y1 - 2020/12
N2 - Neither the existence nor the nonexistence of a liveness enforcing supervisory policy (LESP) for an arbitrary Petri net (PN) is semidecidable. In an attempt to identify decidable instances, we explore the decidability of certain properties of the set of initial markings for which an LESP exists, and the decidability of the existence of a specific class of LESPs. We first prove that for an arbitrary PN structure, determining if there is an initial marking, or there are no initial markings, for which there is an LESP, is not semidecidable. Then, we characterize the class of PN structures for which the set of all initial markings for which an LESP exists is right-closed. We show that testing membership, or nonmembership, of an arbitrary PN in this class of PNs is not semidecidable. We then consider a restricted class of LESPs, called marking monotone LESPs (MM-LESPs). We show that the existence of an MM-LESP for an arbitrary PN is decidable.
AB - Neither the existence nor the nonexistence of a liveness enforcing supervisory policy (LESP) for an arbitrary Petri net (PN) is semidecidable. In an attempt to identify decidable instances, we explore the decidability of certain properties of the set of initial markings for which an LESP exists, and the decidability of the existence of a specific class of LESPs. We first prove that for an arbitrary PN structure, determining if there is an initial marking, or there are no initial markings, for which there is an LESP, is not semidecidable. Then, we characterize the class of PN structures for which the set of all initial markings for which an LESP exists is right-closed. We show that testing membership, or nonmembership, of an arbitrary PN in this class of PNs is not semidecidable. We then consider a restricted class of LESPs, called marking monotone LESPs (MM-LESPs). We show that the existence of an MM-LESP for an arbitrary PN is decidable.
KW - Discrete-event dynamic systems (DEDSs)
KW - Petri nets (PNs)
KW - supervisory control
UR - http://www.scopus.com/inward/record.url?scp=85097643361&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097643361&partnerID=8YFLogxK
U2 - 10.1109/TAC.2020.2970060
DO - 10.1109/TAC.2020.2970060
M3 - Article
AN - SCOPUS:85097643361
SN - 0018-9286
VL - 65
SP - 5236
EP - 5247
JO - IRE Transactions on Automatic Control
JF - IRE Transactions on Automatic Control
IS - 12
M1 - 8972386
ER -