Definitions with no quantifier alternation
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Let $D(G)$ be the minimum quantifier depth of a first order sentence $Φ$ that defines a graph $G$ up to isomorphism. Let $D_0(G)$ be the version of $D(G)$ where we do not allow quantifier alternations in $Φ$. Define $q_0(n)$ to be the minimum of $D_0(G)$ over all graphs $G$ of order $n$. We prove that for all $n$ we have $\log^*n-\log^*\log^*n-1\le q_0(n)\le \log^*n+22$, where $\log^*n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.
24 pages, we complement the lower bound proved in the first version with a tight upper bound. The title of the paper has been changed
24 pages, we complement the lower bound proved in the first version with a tight upper bound. The title of the paper has been changed