论文标题
基于代数i的局部结构
Local structure of idempotent algebras I
论文作者
论文摘要
我们完善并推进了对掌握有限代数的局部结构的研究，始于[A.Bulatov，关系结构和约束满意度问题的图，LICS，2004年]。我们在任意有限的IDEMPOTENT代数上引入类似图形的结构，包括那些接受类型1的代数。我们证明该图已连接，其边缘可以分为4种与某些术语操作的局部行为（集合，半静脉，多数或亲戚）相对应的4种类型。我们还表明，如果代数产生的品种省略了1型，那么代数的结构可以“改进”，而无需通过选择原始代数的适当还原来引入类型1。泰勒最近引入的泰勒最小的基本代数是这种减少的特殊情况。然后，我们完善了这种结构，表明可以使代数省略1的图表的边缘“稀薄”，也就是说，有一些术语操作与代数的2元素集对半层次，多数或仿射操作非常相似。最后，我们证明了精制结构的某些连接性能。 这项研究是由对约束满意度问题的研究引起的，尽管该问题本身并未在本文中真正显示出来。
We refine and advance the study of the local structure of idempotent finite algebras started in [A.Bulatov, The Graph of a Relational Structure and Constraint Satisfaction Problems, LICS, 2004]. We introduce a graph-like structure on an arbitrary finite idempotent algebra including those admitting type 1. We show that this graph is connected, its edges can be classified into 4 types corresponding to the local behavior (set, semilattice, majority, or affine) of certain term operations. We also show that if the variety generated by the algebra omits type 1, then the structure of the algebra can be `improved' without introducing type 1 by choosing an appropriate reduct of the original algebra. Taylor minimal idempotent algebras introduced recently is a special case of such reducts. Then we refine this structure demonstrating that the edges of the graph of an algebra omitting type 1 can be made `thin', that is, there are term operations that behave very similar to semilattice, majority, or affine operations on 2-element subsets of the algebra. Finally, we prove certain connectivity properties of the refined structures. This research is motivated by the study of the Constraint Satisfaction Problem, although the problem itself does not really show up in this paper.
