A Reduced Reachability Tree for a Class of Unbounded Petri Nets

Shouguang Wang; Mengdi Gan; Mengchu Zhou; Dan You

Volume 2 Issue 4

Oct. 2015

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2015 > 2(4): 345-352

Shouguang Wang, Mengdi Gan, Mengchu Zhou and Dan You, "A Reduced Reachability Tree for a Class of Unbounded Petri Nets," IEEE/CAA J. of Autom. Sinica, vol. 2, no. 4, pp. 345-352, 2015.

Citation:

Shouguang Wang, Mengdi Gan, Mengchu Zhou and Dan You, "A Reduced Reachability Tree for a Class of Unbounded Petri Nets," IEEE/CAA J. of Autom. Sinica, vol. 2, no. 4, pp. 345-352, 2015.

Shouguang Wang, Mengdi Gan, Mengchu Zhou and Dan You, "A Reduced Reachability Tree for a Class of Unbounded Petri Nets," IEEE/CAA J. of Autom. Sinica, vol. 2, no. 4, pp. 345-352, 2015.

Citation:

Shouguang Wang, Mengdi Gan, Mengchu Zhou and Dan You, "A Reduced Reachability Tree for a Class of Unbounded Petri Nets," IEEE/CAA J. of Autom. Sinica, vol. 2, no. 4, pp. 345-352, 2015.

PDF( 2053 KB)

A Reduced Reachability Tree for a Class of Unbounded Petri Nets

1. the School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China, and also with the State Key Laboratory for Manufacturing Systems Engineering, Xi'an Jiaotong University, Xi'an 710049, China;
2. the Ministry of Education (MoE) Key Laboratory of Embedded System and Service Computing, Tongji University, Shanghai 200092, China;
3. the MoE Key Laboratory of Embedded System and Service Computing, Tongji University, Shanghai 200092, China, and also with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102-1982, USA;
4. the School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China

Funds:

This work is in part supported by National Natural Science Foundation of China (61374148, 61472361), Natural Science Foundation of Zhejiang Province (LY15F030003, LY15F030002, LR14F020001), the National Science Foundation of USA (CMMI-1162482), the Opening Project of State Key Laboratory for Manufacturing Systems Engineering (sklms2014011), Zhejiang NNST Key Laboratory (2015C31064), and the State Scholarship Fund of China.

Abstract

Abstract

As a powerful analysis tool of Petri nets, reachability trees are fundamental for systematically investigating many characteristics such as boundedness, liveness and reversibility. This work proposes a method to generate a reachability tree, called ωRT for short, for a class of unbounded generalized nets called ω-independent nets based on new modified reachability trees (NMRTs). ωRT can effectively decrease the number of nodes by removing duplicate and ω-duplicate nodes in the tree, and verify properties such as reachability, liveness and deadlocks. Two examples are provided to show its superiority over NMRTs in terms of tree size.
- Petri nets,
- reachability tree,
- deadlock

FullText(HTML)

References(30)

References

