Descriptive complexity of finite structures: Saving the quantifier rank

DOI10.2178/JSL/1120224721zbMath1105.03029arXivmath/0305244OpenAlexW2025099804MaRDI QIDQ5718668

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

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

Related Items (4)

Succinct definitions in the first order theory of graphs ⋮ The first order definability of graphs: Upper bounds for quantifier depth ⋮ Decomposable graphs and definitions with no quantifier alternation ⋮ Defining long words succinctly in FO and MSO

Cites Work

• Unnamed Item
• Finite-model theory -- A personal perspective
• Definability with bounded number of bound variables
• An optimal lower bound on the number of variables for graph identification
• The strange logic of random graphs

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