开放科学(资源服务)标志码(OSID)：

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网系统定义为$\sum = (S, T;F, M) $，其中：

1) $ S\bigcup T\ne \mathrm{\varnothing } $；

2) $ S\bigcap T=\mathrm{\varnothing } $；

3) $ F\subseteq (S\times T)\bigcup (T\times S) $；

4) $ M:S\to \{\mathrm{0, 1}, \cdots \} $。

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

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

定义2^[12] (冲突结构)  设Petri网系统为$\sum = (S, T;F, M) $，若$ \exists s\in S $，$ \left|{s}^{•}\right|\ge 2 $，则称库所$ s $及其后置变迁元素集合之间形成冲突结构。

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

定义3^[12](活性)  设Petri网系统为$\sum = (S, T;F, {M}_{0}) $，其中，$ {M}_{0} $为初始标识，$ t\in T $。若$ \forall M\in R\left({M}_{0}\right) $，$ \exists {M}^{\text{'}}\in R\left(M\right) $，使得$ {M}^{\text{'}}[t> $，则称$ t $是活的。若每个$ t\in T $都是活的，则称$ \Sigma $是活的Petri网系统。

定义4^[12](结构活性)  设$ N=(S, T;F) $为一个Petri网结构，如果存在初始标识$ {M}_{0} $使得$\sum = (S, T;F, {M}_{0}) $是活的Petri网系统，则称$ N $是结构活网，$ {M}_{0} $是网$ N $的一个活标识。

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

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

定义5(无冲突Petri网)  设$ N=(S, T;F) $为一个网结构，若$ \forall s\in S $，$ \left|{s}^{•}\right|\le 1 $，则称$ N $是无冲突Petri网。

与S-图^[12]($ \forall t\in T:\left|{t}^{•}\right|={|}^{•}t|=1 $)和T-图^[12]($ \forall s\in S:\left|{s}^{•}\right|={|}^{•}s|=1 $)结构要求不同，与定义2中的冲突结构相对应，无冲突Petri网仅对库所元素的后置变迁元素个数进行约束。可以看出，在无冲突Petri网$ N=(S, T;F) $中，若$ \exists s\in S\wedge \left|{s}^{•}\right|=0 $，则在Petri网N中删除该库所元素$ s $及其对应的流关系后得到的Petri网结构活性与原网保持一致。基于此，约定在本文讨论的无冲突Petri网中，$ \forall t\in T\wedge {|}^{•}t|\ge 1 $，即在Petri网N中不含源变迁元素，且$ \forall s\in S\wedge \left|{s}^{•}\right|=1 $。

定义6(T-外延子网)  设Petri网$ N=(S, T;F) $，$ {T}_{1}\subseteq T $，$ {N}_{1}=({S}_{1}, {T}_{1}, {F}_{1}) $是关于$ {T}_{1} $的T-外延子网^[12]，其中，$ {S}_{1}={}^{•}T{T}_{1}\bigcup {T}_{1}^{•} $，$ {F}_{1}=\left(\right({S}_{1}\times {T}_{1})\bigcup ({T}_{1}\times {S}_{1}\left)\right)\bigcap F $。

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

引理1  设Petri网$ N=(S, T;F) $是无冲突Petri网，C为网N中的一个有向回路，若网N的一个标识$ {M}_{0}:{M}_{0}\left(C\right)\mathrm{ }\ge \mathrm{ }1 $，则$ \forall {M}_{1}\in R\left({M}_{0}\right) $，$ {M}_{1}\left(C\right)\mathrm{ }\ge \mathrm{ }1 $，其中$ M\left(C\right)\mathrm{ }= $ $ \sum _{s\in C}M\left(s\right) $。

证明  不妨设$ \exists {t}_{1}\in T $：$ {M}_{0}[{t}_{1}>{M}_{1} $，则：

1) 若$ {t}_{1}\in C $，则在有向回路C中必含有$ {t}_{1} $的前置及后置库所元素各1个，从而$ {t}_{1} $的发生不会影响C中的标识数量，即$ {M}_{1}\left(C\right)\ge 1 $。

2) 若$ {t}_{1}\notin C $，则由于网N中无冲突结构，因此有向回路C中不含有$ {t}_{1} $的前置库所元素，即$ {t}_{1} $的发生不会减少C中的标识数量，即$ {M}_{1}\left(C\right)\ge 1 $。

进一步地，若$ {M}_{1} $是由$ {M}_{0} $经过多个变迁的发生达到的标识，则由上所述可得$ {M}_{1}\left(C\right)\ge 1 $，引理1得证。

定理1  设Petri网$ N=(S, T;F) $是无冲突Petri网，若$ \forall s\in S\wedge t\in {s}^{•} $，$ s $与$ t $存在于一个有向回路结构中，则网N是结构活的。

