paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the denotation of circular and non-wellfounded proofs in linear logic with fixed points

论带不动点的线性逻辑中循环与非良基证明的指称语义
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 2/10 · 论文属于纯证明论与范畴语义研究,讨论线性逻辑中带不动点的循环/非良基证明,与用户关注的静态分析、LLM/Agent 结合、浮点程序分析或贝叶斯程序分析均无直接关联。虽属形式化方法的基础理论,但未涉及工具实现、工业落地或问题驱动的分析场景。引用 0 inbox
Thomas Ehrhard, Farzad Jafarrahmani, Alexis Saurin
crossref: 2026-09-12

AI 速览

一句话:为带最小/最大不动点的线性逻辑 μLL 的非良基与循环证明建立范畴语义,并证明翻译保持解释。

本文研究带最小和最大不动点的线性逻辑 μLL 中非良基证明与循环证明的指称不变量,提出一套范畴语义。作者依次为三类对象给出语义:(i) 任意非良基预证明,无论是否有效;(ii) 有效预证明,利用范畴模型上的正交性构造刻画有效性;(iii) 循环强有效预证明,同时利用有效性和正则性归纳定义解释。随后分析从有穷证明到非良基证明、以及从(强有效)循环证明到有穷证明的翻译,证明这两个方向的翻译都保持语义解释。

问题
如何为 μLL 中非良基与循环证明提供统一的指称语义,并刻画有效性和正则性带来的语义约束。
方法
在范畴模型中分层构造语义:先处理任意预证明,再通过正交性处理有效预证明,最后对循环强有效预证明进行归纳解释。
评估
通过分析有穷证明与非良基/循环证明之间的翻译,证明其保持解释;工作以语义模型与元定理证明为评估手段。
原文摘要(Abstract)

This paper investigates the denotational invariants of non-wellfounded and circular proofs of linear logic with least and greatest fixed points, μLL, by providing a categorical semantics. More precisely the paper successively introduces semantics for (i) non-wellfounded pre-proofs, be they valid or not, (ii) valid pre-proofs exploiting their validity condition by considering an orthogonality construction on the given categorical model and finally (iii) circular strongly valid pre-proofs, exploiting both validity and regularity in order to define inductively the interpretation. Then the paper investigates the semantical content of the translation from finitary proofs to non-wellfounded proofs and, conversely, from (strongly valid) circular proofs to finitary proofs, showing that both translations preserve the interpretation.

链接与引用

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

BibTeX
@inproceedings{paperbot8655,
  title = {On the denotation of circular and non-wellfounded proofs in linear logic with fixed points},
  author = {Thomas Ehrhard and Farzad Jafarrahmani and Alexis Saurin},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00014}
}