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

被引：3

作者：

包云霞 ^{[1
]}

鲁法明 ^{[2
]}

曾庆田 ^{[2
]}

机构：

[1] 山东科技大学理学院

[2] 山东科技大学信息学院

来源：

系统仿真学报 | 2007年 / S1期

关键词：

Petri网; 可达性; 极小陷阱回路网; 后向回路网;

D O I：

10.16182/j.cnki.joss.2007.s1.016

中图分类号：

TP301.1 [自动机理论];

学科分类号：

摘要：

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

引用

页码：44 / 46

页数：3