[拼音]：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中的网是简单的，但不单纯。

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

严正声明：本文由历史百科网注册或游客用户辉城自行上传发布关于» 佩特里网论的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：辉城；本文链接：https://www.freedefine.cn/wenzhan/54090.html