Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.

DOI10.4230/LIPICS.CSL.2017.19zbMATH Open1434.03019arXiv1704.03167OpenAlexW2964221993MaRDI QIDQ5111186FDOQ5111186

Authors: Yijia Chen, Jörg Flum, Xuangui Huang 

Publication date: 26 May 2020

Abstract: For every $qinmathbbN$ let $extrm{FO}_q$ denote the class of sentences of first-order logic FO of quantifier rank at most $q$. If a graph property can be defined in $extrm{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 $extrm{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 $extrm{para-AC}^0$. It is crucial for our results that the FO-sentences have access to built-in addition and multiplication. It is known that then FO corresponds to the circuit complexity class uniform $extrm{AC}^0$. We explore the connection between the quantifier rank of FO-sentences and the depth of $extrm{AC}^0$-circuits, and prove that $extrm{FO}_{q}subsetneqextrm{FO}_{q+1}$ for structures with built-in addition and multiplication.

Full work available at URL: https://arxiv.org/abs/1704.03167

Recommendations

• The structure of slices over minimal logic
• Strong computability of slices over the logic GL
• First-order concatenation theory with bounded quantifiers
• A binary quantifier for definite descriptions for cut free free logics
• Definability hierarchies of generalized quantifiers
• Quantified propositional calculi and fragments of bounded arithmetic
• First-order definability on finite structures
• Slices and levels of extensions of the minimal logic
• scientific article; zbMATH DE number 4039872
• scientific article; zbMATH DE number 1555183

zbMATH Keywords

first-order logiccircuit depthquantifier rankparameterized \(\mathrm{AC}^0\)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Cited In (11)

• Efficient parallel algorithms for parameterized problems
• Dynamic kernels for hitting sets and set packing
• Quantifier rank for parity of embedded finite models.
• Title not available (Why is that?)
• Computing Hitting Set Kernels By AC^0-Circuits
• On the parallel parameterized complexity of MaxSAT variants
• On the descriptive complexity of color coding
• Computing kernels in parallel: lower and upper bounds
• The quantifier complexity of polynomial-size iterated definitions in first-order logic
• Parameterized Parallel Computing and First-Order Logic
• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits

This page was built for publication: Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111186)