佩特里網

佩特里網（英語：Petri net），又譯為裴氏網、派翠網路，是對離散並行系統的數學表示。佩特里網屬於離散事件動態系統，是1960年代由卡爾·亞當·佩特里發明的^[1]，適合於描述異步的、並發的計算機系統模型。佩特里網既有嚴格的數學表述方式，也有直觀的圖形表達方式。

由於佩特里網能表達並發的事件，被認為是自動化理論的一種。研究領域趨向認為佩特里網是所有流程定義語言之母。

背景

卡爾·亞當·佩特里是一名物理學家，他發明佩特里網主要是從物理的角度去描述並發現象的。據佩特里本人所述，他認為60年代計算機科學的概念構架由於缺乏並發不適合於描述物理系統。其中一個重要的概念，就是佩特里網裡面不存在所謂的「全局時間」的概念，因為這跟狹義相對論是衝突的。相反，佩特里網可以描述每一個節點的時序。

從狹義相對論的觀點出發，兩個時空點之間如果沒有因果關係把它們連接起來（或者說「類空」的），它們就是獨立的，不能說其中一個發生在前另一個在後或者相反。因此，佩特里網裡面的兩種變遷（見下文）如果都有發生的條件，則不能認為其執行順序有任何關係。然而，佩特里網旨在描述變遷之間的因果關係，並由此構造時序。

經典佩特里網

經典的佩特里網是簡單的過程模型，由兩種節點：庫所和變遷，有向弧，以及令牌等元素組成的。

結構

佩特里網的元素：

庫所（Place）圓形節點
變遷（Transition）方形節點
有向弧（Arc）是庫所和變遷之間的有向弧
令牌（Token）是庫所中的動態對象，可以從一個庫所移動到另一個庫所。

佩特里網的規則是：

有向弧是有方向的
兩個庫所之間或兩個變遷之間不允許有弧
庫所可以擁有任意數量的令牌

行為

如果一個變遷的每個輸入庫所（input place）都擁有數量足夠的令牌時，該變遷即為被允許（enable）。一個變遷被允許時，變遷將發生（fire），輸入庫所（input place）的令牌被消耗，同時為輸出庫所（output place）產生令牌。

注意：

變遷的發生時是獨立且唯一的，也就是說，沒有一個變遷只發生了一半的可能性。
有兩個或多個變遷都被允許的可能，但是一次只能發生一個變遷。這種情況下變遷發生的順序沒有定義。
如果出現一個變遷，其輸入庫所的個數與輸出庫所的個數不相等，令牌的個數將發生變化，也就是說，令牌數目不守恆。
佩特里網絡是靜態的，也就是說，不存在發生了一個變遷之後忽然冒出另一個變遷或者庫所，從而改變Petri網結構的可能。
佩特里網的狀態由令牌在庫所的分布決定。也就是說，變遷發生完畢、下一個變遷等待發生的時候才有確定的狀態，正在發生變遷的時候是沒有一個確定的狀態的。

兩個變遷爭奪一個令牌的情形被稱之為衝突。當發生衝突的時候，由於佩特里網的時序是不確定的，因此具體哪個變遷得以發生也是不確定的。實際應用中，往往需要避免這種情形。用於描述現象的佩特里網也可能自然出現衝突，這表明我們對於變遷發生的條件沒有完全了解。

多個弧連接兩個節點的情況。在輸入庫所和變遷之間的弧的個數決定了該變遷變為被允許需要的令牌的個數。弧的個數決定了消耗／產生的令牌的個數。

佩特里網的形式化定義

一個經典的佩特里網由四元組（庫所，變遷，輸入函數，輸出函數）組成。任何圖都可以映射到這樣一個四元組上，反之亦然。

被允許的形式化變遷發生的形式化佩特里網到變遷系統的映射可達性圖

佩特里網是一個三元組(P,T,F)

F(P X T)U(T X P)是弧的集合

流程建模

一個流程的狀態是由在場所中的令牌建模的，狀態的變遷是由變遷建模的。令牌表示事物（人，貨物，機器），信息，條件，或對象的狀態；庫所代表庫所，通道或地理位置；變遷代表事件，轉化或運輸

一個流程（Flow）有當前狀態，可達狀態，不可達狀態。

經典Petri網的局限性

沒有測試庫所中零令牌的能力
模型容易變得很龐大
模型不能反映時間方面的內容
不支持構造大規模模型，如自頂向下或自底向上

高級佩特里網

為了壓縮經典佩特里網中的重複結構，提高佩特里網的建模能力，高級佩特里網應運而生。高級佩特里網包括有色佩特里網和謂詞/變遷系統。這類網系統的特點是通過摺疊來減少網的網元，壓縮網的規模。

有色佩特里網

一個有色的令牌（托肯）通常代表具有一個可以標識的對象，從而避免相同網絡結構的重複建模，如一個令牌可以取值「令牌A」，另一個令牌取值「令牌B」。當有色令牌的標識符取值（顏色）可以使用複雜的複合類型時，因此令牌擁有取值（顏色）代表由令牌建模的對象的具體特徵，如一個令牌代表一個工人（張三，28歲，經驗3級）。

佩特里網拓展

為了擴展佩特里網的建模能力，很多研究學者在多個方面對Petri網進行了擴展：

時間

為了進行分析，我們需要建模期間，延遲等，因此可以為每一個令牌附加一個時間戳，由變遷決定生產出的令牌的延遲。常用的時間佩特里網可分為Timed Petri Net 和 Time Petri Net。

時序

增加時序邏輯的定義，更好的描述行為過程。

層次化

構造一個複雜性與數據流圖相當的佩特里網的機制。層次佩特里網是由庫所，變遷和子網構成的網絡。佩特里網的層次化具有多種實現形式，例如高層次佩特里網中的一個變遷可以代表一個子佩特里網。

Petri網的應用

外部連結

Petri網世界（英文）
Petri網標記語言（頁面存檔備份，存於網際網路檔案館）（英文）

^ Petri CA. 1962. Kommunikation mit Automaten (Communication with automata). University of Bonn.

[1] Petri CA. 1962. Kommunikation mit Automaten (Communication with automata). University of Bonn.

[1]