Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets |
| |
| Authors: | Jiang Changjun |
| |
| Affiliation: | Department of Computer Science, Tongji University,;Department of Computer Science, Shandong Science Technology University,;Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, |
| |
| Abstract: | 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. |
| |
| Keywords: | Petri net synchronous composition legal firing sequence testing algorithm NP-complete problem polynomial-time complex |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
|
