paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Clause Set Cycles and Induction

子句集环与归纳
LMCS vol.Volume 16, Issue 42020匹配度 2/10 · 该论文属于自动归纳定理证明与形式逻辑理论,虽与形式化验证相关,但未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析等用户核心方向。其研究问题与用户画像中的交叉点不直接匹配。引用 5 inbox
Stefan Hetzl, Jannik Vierling
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:将饱和证明器中基于循环检测的归纳证明方法抽象为子句集环,并厘清其与若干归纳理论的包含关系。

本文研究基于饱和式证明器中循环检测的一类自动归纳定理证明方法,旨在明确其逻辑强度。作者提出“子句集环”这一形式化概念,用以抽象子句集之间的循环依赖。首先证明子句集环形式化包含于 ∃₁ 归纳理论;随后通过给出三角数理论在开放归纳下的有限公理化,证明子句集环不包含于开放归纳理论,并猜想二者不可比较。最后把这些结果迁移到具体的自动归纳证明方法 n-clause calculus。

问题
如何刻画自动归纳定理证明中基于循环检测的方法的逻辑强度,并确定其与经典归纳理论的关系。
方法
引入子句集环形式化,抽象饱和证明器中的循环依赖;比较其与 ∃₁ 归纳、开放归纳等理论的包含关系,借助三角数理论的有限公理化进行分离。
评估
通过理论包含与不可包含的数学证明,以及将结论迁移到 n-clause calculus,评估该形式化的表达力与适用范围。
原文摘要(Abstract)

In this article we relate a family of methods for automated inductive theorem proving based on cycle detection in saturation-based provers to well-known theories of induction. To this end we introduce the notion of clause set cycles -- a formalism abstracting a certain type of cyclic dependency between clause sets. We first show that the formalism of clause set cycles is contained in the theory of $\exists_1$ induction. Secondly we consider the relation between clause set cycles and the theory of open induction. By providing a finite axiomatization of a theory of triangular numbers with open induction we show that the formalism of clause set cycles is not contained in the theory of open induction. Furthermore we conjecture that open induction and clause set cycles are incomparable. Finally, we transfer these results to a concrete method of automated inductive theorem proving called the n-clause calculus.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@article{abs-1910-03917,
  title = {Clause Set Cycles and Induction},
  author = {Stefan Hetzl and Jannik Vierling},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 4},
  year = {2020},
  doi = {10.23638/lmcs-16(4:11)2020}
}