Kiss, Emil and Valeriote, Matthew - On tractability and congruence distributivity

lmcs:1005 - Logical Methods in Computer Science, June 8, 2007, Volume 3, Issue 2
On tractability and congruence distributivity

Authors: Kiss, Emil and Valeriote, Matthew

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 Jonsson terms, that satisfy certain equations. We prove that constraint languages consisting of relations that are invariant under a short sequence of Jonsson terms are tractable by showing that such languages have bounded relational width.


Source : oai:arXiv.org:0705.2229
DOI : 10.2168/LMCS-3(2:6)2007
Volume: Volume 3, Issue 2
Published on: June 8, 2007
Submitted on: October 19, 2006
Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,F.1.3,F.4.1


Share

Consultation statistics

This page has been seen 40 times.
This article's PDF has been downloaded 39 times.