paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Cartesian Closed Bicategory of Thin Spans of Groupoids

群胚的 thin spans 笛卡尔闭双范畴
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 2/10 · 该论文属于纯范畴论形式语义,研究群胚 thin spans 双范畴及其 Kleisli 双范畴的笛卡尔闭性,与用户画像中 PL→AI 静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向无直接关联,仅可作为 PL 理论基础背景。引用 7 inbox
Pierre Clairambault, Simon Forest
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出群胚的 thin spans 双范畴,并证明其 Kleisli 双范畴在伪余单子 ! 下是笛卡尔闭的。

语言的双范畴语义需要区分执行迹,并将归约路径解释为同构,但已有广义结构物种、同伦模板博弈等模型因语义个体可携带任意对称性而呈饱和、解释被膨胀。本文提出“薄”模型:群胚的 thin spans 双范畴。其对象为带额外结构的群胚,态射为跨度,按普通拉回复合,恒等为恒等跨度;2-胞是使诱导三角形仅在同构意义下交换的跨度态射。作者构造双范畴 Thin,为其配备伪余单子 !,并证明 Kleisli 双范畴 Thin! 是笛卡尔闭的。模型借鉴 thin concurrent games:项的解释不携带对称性,而语义个体通过双正交性满足一个精细不变式,从而在对称性下不变。

问题
如何为编程语言建立 proof-relevant 的双范畴模型,既保留执行迹与归约路径信息,又避免饱和模型中由任意对称性导致的语义膨胀。
方法
引入群胚的 thin spans 双范畴 Thin;对象为带额外结构的群胚,态射为经拉回复合的跨度,2-胞仅在同构意义下交换;用双正交性定义薄不变式,并为其配备伪余单子 !。
评估
以范畴构造与数学证明评估:构造 Thin,配备伪余单子 !,并证明 Kleisli 双范畴 Thin! 是笛卡尔闭的。
原文摘要(Abstract)

Recently, there has been growing interest in bicategorical models of programming languages, which are "proof-relevant" in the sense that they keep distinct account of execution traces leading to the same observable outcomes, while assigning a formal meaning to reduction paths as isomorphisms.In this paper we introduce a new model, a bicategory called thin spans of groupoids. Conceptually it is close to Fiore et al.’s generalized species of structures and to Melliès’ homotopy template games, but fundamentally differs as to how replication of resources and the resulting symmetries are treated. Where those models are saturated – the interpretation is inflated by the fact that semantic individuals may carry arbitrary symmetries – our model is thin, drawing inspiration from thin concurrent games: the interpretation of terms carries no symmetries, but semantic individuals satisfy a subtle invariant defined via biorthogonality, which guarantees their invariance under symmetry.We first build the bicategory Thin of thin spans of groupoids. Its objects are certain groupoids with additional structure, its morphisms are spans composed via plain pullback with identities the identity spans, and its 2-cells are span morphisms making the induced triangles commute only up to natural isomorphism. We then equip Thin with a pseudocomonad !, and finally show that the Kleisli bicategory Thin! is cartesian closed.

链接与引用

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

BibTeX
@inproceedings{ClairambaultF23,
  title = {The Cartesian Closed Bicategory of Thin Spans of Groupoids},
  author = {Pierre Clairambault and Simon Forest},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175754}
}