Paper: On tractability and congruence distributivity (at LICS 2006)

Authors: Emil Kiss Matthew Valeriote

Abstract

Constraint languages that arise from finite algebras have recently been the object of study, especially in connection with the Dichotomy Conjecture of Feder and Vardi. An important class of algebras are those that generate congruence distributive varieties and included among this class are lattices, and more generally, those algebras that have near-unanimity term operations. An algebra will generate a congruence distributive variety if and only if it has a sequence of ternary term operations, called J´onsson terms, that satisfy certain equations. We prove that constraint languages consisting of relations that are invariant under a short sequence of J´onsson terms are tractable by showing that such languages have bounded width. Consequently, the class of instances of the constraint satisfaction problem arising from such a constraint language that fail to have solutions is definable in Datalog.

BibTeX

  @InProceedings{KissValeriote-Ontractabilityandco,
    author = 	 {Emil Kiss and Matthew Valeriote},
    title = 	 {On tractability and congruence distributivity},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {221--230},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }