###
DOI:
Journal of Software:2009.20(3):505-514

Petri 网的步问题研究
潘理,赵卫东,王志成,周新民,柳先辉
(同济大学 企业数字化技术教育部工程研究中心,上海 200092;湖南理工学院 计算机与信息工程系,湖南 岳阳 414006)
On the Step Problem for Petri Nets
PAN Li,ZHAO Wei-Dong,WANG Zhi-Cheng,ZHOU Xin-Min,LIU Xian-Hui
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4147   Download 4512
Received:August 28, 2007    Revised:December 24, 2007
> 中文摘要: 在基于Petri 网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP 完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP 等价性证明.最后分析两类特殊子问题是P 问题.
中文关键词: Petri 网    步问题  NP 完全性  NP 等价性
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.
文章编号:     中图分类号:    文献标志码:
基金项目: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 (上海市科委项目) 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 (上海市科委项目)
Foundation items:
Reference text:

潘理,赵卫东,王志成,周新民,柳先辉.Petri 网的步问题研究.软件学报,2009,20(3):505-514

PAN Li,ZHAO Wei-Dong,WANG Zhi-Cheng,ZHOU Xin-Min,LIU Xian-Hui.On the Step Problem for Petri Nets.Journal of Software,2009,20(3):505-514