无冲突Petri网的结构活性判定研究

徐颖蕾，马炳先

（1.山东财经大学计算机科学与技术学院，济南250014；2.山东省数字媒体技术重点实验室，济南250014；3.济南大学信息科学与工程学院，济南250022）

0 概述

活性作为Petri 网系统重要的动态性质之一，反映了Petri 网系统运行过程中变迁激发条件的可满足性，通常对应实际系统运行过程中某事件是否具备发生条件。如果一个变迁元素不是活性的，那么该事件在某时刻将不会继续发生，若在某标识下系统中的所有变迁元素均不能发生，则系统陷入死锁，因此，有效检测与判断系统的活性是Petri 网相关理论与方法应用于实际系统的关键问题，如自动制造系统的死锁分析［1-2］、面向资源调度系统的死锁分析［3］及并发程序的死锁检测和验证［4-6］等。

目前，对于Petri 网系统活性的判定尚未有通用的方法［7］，主要包括以下4 类判定方法。第1 类为从Petri 网的网结构入手，研究结构较特殊的一些Petri网的活性判定方法，例如标识T-图［8］、加权T-图［9］、标识S-图［10］和标识自由选择网［11］等结构的Petri 网已有较系统和有效的判定方法或者结论。第2 类为从Petri 网的分析方法入手，利用Petri 网的可达标识图或可覆盖树［12］、Petri 网进程［13］等判断Petri 网的活性，该类方法对Petri 网系统的活性分析提供了一定的思路，但由于系统状态的快速增长［14］或者线性方程组的求解通常伴有较高的时间复杂度，目前仍需更为深入的研究。第3 类为从Petri 网结构的分解或合成的角度入手，研究子网系统的活性与原网系统活性之间的关系［15-16］，进而研究Petri 网系统的活性，该类方法同样取得了一定的研究成果，但对于一般Petri 网系统而言也尚未有明确结论。……