Existence theorems for weakly symmetric operations
Existence theorems for weakly symmetric operations
复制标题
弱对称运算的存在定理
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. McKenzie
中科院分区：
文献类型：
--
作者：
M. Maróti;R. McKenzie
A上的k元弱近似运算（或k-WNU）是满足方程w（x，. . . x）≠ x和w（y，x，. . .，x）n（x，y，. . .，x）n···n w（x，x，. . .，x，y）。如果一个代数A有一个k-NU（或k-WNU）项运算，我们说A满足NU（k）（或WNU（k））。同样地，一个簇被称为满足NU（k）（或WNU（k），分别），如果它有一个满足这些方程的k-变量项。证明了有限幂等代数A具有有限关系宽度当且仅当V（A）（A生成的簇）具有交半分配同余格。“有限关系宽度”的概念出现在算法复杂性理论中，在约束满足问题的代数研究中。事实上，这个概念有几个不同的定义，不知道它们是否等同。上述概念和猜想的一个版本是由于B。Larose和L. Zadori [10].交半分配同余格簇的重要簇族有各种已知的刻画。有一个特定的Maltsev条件的特征;此外，已知局部有限簇具有此性质当且仅当它省略了类型1和类型2的同余覆盖（定义在D.霍比河McKenzie [6]）。E. Kiss证明了一个关系宽度为k的有限幂等代数对每一个m ≥ k必有一个m-WNU项运算。E.吻和M。Valeriote然后观察到，具有k-WNU项运算的有限代数，k > 1，必须省略类型1的同余覆盖。这些观察导致M。证明了两个定理：任何局部有限簇省略1型同余覆盖当且仅当对任意k > 1，它满足WNU（k）;任何局部有限簇有交半分配同余格当且仅当对任意k，它满足WNU（m），对任意m ≥ k.本文证明了M.瓦莱里奥特省略类型1的局部有限簇族是由非平凡幂等Maltsev条件定义的最大的局部有限簇族。为此
A k-ary weak near-unanimity operation (or k-WNU) on A is an operation that satisfies the equations w(x, . . . x) ≈ x and w(y, x, . . . , x) ≈ w(x, y, . . . , x) ≈ · · · ≈ w(x, x, . . . , x, y) . If an algebra A has a k-NU (or a k-WNU) term operation, we say that A satisfies NU(k) (or WNU(k), respectively). Likewise, a variety is said to satisfy NU(k) (or WNU(k), respectively), it it has a k-variable term satisfying these equations. It has been conjectured that a finite idempotent algebra A has finite relational width if and only if V(A) (the variety generated by A) has meet semi-distributive congruence lattices. The concept of “finite relational width” arises in the theory of complexity of algorithms, in the algebraic study of constraint-satisfaction problems. Actually, there are several different definitions of this concept and it is not known if they are equivalent. One version of the concept and the conjecture mentioned above are due to B. Larose and L. Zadori [10]. The important family of varieties with meet semi-distributive congruence lattices has various known characterizations. There is a characterization by a certain Maltsev condition; also, it is known that a locally finite variety has this property iff it omits congruence covers of types 1 and 2 (defined in the tame congruence theory of D. Hobby, R. McKenzie [6]). E. Kiss showed that a finite idempotent algebra of relational width k must have an m-WNU term operation for every m ≥ k. E. Kiss and M. Valeriote then observed that a finite algebra with a k-WNU term operation, k > 1, must omit congruence covers of type 1. These observations led M. Valeriote to make two conjectures: any locally finite variety omits congruence covers of type 1 iff it satisfies WNU(k) for some k > 1; any locally finite variety has meet semi-distributive congruence lattices if and only if for some k, it satisfies WNU(m) for all m ≥ k. In this paper, we prove both of these conjectures of M. Valeriote. The family of locally finite varieties omitting type 1 is the largest family of locally finite varieties defined by a nontrivial idempotent Maltsev condition. For this