無沖突Petri網(wǎng)的結(jié)構(gòu)活性判定研究

徐穎蕾，馬炳先

（1.山東財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南250014；2.山東省數(shù)字媒體技術(shù)重點(diǎn)實(shí)驗(yàn)室，濟(jì)南250014；3.濟(jì)南大學(xué)信息科學(xué)與工程學(xué)院，濟(jì)南250022）

0 概述

活性作為Petri 網(wǎng)系統(tǒng)重要的動(dòng)態(tài)性質(zhì)之一，反映了Petri 網(wǎng)系統(tǒng)運(yùn)行過程中變遷激發(fā)條件的可滿足性，通常對應(yīng)實(shí)際系統(tǒng)運(yùn)行過程中某事件是否具備發(fā)生條件。如果一個(gè)變遷元素不是活性的，那么該事件在某時(shí)刻將不會(huì)繼續(xù)發(fā)生，若在某標(biāo)識(shí)下系統(tǒng)中的所有變遷元素均不能發(fā)生，則系統(tǒng)陷入死鎖，因此，有效檢測與判斷系統(tǒng)的活性是Petri 網(wǎng)相關(guān)理論與方法應(yīng)用于實(shí)際系統(tǒng)的關(guān)鍵問題，如自動(dòng)制造系統(tǒng)的死鎖分析［1-2］、面向資源調(diào)度系統(tǒng)的死鎖分析［3］及并發(fā)程序的死鎖檢測和驗(yàn)證［4-6］等。

目前，對于Petri 網(wǎng)系統(tǒng)活性的判定尚未有通用的方法［7］，主要包括以下4 類判定方法。第1 類為從Petri 網(wǎng)的網(wǎng)結(jié)構(gòu)入手，研究結(jié)構(gòu)較特殊的一些Petri網(wǎng)的活性判定方法，例如標(biāo)識(shí)T-圖［8］、加權(quán)T-圖［9］、標(biāo)識(shí)S-圖［10］和標(biāo)識(shí)自由選擇網(wǎng)［11］等結(jié)構(gòu)的Petri 網(wǎng)已有較系統(tǒng)和有效的判定方法或者結(jié)論。第2 類為從Petri 網(wǎng)的分析方法入手，利用Petri 網(wǎng)的可達(dá)標(biāo)識(shí)圖或可覆蓋樹［12］、Petri 網(wǎng)進(jìn)程［13］等判斷Petri 網(wǎng)的活性，該類方法對Petri 網(wǎng)系統(tǒng)的活性分析提供了一定的思路，但由于系統(tǒng)狀態(tài)的快速增長［14］或者線性方程組的求解通常伴有較高的時(shí)間復(fù)雜度，目前仍需更為深入的研究。第3 類為從Petri 網(wǎng)結(jié)構(gòu)的分解或合成的角度入手，研究子網(wǎng)系統(tǒng)的活性與原網(wǎng)系統(tǒng)活性之間的關(guān)系［15-16］，進(jìn)而研究Petri 網(wǎng)系統(tǒng)的活性，該類方法同樣取得了一定的研究成果，但對于一般Petri 網(wǎng)系統(tǒng)而言也尚未有明確結(jié)論。第4 類為從Petri 網(wǎng)系統(tǒng)性質(zhì)［17-18］或結(jié)構(gòu)活性判定入手，尤其后者，首先通過判斷Petri網(wǎng)的結(jié)構(gòu)活性，其次研究結(jié)構(gòu)活的Petri 網(wǎng)的活標(biāo)識(shí)應(yīng)滿足的條件，最后實(shí)現(xiàn)對Petri 網(wǎng)的活性判定，目前該類方法同樣需要進(jìn)一步深入的研究。

