论文标题
游戏ComOnads和广义量词
Game Comonads & Generalised Quantifiers
论文作者
论文摘要
由Abramsky，Dawar和Wang引入的游戏Comonads并由Abramsky和Shah开发，为某些有限模型理论中常见的扰流板模型游戏提供了有趣的分类语义。特别是它们在单方面和双面游戏之间露出连接，以及诸如TreeWidth和Treedepth之类的参数以及分解的相应概念。在本文中，我们将游戏ComoNADS的领域扩展到具有广义量词的逻辑。特别是，我们介绍了一个由两个参数$ n \ leq k $分级的comonad，因此，由此产生的kleisli类别中的同构是在Hella的$ n $ bijection游戏中赢得了$ k $ ebbles的重复策略。我们定义了该游戏的单方面版本，该版本使我们能够为带有广义量词的许多逻辑提供分类语义。我们还给出了从结构中出现的树木分解的新颖概念。
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.
