無沖突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 網結構活性的判斷等同于對其中是否存在源庫所元素的判斷?；赑etri 網的關聯矩陣［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 網系統的活性判定方法。