一句话：刻画 arb-invariant FO+MOD_p 的 Gaifman 与 Hanf 局部性，并给出正负结果及其与布尔电路的联系。
本文研究带模 p 计数量词的一阶逻辑 FO+MOD_p 在任意数值谓词下的 Gaifman 局部性与 Hanf 局部性。作者要求公式的有效性不依赖于数值谓词的具体解释，称此类公式为 arb-invariant 公式。论文给出 arb-invariant FO+MOD_p 局部性与非局部性的完整图景：在所有有限结构上，对任意 p >= 2，该逻辑既不是 Hanf 局部也不是 Gaifman 局部（相对于亚线性局部半径）；但当 p 为奇素数幂时，它具有多对数局部半径的弱 Gaifman 局部性。在字符串结构上，对奇素数幂 p，该逻辑同时具有多对数局部半径的 Hanf 局部性与 Gaifman 局部性。负结果基于 Niemistö 博士论文中 order-invariant FO+MOD_p 公式的例子，正结果则利用 FO+MOD_p 与由 NOT 门及任意扇入 AND、OR、MOD_p 门构成的布尔电路之间的紧密联系。
We study Gaifman locality and Hanf locality of an extension of first-order logic with modulo p counting quantifiers (FO+MOD_p, for short) with arbitrary numerical predicates. We require that the validity of formulas is independent of the particular interpretation of the numerical predicates and refer to such formulas as arb-invariant formulas. This paper gives a detailed picture of locality and non-locality properties of arb-invariant FO+MOD_p. For example, on the class of all finite structures, for any p >= 2, arb-invariant FO+MOD_p is neither Hanf nor Gaifman local with respect to a sublinear locality radius. However, in case that p is an odd prime power, it is weakly Gaifman local with a polylogarithmic locality radius. And when restricting attention to the class of string structures, for odd prime powers p, arb-invariant FO+MOD_p is both Hanf and Gaifman local with a polylogarithmic locality radius. Our negative results build on examples of order-invariant FO+MOD_p formulas presented in Niemist\"o's PhD thesis. Our positive results make use of the close connection between FO+MOD_p and Boolean circuits built from NOT-gates and AND-, OR-, and MOD_p- gates of arbitrary fan-in.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{HarwathS16,
title = {On the locality of arb-invariant first-order formulas with modulo counting quantifiers},
author = {Frederik Harwath and Nicole Schweikardt},
journal = {Logical Methods in Computer Science},
volume = {Volume 12, Issue 4},
year = {2017},
doi = {10.2168/lmcs-12(4:8)2016}
}