证明  为网$ N $配置初始标识$ {M}_{0} $使得网N中任一有向回路C均有$ {M}_{0}\left(C\right)\ge 1 $，$ \forall t\in T $：

1) 若$ {}^{•}t=\left\{{s}_{1}\right\} $且$ {s}_{1} $与$ t $存在于一有向回路$ {C}_{1} $中，则由引理1可得$ \forall M\in R\left({M}_{0}\right) $，$ M\left({C}_{1}\right)\ge 1 $，从而必有$ \exists {M}_{1}\in R\left(M\right) $，使得$ {M}_{1}[t> $。

2) 若$ \left|{}^{•}t\right|\ge 2 $，不妨设$ {}^{•}t=\{{s}_{1}, {s}_{2}\} $，且$ {s}_{i} $与$ t $存在于一个有向回路$ {C}_{i}(i=\mathrm{1, 2}) $中，则由引理1可得$ \forall M\in $ $ R\left({M}_{0}\right) $，$ M\left({C}_{i}\right)\ge 1(i=\mathrm{1, 2}) $，由于网$ N $中无冲突结构，因此$ \exists {M}_{1}\in R\left(M\right)\wedge {M}_{1}\left({s}_{1}\right)\ge 1 $，同时$ {M}_{1}\left({C}_{2}\right)\ge 1 $，此时若已有$ {M}_{1}\left({s}_{2}\right)\ge 1 $，则$ {M}_{1}[t> $；否则，对有向回路$ {C}_{2} $，存在一不包含变迁$ t $的变迁序列$ {\sigma }_{1}\in T\mathrm{*} $使得$ {M}_{1}[{\sigma }_{1}>{M}_{2} $且$ {M}_{2}\left({s}_{2}\right)\ge 1 $，由于$ t\notin {\sigma }_{1} $，因此此时$ {M}_{2}\left({s}_{1}\right)\ge 1 $，即$ {M}_{2}[t> $。

综上所述，$ \forall M\in R\left({M}_{0}\right) $和$ \exists {M}^{\text{'}}\in R\left(M\right) $使得$ {M}^{\text{'}}[t> $，即$ {M}_{0} $是网$ N $的一个活标识，因此网N是结构活的。

推论1  设Petri网$ N=(S, T;F) $是无冲突Petri网，$ \forall t\in T $，若$ \forall s\in {}^{•}t $，$ s $与$ t $存在于一个有向回路结构中，则网N是结构活的。

为表述方便，将定理1中"$ \forall s\in S\wedge t\in {s}^{•} $，$ s $与$ t $存在于一个有向回路结构中"称为自回路条件。

定义7 (自回路条件)  设Petri网$ N=(S, T;F) $，$ s\in S $满足自回路条件当且仅当$ \forall t\in {s}^{•} $，$ s $与$ t $存在于一个有向回路结构中。

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

定义8 (前置回路条件)  设Petri网$ N=(S, $ $ T;F) $是无冲突Petri网，库所元素$ s\in S $且$ {s}^{•}=\left\{{t}_{1}\right\} $，$ s $满足前置回路条件当且仅当存在网$ N $的T-外延子网$ {N}_{1}=({S}_{1}, {T}_{1};{F}_{1}) $使得：

1) $ \forall {s}_{1}\in {S}_{1} $，$ {s}_{1} $在N₁中满足自回路条件。

2) $ \exists {t}_{2}\in {T}_{1} $，$ {t}_{2} $到$ s $存在有向路P。

3) $ {t}_{1} $不属于$ {T}_{1} $及情形2中的有向路P。

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

必要性证明  设已知无冲突Petri网N是结构活的，$ {M}_{0} $是网N的一个活标识。若$ \exists {s}_{1}\in S $，则$ {s}_{1} $不满足自回路条件及前置回路条件，不妨设$ {M}_{0}\left({s}_{1}\right)=k(k\ge 1) $，显然若$ \exists {t}_{1}\in {s}_{1}^{•} $，则对于变迁序列$ \sigma \in {T}^{\mathrm{*}} $满足$ {M}_{0}[\sigma >{M}_{1}\wedge \#({t}_{1}/\sigma )=k $，由于$ {s}_{1} $不满足自回路条件及前置回路条件，此时$ {M}_{1}\left({s}_{1}\right)=0 $且不存在$ {M}_{2}\in R\left({M}_{1}\right) $使得$ {M}_{2}\left({s}_{1}\right)>0 $，$ {t}_{1} $成为死变迁，这与$ {M}_{0} $是网N的活标识相矛盾，因此$ \forall s\in S $，$ s $满足自回路条件或前置回路条件，定理2的必要性得证。

充分性证明  已知$ \forall s\in S $满足自回路条件或前置回路条件，设网N的标识$ {M}_{0} $使得网N中任一有向回路C满足$ {M}_{0}\left(C\right)\ge 1 $，$ \forall t\in T $，$ t $的前置库所满足自回路条件或前置回路条件的情形具体如下：

1) $ \forall s\in {}^{•}t $，$ s $满足自回路条件。

2) $ \forall s\in {}^{•}t $，$ s $满足前置回路条件。

