paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Intuitionistic proofs without syntax

无语法表示的直觉主义证明
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 1/10 · 论文属于纯证明论与形式语义领域,研究直觉主义组合证明、序列演算翻译与典范性,并未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。其理论结果与用户当前关注的 PL 与 AI 交叉方向几乎没有直接关联。引用 11 inbox
Willem B. Heijltjes, Dominic J. D. Hughes, Lutz StraBburger
crossref: 2026-09-12

AI 速览

一句话:提出直觉主义组合证明(ICPs),一种复杂度感知的几何语义,多项式保持序列演算翻译并实现局部典范性。

本文提出直觉主义组合证明(ICPs),为直觉主义逻辑给出一种具体的几何语义,推广自经典组合证明。每个 ICP 自然分解为线性片段(IMLL 证明网的图形抽象,即 arena net)与并行 contraction-weakening 片段(skew fibration)。ICP 与游戏语义关联,可视为 Hyland-Ong arena 中从树状推广到 DAG 状的策略。第一个主要结果是多项式完全性(Polynomial Full Completeness):ICP 语义是复杂度感知的,其与序列演算之间的翻译可多项式大小保持;相比之下,lambda 演算与游戏语义会产生指数膨胀。第二个主要结果是局部典范性(Local Canonicity):ICP 完全且忠实地抽象掉序列演算中非复制排列,类似作者对 MALL 的近期结果。该工作为直觉主义证明提供无语法、可组合的语义表示。

问题
如何为直觉主义逻辑提供一种具体几何语义,避免传统 lambda 演算与游戏语义在表示证明时的指数膨胀,并刻画序列演算证明的排列等价。
方法
引入直觉主义组合证明(ICPs),将其分解为 arena net 线性片段与 skew fibration 的 contraction-weakening 片段,并建立与序列演算之间的翻译。
评估
通过证明 Polynomial Full Completeness(与序列演算翻译大小保持至多项式)和 Local Canonicity(完全忠实抽象非复制排列)来评估,并与 lambda 演算和游戏语义的指数膨胀对比。
原文摘要(Abstract)

We present Intuitionistic Combinatorial Proofs (ICPs), a concrete geometric semantics of intuitionistic logic based on the principles of the second author's classical Combinatorial Proofs. An ICP naturally factorizes into a linear fragment, a graphical abstraction of an IMLL proof net (an arena net), and a parallel contraction-weakening fragment (a skew.fibration). ICPs relate to game semantics, and can be seen as a strategy in a Hyland-Ong arena, generalized from a tree-like to a dag-like strategy. Our first main result, Polynomial Full Completeness, is that ICPs as a semantics are complexity-aware: the translations to and from sequent calculus are size-preserving (up to a polynomial). By contrast, lambda-calculus and game semantics incur an exponential blowup. Our second main result, Local Canonicity, is that ICPs abstract fully and faithfully over the non-duplicating permutations of the sequent calculus, analogously to the first and second authors' recent result for MALL.

链接与引用

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

BibTeX
@inproceedings{paperbot5001,
  title = {Intuitionistic proofs without syntax},
  author = {Willem B. Heijltjes and Dominic J. D. Hughes and Lutz StraBburger},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785827}
}