Constraint Satisfaction with Countable Homogeneous Templates

DOI10.1093/logcom/exi083zbMath1113.03026OpenAlexW2070051236MaRDI QIDQ3430949

Manuel Bodirsky, Jaroslav Nešetřil

Publication date: 5 April 2007

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/exi083

zbMATH Keywords

computational complexityageNP-completeconstraint satisfaction problem\(\omega\)-categorical structureclone of polymorphismscountable homogeneous digraphcountable homogeneous relational structurepolymorphism preservation theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Directed graphs (digraphs), tournaments (05C20) Equational classes, universal algebra in model theory (03C05) Properties of classes of models (03C52) Categoricity and completeness of theories (03C35)

Related Items (38)

On a stronger reconstruction notion for monoids and clones ⋮ In praise of homomorphisms ⋮ Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮ Constraint Satisfaction Problems over the Integers with Successor ⋮ Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicity ⋮ More sublattices of the lattice of local clones ⋮ Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ Permutation monoids and MB-homogeneity for graphs and relational structures ⋮ A new line of attack on the dichotomy conjecture ⋮ Reconstructing the topology of clones ⋮ Action of endomorphism semigroups on definable sets ⋮ The wonderland of reflections ⋮ The complexity of equality constraint languages ⋮ Quantified Constraints in Twenty Seventeen ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Countable 1-Transitive Trees ⋮ Solving equation systems in ω-categorical algebras ⋮ \({\aleph_{0}}\)-categorical structures: endomorphisms and interpretations ⋮ On polymorphism-homogeneous relational structures and their clones. ⋮ Minimal functions on the random graph ⋮ A survey of homogeneous structures ⋮ Unnamed Item ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Schaefer's Theorem for Graphs ⋮ Permutation groups with small orbit growth ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Unnamed Item ⋮ Maximal infinite-valued constraint languages ⋮ Tractable combinations of theories via sampling ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Determining the consistency of partial tree descriptions ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ Topological Birkhoff ⋮ Introduction to the Maximum Solution Problem ⋮ Using model theory to find decidable and tractable description logics with concrete domains ⋮ Description logics with concrete domains and general concept inclusions revisited ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom ⋮ Distance constraint satisfaction problems

This page was built for publication: Constraint Satisfaction with Countable Homogeneous Templates