中国邮电高校学报(英文版) ›› 2017, Vol. 24 ›› Issue (1): 77-86.doi: 10.1016/S1005-8885(17)60190-0

• Artificial Intelligence • 上一篇    下一篇

Modeling and reachability analysis of synchronizing transitions bounded Petri net systems based upon semi-tensor product of matrices

Gao Na, Han Xiaoguang, Chen Zengqiang, Zhang Qing   

  1. 1. College of Computer and Control Engineering, Nankai University 
    2. Tianjin Key Laboratory of Intelligent Robotics 
    3. College of Science, Civil Aviation University of China
  • 收稿日期:2016-08-19 修回日期:2017-01-19 出版日期:2017-02-28 发布日期:2017-02-28
  • 通讯作者: 陈增强 E-mail:chenzq@nankai.edu.cn
  • 基金资助:
    This work was supported by the National Natural Science Foundation of China (61573199, 61573200), the Tianjin Natural Science Foundation (14JCYBJC18700).

Modeling and reachability analysis of synchronizing transitions bounded Petri net systems based upon semi-tensor product of matrices

Gao Na, Han Xiaoguang, Chen Zengqiang, Zhang Qing   

  1. 1. College of Computer and Control Engineering, Nankai University 
    2. Tianjin Key Laboratory of Intelligent Robotics 
    3. College of Science, Civil Aviation University of China
  • Received:2016-08-19 Revised:2017-01-19 Online:2017-02-28 Published:2017-02-28
  • Contact: Chen Zeng-Qiang E-mail:chenzq@nankai.edu.cn
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61573199, 61573200), the Tianjin Natural Science Foundation (14JCYBJC18700).

摘要: The reachability problem of synchronizing transitions bounded Petri net systems (BPNSs) is investigated in this paper by constructing a mathematical model for dynamics of BPNS. Using the semi-tensor product (STP) of matrices, the dynamics of BPNSs, which can be viewed as a combination of several small bounded subnets via synchronizing transitions, are described by an algebraic equation. When the algebraic form for its dynamics is established, we can present a necessary and sufficient condition for the reachability between any marking (or state) and initial marking. Also, we give a corresponding algorithm to calculate all of the transition paths between initial marking and any target marking. Finally, an example is shown to illustrate proposed results. The key advantage of our approach, in which the set of reachable markings of BPNSs can be expressed by the set of reachable markings of subnets such that the big reachability set of BPNSs do not need generate, is partly avoid the state explosion problem of Petri nets (PNs).

关键词: reachability, Petri nets, BPNSs, semi-tensor product (STP) of matrices, synchronizing transitions

Abstract: The reachability problem of synchronizing transitions bounded Petri net systems (BPNSs) is investigated in this paper by constructing a mathematical model for dynamics of BPNS. Using the semi-tensor product (STP) of matrices, the dynamics of BPNSs, which can be viewed as a combination of several small bounded subnets via synchronizing transitions, are described by an algebraic equation. When the algebraic form for its dynamics is established, we can present a necessary and sufficient condition for the reachability between any marking (or state) and initial marking. Also, we give a corresponding algorithm to calculate all of the transition paths between initial marking and any target marking. Finally, an example is shown to illustrate proposed results. The key advantage of our approach, in which the set of reachable markings of BPNSs can be expressed by the set of reachable markings of subnets such that the big reachability set of BPNSs do not need generate, is partly avoid the state explosion problem of Petri nets (PNs).

Key words: reachability, Petri nets, BPNSs, semi-tensor product (STP) of matrices, synchronizing transitions