paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Game Comonads & Generalised Quantifiers

游戏余单子与广义量词
LMCS vol.Volume 20, Issue 32024匹配度 1/10 · 该论文属于范畴语义、有限模型论与描述逻辑中的游戏余单子研究,核心是 Hella n-双射 k-石子游戏和树分解的形式化刻画;与用户关注的 PL/AI 交叉(Agentic 程序静态分析、LLM 辅助形式化验证、浮点/贝叶斯程序分析及其与 LLM 的结合)几乎没有直接关联。引用 0 inbox
Adam Ó Conghaile, Anuj Dawar
crossref: 2026-09-10

AI 速览

一句话:将游戏余单子推广到含广义量词的逻辑,用双参数余单子刻画 Hella n-双射 k-石子游戏,并给出范畴语义与新型树分解。

本文研究有限模型论中 Spoiler-Duplicator 游戏的范畴语义。以往游戏余单子主要处理一阶逻辑及若干受限逻辑,本文则将其扩展到带广义量词的逻辑。作者引入一个由 n≤k 两个参数分级的余单子,证明其 Kleisli 范畴中的同构恰对应 Hella 的 n-双射游戏中带 k 个石子的 Duplicator 获胜策略。接着定义该游戏的一侧版本,从而为多种含广义量词的逻辑给出范畴语义。构造还产生了一种新的树分解概念,将余单子参数与分解宽度/深度等参数联系起来。

问题
如何为有限模型论中带广义量词的逻辑及其 Spoiler-Duplicator 博弈提供统一的范畴语义,并刻画 Hella 的 n-双射 k-石子游戏。
方法
构造由 n≤k 分级的新游戏余单子,并定义单侧游戏,利用 Kleisli 范畴同构对应 Duplicator 获胜策略。
评估
以范畴论证明与游戏等价性定理进行评估,展示其对多类广义量词逻辑的覆盖,并导出新的树分解概念。
原文摘要(Abstract)

Game comonads, introduced by Abramsky, Dawar and Wang and developed by Abramsky and Shah, give an interesting categorical semantics to some Spoiler-Duplicator games that are common in finite model theory. In particular they expose connections between one-sided and two-sided games, and parameters such as treewidth and treedepth and corresponding notions of decomposition. In the present paper, we expand the realm of game comonads to logics with generalised quantifiers. In particular, we introduce a comonad graded by two parameters $n \leq k$ such that isomorphisms in the resulting Kleisli category are exactly Duplicator winning strategies in Hella's $n$-bijection game with $k$ pebbles. We define a one-sided version of this game which allows us to provide a categorical semantics for a number of logics with generalised quantifiers. We also give a novel notion of tree decomposition that emerges from the construction.

链接与引用

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

BibTeX
@article{paperbot2741,
  title = {Game Comonads & Generalised Quantifiers},
  author = {Adam Ó Conghaile and Anuj Dawar},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 3},
  year = {2024},
  doi = {10.46298/lmcs-20(3:8)2024}
}