D 的个人博客

全职做开源,自由职业者

  menu

Petri Net 的形式化定义

Petri Net 定义


定义 1.1 如果三元组  (S, T, W) 称为一个 Petri 网图,那么

  • S 是库所的有限集合
  • T 是变迁的有限集合
  • S ∪ T ≠ Φ,且 S ∩ T = Φ
  • W: (S × T) ∪ (T × S) → N 为弧的多重集

流关系是弧的集合:F = {(x, y) | W(x, y) > 0}。在一些介绍 Petri 网相关文献中,弧的重度只定义为 1,并在定义 Petri 网图时使用 F 代替了 W。

 

定义 1.3 设 N = (S, T, F) 为一个 Petri 网图,∑ = (S, T, F, M) 称为一个标记网,其中

  • M ⊆ S,称为 N 的一个标记或一个瞬态
  • 若 S ∈ T,且 .x ⊆ M,x. ∩ M = Φ,称事件 x 为可触发的
  • 若事件 x 被触发(称为点火),则标记网 ∑ 转化为 ∑' = (S, T, F, M'),其中 M' = (M - .x) ∪ x.,M' 也是 N 的一个标记,∑' 也是一个标记网

定义 1.2 设 N = (S, T, F) 为一个 Petri 网图,x ∈ S ∪ T,则

  • .x = {y ∈ S ∪ T | (y, x) ∈ F}
  • x. = {y ∈ S ∪ T | (x, y) ∈ F}
  • .x. .x ∪ x.

其中,.x 称为 x 的前提,x. 称为 x 的后提,.x. 称为 x 的前后提。

定义 1.4 六元组 ∑ = (S, T, F, K, W, M) 称为一个库所 / 变迁系统,简称为 P / T 系统,如果下列条件成立

  • (S, T, F) 是一个 Petri 网图,S 是库所的有限集合,T 是变迁的有限集合,F 是有向弧的有限集合
  • K: S → N ∪ {ω} 是一个映射,使 S 中的每个元素 x 与一个自然数或无穷大值相对应,称为 x 的容量
  • W: F → N - {0} 是一个映射,使 F 中的每条弧 f 与一个正整数对应,称为 f 的流量
  • M: S → N ∪ {ω} 是一个映射,使 S 中的每个元素与一个有穷或无穷的初始标码数相对应,整个 M 称为 ∑ 的初始标记,满足 M(x) ≤ K(x)


定义 1.5 P / T 系统 ∑ = (S, T, F, K, W, M) 的运行规则如下:

  • T 中任一变迁 t 被允许发生的条件是:
    ∀ s ∈ .t,M(s) ≥ W(s, t)
    ∀ s ∈ t.,M(s) ≤ K(s) - W(t, s)
    其中 W(s, t) 表示从 s 到 t 的弧的流量
  • 如果变迁发生前的标记为 M,则变迁发生后的标记 M' 是
                  M(s) - W(s, t), 若 s ∈ .t - t.
    M'(s) = { M(s) + W(t, s),若 s ∈ t. - .t }
                  M(s),               其他
    注意,这里恒要求 .t ∩ t. = Φ
  • 初始标记是标记,任一标记经过变迁以后仍然变为标记

参考

[1] 李彤, 孔兵, 王黎霞等. 软件并行开发过程. 北京:科学出版社, 2003
[2] http://en.wikipedia.org/wiki/Petri_net

 

well-formatted doc:

http://docs.google.com/Doc?id=ddrm6c35_512f45hshcz