paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Pebble-Relation Comonad in Finite Model Theory

有限模型论中的卵石关系余单子
LMCS vol.Volume 20, Issue 22024匹配度 1/10 · 论文属于有限模型论、范畴论与卵石游戏,研究路径宽度与k变量无穷逻辑片段,与用户关注的静态分析、浮点/贝叶斯程序分析及 LLM/Agent 交叉均无直接关联。仅其形式逻辑背景与形式化验证有非常弱的联系。引用 3 inbox
Yoàv Montacute, Nihil Shah
crossref: 2026-09-10

AI 速览

一句话:引入卵石关系余单子,以其余代数刻画路径宽度,并建立其与 k 变量无穷逻辑受限合取片段的 Lovász 型定理。

Abramsky、Dawar 与 Wang 的卵石余单子为有限模型论中的 k-卵石游戏给出范畴解释:其余 Kleisli 范畴刻画无穷 k 变量逻辑不同片段的等价,余代数则对应树分解并刻画树宽度。本文引入卵石关系余单子,用其余代数对应路径分解并刻画路径宽度。作者证明该余单子中存在 coKleisli 态射当且仅当受限合取片段保持真值,证明借助 Dalmau 的卵石关系游戏及等价的 all-in-one 卵石游戏;并用双射版 all-in-one 游戏处理 coKleisli 同构。作为推论,得到将路径宽度与带计数量词的 k 变量无穷逻辑受限合取片段相联系的新 Lovász 型定理。

问题
如何在范畴框架下统一刻画有限模型论中的卵石游戏、逻辑片段与图宽度,特别是路径宽度?
方法
引入卵石关系余单子及其 coKleisli 范畴与余代数,并使用 Dalmau 卵石关系游戏及 all-in-one 卵石游戏建立态射/同构与逻辑真值保持的对应。
评估
通过范畴论与模型论证明:余代数对应路径分解并刻画路径宽度,coKleisli 态射等价于受限合取片段的真值保持,并导出带计数量词的 Lovász 型定理。
原文摘要(Abstract)

The pebbling comonad, introduced by Abramsky, Dawar and Wang, provides a categorical interpretation for the k-pebble games from finite model theory. The coKleisli category of the pebbling comonad specifies equivalences under different fragments and extensions of infinitary k-variable logic. Moreover, the coalgebras over this pebbling comonad characterise treewidth and correspond to tree decompositions. In this paper we introduce the pebble-relation comonad, which characterises pathwidth and whose coalgebras correspond to path decompositions. We further show that the existence of a coKleisli morphism in this comonad is equivalent to truth preservation in the restricted conjunction fragment of k-variable infinitary logic. We do this using Dalmau's pebble-relation game and an equivalent all-in-one pebble game. We then provide a similar treatment to the corresponding coKleisli isomorphisms via a bijective version of the all-in-one pebble game. Finally, we show as a consequence a new Lov\'asz-type theorem relating pathwidth to the restricted conjunction fragment of k-variable infinitary logic with counting quantifiers.

链接与引用

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

BibTeX
@article{paperbot2760,
  title = {The Pebble-Relation Comonad in Finite Model Theory},
  author = {Yoàv Montacute and Nihil Shah},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 2},
  year = {2024},
  doi = {10.46298/lmcs-20(2:9)2024}
}