Free burnside semigroups

Do Lago, Alair Pereira; Simon, Imre

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 579-595 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

This paper surveys the area of Free Burnside Semigroups. The theory of these semigroups, as is the case for groups, is far from being completely known. For semigroups, the most impressive results were obtained in the last 10 years. In this paper we give priority to the mathematical treatment of the problem and do not stress too much neither motivation nor the historical aspects. No proofs are presented in this paper, but we tried to give as many examples as was possible.

Publié le : 2001-01-01

MR 1922297 | Zbl 1061.20049

Classification: 20M05, 20F50

@article{ITA_2001__35_6_579_0,
     author = {Do Lago, Alair Pereira and Simon, Imre},
     title = {Free burnside semigroups},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {579-595},
     mrnumber = {1922297},
     zbl = {1061.20049},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2001__35_6_579_0}
}

Do Lago, Alair Pereira; Simon, Imre. Free burnside semigroups. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) pp. 579-595. http://gdmltest.u-ga.fr/item/ITA_2001__35_6_579_0/

Bibliographie

[1] S.I. Adian, The Burnside problem and identities in groups. Springer-Verlag, Berlin-New York, Ergebnisse der Mathematik und ihrer Grenzgebiete 95 [Results in Mathematics and Related Areas] (1979). Translated from the Russian by John Lennox and James Wiegold. | Zbl 0417.20001

[2] S.I. Adyan, The Burnside problem and identities in groups. Izdat. “Nauka”, Moscow (1975). | Zbl 0417.20001

[3] J. Brzozowski, Open problems about regular languages, edited by R.V. Book. Academic Press, New York, Formal Language Theory, Perspectives and Open Problems (1980) 23-47. | MR 600670

[4] J. Brzozowski, K. Čulík and A. Gabrielian, Classification of non-counting events. J. Comput. System Sci. 5 (1971) 41-53. | MR 286578 | Zbl 0241.94050

[5] J.A. Brzozowski and I. Simon, Characterizations of locally testable events. Discrete Math. 4 (1973) 243-271. | MR 319404 | Zbl 0255.94032

[6] W. Burnside, On an unsettled question in the theory of discontinuous groups. Quart. J. Math. 33 (1902) 230-238. | JFM 33.0149.01

[7] A. De Luca and S. Varricchio, On non-counting regular classes, edited by M.S. Paterson, Automata, Languages and Programming. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 443 (1990) 74-87. | Zbl 0765.68074

[8] A. De Luca and S. Varricchio, On non-counting regular classes. Theoret. Comput. Sci. 100 (1992) 67-104. | MR 1171435 | Zbl 0780.68084

[9] A.P. Do Lago, Local groups in free groupoids satisfying certain monoid identities (to appear). | Zbl 1010.20039

[10] A.P. Do Lago, Sobre os semigrupos de Burnside $x^{n} = x^{n + m}$ , Master's Thesis. Instituto de Matemática e Estatística da Universidade de São Paulo (1991).

[11] A.P. Do Lago, On the Burnside semigroups $x^{n} = x^{n + m}$ , in LATIN'92, edited by I. Simon. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 583 (1992) 329-343.

[12] A.P. Do Lago, On the Burnside semigroups $x^{n} = x^{n + m}$ . Int. J. Algebra Comput. 6 (1996) 179-227. | MR 1386074 | Zbl 0857.20039

[13] A.P. Do Lago, Grupos Maximais em Semigrupos de Burnside Livres, Ph.D. Thesis. Universidade de São Paulo (1998). Electronic version at http://www.ime.usp.br/~alair/Burnside/

[14] A.P. Do Lago, Maximal groups in free Burnside semigroups, in LATIN'98, edited by C.L. Lucchesi and A.V. Moura. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 1380 (1998) 70-81. | Zbl 0904.20041

[15] S. Eilenberg, Automata, languages, and machines, Vol. B. Academic Press [Harcourt Brace Jovanovich Publishers], New York (1976). With two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by B. Tilson, Pures Appl. Math. 59. | Zbl 0359.94067

[16] J.A. Green and D. Rees, On semigroups in which $x^{r} = x$ . Proc. Cambridge. Philos. Soc. 48 (1952) 35-40. | MR 46353 | Zbl 0046.01903

