Segment theory to compute elementary siphons in Petri nets for deadlock control

Abstract

Unlike other techniques, Li and Zhou add control nodes and arcs for only elementary siphons greatly reducing the number of control nodes and arcs (implemented by costly hardware of I/O devices and memory) required for deadlock control in Petri net supervisors. Li and Zhou propose that the number of elementary siphons is linear to the size of the net. An elementary siphon can be synthesized from a resource circuit consisting of a set of connected segments. We show that the total number of elementary siphons, |ПE|, is upper bounded by the total number of resource places |PR | lower than that min(|P|, |T|) by Li and Zhou where |P| (|T|) is the number of places (transitions) in the net. Also, we claim that the number of elementary siphons |ПE| equals that of independent segments (simple paths) in the resource subnet of an S3PR (systems of simple sequential processes with resources). Resource circuits for the elementary siphons can be traced out based on a graph-traversal algorithm. During the traversal process, we can also identify independent segments (i.e. their characteristic T-vectors are independent) along with those segments for elementary siphons. This offers us an alternative and yet deeper understanding of the computation of elementary siphons. Also, it allows us to adapt the algorithm to compute elementary siphons in [2] for a subclass of S3PR (called S4PR) to more complicated S3PR that contains weakly dependent siphons.

不同於其他方法 ， 李和周所提的僅為基本虹吸加入加控制節點與弧線之技術 ， 明顯地減少了派翠網路所需的監控節點和弧線。 李和周提出的虹吸技術 ， 其基本虹吸的數量與網路結構的大小呈線性關係成長。 基本虹吸可由基本資源迴圈合成 ， 迴圈又以小區塊分段方式組成。 本文提出虹吸結構總數|ПE|的上界為|PR|(資源位置數) ， 其低於最小的(|P|, |T|) ， 其中|P|和|T|各是李和周所提出網路中的操作位置(place)和轉移(transitions) 的數量。 此外 ， 我們聲稱基本虹吸的數量|ПE|等於資源子網路獨立段的數量。 基本虹吸結構在簡單的循序過程資源系統(S3PR)網路中 ， 可視為獨立區段。 一個圖的遍歷算法(graph-traversal)的基礎上 ， 可以追溯到對應於一個網路中基本虹吸的資源迴圈。 在遍歷過程中 ， 我們也可以找出獨立的區段（即 ， 其特徵T-向量都是獨立的）和對應於基本虹吸的區段。 這提供了一個替代方案深入地瞭解基本虹吸結構。 此外 ， 也能夠運用這個演算法來為S3PR的子類別(所謂S4PR) ， 與包含弱依賴虹吸更複雜的S3PR計算基本虹吸結構。