无冲突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 网系统而言也尚未有明确结论。第4 类为从Petri 网系统性质［17-18］或结构活性判定入手，尤其后者，首先通过判断Petri网的结构活性，其次研究结构活的Petri 网的活标识应满足的条件，最后实现对Petri 网的活性判定，目前该类方法同样需要进一步深入的研究。

冲突结构在Petri 网的活性判定方法研究中具有重要作用［19］，相关文献在对标识T-图［8-9］、可重复Petri 网［12］的活性（或结构活性）研究时基于有向回路结构或者冲突结构对库所元素［20］中流出标识（token）能否流回该库所的影响情况进行分析研究，进而对Petri 网系统的活性或结构活性进行判定，表明Petri 网中的有向回路及冲突结构是影响Petri 网活性性质的重要因素，但现有相关方法尚未从综合考虑Petri 网中有向回路与冲突结构间的关系对系统活性的影响入手开展Petri 网活性判定的研究［21-22］。基于此，本文考虑从Petri网的结构入手，分析Petri网中的有向回路与冲突结构对Petri 网结构活性的影响，进而探讨Petri 网结构活性和系统活性的判定方法。

1 相关概念及知识

本节将简要介绍与本文研究相关的Petri 网相关概念和知识。

定义1［12］一个Petri 网系统定义为∑=(S,T；F,M)，其中：

1）S∪T≠∅；

2）S∩T=∅；

3）F⊆(S×T)∪(T×S)；

4）M：S→{0,1,…}。

在定义1 中，S为Petri 网的库所元素集合，T为Petri 网的变迁元素集合，F为库所和变迁元素之间存在的流关系，M为Petri 网系统∑的标识函数。

Petri 网系统的变迁元素在变迁激发规则条件满足的前提下可以发生，从而使得Petri 网系统在不同的标识之间转化，即Petri 网系统的运行。

定义2［12］（冲突结构）设Petri 网系统为∑=(S,T；F,M)，若∃s∈S，|s˙|≥2，则称库所s及其后置变迁元素集合之间形成冲突结构。

由定义2 可以看出，冲突结构实际上对应库所标识在Petri 网系统运行过程中的一种选择或竞争，并且现有研究已表明冲突结构是影响Petri 网活性分析的关键因素之一［10］。

