Recent Results on the Algebraic Approach to the CSP

DOI10.1007/978-3-540-92800-3_4zbMath1171.08300OpenAlexW1511747486MaRDI QIDQ5504700

Andrei A. Bulatov, Matthew A. Valeriote

Publication date: 22 January 2009

Published in: Complexity of Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_4

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)

Related Items (24)

Tractability in constraint satisfaction problems: a survey ⋮ Aggregation of Votes with Multiple Positions on Each Issue ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Testing list \(H\)-homomorphisms ⋮ List-homomorphism problems on graphs and arc consistency ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ Not all nilpotent monoids are finitely related ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ On the CSP Dichotomy Conjecture ⋮ Key (critical) relations preserved by a weak near-unanimity function ⋮ The complexity of the list homomorphism problem for graphs ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ CSP duality and trees of bounded pathwidth ⋮ On algebras with many symmetric operations ⋮ OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT ⋮ The number of clones determined by disjunctions of unary relations ⋮ Dualities for Constraint Satisfaction Problems ⋮ Characterizations of several Maltsev conditions. ⋮ Commutative idempotent groupoids and the constraint satisfaction problem. ⋮ Distance constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expressive rate of constraints
• \(H\)-coloring dichotomy revisited
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• The set of types of a finitely generated variety
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Constraints and universal algebra
• A new tractable class of constraint satisfaction problems
• Few subpowers, congruence distributivity and near-unanimity terms
• Combinatorial problems raised from 2-semilattices
• Tractable Clones of Polynomials over Semigroups
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Varieties with few subalgebras of powers
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Affine Systems of Equations and Counting Infinitary Logic
• A Characterisation of First-Order Constraint Satisfaction Problems
• A Simple Algorithm for Mal'tsev Constraints
• Mathematical Foundations of Computer Science 2005
• Dualities for Constraint Satisfaction Problems

This page was built for publication: Recent Results on the Algebraic Approach to the CSP