paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Companions, Causality and Codensity

Companion、因果性与余密度
LMCS vol.Volume 15, Issue 32019匹配度 2/10 · 该论文属于纯范畴论/共代数的共归纳证明增强,研究 companion、codensity monad 与因果性,不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,也未提供工业落地或 benchmark,与用户研究核心几乎没有交集。引用 2 inbox
Damien Pous, Jurriaan Rot
crossref: 2026-09-10

AI 速览

一句话:把共归纳 companion 提升到 universal coalgebra,证明 final distributive law 是 codensity monad,并用因果性刻画 up-to 技术。

论文研究抽象共归纳证明原理的增强技术。在完备格中,最大相容函数(companion)可统一多数 up-to 技术;本文将其提升到 universal coalgebra,对应概念为 final distributive law。作者证明:当 final distributive law 存在时它是一个 monad,并与给定函子的 final sequence 的 codensity monad 重合。在集合范畴上,他们引入一种抽象的因果性概念来刻画该 codensity monad。由此可恢复经典结果:在流上,由 distributive law 或 GSOS 规约定义的函数恰为因果函数。最后回到共归纳证明,证明任意因果函数都能产生有效的 up-to-context 技术。

问题
如何为共归纳证明原理的各类 up-to 增强给出统一的 coalgebra 语义基础,并解释 companion 与因果性、余密度 monad 的关系。
方法
在 universal coalgebra 中考察 final distributive law,证明其 monad 性质及与 final sequence 的 codensity monad 重合;在 Set 上引入抽象因果性进行刻画。
评估
以范畴论证明为主要评估,并在流与 GSOS 规约等实例上恢复因果函数的经典刻画及 up-to-context 有效性。
原文摘要(Abstract)

In the context of abstract coinduction in complete lattices, the notion of compatible function makes it possible to introduce enhancements of the coinduction proof principle. The largest compatible function, called the companion, subsumes most enhancements and has been proved to enjoy many good properties. Here we move to universal coalgebra, where the corresponding notion is that of a final distributive law. We show that when it exists, the final distributive law is a monad, and that it coincides with the codensity monad of the final sequence of the given functor. On sets, we moreover characterise this codensity monad using a new abstract notion of causality. In particular, we recover the fact that on streams, the functions definable by a distributive law or GSOS specification are precisely the causal functions. Going back to enhancements of the coinductive proof principle, we finally obtain that any causal function gives rise to a valid up-to-context technique.

链接与引用

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

BibTeX
@article{paperbot772,
  title = {Companions, Causality and Codensity},
  author = {Damien Pous and Jurriaan Rot},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 3},
  year = {2019},
  doi = {10.23638/lmcs-15(3:14)2019}
}