О комбинаторных свойствах бернсайдовых полугрупп

Теория бернсайдовых полугрупп, или полугрупп с тождеством хп = хп+т для некоторых п, m ^ 1 занимает важное место в теории периодических полугрупп. Бернсайдовы полугруппы возникают при рассмотрении полугрупп с ограниченным периодом. Проблематика бернсайдовых полугрупп естественным образом развивает аналогичную проблематику для бернсайдовых групп, т. е. групп с тождеством хт = 1. Изучение последних было начато в 1902 году Бернсайдом, интересовавшимся, всякая ли конечно порожденная группа с ограниченным периодом конечна (так называемая ограниченная проблема Бернсайда).

Важнейшими объектами для исследования, несомненно, являются свободные бернсайдовы полугруппы, то есть полугруппы, свободные в многообразии var{x™ = хп+т} (для фиксированных п, т ^ 1), поскольку всякая полугруппа из var{a-n = хп+т} есть гомоморфный образ подходящей свободной бернсайдовой полугруппы.

Свободным бернсайдовым полугруппам посвящено немало исследований, проясняющих многие особенности их внутренней структуры. Был разработан соответствующий инструментарий для изучения таких полугрупп, использующий как теоретико-групповые методы, так и методы теории формальных языков (в этом случае элементы свободной бернсайдовой полугруппы рассматриваются как классы эквивалентных слов над соответствующим алфавитом), методы общей комбинаторики и теории графов. Краткий обзор результатов приводится ниже в § 2°. Более подробно с теорией бернсайдовых полугрупп можно ознакомиться, например, по обзорной статье [20], немало интересных сведений можно почерпнуть из книг по теории полугрупп [3,15] и др.

Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы. Тесным образом решение проблемы равенства слов связано с гипотезой о том, что любой элемент свободной бернсайдовой полугруппы является рациональным языком. Эта гипотеза, сформулированная Бжозовским в 1969 году для полугрупп с тождеством хп = жта+1, была затем расширена Маккаммондом на случай произвольных пит. Заметим, что из справедливости (обобщенной) гипотезы Бжозовского вытекает разрешимость проблемы равенства слов в рассматриваемой полугруппе.

Центральное место в диссертации отведено исследованию проблемы равенства слов и гипотезы Бжозовского для свободных бернсайдовых полугрупп. К настоящему времени, благодаря целому ряду работ, удалось подтвердить гипотезу Бжозовского и, как следствие, решить проблему равенства слов для случая п ^ 3. Значимые результаты получены и для полугрупп с п = 1 (см. § 2°). Наименее изученными остаются полугруппы с тождеством х2 = х2+т: проблема равенства слов в этом случае до сих пор не решена, а гипотеза Бжозовского при болыпйх значениях т оказывается неверной. В данной работе рассматриваются полугруппы с тождеством х2 = х3, для которых обе исследуемые проблемы остаются открытыми. Часть полученных в диссертации результатов обобщается на случай п = 2 и произвольного т.

1. С. И. Адян. Проблема Бернсайда и тождества в группах. М.: Наука, 1975. 335с.

2. М. Ф. Бакиров, Е. В. Суханов. Слова Туэ-Морса и V-строение свободной бернсайдо-вой полугруппы // Изв. Уральского государственного университета. Серия «Математика и механика». 2000. Т. 18 (выпуск 3). С. 5−19.

3. Ж. Лаллеман. Полугруппы и комбинаторные приложения. М.: «Мир», 1985. 440с.

4. И. Г. Лысенок. Бесконечность бернсайдовых групп периода 2к при к ^ 13 // Успехи мат. наук. 1992. Т. 47: 2(284). С. 201−202.

5. П. С. Новиков, С. И. Адян. Бесконечные периодические группы. I // Изв. АН СССР. Сер. «Математика». 1968. Т. 32. С. 212−244.

6. П. С. Новиков, С. И. Адян. Бесконечные периодические группы. II // Изв. АН СССР. Сер. «Математика». 1968. Т. 32. С. 251−524.

7. И. Н. Санов. Решение проблемы Бернсайда для показателя, 4 // Ученые записки Ленинградского государственного университета. Сер. «Математика». 1940. Т. 10. С. 166 -170.

8. S. I. Adjan, I. G. Lysionok. The method of classification of periodic words and the Burnside problem // Contemporary Mathematics. 1992. Vol. 131. P. 13−28.

9. J. Brzozowski. Open problems about regular languages // Formal language theory: perspectives and open problems. R. Book. Ed. Academic Press, New York, 1980. P. 23−47.

10. J. Brzozowski, K. Culik, A. Gabrielian. Classification of non-counting events // J. Comput. Syst. Sci. 1971. Vol. 5. P. 41−53.

