paperbot · PL 论文追踪

全部论文 待读 收藏

P2 SAT-Inspired Higher-Order Eliminations

SAT 启发的高阶消去技术
LMCS vol.Volume 19, Issue 22023匹配度 3/10 · 论文属于自动定理证明与形式化验证中的预处理技术,与用户关注的静态分析/形式化验证有间接关联;但它不涉及程序分析、浮点分析、贝叶斯程序分析,也未与 LLM/Agent 结合,因此不命中核心方向。引用 1 inbox
Jasmin Blanchette, Petar Vukmirović
crossref: 2026-09-10

AI 速览

一句话:将多种命题预处理消去技术推广到高阶逻辑,提出拟纯文字消去,并在 Zipperposition 中提升自动证明搜索。

本文研究如何简化高阶逻辑问题以利于自动定理证明。作者从 SAT 预处理思想出发,在已有的一阶推广基础上,将消去文字、子句或谓词符号的若干技术提升到高阶逻辑,并提出新的拟纯文字消去(quasipure literal elimination),后者严格包含传统的纯文字消去。所有技术均在 Zipperposition 定理证明器中实现。在来自 Isabelle 形式化和 TPTP 库的问题上评估表明,这些消去技术有时能帮助证明器成功证明目标,说明 SAT 启发的预处理在高阶自动定理证明中具有实用价值。

问题
高阶逻辑自动定理证明中,冗余文字、子句或谓词符号会增加搜索空间,如何借鉴 SAT 预处理来简化问题并提升证明搜索效率。
方法
在已有的一阶推广基础上,将多种命题消去技术推广到高阶逻辑,并提出严格包含纯文字消去的拟纯文字消去;这些技术均实现在 Zipperposition 中。
评估
在来自 Isabelle 形式化和 TPTP 库的问题上运行 Zipperposition,观察这些消去技术是否有助于自动证明成功。
原文摘要(Abstract)

We generalize several propositional preprocessing techniques to higher-order logic, building on existing first-order generalizations. These techniques eliminate literals, clauses, or predicate symbols from the problem, with the aim of making it more amenable to automatic proof search. We also introduce a new technique, which we call quasipure literal elimination, that strictly subsumes pure literal elimination. The new techniques are implemented in the Zipperposition theorem prover. Our evaluation shows that they sometimes help prove problems originating from Isabelle formalizations and the TPTP library.

链接与引用

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

BibTeX
@article{paperbot2218,
  title = {SAT-Inspired Higher-Order Eliminations},
  author = {Jasmin Blanchette and Petar Vukmirović},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 2},
  year = {2023},
  doi = {10.46298/lmcs-19(2:9)2023}
}