CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms

  Published:2011-12-24
 Printed: Feb 2013
  • Libor Barto,
    Department of Mathematics and Statistics, McMaster University, Hamilton, ON
Format:   LaTeX   MathJax   PDF  

Abstract

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.
Keywords: congruence distributive variety, Jónsson operations, near unanimity operation, finitely related algebra, constraint satisfaction problem congruence distributive variety, Jónsson operations, near unanimity operation, finitely related algebra, constraint satisfaction problem
MSC Classifications: 08B05, 08B10 show english descriptions Equational logic, Mal'cev (Mal'tsev) conditions
Congruence modularity, congruence distributivity
08B05 - Equational logic, Mal'cev (Mal'tsev) conditions
08B10 - Congruence modularity, congruence distributivity
 

© Canadian Mathematical Society, 2014 : https://cms.math.ca/