Definitions with no quantifier alternation

Details Definitions with no quantifier alternation Definitions with no quantifier alternation

2004-05-17

arxiv.org/abs/math/0405326v2

Mathematics

Logic

24 pages, we complement the lower bound proved in the first version with a tight upper bound. The title of the paper has been

Scientific paper

Let $D(G)$ be the minimum quantifier depth of a first order sentence $\Phi$ 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 $\Phi$. 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.

Affiliated with

Also associated with

No associations

Rating

Definitions with no quantifier alternation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Definitions with no quantifier alternation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Definitions with no quantifier alternation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284908