| Summary: | 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.
|
|---|