Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms
Printed: Feb 2013
We show that every finite, finitely related algebra in a congruence
distributive variety has a near unanimity term operation.
As a consequence we solve the near unanimity problem for relational
structures: it is decidable whether a given finite set of relations on
a finite set admits a compatible near unanimity operation. This
consequence also implies that it is decidable whether a given finite
constraint language defines a constraint satisfaction problem of
bounded strict width.
congruence distributive variety, Jónsson operations, near unanimity operation, finitely related algebra, constraint satisfaction problem
08B05 - Equational logic, Mal'cev (Mal'tsev) conditions
08B10 - Congruence modularity, congruence distributivity