有界Petri網(wǎng)的合法引發(fā)序列判定算法.pdf

1、合法引發(fā)序列是Petri網(wǎng)可達性問題的一部分,它是Petri網(wǎng)研究領(lǐng)域的一個重要研究課題,該文針對Petri網(wǎng)的一個子類——有界Petri網(wǎng)給出了一個判定合法引發(fā)序列算法.該文給出的算法是在變遷序列分解的基礎(chǔ)上實現(xiàn)的.我們討論了變遷序列分解的依據(jù)、分解方法在合法引發(fā)序列判定中的應用以及分解的逆過程——變遷子序列合成合法引發(fā)序列的運算等.這些,是該文提出的判定算法的Petri網(wǎng)方面的理論依據(jù).在變遷序列分解的指導思想下,我們的算法主要通過

2、以下兩步工作完成:(1)首先對給出的已知條件中滿足狀態(tài)方程的n維非負整數(shù)向量進行處理,得到一組X的基礎(chǔ)向量X<,b>,使得在Petri網(wǎng)的可達標識圖中,若存在一條由M<,0>到M<,d>的有向無環(huán)路,則X<,b>為這樣的路上變遷引發(fā)序列的發(fā)生數(shù)向量.同時,我們記錄下所有X<,b>的非零分量和的最大值作為控制第二步工作的終止.這一部分是以網(wǎng)的極小T-不變量為工具完成的.(2)經(jīng)過第一步的工作,我們得到與判定X的合法引發(fā)序列問題等價而問題規(guī)

3、?？s減了簡化問題--判定X的基礎(chǔ)向量X<,b>的合法引發(fā)序列.故我們解決后一問題.而由X<,b>的定義可知,它只能對應一條有向無環(huán)路上的變遷引發(fā)序列,所以,算法中在構(gòu)建Σ<,1>=(S,T;F,M<,0>)的部分可達樹RT(Σ<,1>)和Σ<,2>=(S,T;F,M<,d>)的部分逆向可達樹RT<'-1>(Σ<,2>)的同時尋找這樣的有向無環(huán)路.若能夠找到,則說明有某個X<,b>對應一條使M<,d>由M<,0>可達的有向無環(huán)路上的變遷引