徐關(guān)懷　王明新

摘 要：Petri網(wǎng)進(jìn)程是Petri網(wǎng)分析和驗(yàn)證的有效手段，而Petri網(wǎng)的進(jìn)程表達(dá)式可以給出系統(tǒng)全部進(jìn)程的描述。針對(duì)文獻(xiàn)《一種基于同步合成構(gòu)造Petri網(wǎng)進(jìn)程表達(dá)式的方法》提出的基于同步合成的Petri網(wǎng)表達(dá)式構(gòu)成方法中的一個(gè)引理進(jìn)行深入研究，并通過一個(gè)反例，說明這種方法的錯(cuò)誤之處。

關(guān)鍵詞：Petri網(wǎng)；同步合成；基本進(jìn)程段；進(jìn)程表達(dá)式

中圖分類號(hào)：TN301 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1672-1098（2014）03-0057-03

Petri網(wǎng)是一種描述與分析異步并發(fā)系統(tǒng)的數(shù)學(xué)模型[1-3]，特別便于描述并發(fā)與沖突，是研究并發(fā)系統(tǒng)的一個(gè)合適而有效的工具[4-5]。Petri網(wǎng)進(jìn)程則是對(duì)系統(tǒng)行為描述和分析的最有力的工具[6]390，因?yàn)檫M(jìn)程將狀態(tài)和變遷并重， 把系統(tǒng)中發(fā)生的變化和引起的狀態(tài)改變?nèi)鐚?shí)記錄下來， 它可以很清楚地反映出網(wǎng)系統(tǒng)運(yùn)行中的變遷之間的順序、并發(fā)、同步等現(xiàn)象[7]。Petri網(wǎng)的進(jìn)程表達(dá)式可以給出系統(tǒng)全部進(jìn)程的描述， 因此對(duì)其進(jìn)行深入研究具有極其重要的意義。目前，國內(nèi)外學(xué)者對(duì)于Petri網(wǎng)的進(jìn)程表達(dá)式的研究比較廣泛[8]340。其中，文獻(xiàn)[6]387 考察結(jié)構(gòu)簡單的Petri網(wǎng)的進(jìn)程行為， 給出各種類型的Petri網(wǎng)的進(jìn)程表達(dá)式的描述方法， 然后拓展了Petri 網(wǎng)同步合成的概念， 分析了同步合成過程中基本進(jìn)程段集之間的關(guān)系， 并利用同步混排給出了進(jìn)程表達(dá)式之間的關(guān)系。本文主要針對(duì)文獻(xiàn)[6]385中的一個(gè)引理進(jìn)行進(jìn)一步的探討，以期為基于同步合成的Petri 網(wǎng)進(jìn)程表達(dá)式的更為完善的構(gòu)成方法奠定基礎(chǔ)。

1 引理證明中的錯(cuò)誤

關(guān)于基本進(jìn)程段的定義及相關(guān)概念參考文獻(xiàn)[6]385，下面是文獻(xiàn)[6]385中的兩個(gè)值得商討的結(jié)論。 假設(shè)有兩個(gè)活的S-網(wǎng)Σ1和Σ2，它們的基本進(jìn)程段集分別為P1={P11，P12，…，P1m}（m>0）和P2={P21，P22，…，P2n}（n>0），其中P1i（1≤i≤m），P2j（1≤j≤n）都是可重復(fù)的進(jìn)程段且滿足：若P1i 與P2j有共同的變遷，則這些共同的變遷在P1i中的順序與在P2j中的順序是相同的。這樣由引理4所求得的同步合成網(wǎng)Σ的所有基本進(jìn)程段也都是可重復(fù)的進(jìn)程段，這表明合成網(wǎng)Σ是活的Petri網(wǎng)，它的所有變遷都是活的。

但是兩個(gè)活的S-網(wǎng)同步合成之后，所得到的同步合成網(wǎng)并不一定就是活的，即由引理4所得到的合成網(wǎng)的基本進(jìn)程段集合是錯(cuò)誤。同理，定理4也是錯(cuò)誤的。

下面給出了一個(gè)反例并進(jìn)行了討論，這個(gè)反例來自于文獻(xiàn)[6]385。

2 反例與討論

