Petri 网的步问题研究 - 软件学报.PDFVIP

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@ Journal of Software , Vol.20, No.3, March 2009, pp.505−514 DOI: 10.3724/SP.J.1001.2009.03281 Tel/Fax: +86-10 © by Institute of Software , the Chinese Academy of Sciences . All rights reserved. ∗ Petri 网的步问题研究 1,2+ 1 1 1 1 潘 理 , 赵卫东 , 王志成 , 周新民 , 柳先辉 1( 同济大学 企业数字化技术教育部工程研究中心,上海 200092) 2(湖南理工学院 计算机与信息工程系,湖南 岳阳 414006) On the Step Problem for Petri Nets 1,2+ 1 1 1 1 PAN Li , ZHAO Wei-Dong , WANG Zhi-Cheng , ZHOU Xin-Min , LIU Xian-Hui 1(Engineering Research Center for Enterprise Digital Technology, Tongji University, Shanghai 200092, China) 2(Department of Computer and Information Engineering, Hu’nan Institute of Science and Technology, Yueyang 414006, China) + Corresponding author: E-mail: panli12345@ Pan L, Zhao WD, Wang ZC, Zhou XM, Liu XH. On the step problem for Petri nets. Journal of Software, 2009,20(3):505−514. /1000-9825/3281.htm 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 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