Analysis of Unbounded Petri Net With Lean Reachability Trees
提出一种基于精简可达树的方法，用于分析一般非有界Petri网的有界性、活性、死锁和可逆性，并给出首个统一算法，案例验证有效。
At present, no efficient method is proposed for the liveness analysis of general unbounded Petri nets (UPNs) except some of their subclasses. Our previous work presents a non-Karp-Miller finite reachability tree, i.e., lean reachability tree (LRT) to represent their markings. It faithfully expresses and folds the reachability set of an unbounded net. It can totally avoid the efforts made by the existing modified Karp-Miller trees on the expression of potentially unbounded nodes and elimination of all fake markings. By exploiting it, this paper presents a method for comprehensively analyzing the properties of general UPNs. Particularly, we reveal the repeatability of deadlock with the unfolding of some unbounded leaves in LRT and present a sufficient and necessary condition of deadlock existence. Then, LRT and some partial trees generated from it, instead of entire reachability graphs, are utilized to analyze the liveness and reversibility of general UPNs rather than some special ones. The related theoretical results are proven. A unified algorithm based on LRT for analysis of boundedness, liveness, deadlock, and reversibility of general UPNs is developed for the first time. The results of a case study show that the presented method is effective for general UPNs.