paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the Completeness of Interpolation Algorithms

论插值算法的完备性
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 3/10 · 论文研究插值算法的完备性,属于形式化验证与定理证明的基础理论,与用户关注的LLM/Agent改进静态分析或形式化验证交叉方向距离较远,也未涉及浮点或贝叶斯程序分析。引用 4 inbox
Stefan Hetzl, Raheleh Jalali
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:首次系统研究插值算法的完备性,证明若干归结与相继式演算标准插值算法的不完备性及多种完备性。

克雷格插值在哲学逻辑与计算机辅助验证中有广泛应用,但一个插值算法能否生成所有可能的插值尚不清楚。本文首次提出插值算法完备性的研究框架:若对任意蕴含 A→B 的任意插值 C,都存在 A→B 的证明 P,使得 I(P) 与 C 逻辑等价,则称算法 I 完备。作者针对命题、模态与一阶逻辑的归结和相继式演算,分析若干标准插值算法的完备性,得到不完备性结果以及不同强度的完备性定理,从而刻画这些算法可产生插值的范围。

问题
研究标准插值算法在命题、模态和一阶逻辑中能否生成所有(模逻辑等价)的 Craig 插值,即插值算法的完备性问题。
方法
定义插值算法完备性,并针对归结与相继式演算的标准插值算法进行证明论分析。
评估
通过证明论论证建立不完备性与多种完备性结果,比较不同逻辑与演算下标准插值算法的能力。
原文摘要(Abstract)

Craig interpolation is a fundamental property of logics with a plethora of applications from philosophical logic to computer-aided verification. The question of which interpolants can be obtained from an interpolation algorithm is of profound importance. Motivated by this question, we initiate the study of completeness properties of interpolation algorithms. An interpolation algorithm ℐ is complete if, for every interpolant C of an implication A → B, there is a proof P of A → B such that C is logically equivalent to ℐ(P). We establish incompleteness and different kinds of completeness results for several standard algorithms for resolution and the sequent calculus for propositional, modal, and first-order logic.

链接与引用

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

BibTeX
@inproceedings{abs-2402-02829,
  title = {On the Completeness of Interpolation Algorithms},
  author = {Stefan Hetzl and Raheleh Jalali},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662112}
}