定义3［12］（活性）设Petri 网系统为∑=(S,T；F,M0)，其中，M0为初始标识，t∈T。若∀M∈R(M0)，∃M′∈R(M)，使得M′[t＞，则称t是活的。若每个t∈T都是活的，则称Σ是活的Petri 网系统。

定义4［12］（结构活性）设N=(S,T；F)为一个Petri 网结构，如果存在初始标识M0使得∑=(S,T；F,M0)是活的Petri 网系统，则称N是结构活网，M0是网N的一个活标识。

由定义3 和定义4 可以看出，一个Petri 网若是结构活的，则必存在一个标识使得对应的Petri 网系统是活的，即为该网的一个活标识。因此，在判断一个Petri 网系统∑=(S,T；F,M0)的活性时可以从判定网的结构活性入手，即判断该Petri 网系统对应的网结构是否为结构活的：1）若该网是结构活的，进一步分析其活标识对应的性质或者特征，并在此基础上进一步分析Petri 网系统的活性；2）若该网不是结构活的，则该Petri 网系统不是活的网系统。

2 无冲突Petri网的结构活性判定方法

定义5（无冲突Petri 网）设N=(S,T；F)为一个网结构，若∀s∈S，|s˙|≤1，则称N是无冲突Petri 网。

与S-图［12］（∀t∈T：|t˙|=|˙t|=1）和T-图［12］（∀s∈S：|s˙|=|˙s|=1）结构要求不同，与定义2 中的冲突结构相对应，无冲突Petri 网仅对库所元素的后置变迁元素个数进行约束。可以看出，在无冲突Petri 网N=(S,T；F)中，若∃s∈S˄|s˙|=0，则在Petri 网N中删除该库所元素s及其对应的流关系后得到的Petri 网结构活性与原网保持一致。基于此，约定在本文讨论的无冲突Petri 网中，∀t∈T˄|˙t|≥1，即在Petri 网N中不含源变迁元素，且∀s∈S˄|s˙|=1。

定义6（T-外延子网）设Petri 网N=(S,T；F)，T1⊆T，N1=(S1,T1,F1)是关于T1的T-外延子网［12］，其中，。

本文基于库所元素与其后置变迁元素是否存在于一个有向回路中，对无冲突Petri 网N=(S,T；F)结构活性进行判定。下文考虑无冲突Petri 网中一个有向回路的标识保持情况。

引理1设Petri 网N=(S,T；F)是无冲突Petri网，C为网N中的一个有向回路，若网N的一个标识M0：M0(C)≥1，则∀M1∈R(M0)，M1(C)≥1，其中M(C)=。

证明不妨设∃t1∈T：M0[t1＞M1，则：

1）若t1∈C，则在有向回路C中必含有t1的前置及后置库所元素各1 个，从而t1的发生不会影响C中的标识数量，即M1(C)≥1。

2）若t1∉C，则由于网N中无冲突结构，因此有向回路C中不含有t1的前置库所元素，即t1的发生不会减少C中的标识数量，即M1(C)≥1。

进一步地，若M1是由M0经过多个变迁的发生达到的标识，则由上所述可得M1(C)≥1，引理1得证。

定理1设Petri 网N=(S,T；F)是无冲突Petri网，若∀s∈S˄t∈s˙，s与t存在于一个有向回路结构中，则网N是结构活的。

证明为网N配置初始标识M0使得网N中任一有向回路C均有M0(C)≥1，∀t∈T：

1）若˙t={s1}且s1与t存在于一有向回路C1中，则由引理1 可得∀M∈R(M0)，M(C1)≥1，从而必有∃M1∈R(M)，使得M1[t＞。

2）若|˙t|≥2，不妨设˙t={s1,s2}，且si与t存在于一个有向回路Ci(i=1,2)中，则由引理1可得∀M∈R(M0)，M(Ci)≥1(i=1,2)，由于网N中无冲突结构，因此∃M1∈R(M)˄M1(s1)≥1，同时M1(C2)≥1，此时若已有M1(s2)≥1，则M1[t＞；否则，对有向回路C2，存在一不包含变迁t的变迁序列σ1∈T* 使得M1[σ1＞M2且M2(s2)≥1，由于t∉σ1，因此此时M2(s1)≥1，即M2[t＞。

综上所述，∀M∈R(M0)和∃M′∈R(M)使得M′[t＞，即M0是网N的一个活标识，因此网N是结构活的。

推论1设Petri 网N=(S,T；F)是无冲突Petri网，∀t∈T，若∀s∈˙t，s与t存在于一个有向回路结构中，则网N是结构活的。

为表述方便，将定理1 中“∀s∈S˄t∈s˙，s与t存在于一个有向回路结构中”称为自回路条件。

定义7（自回路条件）设Petri 网N=(S,T；F)，s∈S满足自回路条件当且仅当∀t∈s˙，s与t存在于一个有向回路结构中。

然而，自回路条件仅是无冲突Petri 网结构活的充分而非必要条件，例如对图1 中的网N1虽然库所s3不满足自回路条件，但满足前置回路条件，并且网N1是结构活的。

图1 活性结构的Petri 网N1Fig.1 Petri net N1 with live structure

定义8（前置回路条件）设Petri 网N=(S,T；F)是无冲突Petri 网，库所元素s∈S且s˙={t1}，s满足前置回路条件当且仅当存在网N的T-外延子网N1=(S1,T1；F1)使得：

1）∀s1∈S1，s1在N1中满足自回路条件。

2）∃t2∈T1，t2到s存在有向路P。

3）t1不属于T1及情形2 中的有向路P。

定理2设Petri 网N=(S,T；F)是无冲突Petri网，则网N是结构活的当且仅当∀s∈S满足自回路条件或前置回路条件。

必要性证明设已知无冲突Petri 网N是结构活的，M0是网N的一个活标识。若∃s1∈S，则s1不满足自回路条件及前置回路条件，不妨设M0(s1)=k(k≥1)，显然若∃，则对于变迁序列σ∈T*满足M0[σ＞M1˄#(t1/σ)=k，由于s1不满足自回路条件及前置回路条件，此时M1(s1)=0 且不存在M2∈R(M1)使得M2(s1)＞0，t1成为死变迁，这与M0是网N的活标识相矛盾，因此∀s∈S，s满足自回路条件或前置回路条件，定理2 的必要性得证。

充分性证明已知∀s∈S满足自回路条件或前置回路条件，设网N的标识M0使得网N中任一有向回路C满足M0(C)≥1，∀t∈T，t的前置库所满足自回路条件或前置回路条件的情形具体如下：

1）∀s∈˙t，s满足自回路条件。

2）∀s∈˙t，s满足前置回路条件。

3）∃s1,s2∈˙t，s1≠s2，s1满足自回路条件，s2满足前置回路条件。

对于∀M1∈R(M0)，讨论情形3 中的情况，不妨设˙t={s1,s2}，s1满足自回路条件，s2满足前置回路条件：

1）s1满足自回路条件，由引理1 可得，∃M2∈R(M1)使得M2(s1)≥1，且对网N中任一有向回路C满足M2(C)≥1。

2）s2满足前置回路条件，设其对应的T-外延子网为N1=(S1,T1；F1)，∀s∈S1在网N1中满足自回路条件，且∃t1∈T1到s2存在有向路P，由于M2使得网N的任一有向回路C满足M2(C)≥1，因此˄t∉σ1，M2[σ1＞M3使得M3[t1＞，进一步由于t1到s2存在有向路P且t∉P，因此∃σ2∈(T-{t})*使得M3[σ2＞M4，且M4(s2)≥1，即∃σ=σ1σ2使得M2[σ＞M4，又由于t∉σ，因此M4(s1)=M2(s1)，M4(s1)≥1 可得M4[t＞，即∃M4∈R(M1)，M4[t＞。

基于引理1，与∀M1∈R(M0)时情形3 的分析证明过程类似，并且证明在情形1 和情形2 下，∃M′∈R(M1)˄M′[t＞也是成立的。

综上可得，标识M0是网N的一个活标识，即网N是结构活的，定理2 的充分性得证。进一步研究发现在无冲突Petri 网中，若存在无源库所（即库所元素无前置变迁），则必满足定理2 中的条件。

性质1设无冲突Petri 网N=(S,T；F) 中∀s∈S˄|˙s|≥1，则∀s∈S满足自回路条件或前置回路条件。

证明若，则满足以下情形：

1）若s1和t1存在于网N中的一个有向回路中，则s1满足自回路条件，否则转情形2。

2）若s1和t1不存在于网N中的任一有向回路中，记Ts1={t∈T|s1到t存在有向路}。因为|˙s1|≥1，所以∃t2∈T-Ts1为s1的前置变迁，又因为∀t∈T˄|˙t|≥1，所以∃s2∈˙t2，依此类推，可逐步构造变迁库所序列t2s2…tisi…，其中。由于|S|和|T|的有限性，上述序列中必存在tj=tk∈T-Ts1，即tj存在于一个有向回路中，记为Cj，令Tj={t∈T|t∈Cj}，基于Tj得到网N的T-外延子网Nj=(Sj,Tj；Fj)，其中，。此时，若∀s∈Sj在Nj中满足自回路条件，则易得s1满足前置回路条件；否则，若∃sk∈Sj在Nj中不满足自回路条件但在网N中满足自回路条件，其对应的回路为Ck，记Tk={t∈T|t∈Ck}，以Tj∪Tk为基础进一步构造得到N的T-外延子网Njk=(Sjk,Tjk；Fjk)，对Nj中所有在Nj中不满足自回路条件但在网N中满足自回路条件的库所元素进行同样的操作，最终可得到N的T-外延子网，此时若，s在中满足自回路条件，易得s1满足前置回路条件；否则，∃在网与网N中均不满足自回路条件，此时对sr进行与s1相同的操作可得到与sr相应的网N的T-外延子网Nr=(Sr,Tr；Fr)，对Nr进行与Nj相同的处理并持续进行下去。显然，在此过程中各T-外延子网的变迁候选集合规模逐步缩小，由于|T|的有限性，因此上述过程不可能无限进行下去，必存在网N的T-外延子网Ne=(Se,Te；Fe)，且∀s∈Se满足自回路条件，从而说明s1满足前置回路条件。

综合以上两种情形所述，性质1 得证。

定理3若无冲突Petri 网N=(S,T；F) 中∀s∈S˄|˙s|≥1，则网N是结构活的。

显然，若在无冲突Petri 网N=(S,T；F) 中∃s∈S˄|˙s|=0，即存在源库所元素时网N不是结构活的，由定理3 可知，对无冲突Petri 网结构活性的判断等同于对其中是否存在源库所元素的判断。基于Petri 网的关联矩阵［12］，只需检测网N的关联矩阵中是否有某一列元素取值中无“1”存在，就可以在多项式时间O(|S|·|T|)内完成对无冲突Petri网的结构活性判定，即实现无冲突Petri 网结构活性的多项式时间判定方法。

推论2设无冲突Petri 网N=(S,T；F)是结构活的，若网N的标识M0使网N中的任一有向回路C满足M0(c)≥1，则M0是网N的一个活标识。

但推论2 中无冲突Petri 网的活标识条件仅为Petri 网活标识的一个充分条件，例如对图1 中的网N1，M0=(1,0,0,1,0)是网N1的一个活标识，且∀M1≥M0也是网N1的一个活标识，但M2=(1,0,0,0,0)尽管不满足推论2 中的条件，却也是网N1的一个活标识。

3 结束语

本文针对无冲突Petri 网结构活性的判定问题，从Petri 网中有向回路结构入手，通过分析库所元素及其后置变迁元素之间是否存在有向回路等结构逐步分析与无冲突Petri 网结构活性相关的条件及结论，得到无冲突Petri 网结构活性的充分必要条件，并且可在多项式时间复杂度内判定无冲突Petri网的结构活性。该结论能为通过分析Petri 网中有向回路结构对Petri 网结构活性的影响进而判断Petri网的结构活性的方法提供较好的参考和借鉴。后续可将本文方法扩展到具有冲突结构的Petri网的结构活性判断问题中，在此基础上进一步研究Petri 网系统的活性判定方法。