The pebbling comonad in Finite Model Theory
The pebbling comonad in Finite Model Theory
复制标题
有限模型理论中的卵石共生体
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Pengming Wang
中科院分区：
文献类型：
--
作者：
S. Abramsky;A. Dawar;Pengming Wang
Pebble博弈是研究有限模型理论、约束满足和数据库理论的有力工具。单子和共单子是范畴论的基本概念，广泛应用于计算语义学和现代函数式程序设计中。我们证明了存在的k-pebble游戏有一个自然的共单因子公式。在k-卵石博弈中，复制者对于结构A和B的获胜策略等价于在这个comonad的coKleisli范畴中从A到B的态射。这导致了有限模型论中一些中心概念的共单元特征：·共克莱斯利范畴中的同构描述了具有计数量词的k变量逻辑中的基本等价。·对称博弈对应于全k-变量逻辑中的等价性也得到了刻画。·结构A的树宽用它的余代数数来表征：对于k-卵石余单子，在A上存在余代数结构的最小k。· Co-Kleisli态射被用来刻画强相容性，并给出一个Cai-Fürer-Immerman结构的解释。·k-pebbling comonad也被用来给一个新的模态算子赋予语义。这些结果为计算机科学中逻辑的两个领域之间的一些新的和有前途的联系奠定了基础，这两个领域在很大程度上是不相交的：（1）有限和算法模型理论，以及（2）计算的语义和范畴结构。
Pebble games are a powerful tool in the study of finite model theory, constraint satisfaction and database theory. Monads and comonads are basic notions of category theory which are widely used in semantics of computation and in modern functional programming. We show that existential k-pebble games have a natural comonadic formulation. Winning strategies for Duplicator in the k-pebble game for structures A and B are equivalent to morphisms from A to B in the coKleisli category for this comonad. This leads on to comonadic characterisations of a number of central concepts in Finite Model Theory: • Isomorphism in the co-Kleisli category characterises elementary equivalence in the k-variable logic with counting quantifiers. • Symmetric games corresponding to equivalence in full k-variable logic are also characterized. • The treewidth of a structure A is characterised in terms of its coalgebra number: the least k for which there is a coalgebra structure on A for the k-pebbling comonad. • Co-Kleisli morphisms are used to characterize strong consistency, and to give an account of a Cai-Fürer-Immerman construction. • The k-pebbling comonad is also used to give semantics to a novel modal operator. These results lay the basis for some new and promising connections between two areas within logic in computer science which have largely been disjoint: (1) finite and algorithmic model theory, and (2) semantics and categorical structures of computation.