On tractability and congruence distributivity

Details On tractability and congruence distributivity On tractability and congruence distributivity

2007-05-15

arxiv.org/abs/0705.2229v2

LMCS 3 (2:6) 2007

Computer Science

Computational Complexity

Scientific paper

10.2168/LMCS-3(2:6)2007

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.

Affiliated with

Also associated with

No associations

Rating

On tractability and congruence distributivity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On tractability and congruence distributivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On tractability and congruence distributivity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-669441