Geodesic
On identical transformations in commutative semigroups
Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 139-149 
D. M. Motin. On identical transformations in commutative semigroups. Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 139-149. http://geodesic.mathdoc.fr/item/DM_2007_19_4_a9/
@article{DM_2007_19_4_a9,
     author = {D. M. Motin},
     title = {On identical transformations in commutative semigroups},
     journal = {Diskretnaya Matematika},
     pages = {139--149},
     year = {2007},
     volume = {19},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_4_a9/}
}
TY  - JOUR
AU  - D. M. Motin
TI  - On identical transformations in commutative semigroups
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 139
EP  - 149
VL  - 19
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_4_a9/
LA  - ru
ID  - DM_2007_19_4_a9
ER  - 
%0 Journal Article
%A D. M. Motin
%T On identical transformations in commutative semigroups
%J Diskretnaya Matematika
%D 2007
%P 139-149
%V 19
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2007_19_4_a9/
%G ru
%F DM_2007_19_4_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that in any commutative semigroup the complexity of transformation of equal terms of length at most $n$ into each other is of order $n\log n$.

[1] Perkins P., “Bazisy dlya ekvatsionalnykh teorii polugrupp”, Kibern. sb., 11 (1974), 14–17

[2] Lyndon R. C., “Identities in two-valued calculi”, Trans. Amer. Math. Soc., 71:3 (1951), 457–465 | DOI | MR | Zbl

[3] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, Moskva, 1966 | MR | Zbl