[1]	Hrz B, Zhou M C. Modeling and Control of Discrete-Event Dynamic Systems. London, UK: Springer, 2007.
[2]	Ding Z H, Zhou M C, Wang S G. Ordinary differential equationbased deadlock detection. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2014, 44(10): 1435-1454
[3]	Hu H S, Zhou M C. A petri net-based discrete-event control of automated manufacturing systems with assembly operations. IEEE Transactions on Control Systems Technology, 2015, 23(2): 513-524
[4]	Karp R M, Miller R E. Parallel program schemata. Journal of Computer and System Sciences, 1969, 3(2): 147-195
[5]	Li Z W, Zhou M C. Deadlock Resolution in Automated Manufacturing Systems: a Novel Petri Net Approach. London: Springer, 2009.
[6]	Murata T. Petri nets: properties, analysis and applications. Proceedings of the IEEE, 1989, 77(4): 541-580
[7]	Peterson J L. Petri Net Theory and the Modeling of Systems. NJ: Prentice-Hall, 1981.
[8]	Wu N Q, Zhou M C, Chu F, Mammar S. Modeling, analysis, scheduling, and control of cluster tools in semiconductor fabrication. Contemporary Issues in Systems Science and Engineering. Hoboken, NJ: Wiley/IEEE Press, 2015. 289-315
[9]	Yang F J, Wu N Q, Qiao Y, Zhou M C. Petri net-based optimal one-wafer cyclic scheduling of hybrid multi-cluster tools in wafer fabrication. IEEE Transactions on Semiconductor Manufacturing, 2014, 27(2): 192-203
[10]	Zhou M C, Dicesare F. Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. London: Kluwer Academic Publishers, 1993.
[11]	Zhou M C, Venkatesh K. Modeling, Simulation and Control of Flexible Manufacturing Systems: A Petri Net Approach. Singapore: World Scientific, 1998.
[12]	Ding Z J, Jiang C J, Zhou M C. Deadlock checking for one-place unbounded Petri nets based on modified reachability trees. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2008, 38(3): 881-883
[13]	der Jeng M, Peng M Y. On the liveness problem of 1-place-unbounded Petri nets. In: Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation. Orlando, FL: IEEE, 1997. 3221-3226
[14]	Jeng M D, Peng M Y. Augmented reachability trees for 1-placeunbounded generalized Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 1999, 29(2): 173-183
[15]	Ru Y, Wu W W, Hadjicostis C N. Comments on a modified reachability tree approach to analysis of unbounded Petri nets . IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2006, 36(5): 1210
[16]	Wang F Y. A modified reachability tree for Petri nets. In: Proceedings of the 1999 IEEE International Conference on Systems, Man, and Cybernetics. Charlottesville, VA: IEEE, 1991. 329-334
[17]	Wang F Y, Gao Y Q, Zhou M C. A modified reachability tree approach to analysis of unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(1): 303-308
[18]	Wang S G, Zhou M C, Li Z W, Wang C Y. A new modified reachability tree approach and its applications to unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 43(4): 932-940
[19]	Wang Y H, Jiang B, Jiao L. Property checking for 1-place-unbounded Petri nets. In: Proceedings of the 4th IEEE International Symposium on Theoretical Aspects of Software Engineering (TASE). Taipei, China: IEEE, 2010. 117-125
[20]	Fu Jian-Feng, Dong Li-Da, Xu Shan-Shan, Zhu Dan, Zhu Cheng-Cheng. An improved liveness condition for S⁴PR nets. Acta Automatica Sinica, 2013, 39(9): 1439-1446 (in Chinese)
[21]	Li Z W, Wang A R. A Petri net based deadlock prevention approach for flexible manufacturing systems. Acta Automatica Sinica, 2003, 29(5): 733-740
[22]	Xing Ke-Yi, Tian Feng, Yang Xiao-Jun, Hu Bao-Sheng. Polynomialcomplexity deadlock avoidance policies for automated manufacturing systems. Acta Automatica Sinica, 2007, 33(8): 893-896 (in Chinese)
[23]	Wang S G, Gan M D, Zhou M C. Macro liveness graph and liveness of ω-independent unbounded nets. Science China Information Sciences, 2015, 58(3): 032201
[24]	Wong H M, Zhou M C. Automated generation of modified reachability trees for Petri nets. In: Proceedings of the 1992 Regional Control Conference. Brooklyn, NY, 1992. 119-121
[25]	Huang Y S, Pan Y L, Zhou M C. Computationally improved optimal deadlock control policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2012, 42(2): 404-415
[26]	Huang Y S, Weng Y S, Zhou M C. Modular design of urban traffic-light control systems based on synchronized timed Petri nets. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(2): 530-539
[27]	Pan L, Ding Z J, Zhou M C. A configurable state class method for temporal analysis of time Petri nets. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2014, 44(4): 482-493
[28]	Cheng J J, Cheng J L, Zhou M C, Liu F Q, Gao S C, Liu C. Routing in internet of vehicles: a review. IEEE Transactions on Intelligent Transportation Systems, to be published
[29]	Ding Z H, Zhou Y, Jiang M Y, Zhou M C. A new class of Petri nets for modeling and property verification of switched stochastic systems. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(7): 1087-1100
[30]	Lee J S, Zhou M C, Hsu P L. Multiparadigm modeling for hybrid dynamic systems using a Petri net framework. IEEE Transactions on Systems, Man, and Cybernetics: Part A: Systems and Humans, 2008, 38(2): 493-498

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Get Citation

PDF

XML

Article Metrics

Article views (1125) PDF downloads(14)

A Reduced Reachability Tree for a Class of Unbounded Petri Nets

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Export File

Citation

Format

Content