Petri網(wǎng)可達(dá)性分析的代數(shù)方法.pdf

1、可達(dá)性是Petri網(wǎng)最基本最重要的一種動(dòng)態(tài)性質(zhì)，其判定問題是Petri網(wǎng)理論研究的重要課題。本文借助代數(shù)方法對(duì)可達(dá)性進(jìn)行分析，研究?jī)?nèi)容包括以下方面：
　　（1）提出標(biāo)識(shí)的不可達(dá)見證向量的概念，并給出兩類不可達(dá)見證向量的求取方法。
　　第一類見證向量來自于網(wǎng)的S-不變量。為求取此類見證向量，文中將給出幾種求取S-不變量的新算法。其中，STRK算法能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)求得部分極小支集上的極小S-不變量；SRK算法對(duì)任意網(wǎng)都能求

2、出至少一個(gè)立于極小支集上的極小S-不變量（只要該網(wǎng)存在S-不變量），而且，SRK算法平均情況下具有多項(xiàng)式時(shí)間復(fù)雜度；此外， ERK算法能求出全部極小支集上的極小S-不變量，EERK算法能求出全部極小S-不變量。
　　第二類見證向量來自于網(wǎng)的加模S-不變量。文中首先給出初等整數(shù)變換的概念，之后借助初等整數(shù)變換對(duì)整數(shù)矩陣進(jìn)行分解，并在此基礎(chǔ)上給出從加模S-不變量中求取不可達(dá)見證向量的方法。
　?。?）給出狀態(tài)方程實(shí)數(shù)解、有理數(shù)解

3、、整數(shù)解及非負(fù)整數(shù)解存在性的判定方法，分析狀態(tài)方程各類解的存在性與S-不變量、加模S-不變量以及死鎖和陷阱在不可達(dá)判定中的關(guān)系，對(duì)不可達(dá)標(biāo)識(shí)進(jìn)行分類。此外，給出一個(gè)求取狀態(tài)方程非負(fù)整數(shù)解的新算法。
　　（3）提出極小陷阱回路網(wǎng)、變遷單輸入回路網(wǎng)、極小變遷單輸入陷阱回路網(wǎng)以及極小死鎖回路網(wǎng)、變遷單輸出回路網(wǎng)和極小變遷單輸出死鎖回路網(wǎng)的概念。對(duì)于初始標(biāo)識(shí)下不含空極小回路的陷阱回路網(wǎng)、極小陷阱回路網(wǎng)、變遷單輸入回路網(wǎng)和極小變遷單輸入陷阱