Descriptive Complexity of Finite Structures: Saving the Quantifier Rank
Abstract
Description
Given a relational structure M on n elements, let D(M) be the minimum quantifier rank of a first order formula identifying M up to isomorphism in the class of n-element structures. The obvious upper bound is D(M)\le n. We show that if the relations in M have arity at most k, then D(M)<(1-\frac{1}{2k})n+k^2-k+2. The coefficient at n, which equals 1-\frac{1}{2k}, is probably not best possible but this is the first known bound having it strictly below 1 (for fixed k).
If one is content to have the worse coefficient 1-\frac{1}{2k^2+2}, then one can choose an identifying formula of a very special form: a prenex formula with at most one quantifier alternation.
A few other results in this vein are presented.
39 pages
39 pages