Basis Marking Representation of Petri Net Reachability Spaces and Its Application to the Reachability Problem

被引:112
作者
Ma, Ziyue [1 ,2 ]
Tong, Yin [1 ,2 ]
Li, Zhiwu [3 ]
Giua, Alessandro [4 ,5 ]
机构
[1] Xidian Univ, Sch Electromech Engn, Xian 710071, Peoples R China
[2] Univ Cagliari, Dipartimento Ingn Elettr & Elettron, I-09124 Cagliari, Italy
[3] Macau Univ Sci & Technol, Inst Syst Engn, Taipa, Macau, Peoples R China
[4] Aix Marseille Univ, Univ Toulon, CNRS, ENSAM,LSIS UMR 7296, F-13397 Marseille, France
[5] Univ Cagliari, DIEE, I-09124 Cagliari, Italy
基金
中国国家自然科学基金;
关键词
Basis reachability graph; discrete-event systems; Petri nets; DISCRETE-EVENT SYSTEMS; DEADLOCK PREVENTION; ELEMENTARY; SIPHONS; DESIGN;
D O I
10.1109/TAC.2016.2574120
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, a compact representation of the reachability graph of a Petri net is proposed. The transition set of a Petri net is partitioned into the subsets of explicit and implicit transitions in such a way that the subnet induced by implicit transitions does not contain directed cycles. The firing of implicit transitions can be abstracted so that the reachability set of the net can be completely characterized by a subset of reachable markings called basis makings. We show that to determine a max-cardinality-T-I basis partition is an NP-hard problem, but a max-set-T-I basis partition can be determined in polynomial time. The generalized version of the marking reachability problem in a Petri net can be solved by a practically efficient algorithm based on the basis reachability graph. Finally, this approach is further extended to unbounded nets.
引用
收藏
页码:1078 / 1093
页数:16
相关论文
共 34 条
[21]   PERSISTENCE OF VECTOR REPLACEMENT SYSTEMS IS DECIDABLE [J].
MAYR, E .
ACTA INFORMATICA, 1981, 15 (03) :309-318
[22]   Modular Reachability Analysis of Petri Nets for Multiagent Systems [J].
Miyamoto, Toshiyuki ;
Horiguchi, Kyota .
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2013, 43 (06) :1411-1423
[23]   Maximally permissive deadlock avoidance for resource allocation systems with R/W-locks [J].
Nazeem, Ahmed ;
Reveliotis, Spyros .
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2015, 25 (1-2) :31-63
[24]   Designing Compact and Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems Through Classification Theory: The Nonlinear Case [J].
Nazeem, Ahmed ;
Reveliotis, Spyros .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2012, 57 (07) :1670-1684
[25]  
Pastor E., 1999, Application and Theory of Petri Nets 1999. 20th International Conference, ICATPN'99. Proceedings (Lecture Notes in Computer Science Vol.1639), P26
[26]   Synchronizing sequences on a class of unbounded systems using synchronized Petri nets [J].
Pocci, Marco ;
Demongodin, Isabel ;
Giambiasi, Norbert ;
Giua, Alessandro .
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2016, 26 (01) :85-108
[27]  
Ru Y, 2008, IEEE DECIS CONTR P, P1048
[28]   A METHOD FOR STEPWISE REFINEMENT AND ABSTRACTION OF PETRI NETS [J].
SUZUKI, I ;
MURATA, T .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1983, 27 (01) :51-76
[29]  
Tong Y., 2016, IEEE T AUTOM CONTROL, V61
[30]  
Tong Y., IEEE T AUTOM C UNPUB