Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets  

作　　者：蒋昌俊 

出　　处：《Science in China(Series F)》2001年第3期226-233,共8页中国科学（F辑英文版）

基　　金：This work was supported by the National Natural Science Foundation of China (Grant Nos. 69973029 and 69933020) ; the National Key Basic Science Foundation of P. R. China (973 Project, Grant No. G1998030604) ; the Key Project of National Science & Techn

摘　　要：As far as we know, the testing problem of legal firing sequence is NP-complete for gener-al Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classes, such as persistent Petri nets, conflict-free Petri nets and state machine Petri nets. In this paper, the language properties of synchronous composition net are discussed. Based on these results, the testing algorithm polynomial-time complexity for legal firing sequence is proposed. Therefore, net classification of polynomial-time solvability for testing legal firing sequence is extended.As far as we know, the testing problem of legal firing sequence is NP-complete for gener-al Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classes, such as persistent Petri nets, conflict-free Petri nets and state machine Petri nets. In this paper, the language properties of synchronous composition net are discussed. Based on these results, the testing algorithm polynomial-time complexity for legal firing sequence is proposed. Therefore, net classification of polynomial-time solvability for testing legal firing sequence is extended.

关 键 词：Petri net synchronous composition legal firing sequence testing algorithm NP-complete problem polynomial-time complex. 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]