paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Non-Elementary Compression of First-Order Proofs in Deep Inference Using Epsilon-Terms

使用 epsilon-项在深度推理中实现一阶证明的非初等压缩
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 该论文属于纯证明论/定理证明基础研究,聚焦 deep inference、epsilon-演算与无切证明的非初等压缩,不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户当前 PL+AI 交叉方向基本无关。引用 0 inbox
Cameron Allett
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出 falsifier 演算,用 falsifier 规则引入 epsilon 项,使某些一阶定理的无切证明可非初等压缩。

论文研究一阶谓词逻辑中证明大小的非初等压缩。作者在 Hilbert epsilon-演算语言下提出深度推理系统 falsifier 演算,其新规则 falsifier 规则用于引入 epsilon 项,不同于传统 epsilon-演算的 critical axioms,并可视为量词移位规则的推广。作者证明该演算对某些一阶定理给出比相继式演算非初等更短的无切证明,并建立类似 Herbrand 定理的分解定理,引入 falsifier 析取作为新型中间公式。进一步证明某些一阶定理的 falsifier 析取可比 Herbrand 析取非初等地更小。

问题
一阶定理在相继式演算中的无切证明可能非初等地长;能否利用 epsilon-项与深度推理压缩证明,并构造新的中间公式。
方法
提出 falsifier 演算与 falsifier 规则,形式化 epsilon-项的引入,证明分解定理,并比较证明长度与析取公式大小。
评估
通过证明论定理与大小比较进行理论评估:展示某些一阶定理的无切证明压缩,以及 falsifier 析取相对 Herbrand 析取的非初等优势。
原文摘要(Abstract)

I introduce the falsifier calculus, a new deep-inference proof system for first-order predicate logic in the language of Hilbert's epsilon-calculus. It uses a new inference rule, the falsifier rule, to introduce epsilon-terms into a proof, distinct from the critical axioms of the traditional epsilon-calculus. The falsifier rule is a generalisation of one of the quantifier-shifts, inference rules for shifting quantifiers inside and outside of formulae. Like the epsilon-calculus and proof systems which include quantifier-shifts, the falsifier calculus admits non-elementarily shorter cut-free proofs of certain first-order theorems than the sequent calculus. Analogous to the way in which Herbrand's Theorem decomposes a proof into a first-order and a propositional part, connected by a Herbrand disjunction as an intermediate formula, I prove a decomposition theorem for the falsifier calculus which gives rise to a new notion of intermediate formula in the epsilon-calculus, falsifier disjunctions. I then prove that certain first-order theorems admit non-elementarily smaller falsifier disjunctions than Herbrand disjunctions.

链接与引用

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

BibTeX
@inproceedings{Allett24,
  title = {Non-Elementary Compression of First-Order Proofs in Deep Inference Using Epsilon-Terms},
  author = {Cameron Allett},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662101}
}