什么是佩特里网论?

什么是佩特里网论?

[拼音]：Peiteli wanglun

[外文]：Petri net theory

网论分支之一，又称特殊网论。研究如何将佩特里网模拟系统以及佩特里网的分析技术，适用于无中央控制的异步并发系统的动态定性研究。佩特里网论是联邦德国C.A.佩特里于20世纪60年代初创建的。佩特里网已在西欧、北欧和美国获得广泛应用。

两种表示法

佩特里网有图表示和数学表示两种表示法。

（1）图表示： 佩特里网是由圆圈和短线两类节点构成的网状结构（图1）。圆圈表示地点或条件，短线表示变迁或事件。连接圆圈和短线的有向弧称为流关系，圆圈中的黑点叫作码子，标志着网中的信息，信息的流动即用码子的位置和数量的变化模拟。码子在网中的分布构成网的标识，又称状态。上述要素所构成之网状结构满足以下五个条件才是佩特里网：(a)至少有一个节点；(b)每个有向弧的起止点必须是一个圆圈和一条短线，两条有向弧的起止点不能完全相同；(c)每个节点至少必须是一条有向弧的起点或终点；(d)每个地点都有固定的容量，即最多能容纳的码子个数，容量可以是无穷的(ω)；(e)每个网都有一个初始标识。

为叙述方便起见，可以对节点起名字（如p1，p2，t3等），但这些名字不是定义的组成部分。

（2）数学表示:将图示中的各要素表示为数学对象。P，T分别为圆圈和短线的集合；F为流关系；K，μ:P→N +ω分别为容量函数和标识。五元组(P，T，F，K，μ)成为佩特里网的条件可以形式地定义为

式中φ为空集；N +ω为自然数（包括零）上无穷之集合；dom F和cod F分别为F 的定义域和值域;P×T及T×P均为笛卡儿积。

变迁的实施规则

变迁的实施改变码子的位置和数量，标识的变化记录着系统的动态性质。

若存在有向弧从地点p指向变迁t，则p即是t的输入地点；反之，若有向弧从t指向p，则p是t的输出地点。若在标识μ之下，t的每个输入地点都至少有一个码子，且t的每个输出地点中的码子数都比其容量至少小1，那么t在μ之下是具备条件的。凡具备条件的变迁均可实施。实施办法是先从t的输入地点各拿掉一个码子，再在t的输出地点各放一个码子，如此得到的新标识称为μ′(图2)。

分析技术

从初始标识μ出发，通过变迁之实施获得新的标识，所有这些标识之集合称为可到达状态集，记为R(μ)。构造佩特里网的可到达状态树是研究R(μ)的通用分析技术。构造的步骤是：

（1）以μ为根，记作μ0；μ0和一切标识均表示为矢量(n1，n2，…)，其中ni是在该标识下地点Pi中的码子个数。

（2）若μi是已构造的树的叶节点，则分四种情况处理：(a)若在ui之下ti1，ti2，…，tij均具备条件，则μi有j个子分枝，分别标以ti1，ti2，…，tij，相应的子节点依次为在μi之下实施变迁ti1，ti2，…，tij所得之新标识。(b)若在从μ0到μi的道路上存在节点μk， 使得


，且


p∈P:μi(p)＞μk(p)，那么对所有p，只要μi(p)＞μk(p)，就把μi(p)改为ω，这样从μi获得新标识μ'i，即以μ'i代替μi作为节点。(c)若上述μk使凬p∈P:μi(p)＝μk(p)，那么μi即为最终之叶节点。(d)在μi之下任何变迁均不具备条件，这时μi为最终之叶节点。下面是图1所示佩特里网的可到达树

分析可到达树可以获得系统的动态性质。例如是否可能达到指定的状态，是否有永不能实施的变迁等。这些都是佩特里网论分析研究的问题。

扩充网和受限网

扩充网具有较强的模拟力，限受网则易于分析，有较强的决策力。一种有意义的扩充网是约束弧网，这种网与图灵机有相同的模拟力。

简单网和单纯网是两种重要的受限网。前者要求任意两个节点不能有完全相同的输入和输出；后者则要求若有向弧(x，y)∈F……，则(y，x)唘F。图1中的网是简单的，但不单纯。

应用

变迁的实施只决定于变迁本身的输入输出，所以佩特里网特别适用于模拟无中央控制的异步并发系统的动态性质。佩特里网已成功地用于分析 *** 作系统和计算机系统结构的容错性能。佩特里网的缺点是节点过多，通用网论中的网射是克服这一缺点的有力工具。