| Petri 网的步问题研究 |
| |
| 引用本文： | 潘理,赵卫东,王志成,周新民,柳先辉.Petri 网的步问题研究[J].软件学报,2009,20(3):505-514. |
| |
| 作者姓名： | 潘理 赵卫东 王志成 周新民 柳先辉 |
| |
| 作者单位： | 1. 同济大学,企业数字化技术教育部工程研究中心,上海,200092;湖南理工学院,计算机与信息工程系,湖南,岳阳,414006
2. 同济大学,企业数字化技术教育部工程研究中心,上海,200092 |
| |
| 基金项目： | 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 (上海市科委项目) |
| |
| 摘 要： | 在基于Petri 网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP 完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP 等价性证明.最后分析两类特殊子问题是P 问题.
|
| 关 键 词： | Petri网 发 步问题 NP完全性 NP等价性 |
| 收稿时间： | 2007/8/28 0:00:00 |
| 修稿时间： | 2007/12/24 0:00:00 |
On the Step Problem for Petri Nets |
| |
| PAN Li,ZHAO Wei-Dong,WANG Zhi-Cheng,ZHOU Xin-Min and LIU Xian-Hui.On the Step Problem for Petri Nets[J].Journal of Software,2009,20(3):505-514. |
| |
| Authors: | PAN Li ZHAO Wei-Dong WANG Zhi-Cheng ZHOU Xin-Min and 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. |
| |
| Keywords: | Petri nets concurrency step problem NP-completeness NP-equivalence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
