Petri网的步问题研究

• 作者: 周新民 柳先辉 潘理 王志成 赵卫东
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: Petri网 发 步问题 NP完全性 NP等价性
• 年，卷（期）: 2009,（3）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 505-514
• 页数: 10页
• 分类号: TP301
• 字数: 9520字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03281

摘要

在基于Petri 网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP等价性证明.最后分析两类特殊子问题是P问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘理	同济大学企业数字化技术教育部工程研究中心	37	171	8.0	11.0
3	赵卫东	同济大学企业数字化技术教育部工程研究中心	71	366	11.0	15.0
4	王志成	同济大学企业数字化技术教育部工程研究中心	8	65	5.0	8.0
5	柳先辉	同济大学企业数字化技术教育部工程研究中心	21	89	6.0	9.0
8	周新民	同济大学企业数字化技术教育部工程研究中心	1	8	1.0	1.0