On the locality of arb-invariant first-order formulas with modulo counting quantifiers
- 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.
Author: | Frederik Harwath, Nicole Schweikardt |
---|---|
URN: | urn:nbn:de:hebis:30:3-438293 |
DOI: | https://doi.org/10.2168/LMCS-12(4:8)2016 |
ISSN: | 1860-5974 |
ArXiv Id: | http://arxiv.org/abs/1611.07716 |
Parent Title (English): | Logical methods in computer science |
Publisher: | Department of Theoretical Computer Science, Technical University of Braunschweig |
Place of publication: | Braunschweig |
Document Type: | Article |
Language: | English |
Date of Publication (online): | 2017/08/31 |
Year of first Publication: | 2016 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2017/08/31 |
Tag: | Computer science; F.1.3; F.4.1; H.2.3; Logic in computer science |
Volume: | 12 |
Issue: | 4, Art. 8 |
Page Number: | 34 |
First Page: | 1 |
Last Page: | 34 |
Note: | 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 |
HeBIS-PPN: | 425323331 |
Institutes: | Informatik und Mathematik / Informatik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Sammlungen: | Universitätspublikationen |
Licence (German): | Creative Commons - Namensnennung-Keine Bearbeitung |