Preservation under Extensions on Well-Behaved Finite Structures

DOI10.1137/060658709MaRDI QIDQ3395035zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Albert Atserias, Anuj Dawar, 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)

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

Cited in

(12)

• Automata, Languages and Programming
• 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
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• Preservation under substructures modulo bounded cores
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures
• Extension preservation theorems on classes of acyclic finite structures
• Forbidden induced subgraphs and the Łoś-Tarski theorem

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)