| |
VOLUME 3, ISSUE 2, PAPER 6
|
On tractability and congruence distributivity
|
©Emil Kiss, Eotvos University
©Matt Valeriote, McMaster University
|
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 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.
|
Publication date: June 8, 2007
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-3(2:6)2007
Hit Counts: 2786 |
 Creative Commons | |
