| 名称 | 循环终止证明器 |
| 描述 | ‘使用排名函数证明循环终止。在以下情况使用：(1) 验证程序，(2) 证明总正确性，(3) 程序分析。’ |
| 版本 | 1.0.0 tags: - 验证 - 终止 - 排名函数 - 循环 difficulty: 高级 languages: - python - z3 - coq dependencies: - 不变式生成器 |
循环终止证明器
使用排名函数证明循环终止。
何时使用
- 程序验证
- 总正确性
- 证明终止
- 形式方法
本技能的作用
- 分析循环 - 检查循环结构
- 发现排名 - 寻找排名函数
- 证明终止 - 显示递减界限
- 处理复杂性 - 多路径、嵌套
关键概念
| 概念 | 描述 |
|---|---|
| 排名函数 | 递减且有下界 |
| 良基 | 无无限下降链 |
| 词典序 | 元组排序 |
| 多阶段 | 多个阶段 |
排名模式
| 模式 | 排名 |
|---|---|
while i > 0 { i-- } |
i |
while i < n { i++ } |
n - i |
while i > 0 { j-- } |
i |
| 嵌套 | 词典序 |
提示
- 从简单的候选开始
- 复杂情况使用SMT求解器
- 考虑多阶段
- 也处理递归
经典参考文献
| 参考文献 | 重要性 |
|---|---|
| Podelski & Rybalchenko, “A Complete Method for the Synthesis of Linear Ranking Functions” (VMCAI 2004) | 线性排名函数 |
| Bradley, Manna & Sipma, “Linear Ranking with Reachability” (CAV 2005) | 终止证明 |
| Cook et al., “Ranking Abstractions” (POPL 2006) | 终止抽象 |
相关技能
hoare-logic-verifier- Hoare逻辑invariant-generator- 循环不变式symbolic-execution-engine- 符号执行
研究工具与成果
终止工具：
| 工具 | 学习内容 |
|---|---|
| AProVE | 终止证明器 |
| Ctrl | 终止检查器 |
研究前沿
1. 复杂度分析
- 目标：推导复杂度界限
实现陷阱
| 陷阱 | 实际后果 | 解决方案 |
|---|---|---|
| 非终止 | 无限循环 | 寻找排名 |