| 摘要: |
| 在基于Petri 网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP 完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP 等价性证明.最后分析两类特殊子问题是P 问题. |
| 关键词: Petri 网 发 步问题 NP 完全性 NP 等价性 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National High-Tech Research and Development Plan of China under Grant No.2007AA04Z1A7 (国家高技术研究发展计划(863)); the National Key Technology R&D Programs of China under Grant Nos.2006BAF01A35, 2006BAF01A42 (国家科技支撑计划); the Research Program of Science and Technology Commission of Shanghai Municipality of China under Grant Nos.072112026,07dz11309, 08dz1126101 (上海市科委项目) |
|
| On the Step Problem for Petri Nets |
|
PAN Li,ZHAO Wei-Dong,WANG Zhi-Cheng,ZHOU Xin-Min,LIU Xian-Hui
|
| Abstract: |
| In verification methods based on Petri nets, the step has been widely applied to the decrease of the
interleaving of transition firings. To study the computational complexity of the algorithm for building a reachabilitygraph based on steps, a new decision problem, the step problem, is proposed for Petri nets. The NP-completeness ofthis problem is proved by the reduction from the independent set problem. A polynomial-time algorithm for themaximal step problem is then presented. Furthermore, the maximum step problem is proved to be NP-equivalent.Finally, two kinds of sub-problems solvable in polynomial time are also discussed and analyzed. |
| Key words: Petri nets concurrency step problem NP-completeness NP-equivalence |
