Chen, Yijia ;
Flum, Jörg ;
Huang, Xuangui
Slicewise Definability in FirstOrder Logic with Bounded Quantifier Rank
Abstract
For every natural number q let FO_q denote the class of sentences of
firstorder logic FO of quantifier rank at most q. If a graph property can be defined in FO_q, then it can be decided in time O(n^q). Thus, minimizing q has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size k. Usually this can only be expressed by a sentence of quantifier rank at least k. We use the color coding method to demonstrate that some (hyper)graph problems can be defined in FO_q where q is independent of k. This property of a graph problem is equivalent to the question of whether the corresponding parameterized problem is in the class paraAC^0.
It is crucial for our results that the FOsentences have access to builtin addition and multiplication (and constants for an initial segment of natural numbers whose length depends only on k). It is known that then FO corresponds to the circuit complexity class uniform AC^0. We explore the connection between the quantifier rank of FOsentences and the depth of AC^0circuits, and prove that FO_q is strictly contained in FO_{q+1} for structures with builtin addition and multiplication.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2017:7674,
author = {Yijia Chen and J{\"o}rg Flum and Xuangui Huang},
title = {{Slicewise Definability in FirstOrder Logic with Bounded Quantifier Rank}},
booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
pages = {19:119:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770453},
ISSN = {18688969},
year = {2017},
volume = {82},
editor = {Valentin Goranko and Mads Dam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7674},
URN = {urn:nbn:de:0030drops76742},
doi = {10.4230/LIPIcs.CSL.2017.19},
annote = {Keywords: firstorder logic, quantifier rank, parameterized AC^0, circuit depth}
}
2017
Keywords: 

firstorder logic, quantifier rank, parameterized AC^0, circuit depth 
Seminar: 

26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Issue date: 

2017 
Date of publication: 

2017 