paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Interaction Graphs: Exponentials

交互图:指数连接词
LMCS vol.Volume 15, Issue 32019匹配度 1/10 · 论文属于线性逻辑与几何交互(GoI)的纯形式语义研究,讨论指数连接词与ELL模型,与用户关注的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析等交叉方向没有直接关联,仅在最宽泛的PL形式化理论层面相关。引用 7 inbox
Thomas Seiller
crossref: 2026-09-10

AI 速览

一句话:本文将交互几何扩展到指数连接词,使用 graphings 为带二阶量化的初等线性逻辑 ELL 构造 GoI 模型。

本文是交互几何(Geometry of Interaction, GoI)系列工作的第四篇,目标是在 Girard 的 GoI 纲领下系统发展一种组合式方法,为线性逻辑构造能刻画切消动态的可实现性模型。前作已建立交互图框架,本文处理其中最困难的部分:指数连接词(! 与 ?)的语义定义。作者采用此前引入的 graphings——图的一种推广——作为核心结构,说明如何为带二阶量化的初等线性逻辑(Elementary Linear Logic, ELL)定义 GoI 模型。ELL 是线性逻辑的子系统,可刻画初等时间可计算函数类。因此,该工作将 GoI/交互图方法推进到可表达指数与二阶量化的逻辑片段,并为指数连接词提供组合式语义。

问题
如何在 Girard 的 Geometry of Interaction 框架中定义指数连接词,从而为线性逻辑构造能刻画切消动态的可实现性模型。
方法
在交互图框架中采用 graphings(图的一种推广)作为核心结构,构造带二阶量化的初等线性逻辑 ELL 的 GoI 语义。
评估
以理论构造与语义分析为主,通过定义带二阶量化的 ELL 的 GoI 来展示该方法的适用性。
原文摘要(Abstract)

This paper is the fourth of a series exposing a systematic combinatorial approach to Girard's Geometry of Interaction (GoI) program. The GoI program aims at obtaining particular realisability models for linear logic that accounts for the dynamics of cut-elimination. This fourth paper tackles the complex issue of defining exponential connectives in this framework. For that purpose, we use the notion of \emph{graphings}, a generalisation of graphs which was defined in earlier work. We explain how to define a GoI for Elementary Linear Logic (ELL) with second-order quantification, a sub-system of linear logic that captures the class of elementary time computable functions.

链接与引用

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

BibTeX
@article{paperbot760,
  title = {Interaction Graphs: Exponentials},
  author = {Thomas Seiller},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 3},
  year = {2019},
  doi = {10.23638/lmcs-15(3:25)2019}
}