可达性与状态方程可满足性等价的两个Petri网子类

摘要：

可达性是Petri网最基本最重要的动态性质之一,但一般Petri网的可达性判定问题至少具有指数空间复杂度,且目前尚无有效的判定算法。不过,存在某些Petri网子类,其可达性判定问题要相对简单,寻找这样的Petri网子类具有重要意义.为此,提出极小陷阱回路网与后向回路网的概念,并证明了初始标识下不含空极小回路的这两个Petri网子类。其可达性判定同题等价于状态方程的可满足性问题.

关键词： Petri网 可达性 状态方程 极小陷阱回路网 后向回路网 空间复杂度

作者: 包云霞 鲁法明 曾庆田

作者单位: 山东科技大学理学院 山东青岛 266510 山东科技大学信息学院,山东青岛 266510

会议类型: 国内会议

会议名称: 第十一届全国Petri网理论与应用学术年会

会议地点: 大连

会议语种:中文

页码: 44-46

在线出版日期: 2007-08-01（万方平台首次上网日期，不代表论文的发表时间）