Lov´asz-Type Theorems and Game Comonads (extended abstract)
Lov´asz-Type Theorems and Game Comonads (extended abstract)
复制标题
Lov´asz 型定理和博弈共同点（扩展摘要）
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tomás Jakl
中科院分区：
文献类型：
--
作者：
A. Dawar;Tomás Jakl
Lov 'asz（1967）证明了两个有限关系结构A和B是同构的当且仅当，对于任意有限结构C，从C到A的同态的个数与从C到B的同态的个数相同。不久之后，Pultr（1973）证明了这一事实的绝对概括。我们提出了一个新的范畴公式，它适用于任何具有推出和适当的因式分解系统的局部有限范畴。作为这个一般定理的特殊情况，我们得到了Lov 'asz'定理的两个变体：Dvo Schirak（2010）的结果和Grohe（2020）的结果。他们都证明了图关于一阶逻辑的片段的不可逆性，其中计数量化器是从树宽度的图的同态计数（分别是）。树深度）至多k。我们的范畴公式与这些结果的联系是通过Abramsky等人（2017，2018）的游戏comonads获得的。我们还提出了模态逻辑中同态计数的新应用。
Lov´asz (1967) showed that two finite relational structures A and B are isomorphic if, and only if, the number of homomorphisms from C to A is the same as the number of homomorphisms from C to B for any finite structure C . Soon after, Pultr (1973) proved a categorical generalisation of this fact. We propose a new categorical formulation, which applies to any locally finite category with pushouts and a proper factorisation system. As special cases of this general theorem, we obtain two variants of Lov ´ asz’ theorem: the result by Dvo ˇ r ´ ak (2010) and the result of Grohe (2020). They both characterise the indistinguishability of graphs with respect to a fragment of first-order logic with counting quantifiers in terms of homomorphism counts from graphs of tree-width (resp. tree-depth) at most k . The connection of our categorical formulation with these results is obtained by means of the game comonads of Abramsky et al. (2017, 2018) We also present a novel application to homomorphism counts in modal logic.
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Adam Ó Conghaile
通讯作者：
Adam Ó Conghaile