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

• Автор: Плющенко, Андрей Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Екатеринбург
• Количество страниц: 108 с.

Оглавление
Введение
1° Предварительные сведения
1°.1 Слова
1°.2 Языки и автоматы
1°.3 Свободные бернсайдовы полугруппы, моноиды, группы
2° Обзор исследований в предметной области
2°.1 Общие методы и результаты
2°.2 Случай п
2°.3 Случай п
2°.4 Случай п
3° Обзор диссертации
3°.1 Цели диссертации. Основные проблемы
3°.2 Основные результаты
3°.3 Основные методы
3°.4 Структура диссертации и организация текста
3°.5 Апробация и публикации
Глава 1. Полугруппы В(к, 2,3)
§ 1.1 Введение и формулировка результатов
§ 1.2 Основная техника, используемая в диссертации
§ 1.3 Построение отображения а
§1.4 Доказательство основных результатов
§1.5 Обобщение результатов на полугруппы В{к, 2,2 + т)
Глава 2. Проблема равенства слов для полугруппы В(2,2,3)
§2.1 Введение и формулировка результатов
§ 2.2 Свойства г-редукции
2.2.1 Нередуцируемые хвосты. Свойство г (и) ~ 17
2.2.2 Регулярные соседние слова и квазисоседние слова
§ 2.3 Нерегулярные почти сильно бескубные слова. Хвосты первого рода

ОГЛАВЛЕНИЕ
2.3.1 Нерегулярные почти сильно бескубные слова
2.3.2 Хвосты первого рода. Операция Гу
2.3.3 Классы [112112211211] и [221221122122]Г1
§ 2.4 Функции £ и г]
§2.5 Доказательство теоремы
§ 2.6 Главные и нормальные ряды
2.6.1 Процедура Ancestor. Главные ряды
2.6.2 Нормальные ряды
2.6.3 Обработка плохих пар
§2.7 Алгоритм EqAOF. Доказательство теоремы
Глава 3. Приложения алгоритма EqAOF и обобщение результатов
§ 3.1 Гипотеза Бжозовского и другие приложения
3.1.1 Описание класса эквивалентности произвольного почти сильно бес-кубного слова
3.1.2 Гипотеза Бжозовского
3.1.3 Слова минимальной длины
§ 3.2 Индекс роста классов эквивалентности
§3.3 Обобщение результатов на почти 7/3-свободные слова

Список литературы

Введение
Теория бсрисайдовых полугрупп, или полугрупп с тождеством хп = хп+пг для некоторых п, ггг > 1 занимает важное место в теории периодических полугрупп. Бернсайдовы полугруппы возникают при рассмотрении полугрупп с ограниченным периодом. Проблематика бернсайдовых полугрупп естественным образом развивает аналогичную проблематику для бернсайдовых групп, т. е. групп с тождеством хт = 1. Изучение последних было начато в 1902 году Бернсайдом, интересовавшимся, всякая ли конечно порожденная группа с ограниченным периодом конечна (так называемая ограниченная проблема Бернсайда).
Важнейшими объектами для исследования, несомненно, являются свободные бернсайдовы полугруппы, то есть полугруппы, свободные в многообразии уаг{хп = хп+т} (для фиксированных п,т 1), поскольку всякая полугруппа из уаг{хп — хп+т} есть гомоморфный образ подходящей свободной бсрнсайдовой полугруппы.
Свободным бернсайдовым полугруппам посвящено немало исследований, проясняющих многие особенности их внутренней структуры. Был разработан соответствующий инструментарий для изучения таких полугрупп, использующий как теоретико-групповые методы, так и методы теории формальных языков (в этом случае элементы свободной бернсайдовой полугруппы рассматриваются как классы эквивалентных слов над соответствующим алфавитом), методы общей комбинаторики и теории графов. Краткий обзор результатов приводится ниже в § 2°. Более подробно с теорией бернсайдовых полугрупп можно ознакомиться, например, по обзорной статье [20], немало интересных сведений можно почерпнуть из книг по теории полугрупп [3,15] и др.
Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы. Тесным образом решение проблемы равенства слов связано с гипотезой о том, что любой элемент свободной бернсайдовой полугруппы является рациональным языком. Эта гипотеза, сформулированная Бжозовским в 1969 году для полугрупп с тождеством хп = хп+1, была затем расширена Маккаммондом на случай произвольных пит. Заметим, что из справедливости (обобщенной) гипотезы Бжозовского вытекает разрешимость проблемы равенства слов в рассматриваемой полугруппе.
Центральное место в диссертации отведено исследованию проблемы равенства слов и гипотезы Бжозовского для свободных бернсайдовых полугрупп. К настоящему времени,
ГЛАВА 1. ПОЛУГРУППЫ В(к, 2,3)

Таким образом, слово В.РС1121 является блоком, первый контент которого совпадает с первыми контентами блоков Вр и Вр-. Следовательно, Вр- ~ Вр ~ НРС} 1121. Заметим, что подслова ХРСО 1121 и RPQRZ блочного слова и состоят из целого числа блоков. Ввиду равенств
хууг = хр(з іщшК2 = (хребті) о1121 (іірсдіг)

хуугг =х.рд; 121 12% д її 21122, длг
ДР ДР
(хрдіїгі) оШ1 (дрдіі2і) °1121 (дрддг),
оба слова II и У являются блочными. Преобразование У* -» У‘ в слове І/ индуцирует преобразование (1Т[р])г —> (ИДр])* в его прообразе IV = 5_1(С/), поэтому прообразы слов и и V являются соседними, что и требовалось доказать. □
Теорема 1.1 непосредственно следует из леммы о сведении.
Доказательство теоремы 1.2. Для доказательства нетривиальной импликации теоремы рассмотрим морфизм /?: Е£ —+ Е2, действующий на Е* по правилу: /3(і) = а(г)(1121)-1. Несложно проверить, что а(и) = (3(11)1121 для любого слова и Є ЕД Если гипотеза Бжозовского справедлива для полугруппы В(2, 2,3), то для любого слова II Є Щ класс [«([/)] является рациональным языком. Следовательно, класс ГГ = /?_1([сс(С/)](1121)"1) также является рациональным языком, поэтому гипотеза Бжозовского справедлива и для полугруппы В(к, 2,3). □
§1.5 Обобщение результатов на полугруппы В (к, 2, 2+т)
До сих пор мы рассматривали только полугруппы В(к, 2,3). Оказывается, при небольших изменениях в доказательстве, теоремы 1.1 и 1.2 могут быть обобщены на полугруппы В(к, 2,2 + т) с произвольным значением т. А именно, справедливы следующие две теоремы.
Теорема 1.3. Проблема равенства слов для полугруппы, В (к, 2,2 + т) ранга к 2 разрешима тогда и только тогда, когда проблема равенства слов разрешима для полугруппы В(2, 2,2 + тп).
Теорема 1.4. Гипотеза Бжозовского для полугруппы В(к, 2,2 +т) при к 2 справедлива тогда и только тогда, когда гипотеза справедлива для полугруппы. В(2,2,2 + т).
Зафиксируем параметры т > 1 и к 2 и рассмотрим полугруппу В (к, 2,2 + т). В этом параграфе, при отсутствии индексов, под обозначениями ~, тг и [У] (где IV Є ЕД мы