Preservation under Extensions on Well-Behaved Finite Structures

DOI10.1137/060658709zbMATH Open1169.03025DBLPjournals/siamcomp/AtseriasDG08OpenAlexW2035165468WikidataQ58215587 ScholiaQ58215587MaRDI QIDQ3395035FDOQ3395035

Anuj Dawar, Albert Atserias, Martin Grohe

Publication date: 20 August 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060658709

zbMATH Keywords

bounded treewidthfinite model theoryfirst-order logicplanar graphsGaifman localityextension preservation property

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Properties of classes of models (03C52) Interpolation, preservation, definability (03C40)

Cited In (8)

• Preservation of weak SAI's under increasing transformations with applications
• Preservation and decomposition theorems for bounded degree structures
• Homomorphism preservation on quasi-wide classes
• Relativised homomorphism preservation at the finite level
• When locality meets preservation
• A generalization of the Łoś-Tarski preservation theorem
• Title not available (Why is that?)
• Forbidden induced subgraphs and the Łoś-Tarski theorem

   Recommendations

• Automata, Languages and Programming 👍 👎
• Extension preservation theorems on classes of acyclic finite structures 👍 👎
• Homomorphism preservation on quasi-wide classes 👍 👎
• A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures 👍 👎
• First order properties on nowhere dense structures 👍 👎

This page was built for publication: Preservation under Extensions on Well-Behaved Finite Structures

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