3) $ \exists {s}_{1}, {s}_{2}\in {}^{•}t $，$ {s}_{1}\ne {s}_{2} $，$ {s}_{1} $满足自回路条件，$ {s}_{2} $满足前置回路条件。

对于$ \forall {M}_{1}\in R\left({M}_{0}\right) $，讨论情形3中的情况，不妨设$ {}^{•}t=\{{s}_{1}, s{}_{2}\} $，$ {s}_{1} $满足自回路条件，$ {s}_{2} $满足前置回路条件：

1) $ {s}_{1} $满足自回路条件，由引理1可得，$ \exists {M}_{2}\in R\left({M}_{1}\right) $使得$ {M}_{2}\left({s}_{1}\right)\ge 1 $，且对网N中任一有向回路C满足$ {M}_{2}\left(C\right)\ge 1 $。

2) $ {s}_{2} $满足前置回路条件，设其对应的T-外延子网为$ {N}_{1}=({S}_{1}, {T}_{1};{F}_{1}) $，$ \forall s\in {S}_{1} $在网$ {N}_{1} $中满足自回路条件，且$ \exists {t}_{1}\in {T}_{1} $到$ {s}_{2} $存在有向路P，由于$ {M}_{2} $使得网N的任一有向回路C满足$ {M}_{2}\left(C\right)\ge 1 $，因此$ \exists {\sigma }_{1}\in {T}_{1}^{\mathrm{*}} $ $ \wedge t\notin {\sigma }_{1} $，$ {M}_{2}[{\sigma }_{1}>{M}_{3} $使得$ {M}_{3}[{t}_{1}> $，进一步由于$ {t}_{1} $到$ {s}_{2} $存在有向路P且$ t\notin P $，因此$ \exists {\sigma }_{2}\in (T-{\left\{t\right\})}^{\mathrm{*}} $使得$ {M}_{3}[{\sigma }_{2}>{M}_{4} $，且$ {M}_{4}\left({s}_{2}\right)\ge 1 $，即$ \exists \sigma ={\sigma }_{1}{\sigma }_{2} $使得$ {M}_{2}[\sigma > $ $ {M}_{4} $，又由于$ t\notin \sigma $，因此$ {M}_{4}\left({s}_{1}\right)={M}_{2}\left({s}_{1}\right) $，$ {M}_{4}\left({s}_{1}\right)\ge 1 $可得$ {M}_{4}[t> $，即$ \exists {M}_{4}\in R\left({M}_{1}\right) $，$ {M}_{4}[t> $。

基于引理1，与$ \forall {M}_{1}\in R\left({M}_{0}\right) $时情形3的分析证明过程类似，并且证明在情形1和情形2下，$ \exists {M}^{\text{'}}\in R\left({M}_{1}\right)\wedge {M}^{\text{'}}[t> $也是成立的。

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

性质1  设无冲突Petri网$ N=(S, T;F) $中$ \forall s\in S\wedge \left|{}^{•}s\right|\ge 1 $，则$ \forall s\in S $满足自回路条件或前置回路条件。

证明  若$ \forall {s}_{1}\in S $，$ {t}_{1}\in \left\{{s}_{1}^{•}\right\} $，则满足以下情形：

1) 若$ {s}_{1} $和$ {t}_{1} $存在于网$ N $中的一个有向回路中，则$ {s}_{1} $满足自回路条件，否则转情形2。

2) 若$ {s}_{1} $和$ {t}_{1} $不存在于网$ N $中的任一有向回路中，记$ {T}_{{s}_{1}}=\{t\in T|{s}_{1}\mathrm{到}\mathrm{t}\mathrm{存}\mathrm{在}\mathrm{有}\mathrm{向}\mathrm{路}\} $。因为$ \left|{}^{•}s{s}_{1}\right|\ge 1 $，所以$ \exists {t}_{2}\in T-{T}_{{s}_{1}} $为$ {s}_{1} $的前置变迁，又因为$ \forall t\in T\wedge \left|{}^{•}t\right|\ge 1 $，所以$ \exists {s}_{2}\in {}^{•}t{t}_{2} $，依此类推，可逐步构造变迁库所序列$ {t}_{2}{s}_{2}\cdots {t}_{i}{s}_{i}\cdots $，其中$ {s}_{i}\in {}^{•}t{t}_{i}\wedge {s}_{i}\in {t}_{i+1}^{•}(i\ge 2) $。由于$ \left|S\right|\mathrm{和}\left|T\right| $的有限性，上述序列中必存在$ {t}_{j}={t}_{k}\in T-{T}_{{s}_{1}} $，即$ {t}_{j} $存在于一个有向回路中，记为$ {C}_{j} $，令$ {T}_{j}=\{t\in T|t\in {C}_{j}\} $，基于$ {T}_{j} $得到网$ N $的T-外延子网$ {N}_{j}=({S}_{j}, {T}_{j};{F}_{j}) $，其中，$ {S}_{j}={}^{•}T{T}_{j}\bigcup {T}_{j}^{•} $，$ {F}_{j}=\left\{\right({S}_{j}\times {T}_{j})\bigcup ({T}_{j}\times {S}_{j}\left)\right\}\bigcap F $。此时，若$ \forall s\in {S}_{j} $在$ {N}_{j} $中满足自回路条件，则易得$ {s}_{1} $满足前置回路条件；否则，若$ \exists {s}_{k}\in {S}_{j} $在$ {N}_{j} $中不满足自回路条件但在网$ N $中满足自回路条件，其对应的回路为$ {C}_{k} $，记$ {T}_{k}=\{t\in T|t\in {C}_{k}\} $，以$ {T}_{j}\bigcup {T}_{k} $为基础进一步构造得到$ N $的T-外延子网$ {N}_{jk}=({S}_{jk}, {T}_{jk};{F}_{jk}) $，对$ {N}_{j} $中所有在$ {N}_{j} $中不满足自回路条件但在网$ N $中满足自回路条件的库所元素进行同样的操作，最终可得到$ N $的T-外延子网$ {N}_{j}^{\text{'}}=({S}_{j}^{\text{'}}, {T}_{j}^{\text{'}};{F}_{j}^{\text{'}}) $，此时若$ \forall s\in {S}_{j}^{\text{'}} $，$ s $在$ {N}_{j}^{\text{'}} $中满足自回路条件，易得$ {s}_{1} $满足前置回路条件；否则，$ \exists {s}_{r}\in {S}_{j}^{\text{'}} $在网$ {N}_{j}^{\text{'}} $与网$ N $中均不满足自回路条件，此时对$ {s}_{r} $进行与$ {s}_{1} $相同的操作可得到与$ {s}_{r} $相应的网$ N $的T-外延子网$ {N}_{r}=({S}_{r}, {T}_{r};{F}_{r}) $，对$ {N}_{r} $进行与$ {N}_{j} $相同的处理并持续进行下去。显然，在此过程中各T-外延子网的变迁候选集合规模逐步缩小，由于$ \left|T\right| $的有限性，因此上述过程不可能无限进行下去，必存在网$ N $的T-外延子网$ {N}_{e}=({S}_{e}, {T}_{e};{F}_{e}) $，且$ \forall s\in {S}_{e} $满足自回路条件，从而说明$ {s}_{1} $满足前置回路条件。

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

定理3  若无冲突Petri网$ N=(S, T;F) $中$ \forall s\in S\wedge \left|{}^{•}s\right|\ge 1 $，则网$ N $是结构活的。

显然，若在无冲突Petri网$ N=(S, T;F) $中$ \exists s\in S\wedge \left|{}^{•}s\right|=0 $，即存在源库所元素时网$ N $不是结构活的，由定理3可知，对无冲突Petri网结构活性的判断等同于对其中是否存在源库所元素的判断。基于Petri网的关联矩阵^[12]，只需检测网$ N $的关联矩阵中是否有某一列元素取值中无"1"存在，就可以在多项式时间$ O\left(\right|S|\cdot |T\left|\right) $内完成对无冲突Petri网的结构活性判定，即实现无冲突Petri网结构活性的多项式时间判定方法。

推论2  设无冲突Petri网$ N=(S, T;F) $是结构活的，若网N的标识$ {M}_{0} $使网N中的任一有向回路C满足$ {M}_{0}\left(c\right)\ge 1 $，则$ {M}_{0} $是网N的一个活标识。

但推论2中无冲突Petri网的活标识条件仅为Petri网活标识的一个充分条件，例如对图 1中的网$ {N}_{1} $，$ {M}_{0}=(\mathrm{1, 0}, \mathrm{0, 1}, 0) $是网$ {N}_{1} $的一个活标识，且$ \forall {M}_{1}\ge {M}_{0} $也是网$ {N}_{1} $的一个活标识，但$ {M}_{2}=(\mathrm{1, 0}, \mathrm{0, 0}, 0) $尽管不满足推论2中的条件，却也是网$ {N}_{1} $的一个活标识。

3 结束语

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