paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Causal Graph Dynamics and Kan Extensions

因果图动力学与 Kan 扩张
LMCS vol.Volume 22, Issue 12026匹配度 1/10 · 该论文是纯范畴论与因果图动力学的形式语义工作,讨论 Kan 扩张和单调子类,不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户研究画像的核心问题几乎没有交集。引用 2 inbox
Luidnel Maignan, Antoine Spicher
crossref: 2026-09-10

AI 速览

一句话:证明因果图动力学可表达为 Kan 扩张,并揭示单调子类及其普遍性。

Global Transformations 形式化声称能刻画局部、同步且确定的空间变换,并已在网格细分、Lindenmayer 系统和元胞自动机等模型上得到验证;其核心是用范畴论、特别是 Kan 扩张从局部行为导出全局行为。另一方面,因果图动力学(Causal Graph Dynamics, CGD)以同步确定方式变换端口图,但此前未被纳入该框架。本文证明该声称对 CGD 同样成立:通过多种方式将 CGD 表达为 Kan 扩张,并揭示其不同特征。文中还发现单调 Causal Graph Dynamics 这一有意思的类,并证明其在一般 Causal Graph Dynamics 中具有普遍性。

问题
Global Transformations 的普遍性声称尚未在因果图动力学(CGD)上得到检验。
方法
用范畴论中的 Kan 扩张对 CGD 进行多种表达,以从局部变换导出全局行为并比较不同特征。
评估
通过理论证明和构造性分析,说明该声称对 CGD 成立,并发现单调 CGD 及其在一般 CGD 中的普遍性。
原文摘要(Abstract)

On the one side, the formalism of Global Transformations comes with the claim of capturing any transformation of space that is local, synchronous and deterministic. The claim has been proven for different classes of models such as mesh refinements from computer graphics, Lindenmayer systems from morphogenesis modeling and cellular automata from biological, physical and parallel computation modeling. The Global Transformation formalism achieves this by using category theory for its genericity, and more precisely the notion of Kan extension to determine the global behaviors based on the local ones. On the other side, Causal Graph Dynamics describe the transformation of port graphs in a synchronous and deterministic way and has not yet being tackled. In this paper, we show the precise sense in which the claim of Global Transformations holds for them as well. This is done by showing different ways in which they can be expressed as Kan extensions, each of them highlighting different features of Causal Graph Dynamics. Along the way, this work uncovers the interesting class of Monotonic Causal Graph Dynamics and their universality among General Causal Graph Dynamics.

链接与引用

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

BibTeX
@article{MaignanS24,
  title = {Causal Graph Dynamics and Kan Extensions},
  author = {Luidnel Maignan and Antoine Spicher},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 1},
  year = {2026},
  doi = {10.46298/lmcs-22(1:16)2026}
}