Homomorphism preservation theorems
From MaRDI portal
Publication:3546368
DOI10.1145/1379759.1379763zbMath1326.03038OpenAlexW2055686117MaRDI QIDQ3546368
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1379759.1379763
first-order logichomomorphismsfinite model theorytree-depthconjunctive queriespreservation theoremsquantifier-rank
Database theory (68P15) Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Basic properties of first-order languages and structures (03C07)
Related Items (35)
A polynomial excluded-minor approximation of treedepth ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Structure and Power: an Emerging Landscape ⋮ In praise of homomorphisms ⋮ A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem ⋮ Certain answers as objects and knowledge ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Constraint satisfaction, irredundant axiomatisability and continuous colouring ⋮ Obstructions to partitions of chordal graphs ⋮ Relativised homomorphism preservation at the finite level ⋮ Security Protocol Analysis in Context: Computing Minimal Executions Using SMT and CPSA ⋮ On low tree-depth decompositions ⋮ Arboreal categories and equi-resource homomorphism preservation theorems ⋮ Positive First-order Logic on Words and Graphs ⋮ Arboreal Categories: An Axiomatic Theory of Resources ⋮ A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases ⋮ A generalization of the Łoś-Tarski preservation theorem ⋮ On nowhere dense graphs ⋮ Action of endomorphism semigroups on definable sets ⋮ The price of query rewriting in ontology-based data access ⋮ SOME MODEL THEORY OF GUARDED NEGATION ⋮ On the complexity of existential positive queries ⋮ Quasi-equational bases for graphs of semigroups, monoids and groups. ⋮ Homomorphism preservation on quasi-wide classes ⋮ A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries ⋮ Graph partitions with prescribed patterns ⋮ Conjunctive query pattern structures: a relational database model for formal concept analysis ⋮ Whither semantics? ⋮ Unnamed Item ⋮ Harmonious logic: Craig's interpolation theorem and its descendants ⋮ From Hilbert's program to a logic tool box ⋮ Counting Homomorphisms to Sparse Graphs ⋮ Schema Mappings: A Case of Logical Dynamics in Database Theory ⋮ Unnamed Item ⋮ Guarded Ontology-Mediated Queries
This page was built for publication: Homomorphism preservation theorems
