Введение к работе
Актуальность темы. Полугруппы, удовлетворяющие тождеству вида хп = хп+т для некоторых п,т ^ 1, образуют важный подкласс класса всех периодических полугрупп и представляют собой классический объект исследования. Такие полугруппы называют полугруппами бернсай-дова типа, или бернсайдовыми полугруппами. Проблематика бернсайдовых полугрупп естественным образом развивает аналогичную проблематику для бернсайдовых групп, т. е. групп с тождеством хт = 1. Изучение последних было начато в 1902 году Бернсайдом [8], интересовавшимся, всякая ли конечно порожденная группа с ограниченным периодом конечна (так называемая ограниченная проблема Бернсайда).
Важное место в теории бернсайдовых полугрупп занимают свободные бернсайдовы полугруппы — полугруппы, свободные в многообразии var{xra = хп+т} (для фиксированных п,т ^ 1), так как всякая полугруппа из var{xra = хп+т} есть гомоморфный образ подходящей свободной бернсайдовой полугруппы.
Свободные бернсайдовы полугруппы изучались многими исследователями, начиная со второй половины XX века и по настоящее время. Был разработан соответствующий инструментарий для изучения таких полугрупп, использующий как теоретико-групповые методы, так и методы теории формальных языков (в этом случае элементы свободной бернсайдовой полугруппы рассматриваются как классы эквивалентных слов над соответствующим алфавитом), методы общей комбинаторики и теории графов. Всплеск активности в этой области наблюдался в 1990-ые годы: благодаря целому ряду работ (Кадорек и Полак [19], де Лука и Варик-кио [9,10], Маккаммонд [21], до Лаго [12-14], В. С. Губа [17,18]), удалось установить немало важных свойств, проясняющих внутреннюю структуру таких полугрупп, а также решить ряд ключевых проблем для свободных бернсайдовых полугрупп. Более подробно с теорией бернсайдовых полугрупп можно ознакомиться, например, по обзорной статье [15], книгам по теории полугрупп [3,11] и др.
Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы. Тесным образом решение проблемы равенства слов связано с гипотезой о том, что любой элемент свободной бернсайдовой полугруппы является рациональным языком. Эта гипотеза, сформулированная Бжозовским в 1969 году для полугрупп с тождеством хп = xn+l, была затем расширена Маккаммондом на случай произвольных пит.
К настоящему времени удалось достаточно хорошо описать строение свободных бернсайдовых полугрупп произвольного ранга к и тождеством хп = хп+т (для таких полугрупп мы будем использовать обозначение В(к,п,п + т)) при п ^ 3. Так, например, в [13] показывается, что все максимальные подгруппы полугруппы В(к,п,п + т) при п ^ 3 циклические порядка т, а каждый элемент такой полугруппы, рассматриваемый как класс эквивалентных слов, содержит единственное слово минимальной длины. В 1990 году де Лука и Вариккио подтвердили гипотезу Бжозовского для полугрупп В(к, п, п-\-1) с п ^ 5 ([9]). Маккаммонд распространил эту гипотезу на случай полугруппы В(к,п, п-\-т) с произвольным т ^ 1 и независимо доказал ее справедливость при п ^ 6, т ^ 1 ([21], 1991). Позже до Лаго усовершенствовал метод де Луки и Вариккио и улучшил оценку до п ^ 4,т ^ 1 ([12], 1992). Наконец, В. С. Губа показал справедливость гипотезы для п ^ 3,т ^ 1 ([17,18], 1993).
Разрешимость проблемы равенства слов следует из справедливости гипотезы Бжозовского: так как всякий элемент полугруппы В(к, п, п-\-т) является рациональным языком, мы можем по одному из двух данных слов построить автомат, распознающий его класс эквивалентности, и проверить, распознает ли этот автомат второе слово.
Несмотря на то, что в общем случае вопрос о разрешимости проблемы равенства слов для полугрупп В (к, 1,1 + т) остается открытым, ответ на него определенным образом зависит от ответа на аналогичный вопрос для свободных бернсайдовых групп (см. [19]). В частности, проблема равенства слов разрешима при т = 1,2, 3,4, 6, так как в этом случае свободная бернсайдова группа В{к,т) (ранга к ж с тождеством хт = 1) конечна для любого к. Более того, в серии работ [1,4-6] показывается разрешимость проблемы равенства слов для групп В(к,т) при любом к и нечетном т ^ 665 или кратном 16 значении т ^ 8000. Следовательно, проблема равенства слов разрешима и для полугрупп В(к, 1,1 + т) при тех же значениях т. Во всех остальных случаях проблема равенства слов остается открытой. Что касается гипотезы Бжозовского, она, очевидно, справедлива для конечных полугрупп В (к, 1,1 + га). Опираясь на результаты работ [1,4-6], до Лаго показал ([14]), что гипотеза Бжозовского неверна для полугрупп В(к, 1,1+ т), где к > 1, при т ^ 8000 и при нечетном т ^ 665. Для остальных значений тик вопрос остается открытым. Кроме того, получено достаточно хорошее описание структуры полугруппы В (к, 1,1 + т) для любого т ^ 1, в частности, работа Грина и Риса ([16]) дает простое описание D-классов такой полугруппы.
Наименее изученными остаются полугруппы с тождеством х2 = х2+т : проблема равенства слов в этом случае до сих пор не решена, а гипотеза Бжозовского при больших значениях т оказывается неверной (см. [14]).
Структура полугрупп В (к, 2, 2 + га) при га ^ 2 оказывается сложнее структуры полугрупп В(к,п,п + га) при п ^ 3,га ^ 1. Так, например, известно ([14]), что полугруппа В{к, 2,2 + га) при к > 1 и га ^ 2 содержит максимальные подгруппы, не являющиеся циклическими группами, а также существуют элементы полугруппы, которые как классы эквивалентных слов содержат несколько слов минимальной длины. Случай га = 1 остается единственным, при котором полугруппа В (к, 2, 2 + га) еще может иметь достаточно простую структуру. В связи с этим, особый интерес представляют полугруппы В(к,2,3): интерес этот вызван и тем, что полугруппы вида В(к,п,п -\- I) составляют важный подкласс бернсайдовых полугрупп. Исторически теория бернсайдовых полугрупп (исключая бернсайдовы группы) начиналась с изучения именно таких полугрупп. Отметим, гипотеза Бжозовского была выдвинута для свободных бернсайдовых полугрупп с тождеством ха = xn+l и еще в 1980 году была включена Бжозовским в список открытых проблем [7]; лишь позже Маккаммонд распространил эту гипотезу на любые бернсайдовы полугруппы. Среди свободных бернсайдовых полугрупп с тождеством Xа = xn+l полугруппы В(к, 2,3) — единственные, для которых и проблема равенства слов, и гипотеза Бжозовского остаются открытыми.
Цель работы. Основной целью диссертации является исследование проблемы равенства слов и гипотезы Бжозовского для полугрупп В (к, 2,3): разработка новых методов и подходов к решению данных проблем. Часть полученных в диссертации результатов обобщается на полугруппы В{к, 2,2 + га) для произвольного га-Научная новизна. Все результаты являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории полугрупп и комбинаторике слов, а также в учебном процессе при чтении специальных курсов.
Апробация результатов работы. Результаты диссертации были представлены на XIV международной конференции студентов, аспирантов и молодых ученых «Ломоносов 2007», на свердловском областном конкурсе студенческих работ «Олимп-2007», на 6-й международной конференции по комбинаторике слов WORDS2007 (Марсель, 2007), «Международной конференции по полугруппам, алгебре и приложениям ААА82» (Потсдам, 2011), 15-й международной конференции «Развитие теории языков» (Милан, 2011), международной конференции «Мальцевские чтения» (Новосибирск, 2011). Автор выступал с докладами по теме диссер-
тации на семинаре «Алгебраические системы» (УрГУ, рук. Л. Н. Шев-рин, 2007-2011), на алгебраическом семинаре института математики и механики УрО РАН (2011), на семинаре «Алгоритмические вопросы алгебры и логики» (МГУ, рук. С. И. Адян, 2011).
Публикации. По теме диссертации написано 7 работ: [23-29]. Из них статья [26] опубликована в издании из списка, рекомендованного ВАК, а статьи [28,29] — в зарубежных изданиях, удовлетворяющих достаточному условию ВАК. Работы [23,25] являются тезисами (в том числе электронная публикация [25]); статьи [27,28] опубликованы в сборниках трудов конференций; 3 работы ([27-29]) написаны совместно с А. М. Шуром, однако доказательства основных результатов принадлежат автору.
Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 108 страниц. Библиографический список содержит 39 наименований.
Похожие диссертации на О комбинаторных свойствах бернсайдовых полугрупп
