摘要
可达性是Petri网最基本最重要的动态性质之一,但一般Petri网的可达性判定问题至少具有指数空间复杂度,且目前尚无有效的判定算法。不过,存在某些Petri网子类,其可达性判定问题要相对简单,寻找这样的Petri网子类具有重要意义。为此,提出极小陷阱回路网与后向回路网的概念,并证明了初始标识下不含空极小回路的这两个Petri网子类,其可达性判定问题等价于状态方程的可满足性问题。
Reachability is one of the most basic and important dynamic properties of Petri nets. But the reachability decidability problem has at least exponential space complexity and no effective algorithm is found by now. However, there exist some special Petri nets the reachability problem of which is easiliy to be decided. And it has great significance to find such Petri nets subclasses. For this reason, the definitions of minimal-trap-circuit Petri net and backward-circuit Petri net are provided in this paper. It is pointed out that the reachability problem of these two kinds of Petri nets subclasses is equivalent to the satisfiability of state equation if no token-freee minimal circuit exists under the initial marking.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2007年第A01期44-46,共3页
Journal of System Simulation
基金
国家自然科学基金(60673053
60603090)
山东省优秀中青年科学家奖励基金(2006BS01019)
关键词
PETRI网
可达性
极小陷阱回路网
后向回路网
Petri nets
Reachability
minimal-trap-circuit Petri nets
backward-circuit Petri nets
