paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Deconstructing the Calculus of Relations with Tape Diagrams

用带图(Tape Diagrams)解构关系演算
POPL 7(POPL)2023匹配度 1/10 · 论文研究范畴论与关系演算的图解语言,属于形式语义/代数理论,与用户关注的 LLM/Agent、静态分析、浮点程序分析、贝叶斯程序分析等方向没有直接关联。引用 7 inbox
Filippo Bonchi, Alessandro Di Giorgio, Alessio Santamaria
crossref: 2026-09-10

AI 速览

一句话:提出带图,为有限双积的 rig 范畴给出可靠且完备的图解语言,并用于关系演算。

本文关注带有限双积的 rig 范畴:这类范畴具有两个 monoidal product,其中一个是 biproduct,另一个对前者满足分配律。作者提出 tape diagrams,一种可靠且完备的图解语言,可直观理解为“string diagrams 的 string diagrams”,用以在这些范畴中进行等式推理。该语言为 rig 范畴提供了图解演算,并给出其相对于范畴公理的可靠性与完备性。作者以 Tarski 关系演算的正片段为测试对象,说明该图解语言能有效刻画关系演算中的推理。结果表明,tape diagrams 能统一处理双积与分配结构,并为关系演算提供直观的图示推理方式。

问题
如何为带有限双积的 rig 范畴(一个积为 biproduct,另一个对之分配)提供一种直观、可操作的图解推理语言。
方法
引入 tape diagrams,将 string diagrams 嵌套为 string diagrams,并证明其相对于该类范畴的可靠性与完备性。
评估
以 Tarski 关系演算的正片段为案例,检验该图解语言在关系推理中的表达效果。
原文摘要(Abstract)

Rig categories with finite biproducts are categories with two monoidal products, where one is a biproduct and the other distributes over it. In this work we present tape diagrams, a sound and complete diagrammatic language for these categories, that can be intuitively thought as string diagrams of string diagrams. We test the effectiveness of our approach against the positive fragment of Tarski's calculus of relations.

链接与引用

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

BibTeX
@article{paperbot2108,
  title = {Deconstructing the Calculus of Relations with Tape Diagrams},
  author = {Filippo Bonchi and Alessandro Di Giorgio and Alessio Santamaria},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {POPL},
  year = {2023},
  doi = {10.1145/3571257}
}