Homomorphism preservation on quasi-wide classes

DOI10.1016/J.JCSS.2009.10.005zbMATH Open1206.68140DBLPjournals/jcss/Dawar10OpenAlexW1980240005WikidataQ58215527 ScholiaQ58215527MaRDI QIDQ980940FDOQ980940

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

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

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)

Cites Work

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

Cited In (15)

• Automata, Languages and Programming
• Preservation under Extensions on Well-Behaved Finite Structures
• On preservation under homomorphisms and unions of conjunctive queries
• On ultralimits of sparse graph classes
• 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
• Title not available (Why is that?)
• 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)