沖突結(jié)構(gòu)在Petri 網(wǎng)的活性判定方法研究中具有重要作用［19］，相關(guān)文獻(xiàn)在對標(biāo)識(shí)T-圖［8-9］、可重復(fù)Petri 網(wǎng)［12］的活性（或結(jié)構(gòu)活性）研究時(shí)基于有向回路結(jié)構(gòu)或者沖突結(jié)構(gòu)對庫所元素［20］中流出標(biāo)識(shí)（token）能否流回該庫所的影響情況進(jìn)行分析研究，進(jìn)而對Petri 網(wǎng)系統(tǒng)的活性或結(jié)構(gòu)活性進(jìn)行判定，表明Petri 網(wǎng)中的有向回路及沖突結(jié)構(gòu)是影響Petri 網(wǎng)活性性質(zhì)的重要因素，但現(xiàn)有相關(guān)方法尚未從綜合考慮Petri 網(wǎng)中有向回路與沖突結(jié)構(gòu)間的關(guān)系對系統(tǒng)活性的影響入手開展Petri 網(wǎng)活性判定的研究［21-22］?；诖耍疚目紤]從Petri網(wǎng)的結(jié)構(gòu)入手，分析Petri網(wǎng)中的有向回路與沖突結(jié)構(gòu)對Petri 網(wǎng)結(jié)構(gòu)活性的影響，進(jìn)而探討Petri 網(wǎng)結(jié)構(gòu)活性和系統(tǒng)活性的判定方法。

1 相關(guān)概念及知識(shí)

本節(jié)將簡要介紹與本文研究相關(guān)的Petri 網(wǎng)相關(guān)概念和知識(shí)。

定義1［12］一個(gè)Petri 網(wǎng)系統(tǒng)定義為∑=(S,T；F,M)，其中：

1）S∪T≠?；

2）S∩T=?；

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

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

在定義1 中，S為Petri 網(wǎng)的庫所元素集合，T為Petri 網(wǎng)的變遷元素集合，F(xiàn)為庫所和變遷元素之間存在的流關(guān)系，M為Petri 網(wǎng)系統(tǒng)∑的標(biāo)識(shí)函數(shù)。

Petri 網(wǎng)系統(tǒng)的變遷元素在變遷激發(fā)規(guī)則條件滿足的前提下可以發(fā)生，從而使得Petri 網(wǎng)系統(tǒng)在不同的標(biāo)識(shí)之間轉(zhuǎn)化，即Petri 網(wǎng)系統(tǒng)的運(yùn)行。

定義2［12］（沖突結(jié)構(gòu)）設(shè)Petri 網(wǎng)系統(tǒng)為∑=(S,T；F,M)，若?s∈S，|s˙|≥2，則稱庫所s及其后置變遷元素集合之間形成沖突結(jié)構(gòu)。

由定義2 可以看出，沖突結(jié)構(gòu)實(shí)際上對應(yīng)庫所標(biāo)識(shí)在Petri 網(wǎng)系統(tǒng)運(yùn)行過程中的一種選擇或競爭，并且現(xiàn)有研究已表明沖突結(jié)構(gòu)是影響Petri 網(wǎng)活性分析的關(guān)鍵因素之一［10］。

