On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

DOI10.2168/LMCS-8(3:13)2012zbMath1308.68062OpenAlexW1998968023MaRDI QIDQ2914234

Barnaby Martin, Manuel Bodirsky, Martin Hils

Publication date: 25 September 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-8(3:13)2012

zbMATH Keywords

model theorypolynomial timeconstraint satisfactionfirst-order definabilityhardnesspolymorphismsinfinite structuresuniversal-algebraic approach

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Basic properties of first-order languages and structures (03C07)

Related Items (14)

On a stronger reconstruction notion for monoids and clones ⋮ Constraint Satisfaction Problems over the Integers with Successor ⋮ New Ramsey classes from old ⋮ Action of endomorphism semigroups on definable sets ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The complexity of counting quantifiers on equality languages ⋮ Solving equation systems in ω-categorical algebras ⋮ Towards a Ryll-Nardzewski-type theorem for weakly oligomorphic structures ⋮ Permutation groups with small orbit growth ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures ⋮ PROJECTIVE CLONE HOMOMORPHISMS ⋮ Using model theory to find decidable and tractable description logics with concrete domains ⋮ Distance constraint satisfaction problems

This page was built for publication: On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction