paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Counting Bounded Tree Depth Homomorphisms

计数有界树深度同态
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 该论文属于有限模型论/逻辑与自动机方向，研究计数一阶逻辑、同态计数与有界树深图之间的等价刻画，与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关系。引用 1 inbox
Martin Grohe
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：证明两个图的计数一阶逻辑量词秩≤k等价，当且仅当它们在树深度≤k的图上同态计数不可区分。

论文研究有限图上带计数量词的一阶逻辑（FOC）的区分能力。核心结果是：图 G 与 G' 满足所有量词秩至多 k 的计数一阶逻辑句子，当且仅当它们在所有树深度至多 k 的图类上同态不可区分；后者指对每个该类中的图 F，从 F 到 G 的同态数与到 G' 的同态数相等。该定理用同态计数刻画了计数一阶逻辑的 k-量词秩等价，将逻辑等价与有界树深度图上的同态计数联系起来，为有限模型论中计数逻辑与图同态计数关系提供了精确刻画。

问题
刻画带计数的一阶逻辑在量词秩至多 k 时能区分的图，并寻找与同态计数相关的等价判据。
方法
证明 G 与 G' 满足相同 k-量词秩计数一阶逻辑句子，当且仅当它们在树深度至多 k 的图类上所有同态计数相等。
评估
以数学定理形式给出等价性证明，不涉及实验评估。
原文摘要（Abstract）

We prove that graphs G, G' satisfy the same sentences of first-order logic with counting of quantifier rank at most k if and only if they are homomorphism-indistinguishable over the class of all graphs of tree depth at most k. Here G, G' are homomorphism-indistinguishable over a class F of graphs if for each graph F ϵ F, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5517,
  title = {Counting Bounded Tree Depth Homomorphisms},
  author = {Martin Grohe},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394739}
}