Skip to Main content Skip to Navigation
New interface
Conference papers

The Meta-Problem for Conservative Mal'tsev Constraints

Clément Carbonnel 1, * 
* Corresponding author
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : In the algebraic approach to CSP (Constraint Satisfaction Problem), the complexity of constraint languages is studied using closure operations called poly-morphisms. Many of these operations are known to induce tractability of any language they preserve. We focus on the meta-problem: given a language Γ, decide if Γ has a polymorphism with nice properties. We design an algorithm that decides in polynomial-time if a constraint language has a conservative Mal'tsev poly-morphism, and outputs one if one exists. As a corollary we obtain that the class of conservative Mal'tsev constraints is uniformly tractable, and we conjecture that this result remains true in the non-conservative case.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Clément Carbonnel Connect in order to contact the contributor
Submitted on : Wednesday, November 18, 2015 - 6:23:13 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Friday, April 28, 2017 - 6:37:01 PM


Files produced by the author(s)


  • HAL Id : hal-01230681, version 1


Clément Carbonnel. The Meta-Problem for Conservative Mal'tsev Constraints. Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16), Feb 2016, Phoenix, Arizona, United States. ⟨hal-01230681⟩



Record views


Files downloads