11. W. Burnside. On an unsettled question in the theory of discontinuous groups // Quart. J. Pure Appl. Math. 1902. Vol. 33. P. 230−238.

12. A. de Luca, S. Varricchio. On non-counting regular classes // Proc. ICALP'90. Berlin: Springer, 1990. P. 74−87. (LNCS Vol. 443).

13. A. de Luca, S. Varricchio. On finitely recognizable semigroups // Acta Inform. 1992. Vol. 29(5). P. 483−498.

14. A. de Luca, S. Varricchio. On non-counting regular classes // Theoret. Comput. Sci. 1992. Vol. 100(1). P. 67−104.

15. A. de Luca, S. Varricchio. Finiteness and regularity in semigroups and formal languages. Berlin: Springer, 1999. 240p.

16. A. P. do Lago. On the Burnside semigroups xn = xn+m // Proc. LATIN'92. Berlin: Springer, 1992. P. 329−343. (LNCS Vol. 583).

17. A. P. do Lago. On the Burnside semigroups xn = xn+m // Internat. J. Algebra Comput. 1996. Vol. 6(2). P. 179−227.

18. A. P. do Lago. Maximal groups in free Burnside semigroups // Proc. LATIN'98. Heidelberg: Springer, 1998. P. 65−75. (LNCS Vol. 1380).

19. A. P. do Lago. Grupos Maximais em Semigrupos de Burnside Livres // PhD Thesis. Universidade de Sao Paulo, 1998. Available at http://www.ime.usp.br/~alair/Burnside. 141p.

20. A. P. do Lago, I. Simon. Free Burnside Semigroups // Theoret. Inform. Appl. 2001. Vol. 35(6). P. 579−595.

21. J. A. Green, D. Rees. On semigroups in which xr = x // Proc. Cambridge Philos. Soc. 1952. Vol. 48. P. 35−40.

22. V. S. Guba. The word problem for the relatively free semigroups satisfying tm = tm+n with m^4orm³, n = l// Internat. J. Algebra Comput. 1993. Vol. 3(2). P. 125−140.

23. V. S. Guba. The word problem for the relatively free semigroups satisfying tm = tm+n with m > 3 // Internat. J. Algebra Comput. 1993. Vol. 3(3). P. 335−348.

24. M. Hall. Solution of the Burnside problem for exponent six // Illinois. J. Math. 1958. Vol. 2. P. 764−786.

25. S. V. Ivanov. On the Burnside problem on periodic groups // Bull. Amer. Math. Soc. 1992. Vol. 27. P. 257−260.

26. L. Kad’ourek, J. Polak. On free semigroups satisfying xr ~ x // Simon Stevin. 1990. Vol. 64(1). P. 3−19.

27. F. W. Levi, B. L. van der Waerden. Uber eine besondere Masse von gruppen // Hamburg: Abh. Math. Sem., 1933. Vol. 9. P. 154−158.

28. М. Lothaire. Combinatorics on words. Reading, MA: Addison-Wesley, 1983. 262p.

29. J. McCammond. The solution to the word problem for the relatively free semigroups satisfying ta = ta+b with a > 6 // Internat. J. Algebra Comput. 1991. Vol. 1. P. 1−32.

30. A. M. Shur. Overlap-free words and Thue-Morse sequences // Internat. J. Algebra Comput. 1996. Vol. 6(3). P. 353−367.

31. A. Thue. Uber unendliche Zeichenreihen // Norske Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. № 7. Christiania, 1906. P. 1−22.

32. A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Norske Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. № 10. Christiania, 1912. P. 1−67.Работы автора по теме диссертации.

33. А. Н. Плющенко. Сильно бескубные слова и свободная бернсайдова полугруппа с тождеством х2 = х3 // Материалы XIV международной научной конференции «Ломоносов-2007». Москва: Мысль, 2007. С. 92.

34. А. Н. Плющенко. Сильно бескубные слова и свободная бернсайдова полугруппа с тождеством х2 = х3 и двумя образующими // Сибирские Эл. Мат. Изв. 2009. Т. 6. С. 166−181.

35. A. H. Плющенко. О проблеме равенства слов для свободных бернсайдовых полугрупп с тождеством х2 = х3 // Известия вузов. Математика. 2011. № 11. С. 89−93.

36. А. N. Plyushchenko, А. М. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x2 = x3 // Proc. WORDS 2007. Marseille, France, 2007. P. 245−253.

37. A.N. Plyushchenko, A.M. Shur. On Brzozowski’s conjecture for the free Burnside semigroup satisfying x2 = x3 // Proc. DLT 2011. Berlin: Springer, 2011. P. 362−373. (LNCS Vol. 6795).

38. A. N. Plyushchenko, A. M. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x2 = x3 // Internat. J. Algebra Comput. 2011. Vol. 21. P. 973−1006.