Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms
Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms
复制标题
同余分布簇中的有限相关代数具有近乎一致的术语
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Barto
中科院分区：
文献类型：
--
作者：
L. Barto
摘要我们证明了在同余分布变量中，每一个有限、有限相关的代数都有一个近一致项运算。因此，我们解决了关系结构的近一致问题：有限集合上给定的有限关系集是否允许相容的近一致运算是可判定的。这一结论还表明，给定的有限约束语言是否定义了有界严格宽度的约束满足问题是可决定的。
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.