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