定義3［12］（活性）設(shè)Petri 網(wǎng)系統(tǒng)為∑=(S,T；F,M0)，其中，M0為初始標(biāo)識(shí)，t∈T。若?M∈R(M0)，?M′∈R(M)，使得M′[t＞，則稱t是活的。若每個(gè)t∈T都是活的，則稱Σ是活的Petri 網(wǎng)系統(tǒng)。

定義4［12］（結(jié)構(gòu)活性）設(shè)N=(S,T；F)為一個(gè)Petri 網(wǎng)結(jié)構(gòu)，如果存在初始標(biāo)識(shí)M0使得∑=(S,T；F,M0)是活的Petri 網(wǎng)系統(tǒng)，則稱N是結(jié)構(gòu)活網(wǎng)，M0是網(wǎng)N的一個(gè)活標(biāo)識(shí)。

由定義3 和定義4 可以看出，一個(gè)Petri 網(wǎng)若是結(jié)構(gòu)活的，則必存在一個(gè)標(biāo)識(shí)使得對應(yīng)的Petri 網(wǎng)系統(tǒng)是活的，即為該網(wǎng)的一個(gè)活標(biāo)識(shí)。因此，在判斷一個(gè)Petri 網(wǎng)系統(tǒng)∑=(S,T；F,M0)的活性時(shí)可以從判定網(wǎng)的結(jié)構(gòu)活性入手，即判斷該P(yáng)etri 網(wǎng)系統(tǒng)對應(yīng)的網(wǎng)結(jié)構(gòu)是否為結(jié)構(gòu)活的：1）若該網(wǎng)是結(jié)構(gòu)活的，進(jìn)一步分析其活標(biāo)識(shí)對應(yīng)的性質(zhì)或者特征，并在此基礎(chǔ)上進(jìn)一步分析Petri 網(wǎng)系統(tǒng)的活性；2）若該網(wǎng)不是結(jié)構(gòu)活的，則該P(yáng)etri 網(wǎng)系統(tǒng)不是活的網(wǎng)系統(tǒng)。

2 無沖突Petri網(wǎng)的結(jié)構(gòu)活性判定方法

定義5（無沖突Petri 網(wǎng)）設(shè)N=(S,T；F)為一個(gè)網(wǎng)結(jié)構(gòu)，若?s∈S，|s˙|≤1，則稱N是無沖突Petri 網(wǎng)。

與S-圖［12］（?t∈T：|t˙|=|˙t|=1）和T-圖［12］（?s∈S：|s˙|=|˙s|=1）結(jié)構(gòu)要求不同，與定義2 中的沖突結(jié)構(gòu)相對應(yīng)，無沖突Petri 網(wǎng)僅對庫所元素的后置變遷元素個(gè)數(shù)進(jìn)行約束?？梢钥闯觯跓o沖突Petri 網(wǎng)N=(S,T；F)中，若?s∈S?|s˙|=0，則在Petri 網(wǎng)N中刪除該庫所元素s及其對應(yīng)的流關(guān)系后得到的Petri 網(wǎng)結(jié)構(gòu)活性與原網(wǎng)保持一致?；诖耍s定在本文討論的無沖突Petri 網(wǎng)中，?t∈T?|˙t|≥1，即在Petri 網(wǎng)N中不含源變遷元素，且?s∈S?|s˙|=1。

定義6（T-外延子網(wǎng)）設(shè)Petri 網(wǎng)N=(S,T；F)，T1?T，N1=(S1,T1,F1)是關(guān)于T1的T-外延子網(wǎng)［12］，其中，。

本文基于庫所元素與其后置變遷元素是否存在于一個(gè)有向回路中，對無沖突Petri 網(wǎng)N=(S,T；F)結(jié)構(gòu)活性進(jìn)行判定。下文考慮無沖突Petri 網(wǎng)中一個(gè)有向回路的標(biāo)識(shí)保持情況。

引理1設(shè)Petri 網(wǎng)N=(S,T；F)是無沖突Petri網(wǎng)，C為網(wǎng)N中的一個(gè)有向回路，若網(wǎng)N的一個(gè)標(biāo)識(shí)M0：M0(C)≥1，則?M1∈R(M0)，M1(C)≥1，其中M(C)=。

證明不妨設(shè)?t1∈T：M0[t1＞M1，則：

1）若t1∈C，則在有向回路C中必含有t1的前置及后置庫所元素各1 個(gè)，從而t1的發(fā)生不會(huì)影響C中的標(biāo)識(shí)數(shù)量，即M1(C)≥1。

2）若t1?C，則由于網(wǎng)N中無沖突結(jié)構(gòu)，因此有向回路C中不含有t1的前置庫所元素，即t1的發(fā)生不會(huì)減少C中的標(biāo)識(shí)數(shù)量，即M1(C)≥1。

進(jìn)一步地，若M1是由M0經(jīng)過多個(gè)變遷的發(fā)生達(dá)到的標(biāo)識(shí)，則由上所述可得M1(C)≥1，引理1得證。

定理1設(shè)Petri 網(wǎng)N=(S,T；F)是無沖突Petri網(wǎng)，若?s∈S?t∈s˙，s與t存在于一個(gè)有向回路結(jié)構(gòu)中，則網(wǎng)N是結(jié)構(gòu)活的。

證明為網(wǎng)N配置初始標(biāo)識(shí)M0使得網(wǎng)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，不妨設(shè)˙t={s1,s2}，且si與t存在于一個(gè)有向回路Ci(i=1,2)中，則由引理1可得?M∈R(M0)，M(Ci)≥1(i=1,2)，由于網(wǎng)N中無沖突結(jié)構(gòu)，因此?M1∈R(M)?M1(s1)≥1，同時(shí)M1(C2)≥1，此時(shí)若已有M1(s2)≥1，則M1[t＞；否則，對有向回路C2，存在一不包含變遷t的變遷序列σ1∈T* 使得M1[σ1＞M2且M2(s2)≥1，由于t?σ1，因此此時(shí)M2(s1)≥1，即M2[t＞。

綜上所述，?M∈R(M0)和?M′∈R(M)使得M′[t＞，即M0是網(wǎng)N的一個(gè)活標(biāo)識(shí)，因此網(wǎng)N是結(jié)構(gòu)活的。

推論1設(shè)Petri 網(wǎng)N=(S,T；F)是無沖突Petri網(wǎng)，?t∈T，若?s∈˙t，s與t存在于一個(gè)有向回路結(jié)構(gòu)中，則網(wǎng)N是結(jié)構(gòu)活的。

為表述方便，將定理1 中“?s∈S?t∈s˙，s與t存在于一個(gè)有向回路結(jié)構(gòu)中”稱為自回路條件。

定義7（自回路條件）設(shè)Petri 網(wǎng)N=(S,T；F)，s∈S滿足自回路條件當(dāng)且僅當(dāng)?t∈s˙，s與t存在于一個(gè)有向回路結(jié)構(gòu)中。

然而，自回路條件僅是無沖突Petri 網(wǎng)結(jié)構(gòu)活的充分而非必要條件，例如對圖1 中的網(wǎng)N1雖然庫所s3不滿足自回路條件，但滿足前置回路條件，并且網(wǎng)N1是結(jié)構(gòu)活的。

圖1 活性結(jié)構(gòu)的Petri 網(wǎng)N1Fig.1 Petri net N1 with live structure

定義8（前置回路條件）設(shè)Petri 網(wǎng)N=(S,T；F)是無沖突Petri 網(wǎng)，庫所元素s∈S且s˙={t1}，s滿足前置回路條件當(dāng)且僅當(dāng)存在網(wǎng)N的T-外延子網(wǎng)N1=(S1,T1；F1)使得：

1）?s1∈S1，s1在N1中滿足自回路條件。

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

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

定理2設(shè)Petri 網(wǎng)N=(S,T；F)是無沖突Petri網(wǎng)，則網(wǎng)N是結(jié)構(gòu)活的當(dāng)且僅當(dāng)?s∈S滿足自回路條件或前置回路條件。

必要性證明設(shè)已知無沖突Petri 網(wǎng)N是結(jié)構(gòu)活的，M0是網(wǎng)N的一個(gè)活標(biāo)識(shí)。若?s1∈S，則s1不滿足自回路條件及前置回路條件，不妨設(shè)M0(s1)=k(k≥1)，顯然若?，則對于變遷序列σ∈T*滿足M0[σ＞M1?#(t1/σ)=k，由于s1不滿足自回路條件及前置回路條件，此時(shí)M1(s1)=0 且不存在M2∈R(M1)使得M2(s1)＞0，t1成為死變遷，這與M0是網(wǎng)N的活標(biāo)識(shí)相矛盾，因此?s∈S，s滿足自回路條件或前置回路條件，定理2 的必要性得證。

充分性證明已知?s∈S滿足自回路條件或前置回路條件，設(shè)網(wǎng)N的標(biāo)識(shí)M0使得網(wǎng)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 中的情況，不妨設(shè)˙t={s1,s2}，s1滿足自回路條件，s2滿足前置回路條件：

1）s1滿足自回路條件，由引理1 可得，?M2∈R(M1)使得M2(s1)≥1，且對網(wǎng)N中任一有向回路C滿足M2(C)≥1。

2）s2滿足前置回路條件，設(shè)其對應(yīng)的T-外延子網(wǎng)為N1=(S1,T1；F1)，?s∈S1在網(wǎng)N1中滿足自回路條件，且?t1∈T1到s2存在有向路P，由于M2使得網(wǎng)N的任一有向回路C滿足M2(C)≥1，因此?t?σ1，M2[σ1＞M3使得M3[t1＞，進(jìn)一步由于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)時(shí)情形3 的分析證明過程類似，并且證明在情形1 和情形2 下，?M′∈R(M1)?M′[t＞也是成立的。

綜上可得，標(biāo)識(shí)M0是網(wǎng)N的一個(gè)活標(biāo)識(shí)，即網(wǎng)N是結(jié)構(gòu)活的，定理2 的充分性得證。進(jìn)一步研究發(fā)現(xiàn)在無沖突Petri 網(wǎng)中，若存在無源庫所（即庫所元素?zé)o前置變遷），則必滿足定理2 中的條件。

性質(zhì)1設(shè)無沖突Petri 網(wǎng)N=(S,T；F) 中?s∈S?|˙s|≥1，則?s∈S滿足自回路條件或前置回路條件。

證明若，則滿足以下情形：

1）若s1和t1存在于網(wǎng)N中的一個(gè)有向回路中，則s1滿足自回路條件，否則轉(zhuǎn)情形2。

2）若s1和t1不存在于網(wǎng)N中的任一有向回路中，記Ts1={t∈T|s1到t存在有向路}。因?yàn)閨˙s1|≥1，所以?t2∈T-Ts1為s1的前置變遷，又因?yàn)?t∈T?|˙t|≥1，所以?s2∈˙t2，依此類推，可逐步構(gòu)造變遷庫所序列t2s2…tisi…，其中。由于|S|和|T|的有限性，上述序列中必存在tj=tk∈T-Ts1，即tj存在于一個(gè)有向回路中，記為Cj，令Tj={t∈T|t∈Cj}，基于Tj得到網(wǎng)N的T-外延子網(wǎng)Nj=(Sj,Tj；Fj)，其中，。此時(shí)，若?s∈Sj在Nj中滿足自回路條件，則易得s1滿足前置回路條件；否則，若?sk∈Sj在Nj中不滿足自回路條件但在網(wǎng)N中滿足自回路條件，其對應(yīng)的回路為Ck，記Tk={t∈T|t∈Ck}，以Tj∪Tk為基礎(chǔ)進(jìn)一步構(gòu)造得到N的T-外延子網(wǎng)Njk=(Sjk,Tjk；Fjk)，對Nj中所有在Nj中不滿足自回路條件但在網(wǎng)N中滿足自回路條件的庫所元素進(jìn)行同樣的操作，最終可得到N的T-外延子網(wǎng)，此時(shí)若，s在中滿足自回路條件，易得s1滿足前置回路條件；否則，?在網(wǎng)與網(wǎng)N中均不滿足自回路條件，此時(shí)對sr進(jìn)行與s1相同的操作可得到與sr相應(yīng)的網(wǎng)N的T-外延子網(wǎng)Nr=(Sr,Tr；Fr)，對Nr進(jìn)行與Nj相同的處理并持續(xù)進(jìn)行下去。顯然，在此過程中各T-外延子網(wǎng)的變遷候選集合規(guī)模逐步縮小，由于|T|的有限性，因此上述過程不可能無限進(jìn)行下去，必存在網(wǎng)N的T-外延子網(wǎng)Ne=(Se,Te；Fe)，且?s∈Se滿足自回路條件，從而說明s1滿足前置回路條件。

綜合以上兩種情形所述，性質(zhì)1 得證。

定理3若無沖突Petri 網(wǎng)N=(S,T；F) 中?s∈S?|˙s|≥1，則網(wǎng)N是結(jié)構(gòu)活的。

顯然，若在無沖突Petri 網(wǎng)N=(S,T；F) 中?s∈S?|˙s|=0，即存在源庫所元素時(shí)網(wǎng)N不是結(jié)構(gòu)活的，由定理3 可知，對無沖突Petri 網(wǎng)結(jié)構(gòu)活性的判斷等同于對其中是否存在源庫所元素的判斷。基于Petri 網(wǎng)的關(guān)聯(lián)矩陣［12］，只需檢測網(wǎng)N的關(guān)聯(lián)矩陣中是否有某一列元素取值中無“1”存在，就可以在多項(xiàng)式時(shí)間O(|S|·|T|)內(nèi)完成對無沖突Petri網(wǎng)的結(jié)構(gòu)活性判定，即實(shí)現(xiàn)無沖突Petri 網(wǎng)結(jié)構(gòu)活性的多項(xiàng)式時(shí)間判定方法。

推論2設(shè)無沖突Petri 網(wǎng)N=(S,T；F)是結(jié)構(gòu)活的，若網(wǎng)N的標(biāo)識(shí)M0使網(wǎng)N中的任一有向回路C滿足M0(c)≥1，則M0是網(wǎng)N的一個(gè)活標(biāo)識(shí)。

但推論2 中無沖突Petri 網(wǎng)的活標(biāo)識(shí)條件僅為Petri 網(wǎng)活標(biāo)識(shí)的一個(gè)充分條件，例如對圖1 中的網(wǎng)N1，M0=(1,0,0,1,0)是網(wǎng)N1的一個(gè)活標(biāo)識(shí)，且?M1≥M0也是網(wǎng)N1的一個(gè)活標(biāo)識(shí)，但M2=(1,0,0,0,0)盡管不滿足推論2 中的條件，卻也是網(wǎng)N1的一個(gè)活標(biāo)識(shí)。

3 結(jié)束語

本文針對無沖突Petri 網(wǎng)結(jié)構(gòu)活性的判定問題，從Petri 網(wǎng)中有向回路結(jié)構(gòu)入手，通過分析庫所元素及其后置變遷元素之間是否存在有向回路等結(jié)構(gòu)逐步分析與無沖突Petri 網(wǎng)結(jié)構(gòu)活性相關(guān)的條件及結(jié)論，得到無沖突Petri 網(wǎng)結(jié)構(gòu)活性的充分必要條件，并且可在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)判定無沖突Petri網(wǎng)的結(jié)構(gòu)活性。該結(jié)論能為通過分析Petri 網(wǎng)中有向回路結(jié)構(gòu)對Petri 網(wǎng)結(jié)構(gòu)活性的影響進(jìn)而判斷Petri網(wǎng)的結(jié)構(gòu)活性的方法提供較好的參考和借鑒。后續(xù)可將本文方法擴(kuò)展到具有沖突結(jié)構(gòu)的Petri網(wǎng)的結(jié)構(gòu)活性判斷問題中，在此基礎(chǔ)上進(jìn)一步研究Petri 網(wǎng)系統(tǒng)的活性判定方法。