paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Lovász-Type Theorems and Game Comonads

Lovász 型定理与博弈余单子
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 该论文属于纯范畴论与逻辑理论,研究 Lovász 型定理、同态计数、Weisfeiler-Leman 与 game comonads,与用户关注的程序静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向没有直接交集。引用 2 inbox
Anuj Dawar, Tomas Jakl, Luca Reggio
crossref: 2026-09-12

AI 速览

一句话:提出一个范畴化 Lovász 定理,统一 Weisfeiler-Leman、计数逻辑与树深度等同态计数刻画,并给出模态逻辑新应用。

Lovász 曾证明有限关系结构的同构可由任意有限结构的同态计数刻画,Pultr 随后给出范畴推广。本文提出一种新的范畴表述,适用于具有 pushout 与合适因子分解系统的局部有限范畴。借助 Abramsky 等人的博弈余单子,该定理可导出两类 Lovász 型结果:Dvořák 用树宽不超过 k 的图的同态计数刻画 k 维 Weisfeiler-Leman 等价,以及 Grohe 用树深不超过 k 的图的同态计数刻画带计数一阶逻辑且量词深度为 k 的等价。作者还将该框架应用于模态逻辑中的同态计数,展示其统一性与扩展性。

问题
如何以范畴论统一刻画 Lovász 定理及其在有限模型论中的多种变体,尤其是 Weisfeiler-Leman 等价、计数逻辑与模态逻辑的同态计数特征。
方法
引入适用于局部有限范畴、pushout 与 proper factorisation system 的新范畴表述,并通过博弈余单子把范畴结果与具体逻辑/组合等价连接起来。
评估
以定理证明方式推导 Dvořák 与 Grohe 的已知结果作为特例,并给出模态逻辑中同态计数的新应用;摘要未报告实验评估。
原文摘要(Abstract)

Lovász (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ász' theorem: the result by Dvořák (2010) that characterises equivalence of graphs in the k-dimensional Weisfeiler-Leman equivalence by homomorphism counts from graphs of tree-width at most k, and the result of Grohe (2020) characterising equivalence with respect to first-order logic with counting and quantifier depth k in terms of homomorphism counts from graphs of 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. We also present a novel application to homomorphism counts in modal logic.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot6233,
  title = {Lovász-Type Theorems and Game Comonads},
  author = {Anuj Dawar and Tomas Jakl and Luca Reggio},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470609}
}