paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Gödel logic: From natural deduction to parallel computation

Gödel 逻辑:从自然演绎到并行计算
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 论文属于证明论/类型论与并行计算的Curry–Howard对应,未涉及用户画像中的ML/Agent程序静态分析、LLM辅助形式化验证、浮点程序分析或贝叶斯程序分析,因此与当前研究方向基本无关。引用 21 inbox
Federico Aschieri, Agata Ciabattoni, Francesco A. Genco
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:为命题 Gödel 逻辑 G 建立 Curry–Howard 对应,用自然演绎类型系统刻画带同步通信的并行函数式计算。

命题 Gödel 逻辑 G 在直觉主义逻辑上加入了非构造性的线性公理 (A → B) ∨ (B → A),但其计算解释长期缺失。本文为 G 引入 Curry–Howard 对应,证明一个简单的自然演绎演算可作为类型系统,由此得到一种扩展简单类型 λ-演算的函数式语言:它通过并行进程之间的同步通信机制进行计算,并因此比简单类型 λ-演算具有更强表达力。论文还给出规范化证明,其终止性论证和证明变换体现了代码移动等机制。该结果给出了 G 的计算解释,从而证明了 A. Avron 于 1991 年提出的论题。

问题
命题 Gödel 逻辑 G 通过线性公理扩展直觉主义逻辑,但此前缺乏构造性计算解释,Avron 1991 年的论题尚待证明。
方法
建立 G 的 Curry–Howard 对应,将自然演绎证明作为类型系统,得到带并行进程同步通信的简单类型 λ-演算扩展,并用终止性论证与实现代码移动的证明变换证明规范化。
评估
理论评估体现在规范化/终止性证明上:作者给出原始终止论证和证明变换,表明该演算可计算地解释 G,并证明 Avron 的论题。
原文摘要(Abstract)

Propositional Gödel logic G extends intuitionistic logic with the non-constructive principle of linearity (A → B) ∨ (B → A). We introduce a Curry-Howard correspondence for G and show that a simple natural deduction calculus can be used as a typing system. The resulting functional language extends the simply typed λ-calculus via a synchronous communication mechanism between parallel processes, which increases its expressive power. The normalization proof employs original termination arguments and proof transformations implementing forms of code mobility. Our results provide a computational interpretation of G, thus proving A. Avron's 1991 thesis.

链接与引用

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

BibTeX
@inproceedings{AschieriCG16,
  title = {Gödel logic: From natural deduction to parallel computation},
  author = {Federico Aschieri and Agata Ciabattoni and Francesco A. Genco},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005076}
}