paperbot · PL 论文追踪

全部论文 待读 收藏

P2 HoCHC: A Refutationally Complete and Semantically Invariant System of Higher-order Logic Modulo Theories

HoCHC:一个反驳完备且语义不变的高阶逻辑模理论系统
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 4/10 · 该论文属于高阶约束 Horn 子句的逻辑与证明论基础,与形式验证/程序分析有间接关联;但未涉及用户核心关注的 ML/Agentic 程序静态分析、LLM 与静态分析/形式验证的交叉、浮点程序分析或贝叶斯程序分析,也缺少工程落地与 benchmark 评估。引用 8 inbox
C.-H. Luke Ong, Dominik Wagner
crossref: 2026-09-12

AI 速览

一句话:为高阶约束 Horn 子句提出简单归结证明系统,并证明其在标准与 Henkin 语义下可靠且反驳完备。

本文研究高阶约束 Horn 子句(HoCHC)——一种高阶逻辑模理论的片段。作者提出一个简单的归结证明系统,并在标准语义与 Henkin 语义下证明其可靠性与反驳完备性。作为推论,对半可判定背景理论得到紧致性定理与 HoCHC 的半可判定性,并证明 HoCHC 具有规范模型性质。论文还证明一种由高阶到一阶逻辑的翻译变体在两种语义下都可靠且完备,并展示如何把一阶逻辑模理论(片段)的可判定性结果迁移到高阶设定;示例是 HoCHC 在受限线性整数算术下的 Bernays–Schönfinkel–Ramsey 片段。

问题
如何为高阶约束 Horn 子句提供兼具可靠性与反驳完备性的证明系统,并保持标准语义与 Henkin 语义下的一致性。
方法
定义简单的归结证明系统,证明其相对两种语义的可靠性与反驳完备性,并研究高阶到一阶逻辑翻译变体的可靠性与完备性。
评估
以理论证明为主,给出紧致性、半可判定性、规范模型性质,并展示受限线性整数算术下 Bernays–Schönfinkel–Ramsey 片段的可判定性迁移。
原文摘要(Abstract)

We present a simple resolution proof system for higher-order constrained Horn clauses (HoCHC)-a system of higher-order logic modulo theories-and prove its soundness and refutational completeness w.r.t. both standard and Henkin semantics. As corollaries, we obtain the compactness theorem and semi-decidability of HoCHC for semi-decidable background theories, and we prove that HoCHC satisfies a canonical model property. Moreover a variant of the well-known translation from higher-order to 1st-order logic is shown to be sound and complete for HoCHC in both semantics. We illustrate how to transfer decidability results for (fragments of) 1st-order logic modulo theories to our higher-order setting, using as example the Bernays-Schonflukel-Ramsey fragment of HoCHC modulo a restricted form of Linear Integer Arithmetic.

链接与引用

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

BibTeX
@inproceedings{paperbot4994,
  title = {HoCHC: A Refutationally Complete and Semantically Invariant System of Higher-order Logic Modulo Theories},
  author = {C.-H. Luke Ong and Dominik Wagner},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785784}
}