形式陈述
对有限普通 P/T 网理路Petri 网Petri net · Place-transition net · P/T net以库所、变迁和 token 多重集建模资源、同步与真正并发,并研究可达标识。,Karp–Miller 树用扩展 marking 标记结点。约定 、。 表示可以覆盖任意有限阈值,不是系统真的拥有无穷 token。
从初态建根。对未关闭结点,枚举使能变迁并计算后继 。若当前分支上有祖先 ,则把所有严格增长坐标 提升为 ;必要时重复沿祖先比较,直到本次加速不再变化。若所得标签与某祖先相同,就关闭该分支。只比较当前分支的祖先,不能看到别处较小的结点就随便加速。[1, covering graph 部分]
树有限,且有限目标 可覆盖,当且仅当某结点标签 满足 。这是覆盖集的有限表示,不是精确可达集的枚举。
直觉
若同一条执行路径从 走到 ,原来的操作可以在更多资源下再做一遍。每次都能增加同样的非负资源差,于是那些真正增长的坐标可以泵到任意大。
当祖先标签已经含 时,树边本身不再是一条从“无限 marking”出发的具体执行。正确性使用更强的有限逼近不变量:对每个标签v和每个有限阈值K,都有从初态可达的有限m,在v的有限坐标上取相同值,并在所有 坐标上同时不少于K。[1, Lemma 3.2.7]
普通触发保持这个不变量:预先给旧 坐标多留本步可能消耗的有限 token。加速时先固定所需的有限重复次数,再为祖先路径中已有的加速选择足够大的有限展开;旧 坐标作为可任意预充的储备,不能假装它们一次真实执行永不减少。一段长为 、每步每库所至多消耗W的具体路径,重复r次只需预留 加上最终阈值的储备;新提升坐标沿所选可比路径真正增长,仍为有限的坐标净效应为零。对此前加速逐层使用同一有限逼近性质,就能为每个固定K构造有限执行,而不必存在一条给所有K同时取无限值的执行。
祖先关系提供这种可展开、可重复的路径依据;单纯数值比较没有这份证据。反向覆盖性则沿每个真实触发逐步跟随树边;遇到与祖先相同的关闭标签可回到该祖先继续,标签始终覆盖真实marking。两方向一起说明树表示的是可覆盖阈值,而非所有中间整数都可精确达到。
例子与边界
一棵可以完整手算的小树
两库所 ,初态 。变迁 增加两个 ,变迁 把一个 移到 。
根经 得 ,覆盖祖先 ,第一坐标严格增长,加速成 。根经 得 ,两变迁均不使能,成为叶子。
在 上, 给相同标签,关闭; 给 ,与祖先 比较后把第二坐标加速,得 。这里再触发 或 都保持相同标签,分别关闭。
这说明任意有限 都可覆盖:先反复 得到足够多的 ,再把其中 个经 移到 ,剩余 仍可不少于 。
覆盖成功不意味着精确到达
该网每次 使 token 总数加二,每次 保持总数,所以所有可达 marking 总数为奇数。目标 被树中 覆盖,也确实被可达的 覆盖;但 本身总数为偶数,永远不可达。
因此不能把一个 随意换成目标数字,然后当成已经找到精确执行。线性同余、触发顺序等信息会被覆盖抽象抹去。
终止机制与模型边界
每条分支上,一个坐标至多从有限值升级为 一次。在最后一次升级之后,剩余有限坐标若产生无限分支,Dickson 引理理路Dickson 引理Dickson lemma自然数向量的逐坐标序为良拟序;用逐坐标抽取证明,并手算二维最小基和维数变化的边界。会给出祖先可比对;严格增长应触发新的升级,无增长则遇到相同标签并关闭,矛盾。给有限变迁集固定编号,把每个结点编码为根到它的变迁编号序列;这些有限序列构成前缀闭树,每个结点至多有 个孩子。于是可用树页无限有根变体的 König 引理理路树Tree连通且无圈的有限简单无向图,也就是任意两点之间只有一条简单路径的图。:若结点无限,就存在无限分支,与刚才结论矛盾。相同marking标签仍可对应不同序列结点,不能据标签相同把整树当成简单路径。
这个论证不包含有用的小运行时间界。添加 inhibitor arc、零测试或任意其他扩展后,“增加资源仍可重复原路径”可能失败,本算法的正确性不能沿用。
推论与应用
树中没有 当且仅当这个给定初态的网有界;有限标签最大值可给各库所上界。若有 ,相应库所无界,但不是说单条有限执行拥有无限资源。
与后向有限基算法理路覆盖性的后向基算法Backward coverability algorithm从向上闭坏状态反向扩展有限基,给出 Petri 网前驱公式、完整小例运行与终止和安全不动点证明。相比,Karp–Miller 从一个初态概括所有可覆盖阈值;后向算法从一个坏阈值集概括所有危险初态。二者共享单调性,保存的方向和摘要却不同。
参考资料