paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Arboreal Categories: An Axiomatic Theory of Resources

Arboreal 范畴:资源的公理化理论
LMCS vol.Volume 19, Issue 32023匹配度 2/10 · 该论文是有限模型论与范畴论的理论工作,研究公理化资源、双模拟与博弈,未涉及 LLM/Agent、静态分析工具、浮点程序分析或贝叶斯程序分析,仅与形式化验证的逻辑基础有较间接的联系。引用 7 inbox
Samson Abramsky, Luca Reggio
crossref: 2026-09-10

AI 速览

一句话:提出公理化的 Arboreal 范畴与覆盖,统一有限模型论中的双模拟、来回博弈及资源计数。

本文针对博弈余单子(game comonads)给出的有限模型论无语法范畴方法,提出公理化框架以刻画余代数范畴的核心性质。作者引入 Arboreal 范畴,使其具有内在过程结构,从而可定义双模拟、来回博弈等动态概念以及博弈轮数等资源概念;并通过资源索引的余单子伴随(Arboreal cover)将这类动态结构与外延或静态结构相联系。该框架在关系结构上得到应用,恢复了 pebbling、Ehrenfeucht-Fraïssé 与模态双模拟博弈的余单子构造,表明有限模型论和描述复杂性中的许多基本概念均可视为 Arboreal cover 的实例。

问题
如何在不依赖具体语法的情况下,公理化地刻画博弈余单子所编码的有限模型论与资源概念。
方法
引入具有内在过程结构的 Arboreal 范畴,以及资源索引的余单子伴随式 Arboreal cover,将动态结构与静态外延结构关联。
评估
在关系结构上实例化,恢复 pebbling、Ehrenfeucht-Fraïssé 和模态双模拟博弈的余单子构造,并统一有限模型论与描述复杂性的若干基本概念。
原文摘要(Abstract)

Game comonads provide a categorical syntax-free approach to finite model theory, and their Eilenberg-Moore coalgebras typically encode important combinatorial parameters of structures. In this paper, we develop a framework whereby the essential properties of these categories of coalgebras are captured in a purely axiomatic fashion. To this end, we introduce arboreal categories, which have an intrinsic process structure, allowing dynamic notions such as bisimulation and back-and-forth games, and resource notions such as number of rounds of a game, to be defined. These are related to extensional or "static" structures via arboreal covers, which are resource-indexed comonadic adjunctions. These ideas are developed in a general, axiomatic setting, and applied to relational structures, where the comonadic constructions for pebbling, Ehrenfeucht-Fra\"iss\'e and modal bisimulation games recently introduced by Abramsky et al. are recovered, showing that many of the fundamental notions of finite model theory and descriptive complexity arise from instances of arboreal covers.

链接与引用

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

BibTeX
@article{paperbot2197,
  title = {Arboreal Categories: An Axiomatic Theory of Resources},
  author = {Samson Abramsky and Luca Reggio},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 3},
  year = {2023},
  doi = {10.46298/lmcs-19(3:14)2023}
}