“Petri 网用库所 token 数组成 $\mathbb N^d$。其逐坐标顺序由本引理得到 wqo,再配合变迁的单调性,形成 良结构转移系统。本引理只处理顺序;添加零测试后,顺序仍 wq…”
形式陈述
一个良结构转移系统(WSTS)由转移系统
这是允许若干步模拟的通常版本。若能要求
WSTS 是结构性质,不自动包含所有算法接口。覆盖性可判定还需顺序可判定、向上闭集有可计算的有限前驱基等有效性条件。
直觉
这是一种单向模拟:大状态可以跟随小状态,不表示小状态也能重现大状态的所有行为。覆盖性只问能否达到“不少于目标”的状态,正好利用这一方向。
例子与边界
普通 Petri 网逐式核验
对 Petri 网,状态为自然数向量
例如变迁消耗
零测试破坏的不是良拟序
考虑控制状态
状态空间仍是有限控制乘以
结构良好仍需可计算接口
即使某个向上闭集合数学上有有限基,也未必能从所给程序描述中求出它。后向算法需要:给目标基点
推论与应用
强兼容保证
兼容性不能把覆盖性偷换成精确可达性。即使
也不能从“覆盖性可判定”推广到任意时序逻辑、互模拟或终止问题。不同问题可能需要有限分支、严格兼容、公平性约束或其他独立条件。
参考资料
- [1] Alain Finkel and Philippe Schnoebelen, Well-Structured Transition Systems Everywhere!, 2001,Definitions 2.5、3.2,Theorem 3.6 及 §4 的兼容性区分。