The Pebble-Relation Comonad in Finite Model Theory
The Pebble-Relation Comonad in Finite Model Theory
复制标题
有限模型理论中的卵石关系共同点
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nihil Shah
中科院分区：
文献类型：
--
作者：
Yoàv Montacute;Nihil Shah
由Abramsky、Dawar和Wang提出的卵石共性从有限模型理论对k-卵石博弈进行了分类解释。鹅卵石公数的coKleisli范畴规定了无限k变量逻辑的不同片段和扩展下的等价性。此外，在这个卵石公共上的余代数表征了树的宽度并对应于树的分解。本文引入了表征路径宽度的卵石关系公数，它的余代数对应于路径分解。进一步证明了在该公域中coKleisli态射的存在性等价于k变量无穷逻辑的受限连接片段中的真值保持。我们使用Dalmau的鹅卵石关系游戏和一个同等的一体化鹅卵石游戏来做到这一点。然后，我们通过一个带有隐藏鹅卵石放置的一体化鹅卵石游戏的双目标版本，对相应的coKleisli同态提供了类似的处理。最后，我们给出了一个新的Lovász-type定理，它将路径宽度与带有计数量词的k变量无限逻辑的受限连接片段联系起来。
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 with a hidden pebble placement. Finally, we show as a consequence a new Lovász-type theorem relating pathwidth to the restricted conjunction fragment of k-variable infinitary logic with counting quantifiers.
影响因子：
0.6
作者：
Abramsky S
通讯作者：
Abramsky S
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Adam Ó Conghaile
通讯作者：
Adam Ó Conghaile
Lovász 型定理和博弈共同点
DOI：
10.1109/lics52264.2021.9470609
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Dawar A
通讯作者：
Dawar A