TY  - JOUR
A1  - Harwath, Frederik
A1  - Schweikardt, Nicole
T1  - On the locality of arb-invariant first-order formulas with modulo counting quantifiers
T2  - Logical methods in computer science
N2  - We study Gaifman locality and Hanf locality of an extension of first-order logic with modulo p counting quantifiers (FO+MODp , 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+MODp . For example, on the class of all finite structures, for any p 2, arb-invariant FO+MODp 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+MODp is both Hanf and Gaifman local with a polylogarithmic locality radius. Our negative results build on examples of order-invariant FO+MODp formulas presented in Niemist ̈o’s PhD thesis. Our positive results make use of the close connection between FO+MODp and Boolean circuits built from NOT-gates and AND-, OR-, and MOD p - gates of arbitrary fan-in.
KW  - Computer science
KW  - Logic in computer science
KW  - F.4.1
KW  - H.2.3
KW  - F.1.3
Y1  - 2017
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/43829
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-438293
SN  - 1860-5974
N1  - This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany
VL  - 12
IS  - 4, Art. 8
SP  - 1
EP  - 34
PB  - Department of Theoretical Computer Science, Technical University of Braunschweig
CY  - Braunschweig
ER  -