paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Braids, Twists, Trace and Duality in Combinatory Algebras

组合代数中的辫、扭曲、迹与对偶
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 1/10 · 该论文属于范畴论与组合代数/形式语义的理论工作,研究 ribbon 组合代数、迹与对偶的等式刻画,与用户关注的静态分析、Agentic 程序、LLM 交叉、浮点程序分析及贝叶斯程序分析均无直接关联。虽然属于 PL 理论,但方向过于抽象且不涉及用户列出的核心问题。引用 3 inbox
Masahito Hasegawa, Serge Lechenne
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出 ribbon 组合代数,证明其与 ribbon 范畴中自反对象对应,并给出迹与对偶两种等式刻画。

本文研究一类组合代数——ribbon 组合代数(带状组合代数),旨在统一解释辫状无类型线性 lambda 演算与带框定向缠结。作者证明:ribbon 范畴中的任何自反对象都给出 ribbon 组合代数;反之,由 ribbon 组合代数可构造带自反对象的 ribbon 范畴,并恢复原组合代数。证明与等式刻画依赖 Hasegawa 近期提出的内部 PRO 构造。关键结果是 ribbon 组合代数具有两种等价特征:带 trace 组合子的平衡组合代数,以及带对偶的平衡组合代数。

问题
为辫状无类型线性 lambda 演算与带框定向缠结提供统一的组合代数语义,并刻画 ribbon 组合代数的等式理论。
方法
引入 ribbon 组合代数,利用 ribbon 范畴中的自反对象和内部 PRO 构造,建立组合代数与 ribbon 范畴之间的双向对应。
评估
以范畴论构造和表示定理进行理论验证,证明 ribbon 组合代数可等价地刻画为带 trace 的平衡组合代数或带对偶的平衡组合代数;无实现或实验评估。
原文摘要(Abstract)

We investigate a class of combinatory algebras, called ribbon combinatory algebras, in which we can interpret both the braided untyped linear lambda calculus and framed oriented tangles. Any reflexive object in a ribbon category gives rise to a ribbon combinatory algebra. Conversely, From a ribbon combinatory algebra, we can construct a ribbon category with a reflexive object, from which the combinatory algebra can be recovered. To show this, and also to give the equational characterisation of ribbon combinatory algebras, we make use of the internal PRO construction developed in Hasegawa's recent work. Interestingly, we can characterise ribbon combinatory algebras in two different ways: as balanced combinatory algebras with a trace combinator, and as balanced combinatory algebras with duality.

链接与引用

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

BibTeX
@inproceedings{HasegawaL24,
  title = {Braids, Twists, Trace and Duality in Combinatory Algebras},
  author = {Masahito Hasegawa and Serge Lechenne},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662098}
}