单触发Petri网的一个可达性判定方法

An Algorithm for Reachability Decision of Live Single Firing Petri-Nets

可达性判定问题是Petri网理论研究的一个重要课题。已有文献提出通过构造Petri网的可达树或可覆盖树来分析其可达性,但其中无界量"的引入导致了无界Petri网运行过程中的信息丢失,使其可达性无法得到判定。众所周知,对于有界Petri网,通过构造其可达性树或可达标识图来判定其可达性是容易的,但对于大量存在的无界Petri网,找到一个能判定其可达性的一般性算法却不太容易。本文给出一个Petri网子类——单触发Petri网,并给出它的一个可达性判定方法。

Reaehability decision problem is one of the most important topics in Petri nets theory. Some articles show that teachability of Petri nets can be studied with its teachability tree, but the limitless variable ＂ω＂ in it bring the information losing during unbounded Petri nets running so that decision of its reaehability can not be achieved. It is well known that deciding reachability of bounded Petri nets with its reachability tree is easy. But for lots of unbounded Petri nets finding an algorithm for its reachability decision is not easy. In this paper, we bring forward a subclass of Petri-Nets ——single firing Petri-Nets, and propose an algorithm for its teachability decision.