Harwath, Frederik ;
Schweikardt, Nicole
On the locality of arbinvariant firstorder logic with modulo counting quantifiers
Abstract
We study Gaifman and Hanf locality of an extension of firstorder 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 arbinvariant formulas. This paper gives a detailed picture of locality and nonlocality properties of arbinvariant FO+MODp. For example, on the class of all finite structures, for any p >= 2, arbinvariant 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, arbinvariant FO+MODp is both Hanf and Gaifman local with a polylogarithmic locality radius. Our negative results build on examples of orderinvariant FO+MODp formulas presented in Niemistö's PhD thesis. Our positive results make use of the close connection between FO+MODp and Boolean circuits built from NOTgates and AND, OR, and MODpgates of arbitrary fanin.
BibTeX  Entry
@InProceedings{harwath_et_al:LIPIcs:2013:4208,
author = {Frederik Harwath and Nicole Schweikardt},
title = {{On the locality of arbinvariant firstorder logic with modulo counting quantifiers}},
booktitle = {Computer Science Logic 2013 (CSL 2013)},
pages = {363379},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897606},
ISSN = {18688969},
year = {2013},
volume = {23},
editor = {Simona Ronchi Della Rocca},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4208},
URN = {urn:nbn:de:0030drops42086},
doi = {10.4230/LIPIcs.CSL.2013.363},
annote = {Keywords: finite model theory, Gaifman and Hanf locality, firstorder logic with modulo counting quantifiers, orderinvariant and arbinvariant formulas, lower }
}
2013
Keywords: 

finite model theory, Gaifman and Hanf locality, firstorder logic with modulo counting quantifiers, orderinvariant and arbinvariant formulas, lower 
Seminar: 

Computer Science Logic 2013 (CSL 2013)

Issue date: 

2013 
Date of publication: 

2013 