無界Petri網(wǎng)可達(dá)樹的研究.pdf

1、眾所周知，Petri網(wǎng)以其圖形化的表現(xiàn)形式、眾多的分析方法和堅實的數(shù)學(xué)基礎(chǔ)，成為研究離散事件系統(tǒng)的建模工具之一。盡管眾多學(xué)者對Petri網(wǎng)進(jìn)行研究并取得了很多成果，但仍然存在著一個世界性難題——可達(dá)性問題。系統(tǒng)的可達(dá)性是其所有性質(zhì)中最基本的。因為在很大程度上，我們都可以用可達(dá)性來分析其他的一些相關(guān)性質(zhì)，比如有界性、可覆蓋性、可逆性、活性、死鎖等。
　　Petri網(wǎng)的可達(dá)樹可以表示標(biāo)識和變遷的實施關(guān)系，是分析Petri網(wǎng)的一種重要方

2、法，且適用于各種網(wǎng)系統(tǒng)。利用有限的可達(dá)樹來分析研究無界Petri網(wǎng)的可達(dá)性問題，一直是Petri網(wǎng)這一領(lǐng)域的研究難題。近幾十年來，經(jīng)過許多研究者的努力，取得了一些成果及突破，但始終存在不足，如現(xiàn)在已有的有限可達(dá)樹不能非常完整準(zhǔn)確表示系統(tǒng)信息等。本文圍繞Petri網(wǎng)可達(dá)性展開研究，具體工作及研究成果如下:
　　1.提出一種適用于一類一般無界Petri網(wǎng)子網(wǎng)——ω獨立網(wǎng)的可達(dá)樹的構(gòu)建算法，即ωRT。與已存在的方法相比，ωRT僅包含由初

3、始標(biāo)識可以到達(dá)的標(biāo)識，有效的避免了虛假標(biāo)識的出現(xiàn)，保證了可達(dá)樹表示信息的準(zhǔn)確性以及完整性。相較于MRT，ωRT還可以大幅度的減少可達(dá)樹節(jié)點數(shù)量，簡化了可達(dá)樹的結(jié)構(gòu)。在此基礎(chǔ)上，提出驗證相關(guān)性質(zhì)與定理，并利用所提出的定理解決ω獨立網(wǎng)的一些可達(dá)性問題，如死鎖、有限性等。
　　2.提出適用于所有無界Petri網(wǎng)的新可達(dá)樹的構(gòu)建算法，即AωRT。AωRT將其適用范圍擴(kuò)大至所有無界網(wǎng)，是本文一個重要創(chuàng)新點。并且在此基礎(chǔ)上提出了AωRT的死鎖