First-order definability on finite structures

DOI10.1016/0168-0072(89)90036-5zbMath0688.03018OpenAlexW2054510469MaRDI QIDQ1263576

Miklós Ajtai

Publication date: 1989

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(89)90036-5

zbMATH Keywords

connectednessfinite structuresexistential hierarchygraph-theoretic propertyundefinability

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40)

Related Items (7)

Formulas versus Circuits for Small Distance Connectivity ⋮ The complexity of graph connectivity ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Lower bounds for recognizing small cliques on CRCW PRAM's ⋮ Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages ⋮ Positive predicate structures for continuous data ⋮ Unnamed Item

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A spectrum hierarchy

This page was built for publication: First-order definability on finite structures