Maximal conflict set enumeration algorithm based on locality of Petri nets

被引：0

作者：

Pan L. ^{[1
]}

Zheng H. ^{[2
]}

Liu X.-M. ^{[3
]}

Yang B. ^{[1
]}

机构：

[1] School of Information and Communication Engineering, Hunan Institute of Science and Technology, Yueyang, 414006, Hunan

[2] Information Science and Engineering College, East China University of Science and Technology, Shanghai

[3] Information and Communication Branch, Jiangxi Electric Power Company, Nanchang, 330077, Jiangxi

来源：

Tien Tzu Hsueh Pao/Acta Electronica Sinica | 2016年 / 44卷 / 08期

关键词：

Conflict set problem; Maximal conflict set enumeration algorithm; NP completeness; Petri nets;

D O I：

10.3969/j.issn.0372-2112.2016.08.013

中图分类号：

O144 [集合论]; O157 [组合数学（组合学）];

学科分类号：

070104 ;

摘要：

Conflict is an essential concept in Petri net theory. The existing research focuses on the modelling and resolution strategies of conflict problems, but less on the computational complexity of the problems their selves. In this paper, we propose the conflict set problem for Petri nets, and prove that the conflict set problem is NP-complete. Furthermore, we present a dynamic algorithm for the maximal conflict set enumeration. Our algorithm only computes those conflict sets that are affected by local firing, which avoids enumerating all maximal conflict sets at each marking. The algorithm needs time O(m2n) where m is the number of maximal conflict sets at the current marking and n is the number of transitions. Finally, we show that the maximal conflict set enumeration problem can be solved in O(n2) for free-choice nets and asymmetric choice nets. The results on complexity of thel conflict set problem provide a theoretical reference for solving conflict problems of Petri nets. © 2016, Chinese Institute of Electronics. All right reserved.

引用

页码：1858 / 1863

页数：5

共 20 条

[1]

Lyapunov A.M., Petri Nets for Systems Engineering: A Guide to Modeling, Verification, and Applications, (2013)

[2]

Murata T., Petri nets: Properties, Analysis and Applications, Proceedings of the IEEE, 77, 4, pp. 541-580, (1989)

[3]

Yen H.C., Priority conflict-free Petri nets, Acta Informatica, 35, 8, pp. 673-688, (1998)

[4]

Merlin P.M., Et al., Recoverability of communication protocols-Implications of a theoretical study, IEEE Transactions on Communications, 24, 9, pp. 1036-1043, (1976)

[5]

Genrich H.J., Predicate/Transition Nets, (1987)

[6]

Balbo G., Introduction to Stochastic Petri Nets, (2001)

[7]

Zeng Q., Liu C., Duan H., Resource conflict detection and removal strategy for nondeterministic emergency response processes using Petri nets, Enterprise Information Systems, pp. 1-22, (2015)

[8]

Tian Z., Zhang Z.D., Ye Y.D., Et al., Analysis of real-time system conflict based on fuzzy time Petri nets, Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, 26, 2, pp. 983-991, (2014)

[9]

Popescu C., Soto M.C., Lastra J.L.M., A Petri net-based approach to incremental modelling of flow and resources in service-oriented manufacturing systems, International Journal of Production Research, 50, 2, pp. 325-343, (2012)

[10]

Cheng A., Et al., Complexity results for 1-safe nets, Theoretical Computer Science, 147, 1-2, pp. 117-136, (1995)

← 1 2 →