Descriptive complexity of finite structures: Saving the quantifier rank

DOI10.2178/JSL/1120224721MaRDI QIDQ5718668zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko, Oleg Verbitsky

Publication date 16 January 2006

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0305244

zbMATH Keywords

descriptive complexityfinite structuresquantifier rank

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Abstract: 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.

Recommendations

• The Complexity of Defining a Relation on a Finite Graph
• On distinguishing sets of structures by first-order sentences of minimal quantifier rank
• On the definability of properties of finite graphs
• Succinct definitions in the first order theory of graphs
• Descriptive complexity of finite abelian groups

Cites work

• An optimal lower bound on the number of variables for graph identification
• Definability with bounded number of bound variables
• Finite-model theory -- A personal perspective
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• The strange logic of random graphs

Cited in

(13)

• Quantifier rank for parity of embedded finite models.
• Defining long words succinctly in FO and MSO
• On distinguishing sets of structures by first-order sentences of minimal quantifier rank
• Succinct definitions in the first order theory of graphs
• Decomposable graphs and definitions with no quantifier alternation
• Descriptive complexity of finite abelian groups
• The Complexity of Defining a Relation on a Finite Graph
• scientific article; zbMATH DE number 1834663 (Why is no real title available?)
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• The first order definability of graphs: Upper bounds for quantifier depth

This page was built for publication: Descriptive complexity of finite structures: Saving the quantifier rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5718668)