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

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

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

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