Universal algebraic methods for constraint satisfaction problems

MaRDI QIDQ5028466zbMATH OpenFDO

Authors Clifford Bergman, William Demeo

Publication date 9 February 2022

Full work available at URL https://arxiv.org/abs/1611.02867, https://lmcs.episciences.org/8975

zbMATH Keywords

algebraic complexity theorycomplexity theory and logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1670830
• Universal algebra and hardness results for constraint satisfaction problems
• Classifying the Complexity of Constraints Using Finite Algebras

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A proof of the CSP dichotomy conjecture
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Commutative idempotent groupoids and the constraint satisfaction problem.
• Computing congruences efficiently
• Constraint Satisfaction Problems of Bounded Width
• Cyclic terms for \(\text{SD}_{\vee}\) varieties revisited
• Finitely related clones and algebras with cube terms.
• Mal'tsev conditions, lack of absorption, and solvability.
• Maltsev families of varieties closed under join or Maltsev product
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The constraint satisfaction problem and universal algebra
• The shape of congruence lattices
• The structure of finite algebras
• Universal algebra. Fundamentals and selected topics
• Varieties Obeying Homotopy Laws

Cited in

(4)

• Alloy*: a general-purpose higher-order relational constraint solver
• The constraint satisfaction problem and universal algebra
• Equivariant algorithms for constraint satisfaction problems over coset templates
• Universal Algebraic Methods for Constraint Satisfaction Problems

This page was built for publication: Universal algebraic methods for constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028466)