Petri網(wǎng)基本性質(zhì)的研究.pdf

1、Petri網(wǎng)適合于描述異步并發(fā)行為的系統(tǒng)。首先，Petri網(wǎng)直接展現(xiàn)并發(fā)系統(tǒng)的物理結(jié)構(gòu)層次及資源狀態(tài)的初始分布狀況。其次，在Petri網(wǎng)引發(fā)規(guī)則的作用下將間接展現(xiàn)出該并發(fā)系統(tǒng)的動(dòng)態(tài)行為機(jī)理。這兩個(gè)層面相互關(guān)聯(lián)，形成了一個(gè)集物理結(jié)構(gòu)和行為機(jī)理于一體的集成模型。它提供的的系統(tǒng)信息更加的豐富，其分析在理論上也更為深刻。Petri網(wǎng)的主要行為特性包括：狀態(tài)的可達(dá)(reachability)、位置的有界性(boundedness)、變遷的活性(1

2、iveness)、狀態(tài)的可逆達(dá)(reversibility)、標(biāo)識(shí)之間的可達(dá)(reachability)、變遷之間的堅(jiān)挺(persistence)、事件之間的同步距離(synchronic distance)和公平性(fairness)等。Pctri網(wǎng)模型的主要分析方法依賴于：可達(dá)標(biāo)識(shí)圖、關(guān)聯(lián)矩陣和狀態(tài)方程、不變量(invariants)和分析化簡規(guī)則。 Petri網(wǎng)以研究模型系統(tǒng)的組織結(jié)構(gòu)和動(dòng)態(tài)行為為目標(biāo)，著眼于系統(tǒng)中可能發(fā)生

3、的各種狀態(tài)變化以及變化之間的關(guān)系，易于表示系統(tǒng)變化發(fā)生的條件及變化發(fā)生后的系統(tǒng)狀態(tài)。Petri網(wǎng)應(yīng)用的主要困難是模型狀態(tài)空間的復(fù)雜性問題，它將隨實(shí)際系統(tǒng)的規(guī)模增大而呈指數(shù)性增長。因此，對(duì)于一般的Petri網(wǎng)，只要一涉及網(wǎng)的性質(zhì)，常常得到的算法都是NP難的(又稱作狀態(tài)空間爆炸)。對(duì)于這些NP問題，目前國內(nèi)、國外的理論研究基本停留在一般子類上的研究。盡管得到了許多好的結(jié)果，但是由于子類的特殊性，使得所得結(jié)果缺乏很好的應(yīng)用性。本人的工作是基于

4、一般網(wǎng)的一些性質(zhì)的研究。 本人的研究主要是從網(wǎng)的基本性質(zhì)出發(fā)。利用結(jié)構(gòu)性分析理論和不變技術(shù)，對(duì)Petri網(wǎng)的主要行為特征進(jìn)行了較為深入細(xì)致的研究，得到了一些新的結(jié)果。主要貢獻(xiàn)包括： (1)沖突是Petri網(wǎng)系統(tǒng)的基本現(xiàn)象，沖突使得庫所中的托肯分配具有不確定性，產(chǎn)生的結(jié)果更加具有多樣性。本文討論的范圍是變遷與庫所數(shù)量有限的C/E系統(tǒng)，根據(jù)C/E對(duì)沖突的定義，找到能產(chǎn)生沖突的靜態(tài)沖突向量結(jié)合相應(yīng)的情態(tài)(case)來確定在什么

5、情態(tài)下哪些變遷產(chǎn)生了沖突。最后給出尋找沖突的算法。 (2)相對(duì)與C/E系統(tǒng)中的沖突而言，P/T系統(tǒng)由于庫所的容量和流上的權(quán)值都大于等于1，因此沖突更加的復(fù)雜。本文討論的范圍是變遷與庫所數(shù)量有限的P/T系統(tǒng)，并給出了沖突和不完全沖突發(fā)生的條件。確定了沖突和不完全沖突發(fā)生時(shí)，庫所所必須的取值范圍，并給出算法。 (3)公平性(fairness)是Petri網(wǎng)的基本性質(zhì)。在本文中利用網(wǎng)的關(guān)聯(lián)矩陣求解出一般網(wǎng)中的基本可重復(fù)向量組，