⚡

循环终止证明器Skill loop-termination-prover

循环终止证明器是一种用于程序验证的技能，通过分析循环结构和发现排名函数来证明循环的终止性。适用于验证程序总正确性、分析程序循环行为，并使用形式方法确保软件可靠性。关键词：循环终止、排名函数、程序验证、终止证明、形式验证、软件测试。

测试 0 次安装 0 次浏览 更新于 3/13/2026

name: 循环终止证明器 description: ‘使用排名函数证明循环终止。在以下情况使用：(1) 验证程序，(2) 证明总正确性，(3) 程序分析。’ version: 1.0.0 tags:

  • 验证
  • 终止
  • 排名函数
  • 循环 difficulty: 高级 languages:
  • python
  • z3
  • coq dependencies:
  • 不变式生成器

循环终止证明器

使用排名函数证明循环终止。

何时使用

  • 程序验证
  • 总正确性
  • 证明终止
  • 形式方法

本技能的作用

  1. 分析循环 - 检查循环结构
  2. 发现排名 - 寻找排名函数
  3. 证明终止 - 显示递减界限
  4. 处理复杂性 - 多路径、嵌套

关键概念

概念 描述
排名函数 递减且有下界
良基 无无限下降链
词典序 元组排序
多阶段 多个阶段

排名模式

模式 排名
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. 复杂度分析

  • 目标：推导复杂度界限

实现陷阱

陷阱 实际后果 解决方案
非终止 无限循环 寻找排名