Petri网的步问题研究  

On the Step Problem for Petri Nets

作　　者：潘理[1,2] 赵卫东[1] 王志成[1] 周新民[1] 柳先辉[1] 

机构地区：[1]同济大学企业数字化技术教育部工程研究中心,上海200092 [2]湖南理工学院计算机与信息工程系,湖南岳阳414006

出　　处：《软件学报》2009年第3期505-514,共10页Journal of Software

基　　金：国家高技术研究发展计划(863);国家科技支撑计划;上海市科委项目~~

摘　　要：在基于Petri网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP等价性证明.最后分析两类特殊子问题是P问题.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 reachability graph based on steps, a new decision problem, the step problem, is proposed for Petri nets. The NP-completeness of this problem is proved by the reduction from the independent set problem. A polynomial-time algorithm for the maximal 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.

关 键 词：PETRI网 发 步问题 NP完全性 NP等价性 

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