Local structure of idempotent algebras I
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916566356983808 |
|---|---|
| author | Bulatov, Andrei A. |
| author_facet | Bulatov, Andrei A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_09599 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Local structure of idempotent algebras I Bulatov, Andrei A. Logic in Computer Science Logic Rings and Algebras 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. |
| title | Local structure of idempotent algebras I |
| topic | Logic in Computer Science Logic Rings and Algebras |
| url | https://arxiv.org/abs/2006.09599 |