[17] V.S. Guba, The word problem for the relatively free semigroup satisfying $t^{m} = t^{m + n}$ with $m \geq 3$ . Int. J. Algebra Comput. 2 (1993) 335-348. | MR 1240389 | Zbl 0818.20070

[18] V.S. Guba, The word problem for the relatively free semigroup satisfying $t^{m} = t^{m + n}$ with $m \geq 4$ or $m = 3, n = 1$ . Int. J. Algebra Comput. 2 (1993) 125-140. | MR 1233216 | Zbl 0783.20034

[19] M. Hall, Solution of the Burnside problem for exponent six. Illinois J. Math. 2 (1958) 764-786. | MR 102554 | Zbl 0083.24801

[20] G. Huet and D.C. Oppen, Equations and rewrite rules: A survey, edited by R.V. Book. Academic Press, New York, Formal Language Theory, Perspectives and Open Problems (1980) 349-405.

[21] S.V. Ivanov, The free Burnside groups of sufficiently large exponents. Int. J. Algebra Comput. 4 (1994) ii+308. | MR 1283947 | Zbl 0822.20044

[22] J. Kaďourek and L. Polák, On free semigroups satisfying $x^{r} ≃ x$ . Simon Stevin 64 (1990) 3-19. | MR 1072481 | Zbl 0712.20038

[23] J.W. Klop, Term rewriting systems: From Church-Rosser to Knuth-Bendix and beyond, edited by M.S. Paterson, Automata, Languages and Programming. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 443 (1990) 350-369. | Zbl 0765.68008

[24] G. Lallement, Semigroups and Combinatorial Applications. John Wiley & Sons, New York (1979). | MR 530552 | Zbl 0421.20025

[25] F.W. Levi and B.L. Van Der Waerden, Über eine besondere Klasse von Gruppen. Abh. Math. Sem. Hamburg 9 (1933) 154-158. | JFM 58.0125.02

[26] I.G. Lysënok, Infinity of Burnside groups of period $2^{k}$ for $k \geq 13$ . Uspekhi Mat. Nauk 47 (1992) 201-202. | MR 1185294 | Zbl 0822.20043

[27] S. Maclane, Categories for the working mathematician. Springer-Verlag, New York, Grad. Texts in Math. 5 (1971). | MR 354798 | Zbl 0232.18001

[28] J. Mccammond, The solution to the word problem for the relatively free semigroups satisfying $t^{a} = t^{a + b}$ with $a \geq 6$ . Int. J. Algebra Comput. 1 (1991) 1-32. | MR 1112297 | Zbl 0732.20034

[29] D. Mclean, Idempotent semigroups. Amer. Math. Monthly 61 (1954) 110-113. | MR 60505 | Zbl 0055.01404

[30] P.S. Novikov and S.I. Adjan, Infinite periodic groups. I. Izv. Akad. Nauk SSSR Ser. Mat. 32 212-244. | MR 240178 | Zbl 0194.03301

[31] P.S. Novikov and S.I. Adjan, Infinite periodic groups. II. Izv. Akad. Nauk SSSR Ser. Mat. 32 (1968) 251-524. | MR 240179 | Zbl 0194.03301

[32] A.Y. Ol'Shanskiĭ, Geometry of defining relations in groups. Kluwer Academic Publishers Group, Dordrecht (1991). Translated from the 1989 Russian original by Yu.A. Bakhturin. | Zbl 0732.20019

[33] I. Sanov, Solution of Burnside’s problem for exponent $4$ . Leningrad. Gos. Univ. Uchen. Zap. Ser. Mat. 10 (1940) 166-170 (Russian). | Zbl 0061.02506

[34] I. Simon, Notes on non-counting languages of order $2$ . Manuscript (1970).

[35] H. Straubing, Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994). | MR 1269544 | Zbl 0816.68086

[36] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. I Mat. Nat. Kl. 1 (1912) 1-67. | JFM 44.0462.01

[37] B. Tilson, Categories as algebra: An essential ingredient in the theory of monoids. J. Pure Appl. Algebra 48 (1987) 83-198. | MR 915990 | Zbl 0627.20031