2026-07-22T16:22:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4190 2024-03-06T10:34:51Z ddc:004 open_access

Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy Berkholz, Christoph Krebs, Andreas Verbitsky, Oleg Alternation hierarchy finite-variable logic Given two structures G and H distinguishable in FO^k (first-order logic with k variables), let A^k(G,H) denote the minimum alternation depth of a FO^k formula distinguishing G from H. Let A^k(n) be the maximum value of A^k(G,H) over n-element structures. We prove the strictness of the quantifier alternation hierarchy of FO^2 in a strong quantitative form, namely A^2(n) >= n/8-2, which is tight up to a constant factor. For each k >= 2, it holds that A^k(n) > log_(k+1) n-2 even over colored trees, which is also tight up to a constant factor if k >= 3. For k >= 3 the last lower bound holds also over uncolored trees, while the alternation hierarchy of FO^2 collapses even over all uncolored graphs. We also show examples of colored graphs G and H on n vertices that can be distinguished in FO^2 much more succinctly if the alternation number is increased just by one: while in Sigma_i it is possible to distinguish G from H with bounded quantifier depth, in Pi_i this requires quantifier depth Omega(n2). The quadratic lower bound is best possible here because, if G and H can be distinguished in FO^k with i quantifier alternations, this can be done with quantifier depth n^(2k-2). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christoph Berkholz and Andreas Krebs and Oleg Verbitsky 2013 Is Part Of LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2013.61 urn:nbn:de:0030-drops-41907 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.61 eng https://creativecommons.org/licenses/by/3.0/legalcode