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 treewidthextension preservation propertyfinite model theoryfirst-order logicGaifman localityplanar graphs

Mathematics Subject Classification ID

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

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

(16)

• Relativised homomorphism preservation at the finite level
• Preservation of weak SAI's under increasing transformations with applications
• Preservation under substructures modulo bounded cores
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures
• Preservation and decomposition theorems for bounded degree structures
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• Extension preservation theorems on classes of acyclic finite structures
• Automata, Languages and Programming
• Forbidden induced subgraphs and the Łoś-Tarski theorem
• When locality meets preservation
• Preservation theorems through the Lens of topology
• Extension preservation in the finite and prefix classes of first-order logic
• Preservation theorems on sparse classes revisited
• Extension preservation on dense graph classes
• A generalization of the Łoś-Tarski preservation theorem
• Homomorphism preservation on quasi-wide classes

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)