The first order definability of graphs: Upper bounds for quantifier depth

DOI10.1016/j.dam.2006.03.002zbMath1109.03023arXivmath/0311041MaRDI QIDQ860411

Oleg Pikhurko, Helmut Veith, Oleg Verbitsky

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

first-order logic; Ehrenfeucht game; graph definability

Mathematics Subject Classification ID

03C13: Model theory of finite structures

03C40: Interpolation, preservation, definability

68Q19: Descriptive complexity and finite models