paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Strategies as Resource Terms, and their Categorical Semantics

策略作为资源项及其范畴语义
LMCS vol.Volume 21, Issue 42025匹配度 2/10 · 该论文属于纯形式语义/范畴论与资源演算、Hyland-Ong 博弈语义方向,虽与程序语言理论相关,但未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心研究方向。引用 3 inbox
Lison Blondeau-Patissier, Pierre Clairambault, Lionel Vaux Auclair
crossref: 2026-09-10

AI 速览

一句话:通过 augmentation 直接建立正规资源项与 Hyland-Ong 策略的对应,并给出归约不变的指称模型与资源范畴。

本文重访 Tsukada 与 Ong 的结果:简单类型、正规且 eta-long 的资源项对应 Hyland-Ong 博弈中的 play(在同伦意义下)。原证明间接依赖关系模型的单射性,动态性仅通过关系模型与正规项复合体现。作者引入称为 augmentation 的因果结构作为同伦下 play 的规范代表,直接显式刻画与正规资源项的联系;进而将对应扩展到资源项归约,以 augmentation 加权和作为策略,构造归约下不变的资源演算指称模型;最后提出 resource category,类比 differential categories 之于 differential lambda-calculus。

问题
原结果虽建立正规 eta-long 资源项与 Hyland-Ong play 在同伦下的对应,但证明间接,且未直接处理资源项归约的动态性。
方法
引入 augmentations 作为同伦下 play 的规范代表,将策略视为 augmentations 的加权和,并构造 resource category 作为资源演算的范畴模型。
评估
理论证明与范畴构造;关键结果为直接显式的对应、对归约不变的指称模型,以及类比 differential categories 的 resource category。
原文摘要(Abstract)

As shown by Tsukada and Ong, simply-typed, normal and eta-long resource terms correspond to plays in Hyland-Ong games, quotiented by Melliès' homotopy equivalence. The original proof of this inspiring result is indirect, relying on the injectivity of the relational model w.r.t. both sides of the correspondence -- in particular, the dynamics of the resource calculus is taken into account only via the compatibility of the relational model with the composition of normal terms defined by normalization. In the present paper, we revisit and extend these results. Our first contribution is to restate the correspondence by considering causal structures we call augmentations, which are canonical representatives of Hyland-Ong plays up to homotopy. This allows us to give a direct and explicit account of the connection with normal resource terms. As a second contribution, we extend this account to the reduction of resource terms: building on a notion of strategies as weighted sums of augmentations, we provide a denotational model of the resource calculus, invariant under reduction. A key step -- and our third contribution -- is a categorical model we call a resource category, which is to the resource calculus what differential categories are to the differential lambda-calculus.

链接与引用

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

BibTeX
@article{Blondeau-Patissier23,
  title = {Strategies as Resource Terms, and their Categorical Semantics},
  author = {Lison Blondeau-Patissier and Pierre Clairambault and Lionel Vaux Auclair},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 4},
  year = {2025},
  doi = {10.46298/lmcs-21(4:9)2025}
}