Skip to content

定义Definition

Petri 网展开与有限完备前缀

施工中 · 内容逐步修订

Petri net unfolding · Finite complete prefix

用条件和事件的无环网保留 Petri 网因果与冲突,手算并发配置,并说明有限完整前缀的截断条件。

形式陈述 ​

本页采用所引展开构造的模型条件:有限、所有弧权为一的 1-safe Petri 网,每个可达库所至多一个 token,且每个变迁的输入库所集和输出库所集都非空。其展开是一个通常无限的发生网,包含表示 token 实例的条件结点、表示变迁发生实例的事件结点,以及到原网库所和变迁的标签映射。

发生网的有向路径给出因果偏序。两个事件若竞争同一个输入条件,则直接冲突;冲突传播到其后继。事件集合 C 若有限、因果向下闭且无冲突,称为一个配置。执行配置中事件的任意拓扑序,得到相同的原网 marking。[1]

展开不把原网里的每个变迁只复制一次。同一变迁在不同因果历史或不同轮次发生时,会产生不同事件实例;正是这些副本让展开自身保持无环。

直觉

状态图把“先做甲后做乙”与“先做乙后做甲”画成两条路径;若二者使用独立资源,这只是同一次并发活动的两种排队方式。展开保留甲、乙没有因果先后的事实,用一个配置代表这些交错。

另一方面,共享输入资源的两项选择不能一起进入配置。因果无先后不自动等于可并发,还必须排除冲突。

例子与边界

两个独立任务只需两个事件 ​

初态在 p,q 各有一个 token。变迁 a:p→p′,b:q→q′。展开含初始条件 p0,q0,事件 a0,b0 以及输出条件 p0′,q0′。

a0 与 b0 没有因果关系,也不冲突。配置有 ∅、{a0}、{b0}、{a0,b0}。最后一个配置同时代表执行 ab 和 ba,终态都在 p′,q′ 各有一个 token。

若再加入 c:p→r,展开中的 c0 与 a0 消耗同一个条件 p0,因此冲突;{a0,c0} 不是配置,即使两事件之间没有有向路径。

循环为什么复制 token 实例 ​

若网只有 t:p→p,初态一个 p token,那么展开为

p0→t0→p1→t1→p2→⋯.

每个 pi 标签都是同一个原库所 p,每个 ti 标签都是 t,但实例不同。直接把 p1 与 p0 合并会重新制造环,并丢失“第几次发生”的因果信息。

有限完整前缀凭什么截断 ​

在上述有限非退化模型下,有界网虽然展开可无限,却能构造有限完整前缀。“完整”不只要求每个可达marking出现:对每个可达M,须有配置C满足 Mark(C)=M,且对M使能的每个变迁t,都有不在C中的事件e,使 C∪{e} 仍是前缀中的配置、e标签为t。只保留所有状态而漏掉某个可执行动作,不满足这个条件。[1, §3.2]

典型规则将事件e的局部配置(e及其全部因果前驱)与已保留的较小配置比较:若到达相同marking,且后者在合适的 adequate order 中更小,就将e标为cutoff。cutoff事件及其输出条件本身仍保留,只抑制其因果后代;直接删掉cutoff事件可能丢失刚才要求的动作扩展。

adequate order 须良基,细化严格包含,即 C⊊C′⇒C≺C′,并在相同marking的匹配有限扩展下保持严格顺序:从两个cut出发的未来展开可按标签同构,给较小配置附上与较大配置同构的事件后缀后,它仍较小。这个条件保证截断后的未来可以转到较小代表继续;只比较事件标签或随意选择相同marking都不够。按事件数严格小于的顺序是一个基本选择。[1, Definitions 3.3–3.5]

允许初始空配置参与比较的变体中,上面的单循环发生一次t后便回到相同marking;保留这次事件,再以空配置代表其未来即可截断。若严格采用原文只比较事件局部配置的版本,则下一次t才与第一次的局部配置比较并被截断;两者都保留执行t的扩展。一般并发网中,任意遇到相同标签就合并不够;比较的是配置到达的完整 marking,并须使用保证完整性的顺序条件。

推论与应用

展开适合分析可达 marking、死锁及因果冲突。其优势取决于并发结构:n 个互不依赖的一次性事件有 n! 种全序交错,却可由 n 个事件的一份偏序表示。若模型主要是冲突选择,展开仍可能指数大。

偏序约简通常从状态探索中删去冗余交错;展开则显式构造事件及 token 的因果结构。二者目标相近,保存的数据对象和正确性证明不同。Mazurkiewicz 迹把独立动作交换归为同类,可帮助理解交错如何对应同一个配置。

本页没有声称任意无界网都能靠同样规则得到有限完整前缀。离开 1-safe 或有界范围时,需要额外的多重 token 处理和明确的终止条件。空输入、空输出变迁也需另定发生实例约定;例如没有输入也没有输出的空动作可重复触发,却不能不加说明地套用由输入条件集合唯一确定事件的构造。

参考资料
关系图谱10 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组