Homomorphism preservation on quasi-wide classes

DOI10.1016/J.JCSS.2009.10.005MaRDI QIDQ980940zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar

Publication date 8 July 2010

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2009.10.005

zbMATH Keywords

finite model theorybounded expansionhomomorphism preservationlocally excluded minorsquasi-wide classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Recommendations

• First order properties on nowhere dense structures
• Automata, Languages and Programming
• Preservation under Extensions on Well-Behaved Finite Structures
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures
• Homomorphism preservation theorems

Cites work

• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1342209 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A counterexample to a conjecture of Scott and Suppes
• Datalog vs first-order logic
• Deciding first-order properties of locally tree-decomposable structures
• Diameter and treewidth in minor-closed graph families
• Finite Model Theory on Tame Classes of Structures
• Homomorphism preservation theorems
• Monotone versus positive
• On preservation under homomorphisms and unions of conjunctive queries
• Preservation under Extensions on Well-Behaved Finite Structures
• The Grad of a Graph and Classes with Bounded Expansion

Cited in

(15)

• Automata, Languages and Programming
• Preservation under Extensions on Well-Behaved Finite Structures
• On ultralimits of sparse graph classes
• On preservation under homomorphisms and unions of conjunctive queries
• Characterising bounded expansion by neighbourhood complexity
• Fixed-parameter tractable distances to sparse graph classes
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• Homomorphism preservation theorems
• Relativised homomorphism preservation at the finite level
• Interpreting nowhere dense graph classes as a classical notion of model theory
• A generalization of the Łoś-Tarski preservation theorem
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• Directed nowhere dense classes of graphs
• A generalization of the Łoś-Tarski preservation theorem over classes of finite structures

This page was built for publication: Homomorphism preservation on quasi-wide classes

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