paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Type Isomorphisms for Multiplicative-Additive Linear Logic

乘法-加法线性逻辑的类型同构
LMCS vol.Volume 21, Issue 42025匹配度 1/10 · 该论文研究线性逻辑中的类型同构与证明网/序列演算,属于纯类型论与形式语义,未涉及静态分析、Agentic 程序、LLM/Agent 或浮点/贝叶斯程序分析等用户核心方向。引用 0 inbox
Rémi Di Guardia, Olivier Laurent
crossref: 2026-09-10

AI 速览

一句话:刻画乘法-加法线性逻辑(MALL)中的类型同构,给出含分配律与消去律的更丰富等式理论。

本文刻画了线性逻辑的乘法-加法片段(MALL)中的类型同构,从而也刻画了带有限积的 *-autonomous 范畴中的同构,扩展了 Balat 与 Di Cosmo 关于乘法片段的结果。该刻画导出比乘法情形丰富得多的等式理论,包括分配律和消去律。对于无单位情形,作者依赖 Hughes 与 Van Glabbeek 引入的证明网语法;对于含所有单位的完整 MALL,则通过研究切消与规则交换,使用序列演算将结果推广到完整系统。论文给出了 MALL 类型同构的特征,并揭示了线性逻辑中由加法结构带来的新同构规律。

问题
线性逻辑乘法片段的类型同构已有 Balat–Di Cosmo 刻画,但包含加法与单位的 MALL 中同构规律尚不清楚;该问题也对应带有限积的 *-autonomous 范畴中的同构。
方法
论文在无单位情形使用 Hughes–Van Glabbeek 的证明网语法,在完整 MALL 情形则借助序列演算,并研究切消与规则交换以处理所有单位。
评估
这是一项理论工作,评估体现为对 MALL(及相应范畴)类型同构的刻画与由分配律、消去律等构成的等式理论的推导和证明。
原文摘要(Abstract)

We characterize type isomorphisms in the multiplicative-additive fragment of linear logic (MALL), and thus in *-autonomous categories with finite products, extending a result for the multiplicative fragment by Balat and Di Cosmo. This yields a much richer equational theory involving distributivity and cancellation laws. The unit-free case is obtained by relying on the proof-net syntax introduced by Hughes and Van Glabbeek. We use the sequent calculus to extend our results to full MALL, including all units, thanks to a study of cut-elimination and rule commutations.

链接与引用

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

BibTeX
@article{paperbot3346,
  title = {Type Isomorphisms for Multiplicative-Additive Linear Logic},
  author = {Rémi Di Guardia and Olivier Laurent},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 4},
  year = {2025},
  doi = {10.46298/lmcs-21(4:24)2025}
}