论文标题
计数有限的树深度同构
Counting Bounded Tree Depth Homomorphisms
论文作者
论文摘要
我们证明，图形g，g'满足了一阶逻辑的相同句子，而量词排名最多为k，并且仅当它们在最多k的所有图中都可以与同构形成 - 与同构形式不同。在这里，如果对于C中的每个图F，则G'是在图中的同态与c的同构形式，那么从F到G的同构数量等于从F到G'的同构数量。
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 C of graphs if for each graph F in C, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'.