圖1a給出了一個(gè)Petri網(wǎng)模型Σ，由文獻(xiàn)[6]390中給出的方法求取Σ對(duì)應(yīng)的Petri網(wǎng)模型的進(jìn)程表達(dá)式，先將Σ分解成Σ1和Σ2，分別如圖1的b和c所示，得到的Σ1和Σ2是S-網(wǎng)并且Σ=Σ1ΞΣ2。其中Σ1的基本進(jìn)程段為P1、P2，Σ2的基本進(jìn)程段為P3、P4，分別如圖2的a和b所示。然后根據(jù)引理4，對(duì)Σ1的基本進(jìn)程段P1、P2與Σ2的基本進(jìn)程段P3、P4進(jìn)行同步合成則得到Σ的兩個(gè)基本進(jìn)程段P5和P6，如圖3所示。顯然，根據(jù)引理4求出的Σ的基本進(jìn)程段集并不能完全表示原網(wǎng)Σ的所有進(jìn)程。在子網(wǎng)模型Σ1和Σ2中，所有的變遷都是活的。Σ1的每個(gè)進(jìn)程都是集合Pref{Exp（P1+P2）*}的一個(gè)元素，Σ2的每個(gè)進(jìn)程都是集合Pref{Exp（P3+P4）*}的一個(gè)元素，所以Σ1和Σ2的基本進(jìn)程段集合都是正確的。但是在原網(wǎng)模型中，Σ并不是一個(gè)活的Petri網(wǎng)。當(dāng)變遷t11與t21都發(fā)生后，就沒有變遷再能發(fā)生，基本進(jìn)程段P5和P6無法表示這種情況，變遷t11與t21發(fā)生所對(duì)應(yīng)的進(jìn)程段并不是集合Pref{Exp（P5+P6）*}中的元素。所以根據(jù)引理4將兩個(gè)S-網(wǎng)（同步合成可以得到原網(wǎng)）的基本進(jìn)程段集進(jìn)行同步合成求得原網(wǎng)的進(jìn)程段集并不能完全描述原網(wǎng)的所有進(jìn)程，即求得的并不是基本進(jìn)程段集，所以引理4和定理4都是不正確的。

在文獻(xiàn)[8]342中有一個(gè)類似于引理4的結(jié)論，而文獻(xiàn)[6]382中敘述的是基本進(jìn)程，并不是文獻(xiàn)[6]385-390中定義的基本進(jìn)程段，這是兩個(gè)不同的概念，引理4直接引用文獻(xiàn)[6]385中的結(jié)論，這是文獻(xiàn)[6]385-390中出現(xiàn)這個(gè)錯(cuò)誤的根源。從而，文獻(xiàn)[6]385-390中基于定理4的其他結(jié)論也是靠不住的。

3 結(jié)論

本文分析和研究了Petri網(wǎng)的進(jìn)程表達(dá)式的作用，深入研究了基于同步合成的Petri網(wǎng)進(jìn)程表達(dá)式構(gòu)成方法中的一個(gè)引理的證明方法，并通過反例說明該構(gòu)成方法的錯(cuò)誤之處。 本文工作本著尊重科學(xué)，堅(jiān)持實(shí)事求是的原則，指出該方法的錯(cuò)誤之處，為進(jìn)一步提出基于同步合成的Petri 網(wǎng)進(jìn)程表達(dá)式的構(gòu)成方法奠定基礎(chǔ)。

參考文獻(xiàn)：

[1] MURATA T.Petri nets： properties， analysis， and applications[J]. Proceedings of the IEEE， 1989， 77（4）：541-580.

[2] 吳哲輝. Petri網(wǎng)導(dǎo)論[M]. 北京： 機(jī)械工業(yè)出版社，2006：10-150.

[3] 閆春鋼， 汪明新，劉關(guān)俊.有界Petri 網(wǎng)進(jìn)程表達(dá)式與活性的關(guān)系[J].應(yīng)用科學(xué)學(xué)報(bào)，2012，30（4）：387-390.

[4] 吳哲輝. 有界Petri網(wǎng)的進(jìn)程表達(dá)式[J]. 中國科學(xué)（A輯），1995，25（12）：1 332-1 340.

[5] 蔣昌俊.同步合成網(wǎng)的進(jìn)程特性研究[J].電子學(xué)報(bào)，1997，25（2）： 57-60.

[6] 曾慶田.一種基于同步合成構(gòu)造Petri網(wǎng)進(jìn)程表達(dá)式的方法[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（3）： 381-390.

[7] 袁崇義. Petri 網(wǎng)原理與應(yīng)用[M]. 北京： 電子工業(yè)出版社， 2005：8-250.

[8] 吳哲輝. 無界公平Petri網(wǎng)的進(jìn)程表達(dá)式[J].計(jì)算機(jī)學(xué)報(bào)， 2000，23（4）： 337-344.

（責(zé)任編輯：李 麗 范 君）