A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 2 Issue 4
Oct.  2015

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 17.6, Top 3% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
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.

A Reduced Reachability Tree for a Class of Unbounded Petri Nets

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.

  • 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.

     

  • loading
  • [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 S4PR 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

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (1089) PDF downloads(10) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return