派翠網路系統( Petri Net Systems)是於1962 年由德國數學家Carl Adam Petri所提出的一個數學模式,透過圖形來描述行為的相依程度,以及檢驗系統是否有循序發生或是衝突。透過派翠網路的各種行為特性( Behavior Properties),可以對系統做有效的分析,確保系統可以持續進行( Liveness ),或是驗證狀態是否可以到達( Reachability )。因為派翠網路可以描述各式各樣的問題,因此已經被廣泛的應用在各個領域。 然而,派翠網路在描述行為時,往往會遭遇到狀態爆炸的問題( State Explosion ),過多的狀態使得派翠網路變得難以分析。於是,如何有效解決狀態爆炸( State Explosion )變成使用派翠網路時最重要的課題。在本論文中,我們提出一個利用配對理論( Matching Theory )的方式來簡化派翠網路,對於每個transition設定不同的權重值( Weight Value ),並且依照每個transition的權重值( Weight Value )來對整個派翠網路做壓縮,不僅可以使得壓縮過後的派翠網路保有最重要的transition,同時也能解決狀態爆炸所產生的問題。
In this thesis, we present an efficient method to solve the state explosion problem in Petri nets by using matching theory. It is really hard to analyze a Petri net while there are too many states in a Petri net. In order to solve such a problem, we address a way to label the weight value on a transition according the relationship between places and transitions. Then we select the transition which is related to the maximum one after sorting weights. The transition we select is the most important and connective one for the whole Petri nets at the moment. After selecting the transition for several times, the last one denotes the least connection in the whole Petri nets, and we could reduce the Petri net model from this transition. Finally, main results are presented and supported by some experiments.