Harwath, Frederik and Schweikardt, Nicole - On the locality of arb-invariant first-order formulas with modulo counting quantifiers

lmcs:2620 - Logical Methods in Computer Science, December 28, 2016, Volume 12, Issue 4
On the locality of arb-invariant first-order formulas with modulo counting quantifiers

Authors: Harwath, Frederik and Schweikardt, Nicole

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.


Source : oai:arXiv.org:1611.07716
DOI : 10.2168/LMCS-12(4:8)2016
Volume: Volume 12, Issue 4
Published on: December 28, 2016
Submitted on: December 28, 2016
Keywords: Computer Science - Logic in Computer Science,F.4.1,H.2.3,F.1.3


Share

Browsing statistics

This page has been seen 79 times.
This article's PDF has been downloaded 50 times.