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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01230681
Contributor : Clément Carbonnel <>
Submitted on : Wednesday, November 18, 2015 - 6:23:13 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Friday, April 28, 2017 - 6:37:01 PM

File

conspoly_preprint.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01230681, version 1

Citation

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⟩

Share

Metrics

Record views

190

Files downloads

91