Skip to content

算法Algorithm

Karp–Miller 覆盖树

施工中 · 内容逐步修订

Karp-Miller tree

用沿祖先的增长比较将 Petri 网无界计数加速为 omega,手算树并以奇偶约束区分覆盖与精确可达。

形式陈述 ​

对有限普通 P/T 网,Karp–Miller 树用扩展 marking (N∪{ω})P 标记结点。约定 n<ω、ω±n=ω。ω 表示可以覆盖任意有限阈值,不是系统真的拥有无穷 token。

从初态建根。对未关闭结点,枚举使能变迁并计算后继 y。若当前分支上有祖先 x≤y,则把所有严格增长坐标 xi<yi 提升为 ω;必要时重复沿祖先比较,直到本次加速不再变化。若所得标签与某祖先相同,就关闭该分支。只比较当前分支的祖先,不能看到别处较小的结点就随便加速。[1, covering graph 部分]

树有限,且有限目标 b 可覆盖,当且仅当某结点标签 v 满足 b≤v。这是覆盖集的有限表示,不是精确可达集的枚举。

直觉

若同一条执行路径从 x 走到 y≥x,原来的操作可以在更多资源下再做一遍。每次都能增加同样的非负资源差,于是那些真正增长的坐标可以泵到任意大。

当祖先标签已经含 ω 时,树边本身不再是一条从“无限 marking”出发的具体执行。正确性使用更强的有限逼近不变量:对每个标签v和每个有限阈值K,都有从初态可达的有限m,在v的有限坐标上取相同值,并在所有 ω 坐标上同时不少于K。[1, Lemma 3.2.7]

普通触发保持这个不变量:预先给旧 ω 坐标多留本步可能消耗的有限 token。加速时先固定所需的有限重复次数,再为祖先路径中已有的加速选择足够大的有限展开;旧 ω 坐标作为可任意预充的储备,不能假装它们一次真实执行永不减少。一段长为 ℓ、每步每库所至多消耗W的具体路径,重复r次只需预留 rℓW 加上最终阈值的储备;新提升坐标沿所选可比路径真正增长,仍为有限的坐标净效应为零。对此前加速逐层使用同一有限逼近性质,就能为每个固定K构造有限执行,而不必存在一条给所有K同时取无限值的执行。

祖先关系提供这种可展开、可重复的路径依据;单纯数值比较没有这份证据。反向覆盖性则沿每个真实触发逐步跟随树边;遇到与祖先相同的关闭标签可回到该祖先继续,标签始终覆盖真实marking。两方向一起说明树表示的是可覆盖阈值,而非所有中间整数都可精确达到。

例子与边界

一棵可以完整手算的小树 ​

两库所 p,q,初态 (1,0)。变迁 a:p→3p 增加两个 p,变迁 b:p→q 把一个 p 移到 q。

根经 a 得 (3,0),覆盖祖先 (1,0),第一坐标严格增长,加速成 (ω,0)。根经 b 得 (0,1),两变迁均不使能,成为叶子。

在 (ω,0) 上,a 给相同标签,关闭;b 给 (ω,1),与祖先 (ω,0) 比较后把第二坐标加速,得 (ω,ω)。这里再触发 a 或 b 都保持相同标签,分别关闭。

这说明任意有限 (r,s) 都可覆盖:先反复 a 得到足够多的 p,再把其中 s 个经 b 移到 q,剩余 p 仍可不少于 r。

覆盖成功不意味着精确到达 ​

该网每次 a 使 token 总数加二,每次 b 保持总数,所以所有可达 marking 总数为奇数。目标 (0,2) 被树中 (ω,ω) 覆盖,也确实被可达的 (1,2) 覆盖;但 (0,2) 本身总数为偶数,永远不可达。

因此不能把一个 ω 随意换成目标数字,然后当成已经找到精确执行。线性同余、触发顺序等信息会被覆盖抽象抹去。

终止机制与模型边界 ​

每条分支上,一个坐标至多从有限值升级为 ω 一次。在最后一次升级之后,剩余有限坐标若产生无限分支,Dickson 引理会给出祖先可比对;严格增长应触发新的升级,无增长则遇到相同标签并关闭,矛盾。给有限变迁集固定编号,把每个结点编码为根到它的变迁编号序列;这些有限序列构成前缀闭树,每个结点至多有 |T| 个孩子。于是可用树页无限有根变体的 König 引理:若结点无限,就存在无限分支,与刚才结论矛盾。相同marking标签仍可对应不同序列结点,不能据标签相同把整树当成简单路径。

这个论证不包含有用的小运行时间界。添加 inhibitor arc、零测试或任意其他扩展后,“增加资源仍可重复原路径”可能失败,本算法的正确性不能沿用。

推论与应用

树中没有 ω 当且仅当这个给定初态的网有界;有限标签最大值可给各库所上界。若有 ω,相应库所无界,但不是说单条有限执行拥有无限资源。

与后向有限基算法相比,Karp–Miller 从一个初态概括所有可覆盖阈值;后向算法从一个坏阈值集概括所有危险初态。二者共享单调性,保存的方向和摘要却不同。

参考资料
  • [1] Javier Esparza, Petri Nets: Lecture Notes,2022-04-25版,§3.2.2,Theorem 3.2.5、Lemma 3.2.7、Theorem 3.2.8:覆盖图终止与同时有限逼近;本页采用只沿当前祖先比较的树版本。
  • [2] Richard M. Karp and Raymond E. Miller, Parallel Program Schemata, JCSS 3, 1969,pp. 147–195。
关系图谱9 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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