Name
Abstract | ||
|---|---|---|
Given two structures G and H distinguishable in FOk (first-order logic with k variables), let Ak(G, H) denote the minimum alternation depth of a FOk formula distinguishing G from H. Let Ak(n) be the maximum value of Ak(G, H) over n-element structures. We prove the strictness of the quantifier alternation hierarchy of FO2 in a strong quantitative form, namely A2(n) > n/8 − 2, which is tight up to a constant factor. For each k ⩾ 2, it holds that Ak(n) > log k + 1n − 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, whereas the alternation hierarchy of FO2 collapses even over all uncolored graphs. We also show examples of colored graphs G and H on n vertices that can be distinguished in FO2 much more succinctly if the alternation number is increased just by one: Whereas in Σi it is possible to distinguish G from H with bounded quantifier depth, in Πi this requires quantifier depth Ω(n2). The quadratic lower bound is best possible here because, if G and H can be distinguished in FOk with i quantifier alternations, this can be done with quantifier depth n2k − 2 + 1 and the same number of alternations. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2732409 | ACM Trans. Comput. Log. |
Keywords | Field | DocType |
alternation hierarchy,finite-variable logic,mathematical logic,theory | Bounded quantifier,Discrete mathematics,Graph,Combinatorics,Colored,Vertex (geometry),Upper and lower bounds,Quadratic equation,Hierarchy,Mathematics,Alternation (linguistics) | Conference |
Volume | Issue | ISSN |
16 | Issue-in-Progress | 1529-3785 |
Citations | PageRank | References |
1 | 0.35 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Berkholz | 1 | 49 | 7.03 |
| Andreas Krebs | 2 | 21 | 8.20 |
| Oleg Verbitsky | 3 | 191 | 27.50 |