«БЕРНСАЙДОВЫХ ПОЛУГРУПП ...»

ФГАОУ ВПО Уральский федеральный университет

имени первого Президента России Б. Н. Ельцина

На правах рукописи

ПЛЮЩЕНКО Андрей Николаевич

УДК 512.531

О КОМБИНАТОРНЫХ СВОЙСТВАХ

БЕРНСАЙДОВЫХ ПОЛУГРУПП

01.01.06 Математическая логика, алгебра и теория чисел

Диссертация на соискание ученой степени кандидата физика-математических наук

Научный руководитель:

доктор физико-математических наук Шур Арсений Михайлович Екатеринбург 2011 г.

Оглавление Введение 1 Предварительные сведения............................ 1.1 Слова..................................... 1.2 Языки и автоматы.............................. 1.3 Свободные бернсайдовы полугруппы, моноиды, группы........ 2 Обзор исследований в предметной области................... 2.1 Общие методы и результаты........................ 2.2 Случай n = 1................................. 2.3 Случай n 3................................. 2.4 Случай n = 2................................. 3 Обзор диссертации................................. 3.1 Цели диссертации. Основные проблемы................. 3.2 Основные результаты............................ 3.3 Основные методы.............................. 3.4 Структура диссертации и организация текста.............. 3.5 Апробация и публикации.......................... Глава 1. Полугруппы B(k, 2, 3) § 1.1 Введение и формулировка результатов..................... § 1.2 Основная техника, используемая в диссертации................ § 1.3 Построение отображения............................ § 1.4 Доказательство основных результатов...................... § 1.5 Обобщение результатов на полугруппы B(k, 2, 2 + m)............. Глава 2. Проблема равенства слов для полугруппы B(2, 2, 3) § 2.1 Введение и формулировка результатов..................... § 2.2 Свойства r-редукции................................ 2.2.1 Нередуцируемые хвосты. Свойство r(U ) U.............. 2.2.2 Регулярные соседние слова и квазисоседние слова........... § 2.3 Нерегулярные почти сильно бескубные слова. Хвосты первого рода.....

ОГЛАВЛЕНИЕ

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

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

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

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

Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом из свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы.

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

Центральное место в диссертации отведено исследованию проблемы равенства слов и

ВВЕДЕНИЕ

гипотезы Бжозовского для свободных бернсайдовых полугрупп. К настоящему времени, благодаря целому ряду работ, удалось подтвердить гипотезу Бжозовского и, как следствие, решить проблему равенства слов для случая n 3. Значимые результаты получены и для полугрупп с n = 1 (см. § 2 ). Наименее изученными остаются полугруппы с тождеством x2 = x2+m : проблема равенства слов в этом случае до сих пор не решена, а гипотеза Бжозовского при большх значениях m оказывается неверной. В данной работе рассматриваются полугруппы с тождеством x2 = x3, для которых обе исследуемые проблемы остаются открытыми. Часть полученных в диссертации результатов обобщается на случай n = 2 и произвольного m. Отметим, что важность изучения именно свободных бернсайдовых полугрупп с тождеством x2 = x3 была подчеркнута Бжозовским, включившим еще в 1980 году проблему равенства слов для таких полугрупп в список открытых проблем [9].

1 Предварительные сведения В этом параграфе мы приводим базовые определения и обозначения, необходимые для понимания результатов диссертации. Большой объем справочной информации по данной тематике содержится в [3, 28].

1.1 Слова 1. Алфавит это непустое множество, элементы которого называются буквами или символами. В данной работе рассматриваются только конечные алфавиты. В дальнейшем, k = {1,..., k}, где k = 1, 2,.... Для обозначения некоторой (неизвестной) буквы в слове используются строчные латинские буквы из начала алфавита.

Словом называется произвольная конечная последовательность букв: W = a1 a2... an.

Число n называется длиной слова W. Длина слова W обозначается через |W |, а его i-ая буква через W [i]. Таким образом, W = W [1]W [2]... W [|W |] или просто W = W [1... |W |]. Символ обозначает пустое слово, имеющее длину 0. Для обозначения слов используются заглавные латинские буквы из второй половины алфавита.

2. Обозначения, +, n используются, соответственно, для множества всех слов, всех непустых слов, слов длины n над алфавитом. Множества + и образуют, соответственно, свободную полугруппу и свободный моноид относительно операции конкатенации (приписывания). Конкатенация слов U и V записывается как U V. Положим для обозначения n-ой степени слова U ; по определению, U 0 =.

Слово Y называется подсловом слова U (обозначается Y U ), если существуют такие слова X, Z, что U = XY Z. Слово Y называется собственным подсловом слова U

ВВЕДЕНИЕ

(обозн. Y < U ), если Y подсловом слова U (обозначается Y U ), если существуют такие слова X, Z +, что U = XY Z. Таким образом, внутреннее подслово Y начинается не раньше второй буквы в слове U и заканчивается не позже предпоследней буквы, то есть содержится целиком внутри U. Слово Y называется префиксом (суффиксом) слова U, если существует слово Z такое, что U = Y Z (соответственно, U = ZY ). Если при этом слово Z непустое, Y называется собственным префиксом (соответственно, собственным суффиксом) слова U.

Подслово Y может входить в слово U несколькими способами; каждое такое вхождение Y в U однозначно определяется позицией первой буквы слова Y в U. Расстояние между вхождениями это разность соответствующих позиций. В дальнейшем под термином подслово часто понимается конкретное вхождение какого-то подслова: из контекста будет понятно, идет ли речь о подслове или о его вхождении.

3. Периодом слова W называется число p со свойством: W [i] = W [i+p] для любого i = 1,..., |W |p. Экспонентой exp(W ) слова W называется отношение длины слова W к его минимальному периоду, а локальной экспонентой lexp(W ) максимум из экспонент всех подслов слова W. Наконец, введем понятие сильно локальной экспоненты lexp< (W ) слова W как максимум из экспонент всех собственных подслов слова W.

Проиллюстрируем введенные в предыдущем абзаце определения примерами.

W = 1211121 имеет периоды 4 и 6; |W | = 7, exp(W ) = 7/4, lexp(W ) = 3, lexp< (W ) = 3;

W = Слово W называется -свободным, если lexp(W ) <, и называется + -свободным, свободным), если, соответственно, lexp< (W ) < и lexp< (W ). [Почти] 2-свободные, (3свободные, 2+ -свободные) слова называют также [почти] бесквадратными (соответственно, бескубными, сильно бескубными) словами.

Пусть <. Очевидно, что любое - или + -свободное слово является также и или, соответственно, + -свободным. Аналогичное утверждение справедливо и для почти свободных слов. Однако слово W может быть почти - или + -свободным, но не являться - или + -свободным. Так, например, слово 111 почти сильно бескубно, но при этом оно является кубом.

4. Морфизмом называется гомоморфизм свободных моноидов. Единственный нетривиальный автоморфизм свободного моноида называется операцией инвертирования и обозначается. Таким образом, операция инвертирования переобозначает буквы в слове:

1 = 2, 2 = 1.

Морфизм Туэ-Морса : задается равенствами (1) = 12 и (2) = 21. Обозначим tn = n (1), тогда tn = n (2). Слова tn и tn называются словами Туэ-Морса.

ВВЕДЕНИЕ

Очевидно, морфизм Туэ-Морса инъективен. Обратное отображение из ( ) в свободный моноид обозначается через 1.

1.2 Языки и автоматы 1. Языком над алфавитом называют произвольное подмножество свободного моноида. Напомним определения основных операций над языками. Под объединением языков L и K (обозначается L K или L + K) понимают их теоретико-множественное объединение, произведением L и K называется язык левое K1 L и правое LK1 частные языков L и K определяются как соответственно. Положим L = Li, L+ = Li (операция называется итерацией).

При записи одноэлементных языков вида {W }, где W, фигурные скобки опускаются.

Например, вместо K{W }1 и {W } мы пишем просто KW 1 и W.

Естественным образом на языки распространяются операции взятия образа и прообраза:

для произвольного отображения h : и языков L, K.

Язык называется рациональным, или регулярным, если он может быть записан при помощи регулярного выражения выражения, содержащего одноэлементные языки и операции объединения, произведения и итерации языков.

Класс рациональных языков замкнут относительно взятия частного и прообраза любого морфизма. Таким образом, для произвольных языков L, K и любого морфизма h :, если язык L рациональный, то и языки LK1 и h1 (L) оказываются рациональными.

В дальнейшем, при рассмотрении регулярных выражений мы будем часто употреблять фразу слово имеет вид : слово W имеет вид (12) 1, слово W вида (12 + 21) и т. п., подразумевая, что слово W принадлежит языку, задаваемому соответствующим регулярным выражением.

2. Детерминированным конечным автоматом (ДКА) называется пятерка (Q,,, s, T ), состоящая из конечного множества состояний (вершин) Q, алфавита , функции перехода : Q Q, начального состояния s Q и множества конечных (терминальных) состояний T Q. Конечный автомат удобно отождествлять с орграфом с множеством вершин Q (и метками, указывающими, является ли вершина начальной и/или конечной) и множеством дуг вида q aq, определяемых условиями (q, a) = q. Операция естественным образом распространяется на слова:

ВВЕДЕНИЕ

Каждый маршрут в автомате помечен словом над алфавитом. ДКА распознает (принимает) слово W, если существует хотя бы один маршрут из начальной вершины в какую-либо из конечных, помеченный словом W. Язык всех распознаваемых ДКА A слов обозначается через L(A). Говорят, что ДКА A распознает язык L(A).

Недетерминированный конечный автомат (НКА) получается из понятия ДКА путем двух обобщений: начальное состояние s заменяется множеством начальных состояний I, а функция перехода : Q Q заменяется на тернарное отношение Q Q.

Представление орграфом, распознаваемый язык определяются так же, как и для ДКА.

Согласно теоремам Рабина-Скотта и Клини, классы языков, распознаваемых ДКА и НКА, совпадают с классом рациональных языков (см., например, [3]).

3. Для любого языка L комбинаторная сложность есть функция pL (n) : N0 N0, которая определяется как pL (n) = |L n |. В дальнейшем термин сложность применительно к языку означает комбинаторную сложность.

Основным инструментом для оценки степени роста комбинаторной сложности языка служит индекс роста gr(L) = limn pL (n)1/n.

1.3 Свободные бернсайдовы полугруппы, моноиды, группы 1. Свободный бернсайдов моноид ранга k и тождеством xn = xn+m для некоторых фиксированных чисел n 0, m 1 с точностью до изоморфизма определяется как фактормоноид свободного моноида по конгруэнции k,n,m, порожденной всеми парами вида (Y n, Y n+m ), где Y +. Моноиды B(k, 0, m) являются группами, которые называются свободными бернсайдовыми группами и обозначаются B(k, m). Свободная бернсайдова полугруппа B(k, n, n + m), где n, m 1, получается из моноида B(k, n, n + m) удалением единицы (нейтрального элемента) класса эквивалентности, состоящего из пустого слова. Того же результата можно достичь, заменив на + и слово моноид на слово полугрупk k па в определении свободного бернсайдова моноида B(k, n, n+m). Класс эквивалентности k,n,m, содержащий слово W, обозначается через [W ]k,n,m.

Все результаты диссертации формулируются для свободных бернсайдовых полугрупп, однако те же результаты справедливы и для соответствующих этим полугруппам свободных бернсайдовых моноидов. Более того, в дальнейшем мы часто будем иметь дело именно с моноидами, рассматривая пустое слово и класс []k,n,m везде, где это необходимо.

2. Для работы с конгруэнцией k,n,m удобно ввести отношения соседства k,n,m :

Слова U и V мы называем соседними, если (U, V ) k,n,m (при фиксированных параметрах n, m и k). Легко проверить, что k,n,m = k,n,m, то есть конгруэнция k,n,m является транзитивным замыканием отношения соседства k,n,m.

ВВЕДЕНИЕ

Ввиду вложенности множеств 1 2 3..., полугруппа B(k, n, n + m) является подполугруппой полугруппы B(k, n, n + m), а моноид B(k, n, n + m) подмоноидом моноида B(k, n, n + m), если k < k. Это позволяет нам опускать индекс k в обозначениях k,n,m, k,n,m и [W ]k,n,m, где W.

2 Обзор исследований в предметной области В данном параграфе приводится краткий обзор исследований и основных результатов других авторов в теории бернсайдовых полугрупп. Более подробно с проблематикой и историей развития данной предметной области можно ознакомиться, например, по обзорной статье [20]; немало интересной информации о бернсайдовых полугруппах можно почерпнуть из книг по общей теории полугрупп, таких как [3, 15], и др.

Основные затрагиваемые здесь проблемы следующие:

Проблема конечности (ограниченная проблема Бернсайда): при каких n, m и k полугруппа B(k, n, n + m) бесконечна? Эта проблема была впервые сформулирована Бернсайдом в 1902 году для бернсайдовых групп. Позже она была распространена на случай произвольной бернсайдовой полугруппы.

(Обобщенная) гипотеза Бжозовского: всякий элемент свободной бернсайдовой полугруппы является рациональным языком над соответствующим алфавитом. Гипотеза была сформулирована Бжозовским в 1969 году для полугрупп B(k, n, n + 1), позже Маккаммонд распространил ее на случай произвольной свободной бернсайдовой полугруппы.

Проблема равенства слов: По произвольно заданным словам U и V определить, представляют ли они один и тот же элемент полугруппы.

Описание структуры полугруппы в терминах отношений Грина, максимальных подгрупп и др.

Ясно, что полугруппы B(1, n, n + m) суть конечные циклические полугруппы, структура которых давно изучена, каждый их элемент является рациональным языком и проблема равенства слов для таких полугрупп разрешима. Ввиду тривиальности этого случая, в дальнейшем, если не оговорено противное, мы полагаем k > 1.

Свойства свободных бернсайдовых полугрупп существенно зависят от параметра n.

Выделяют три существенно различных случая: n = 1, n = 2 и n 3. Рассмотрение бернсайдовых групп выходит за рамки диссертации, однако, ввиду тесной связи результатов для групп B(k, m) и полугрупп B(k, 1, 1 + m), бернсайдовы группы будут затронуты в разделе, посвященном случаю n = 1.

В соответствии с вышесказанным, сначала мы рассмотрим некоторые общие методы и результаты, справедливые для всех свободных бернсайдовых полугрупп B(k, n, n + m), а затем опишем состояние дел по каждому из этих трех случаев.

ВВЕДЕНИЕ

2.1 Общие методы и результаты Зафиксируем параметры k, n, m 1 и рассмотрим полугруппу B(k, n, n + m). Алфавит k будем обозначать символом, а в обозначениях n,m и [W ]n,m (где W ) будем опускать индексы n и m.

В качестве основного инструмента для описания структуры свободных бернсайдовых полугрупп используют отношения Грина R, L, H, D и J. Заметим, что ввиду периодичности свободных бернсайдовых полугрупп, мы имеем D = J.

Строение нерегулярных H-классов полугруппы B(k, n, n + m) описывается следующим предложением (см., например, [19]).

Предложение I. Все нерегулярные H-классы свободной бернсайдовой полугруппы тривиальны.

Несложно доказать, что если n = 1, то все D-классы регулярны. В общем случае это не так, как показывает следующий пример.

Пример ([19]). Рассмотрим полугруппу B(k, n, n + m) с n 2. Тогда D-класс слова [1n 2n ], который совпадает с множеством {[1i 2j ] | i, j n}, нерегулярен, а его H-классы тривиальны.

Характеризация нерегулярных D-классов была получена в терминах теории графов, с использованием фундаментального графа D-класса. Опишем кратко эту весьма полезную конструкцию (фундаментальный граф с примерами его построения подробно рассматривается в [19, 20]).

Отношения Грина в полугруппе индуцируют отношения R, L, H, D и J в соответственно следующим образом:

Слово W мы называем D-входом, если никакое его подслово не лежит в его D -классе.

Переходом (D-переходом) называется любое слово aXb, где a, b, такое, что элементы [aX], [aXb] и [Xb] лежат в одном D-классе, а элемент [X] этому D-классу не принадлежит.

Зафиксируем теперь произвольный элемент [W ] полугруппы. Фундаментальным графом D-класса элемента [W ], или просто фундаментальным графом элемента [W ], называется четверка (V, E,, ), где множество вершин V состоит из всех D-входов, содержащихся в D -классе W, множество ребер E состоит из всех D-переходов D -класса W (строго говоря, множества V и E состоят не из самих D-входов и D-переходов, а из соответствующих им классов эквивалентности), а : E V и : E V две специальные функции инцидентности графа, определяющие для любого D-перехода T начальную (T ) и конечную (T ) вершины как D-входы, являющиеся, соответственно, префиксом и суффиксом слова T. Построенный таким образом граф оказывается сильно связным ([19, 20]).

Теперь приведем описание произвольного нерегулярного D-класса через его фундаментальный граф.

ВВЕДЕНИЕ

Предложение II ([19]). Фундаментальный граф нерегулярного D-класса свободной берснайдовой полугруппы не имеет ребер и состоит из одной вершины.

Величина |E(G)||V (G)|+1 называется цикломатическим числом фундаментального графа G = (V, E). Используя понятие цикломатического числа фундаментального графа, до Лаго описал строение максимальных подгрупп свободной бернсайдовой полугруппы.

Теорема III (теорема о максимальных подгруппах, до Лаго, [18, 19]). Максимальными подгруппами полугруппы B(k, n, n + m) являются в точности свободные бернсайдовы группы с тождеством xm = 1. Если при этом m 2, каждая такая группа имеет ранг, равный цикломатическому числу фундаментального графа D-класса, в котором группа содержится.

В работах [18, 19] также показывается, как построить множество, порождающее максимальную подгруппу.

Следующий важный результат справедлив для произвольных моноидов, в том числе и для моноида B(k, n, n + m) и соответствующей ему бернсайдовой полугруппы.

Теорема IV ([13]). Пусть дан произвольный алфавит и сюръективный гомоморфизм : M свободного моноида на некоторый моноид M. Тогда если M содержит бесконечный H-класс H, то для любого элемента h H язык {W | X = h} не является рациональным.

Теоремы III и IV позволяют установить тесную связь между гипотезой Бжозовского для полугруппы B(k, n, n + m) и проблемой конечности для бернсайдовых полугрупп с тождеством xm = 1. Действительно, возьмем в качестве алфавит k и рассмотрим сюръективный гомоморфизм : B(k, n, n + m), ставящий в соответствие любому слову W его класс эквивалентности [W ]n,m. Согласно теореме IV, для того, чтобы класс [W ] был рациональным языком, необходимо, чтобы H-класс элемента [W ] был конечным.

Согласно классическому результату теории полугрупп (см., например, [3]), всякая максимальная подгруппа полугруппы B(k, n, n+m) совпадает с некоторым ее H-классом. Таким образом, ответ на вопрос, верна гипотеза Бжозовского для полугруппы B(k, n, n + m) или нет, существенно зависит от того, содержит ли полугруппа B(k, n, n + m) бесконечные подгруппы, или, ввиду теоремы III, конечны ли свободные бернсайдовы группы с тождеством xm = 1 и рангом, принимающим значения из множества, образованного цикломатическими числами фундаментальных графов всех регулярных D-классов полугруппы B(k, n, n + m).

2.2 Случай n = Структура свободных бернсайдовых полугрупп с тождеством x1+m = x была в достаточной мере исследована в работе Грина и Риса [21] еще в 1952 году. Центральным понятием,

ВВЕДЕНИЕ

используемым для описания таких полугрупп, служит понятие содержания слова множества c(W ) всех букв, встречающихся в слове W.

Так, в [21] получена достаточно простая характеризация отношения D в терминах содержания слов:

В частности, моноид B(k, 1, 1 + m) имеет в точности 2k различных D-классов. Обозначим через Dk,m мощность D-класса, содержание элементов которого есть k, через Gk,m цикломатическое число фундаментального графа такого D-класса, и через Mk,m мощность моноида B(k, 1, 1+m). Мощность бернсайдовой группы B(k, m) (для произвольного k ) будем обозначать через Bk,m (по теореме III, максимальными подгруппами D-классов моноида B(k, 1, 1 + m) являются свободные бернсайдовы группы с тождеством xm = 1).

Предположим, что значение Bk,m конечно и известно для любого k (параметр m зафиксирован). Тогда следующие величины могут быть вычислены рекуррентно ([20]):

где Ck биномиальные коэффициенты.

Конечность и бесконечность полугрупп B(k, 1, 1 + m). Проблема конечности полугрупп с тождеством x1+m = x тесно связана с проблемой конечности свободных бернсайдовых групп с тождеством xm = 1. Следующий результат принадлежит Грину и Рису:

Теорема V ([21]). Следующие условия эквивалентны для любого m:

(1) B(k, 1, 1 + m) конечна для любого k;

(2) B(k, m) конечна для любого k.

Свободные бернсайдовы группы B(k, 1) конечны (и тривиальны), конечность B(k, m) при любом k была доказана Бернсайдом [11] для m = 2; Бернсайдом [11], де Леви и ван дер Варденом [27] для m = 3; И. Н. Сановым [7] для m = 4; М. Холлом [24] для m = 6.

В 1968 г. П. С. Новиков и С. И. Адян в серии работ [1,5,6] показали, что группы B(k, m) бесконечны для любого k > 1 и любого нечетного m 665. В 1992г. С. В. Иванов ([25]) менно с этим, И. Г. Лысенок анонсировал оценку m

ВВЕДЕНИЕ

работы [4], эту оценку удалось улучшить до n 8000. Во всех этих случаях полугруппы B(k, 1, 1 + m) также оказываются бесконечными.

Проблема остается открытой для m = 5, m [7, 664] и случая, когда m [666, 7998] и m четно.

Проблема равенства слов и гипотеза Бжозовского. Следующая теорема, по формулировке напоминающая теорему V, была получена Кадореком и Полаком в 1980 году. Она позволяет в некоторых случаях свести проблему равенства слов в полугруппе B(k, 1, 1+m) к соответствующей проблеме для группы B(k, m).

Теорема VI ([26]). Предположим, что проблема равенства слов разрешима для группы B(k, m) при любом k. Тогда проблема равенства слов разрешима и для полугруппы B(k, 1, 1 + m) с тем же значением m и любым значением k.

В частности, проблема равенства слов разрешима при m = 1, 2, 3, 4, 6, так как в этом случае группа B(k, m) конечна для любого k. Более того, в серии работ [1, 4–6] показывается разрешимость проблемы равенства слов для групп B(k, m) при любом k и нечетном m 665 или кратном 16 значении m 8000. Во всех остальных случаях проблема равенства слов остается открытой.

Что касается обобщенной гипотезы Бжозовского, она, очевидно, справедлива для конечных полугрупп B(k, 1, 1+m). В [18] до Лаго показал, что все максимальные подгруппы D-класса элемента [123]1,m являются свободными бернсайдовыми группами с тождеством группы будут бесконечными, и, в силу теорем III и IV, все элементы данного D-класса, рассматриваемые как языки над алфавитом из свободных порождающих, не являются рациональными языками. Таким образом, при m 8000 (а также нечетном m 665) и k гипотеза Бжозовского для полугруппы B(k, 1, 1 + m) неверна. Для остальных значений m и k вопрос остается открытым.

Этот случай является наиболее исследованным: структура полугрупп B(k, n, n + m) при 3 хорошо описана и все ключевые проблемы (проблема конечности, проблема раn венства слов и проверка гипотезы Бжозовского) к настоящему времени решены. Большая часть результатов получена совместными усилиями различных авторов в серии работ [12, 14, 16, 17, 22, 23, 29], в которых постепенно понижалась нижняя граница для n.

Структура полугрупп при n 3. Отметим три наиболее интересных результата. Вопервых, в каждом классе эквивалентности полугруппы B(k, n, n + m) единственно слово минимальной длины. Таким образом, слова минимальной длины можно выбирать в качестве канонических представителей своих классов эквивалентности.

Во-вторых, J -остов полугруппы B(k, n, n + m) при n 3 удовлетворяет следующему условию конечности.

ВВЕДЕНИЕ

Предложение VII ([14, 17]). Для любого элемента [W ] множество конечно.

Наконец, третий результат касается строения фундаментального графа регулярных D-классов полугруппы B(k, n, n + m) при n 3: оказывается, фундаментальный граф любого регулярного D-класса есть простой цикл ([16, 17]). Как следствие, всякая максимальная подгруппа свободной бернсайдовой полугруппы с тождеством xn = xn+m при n 3 является циклической группой порядка m.

Проблема конечности, проблема равенства слов и гипотеза Бжозовского. При k > 1 и n 3 бесконечность полугруппы B(k, n, n + m) следует из работы [31], в которой Туэ построил бесконечную последовательность бескубных слов над алфавитом из двух букв.

Гипотеза Бжозовского для полугрупп B(k, n, n + 1) с n 5 была подтверждена де Лукой и Вариккио в 1990 году ([12]). Маккаммонд распространил гипотезу на случай полугруппы B(k, n, n + m) с произвольным m 1 и независимо доказал ее справедливость при n 6, m 1 ([29], 1991). Позже до Лаго усовершенствовал метод де Луки и Варикккио и улучшил оценку до n 4, m 1 ([16], 1992). Наконец, В. С. Губа показал справедливость гипотезы для n 3, m 1 ([22, 23], 1993).

Разрешимость проблемы равенства слов следует из справедливости гипотезы Бжозовского: поскольку всякий элемент полугруппы B(k, n, n + m) является рациональным языком, мы можем по одному из двух данных слов построить автомат, распознающий его класс эквивалентности, и проверить, распознает ли этот автомат второе слово.

Резюмируем приведенные выше результаты в следующей теореме.

Теорема VIII. Пусть n 3, m 1, k > 1. Тогда 1) Каждый класс конгруэнции n,m содержит единственное слово минимальной длины.

2) Все максимальные подгруппы полугруппы B(k, n, n + m) циклические порядка m.

3) Всякий элемент полугруппы B(k, n, n + m) является рациональным языком.

4) Проблема равенства слов для полугруппы B(k, n, n + m) разрешима.

2.4 Случай n = Бесконечность полугруппы B(k, 2, 2 + m) при k 3 следует из работы Туэ [32], построившего бесконечную последовательность бесквадратных слов над алфавитом из трех букв.

В 1971 году Бжозовски, Кулик и Габриэлян показали бесконечность полугруппы B(2, 2, 3) ([10]). Как следствие, полугруппы B(k, 2, 2 + m) бесконечны для всех k 2 и m 1.

В [18] до Лаго показал, что все максимальные подгруппы D-класса элемента [(21212)2 ] являются свободными бернсайдовыми группами с тождеством xm = 1 и рангом как минимум 2m 1. Для достаточно большого m эти группы будут бесконечными, и все элементы

ВВЕДЕНИЕ

данного D-класса, рассматриваемые как языки над алфавитом из свободных порождающих, не являются рациональными языками.

Предложение IX ([18, 19]). Для полугруппы B(k, 2, 2 + m) при k > 1 и m гипотеза Бжозовского неверна.

Мы видим, что уже при m 2 максимальные подгруппы D-классов могут не быть циклическими, и структура полугрупп B(k, 2, 2 + m) в этом случае существенно отличается от структуры полугрупп B(k, n, n + m) как при n 3, так и для n = 1. В частности, произвольный класс эквивалентности уже не обязательно содержит только одно слово минимальной длины, до сих пор не решена проблема равенства слов для полугрупп B(k, 2, 2 + m).

Наименее исследованным остается случай n = 2, m = 1: в этом случае, ввиду теоремы III, все максимальные подгруппы тривиальны, тем не менее, гипотезу Бжозовского для полугрупп B(k, 2, 3) пока подтвердить не удалось. Проблема равенства слов для полугрупп B(k, 2, 3) остается открытой. Также неизвестно, единственно ли слово минимальной длины в каждом классе эквивалентности 2,1. Если ответ на этот вопрос положителен, полугруппа B(k, 2, 3) по структуре и свойствам может оказаться схожей с полугруппами B(k, n, n + m) при n 3.

3 Обзор диссертации 3.1 Цели диссертации. Основные проблемы К настоящему времени, благодаря целому ряду исследований, удалось достаточно хорошо описать строение свободных бернсайдовых полугрупп с тождеством xn = xn+m при n (см. § 2 ). В этом случае гипотеза Бжозовского справедлива и, как следствие, разрешима проблема равенства слов. Несмотря на то, что в общем случае вопросы о справедливости гипотезы Бжозовского и разрешимости проблемы равенства слов для полугрупп B(k, 1, 1 + n) остаются открытыми, ответы на них определенным образом зависят от ответов на аналогичные вопросы для бернсайдовых групп. Более того, работы Грина и Риса, Кадорека и Полака и др. дают хорошее представление о строении полугрупп B(k, 1, 1+m).

Наименее исследованным остается случай n = 2. Основной целью данной диссертации является исследование проблемы равенства слов и гипотезы Бжозовского для полугрупп B(k, 2, 3), разработка новых методов и подходов к решению данных проблем.

Выбор полугруппы B(k, 2, 3) не случаен. Во-первых, стоит отметить, что полугруппы вида B(k, n, n + 1) составляют важный подкласс бернсайдовых полугрупп. Исторически теория бернсайдовых полугрупп (исключая бернсайдовы группы) начиналась с изучения именно таких полугрупп. Многие результаты были получены сперва для полугрупп B(k, n, n + 1), и лишь затем распространены на полугруппы B(k, n, n + m) с произвольным 1. Напомним, что вопрос о справедливости гипотезы Бжозовского и разрешимости

ВВЕДЕНИЕ

проблемы равенства слов для полугрупп B(k, 2, 3) был специально отмечен Бжозовским в списке открытых проблем [9].

Во-вторых, как было сказано в § 2, структура полугрупп B(k, 2, 2 + m) при m существенно сложнее структуры полугрупп B(k, n, n + m) при n 3, и случай m = 1 остается единственным, при котором полугруппа B(k, 2, 2 + m) еще может иметь достаточно простую структуру.

Наконец, ввиду того, что 2,m 2,1, решение проблемы равенства слов для полугруппы B(k, 2, 3) в некоторых случаях позволяет давать отрицательный ответ на вопрос, представляют ли слова U и V один и тот же элемент полугруппы B(k, 2, 2 + m), а именно:

если U 2,1 V, то и U 2,m V для любых слов U и V. Таким образом, решение проблемы равенства слов для полугрупп B(k, 2, 3) может служить первым приближением и отправной точкой для решения соответствующей проблемы в полугруппах B(k, 2, 2 + m).

3.2 Основные результаты Основными результатами диссертации являются следующие.

– Теорема 1.1 об эквивалентности разрешимости проблемы равенства слов в полугруппе B(k, 2, 3) произвольного ранга k > 2 и разрешимости этой же проблемы для полугруппы B(2, 2, 3), и аналогичная ей по формулировке теорема 1.2 о справедливости гипотезы Бжозовского. (Глава 1.) – Теорема 2.1 о единственности почти сильно бескубного слова в классах конгруэнции 2,2,3. (Глава 2.) – Линейный по времени алгоритм EqAOF построения почти сильно бескубного слова, 2,2,3 -эквивалентного заданному слову, и вытекающая из него теорема 2.2 о разрешимости равенства в полугруппе B(2, 2, 3) любой пары слов, хотя бы одно из которых эквивалентно почти сильно бескубному слову. (Глава 2.) – Теорема § 3.1, подтверждающая гипотезу Бжозовского для полугруппы B(2, 2, 3) в частном случае, а именно, доказывающая рациональность всех классов конгруэнции 2,2,3, содержащих почти сильно бескубное слово. (Глава 3.) Кроме того, выделим еще несколько результатов диссертации, которые естественным образом дополняют результаты, описанные выше.

– Теоремы 1.3 и 1.4 являются аналогами, соответственно, теорем 1.1 и 1.2 для полугрупп B(k, 2, 2 + m) при произвольном m 2 и могут служить отправной точкой для применения разработанной в диссертации техники к произвольным полугруппам B(k, 2, 2 + m). (Глава 1.)

ВВЕДЕНИЕ

– Теорема 3.2 гласит, что почти сильно бескубное слово является единственным словом минимальной длины в своем классе и тем самым обнаруживает в полугруппе B(2, 2, 3) свойство, характерное для бернсайдовых полугрупп с n 3. (Глава 3.) – Теоремы 3.3 и 3.4 описывают количественные характеристики классов, содержащих почти сильно бескубные слова, и показывают, что частный случай, для которого доказана разрешимость проблемы равенства слов и подтверждена гипотеза Бжозовского, является достаточно обширным. (Глава 3.) – Теоремы 3.5 и 3.6 являются аналогами теорем 2.1 и 2.2, с заменой почти сильно бескубных слов на почти 7/3-свободные, и демонстрируют границы применимости разработанной в диссертации комбинаторной техники. (Глава 3.) 3.3 Основные методы В доказательстве полученных нами результатов можно выделить следующие методы:

• Методы комбинаторики слов, основанные на применении морфизма Туэ-Морса, сильно бескубных слов, построении и анализе морфизмов, использование результатов по комбинаторике слов других авторов.

• Методы теории автоматов.

• Элементы классической комбинаторики.

• Методы теории бернсайдовых полугрупп, основанные на использовании специальных редукций и исследовании отношения соседства.

3.4 Структура диссертации и организация текста Диссертация состоит, помимо введения, из трех глав и списка литературы. Главы делятся на параграфы, параграфы имеют двухиндексную нумерацию (первый индекс обозначает номер главы). Все предложения и теоремы, сформулированные во введении, отражают предшествующие результаты других авторов в данной проблемной области и не имеют отношения к результатам диссертации; все утверждения во введении нумеруются римскими цифрами и имеют единую нумерацию. Предложения, леммы, наблюдения, примеры в главах 1–3 имеют трехиндексную нумерацию, где первый индекс означает номер главы, а второй номер параграфа. Рисунки и нумерованные формулы, ввиду их немногочисленности, имеют двухиндексную нумерацию (первый индекс соответствует номеру главы).

Наконец, основные результаты диссертации оформлены в виде теорем, также имеющих двухиндексную нумерацию.

Диссертация состоит из трех глав. Первая глава посвящена исследованию проблемы равенства слов и гипотезы Бжозовского для полугрупп B(k, 2, 3) произвольного ранга

ВВЕДЕНИЕ

k 2. В последнем параграфе этой главы рассматриваются полугруппы B(k, 2, 2 + m) с произвольными m 1иk 2. Центральное место в диссертации отводится главе 2, в которой мы строим алгоритм EqAOF, позволяющий за линейное время решать проблему равенства слов для полугруппы B(2, 2, 3) в случае, когда одно из слов эквивалентно почти сильно бескубному. Наконец, третья глава посвящена гипотезе Бжозовского для полугруппы B(2, 2, 3) и другим приложениям алгоритма EqAOF, а также обобщениям результатов главы 2.

3.5 Апробация и публикации Результаты диссертации были представлены на XIV международной конференции студентов, аспирантов и молодых ученых Ломоносов 2007, на свердловском областном конкурсе студенческих работ Олимп-2007, на 6-й международной конференции по комбинаторике слов WORDS2007 (Марсель, 2007), международной конференции по полугруппам, алгебре и приложениям AAA82 (Потсдам, 2011), 15-й международной конференции Развитие теории языков (Милан, 2011), международной конференции Мальцевские чтения (Новосибирск, 2011). Автор выступал с докладами по теме диссертации на семинаре Алгебраические системы (УрГУ, рук. Л.Н. Шеврин, 2007–2011), на алгебраическом семинаре института математики и механики УрО РАН (2011), на семинаре Алгоритмические вопросы алгебры и логики (МГУ, рук. С. И. Адян, 2011).

По теме диссертации написано 7 работ: [33–39]. Из них статья [36] опубликована в издании из списка, рекомендованного ВАК, а статьи [38, 39] в зарубежных изданиях, удовлетворяющих достаточному условию ВАК. Работы [33, 35] являются тезисами (в том числе электронная публикация [35]); статьи [37,38] опубликованы в сборниках трудов конференций; 3 работы ([37–39]) написаны совместно с А. М. Шуром, однако доказательство основных результатов принадлежит автору.

Автор выражает глубокую благодарность своему научному руководителю Арсению Михайловичу Шуру за неоценимую помощь и руководство при написании диссертации и подготовке статей к публикации, Льву Наумовичу Шеврину за его многочисленные советы и ценные замечания. С теплым чувством я вспоминаю своего первого научного руководителя Евгения Витальевича Суханова, который и вдохновил автора на исследования в данной предметной области.

Глава Полугруппы B(k, 2, 3) § 1.1 Введение и формулировка результатов Как говорилось в разделе 2, структура свободных бернсайдовых полугрупп в основном зависит от параметров n и m (от n в большей степени и от m в меньшей). Что касается параметра k, то при k = 1 свободные бернсайдовы полугруппы суть конечные циклические полугруппы. При k > 1 полугруппы B(k, n, m) имеют весьма схожую структуру (при фиксированных n и m). В частности, все приведенные в разделе 2 результаты справедливы для свободных бернсайдовых полугрупп любого конечного ранга k > 1.

В связи с вышесказанным, изучение проблемы равенства слов и гипотезы Бжозовского для полугрупп B(k, 2, 3) представляется разумным проводить в два этапа: на первом этапе доказать сводимость рассматриваемых проблем для полугрупп B(k, 2, 3) произвольного ранга k к соответствующим проблемам для какой-то полугруппы B(k, 2, 3) фиксированного ранга k, после чего работать только с этой полугруппой. Наиболее перспективной в этом плане является полугруппа B(2, 2, 3): во-первых, для исследования слов и языков над бинарным алфавитом разработан достаточно большой и разнообразный инструментарий, во-вторых, случай k = 2 представляется наиболее простым, в-третьих, для полугруппы B(2, 2, 3) уже получен ряд результатов. В частности, представленная диссертация существенно развивает технику и методы, введенные в [2].

В этой главе мы полностью реализуем первый этап нашего исследования. Второму этапу посвящены главы 2–3.

Поскольку в данной главе, за исключением последнего параграфа, рассматриваются свободные бернсайдовы полугруппы с фиксированным тождеством x2 = x3, мы будем опускать индексы n и m и писать,, [W ] вместо 2,1, 2,1 и, соответственно, [W ]2,1 (для произвольного слова W ). Более того, мы будем использовать буквы n и m для обозначений наравне с другими буквами латинского алфавита. (Как было сказано выше, исключение составляет лишь § 1.5, в котором m по-прежнему используется для обозначения одного из параметров полугруппы B(k, 2, 2 + m).) ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) Основными результатами этой главы являются следующие две теоремы.

Теорема 1.1. Проблема равенства слов для полугруппы B(k, 2, 3) произвольного ранга 2 разрешима тогда и только тогда, когда проблема равенства слов разрешима для полугруппы B(2, 2, 3).

Теорема 1.2. Гипотеза Бжозовского для полугруппы B(k, 2, 3) при k 2 справедлива тогда и только тогда, когда эта гипотеза справедлива для полугруппы B(2, 2, 3).

Для доказательства теорем 1.1 и 1.2 мы построим функцию :, такую, что для любых слов U, V + соотношение U V выполняется тогда и только тогда, когда выполняется (U ) (V ).

Глава состоит из пяти параграфов. Во втором и третьем параграфах вводятся вспомогательные конструкции, необходимые для построения отображения с нужными свойствами. Четвертый параграф посвящен доказательству теорем 1.1 и 1.2. Наконец, в последнем, пятом, параграфе мы обобщаем полученные результаты на случай бернсайдовых полугрупп B(k, 2, 2 + m) с произвольным значением m.

§ 1.2 Основная техника, используемая в диссертации В этом разделе собраны понятия и факты, которые необходимы для дальнейшего понимания работы и которые используются во всех главах диссертации. В частности, понятия r1 -редуцируемости и AB-целого слова необходимы для построения отображения.

Используемый инструментарий был разработан в [2, 30], некоторые понятия (такие, как r1 -редукция) возникли и использовались раньше (см., например, [3]).

1. Из определения морфизма Туэ-Морса следует, что ( ) = (12 + 21), т. е. любое слово из ( ) представляется в виде произведения блоков двухбуквенных слов, каждое из которых равно 12 или 21. Далее слова из языка (2 ) мы будем называть -образами.

Сделаем одно полезное наблюдение, характеризующее множество всех -образов.

Наблюдение 1.2.1. Слово W тогда и только тогда будет -образом, когда длина W четна и все вхождения подслов 11 и 22 в слово W начинаются только с четных позиций.

В дальнейшем нам понадобится следующее обобщение свойства слова быть -образом (см. [30]): слово W будем называть регулярным (английский термин uniform ), если все вхождения подслов 11 и 22 начинаются в U в позициях одной четности. Слово W называется буквочередующимся, если оно не содержит подслов 11 и 22. По определению, буквочередующиеся слова являются регулярными.

2. В этом пункте мы получим одну очень полезную характеризацию регулярных слов в терминах вполне редуцируемости. Фактически, мы покажем, как из произвольного слова ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) W получить регулярное слово. Для этого, следуя [2], мы введем три специальные операции редукции, упрощающих структуру слова.

Операция r1 сокращает в слове все степени букв выше второй до квадратов:

Результат применения операции r1 к слову W обозначим через r1 (W ). Ясно, что r1 (W ) не зависит от порядка применения сокращений (1.1). Слово W назовем r1 -редуцированным, если W = r1 (W ).

Пусть A и B обозначают языки буквочередующихся слов нечетной длины 1(21)+ и 2(12)+ соответственно (однобуквенные слова 1 и 2 исключаются). Выбор обозначений A и B объясняется тем, что довольно часто буквы бинарного алфавита обозначают латинскими буквами a и b, при этом полагая 2 = {a, b}. При таких обозначениях мы имеем A = a(ba)+ и B = b(ab)+.

Обозначим через rA (W ) слово, полученное из W применением, пока возможно, преобразований вида а через rB (W ) слово, полученное из W применением (пока возможно) преобразований вида Предварительно заметим, что операции rA и rB применяются только к r1 -редуцированному слову W. В этом случае сокращения (1.2a) и (1.2b) можно производить в любом порядке ([2]). Слово W называется rA -редуцированным, если rA (W ) = W, и называется rB редуцированным, если rB (W ) = W. Наконец, слово W называется вполне редуцированным, или r-редуцированным, если оно r1 -, rA - и rB -редуцировано. Операцию полной редукции обозначим через r. Таким образом, r(W ) = rB (rA (r1 (W ))) = rA (rB (r1 (W ))).

Следующее предложение устанавливает связь между понятиями регулярности, вполне редуцированности и -образами.

Предложение 1.2.1. Для произвольного слова W следующие условия эквивалентны:

(1) W регулярно;

(2) W вполне редуцировано;

(3) W является подсловом -образа.

Доказательство. Импликация (1) (2) очевидна: так как в словах 111, 222, 11(21)l и 22(12)l 2 (для любого l 1) позиции первого и последнего вхождения квадрата буквы имеют разную четность, регулярное слово W не содержит подслов указанного вида, и, следовательно, является вполне редуцированным.

ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) Докажем обратное утверждение. Предположим, что слово W вполне редуцировано, но не регулярно. Пусть Y минимальное по длине нерегулярное подслово W. Тогда Y начинается и заканчивается квадратом буквы, и длина Y нечетна. Ввиду r1 -редуцированности, слово W не содержит подслов 111 и 222, поэтому квадраты букв в слове Y не могут перекрываться. Следовательно, Y = ccY dd для некоторых букв c и d и слова Y нечетной длины.

Если слово cY d не является буквочередующимся, то есть cY d = P eeQ для некоторых P, Q и e 2, то одно из собственных подслов слова Y ccP ee или eeQdd нерегулярно, что противоречит выбору слова Y. Таким образом, cY d буквочередующееся слово нечетной длины, Следовательно, c = d, откуда Y 1A1 или Y 2B2, что невозможно ввиду того, что слово W вполне редуцировано. Полученное противоречие доказывает импликацию (2) (1).

Эквивалентность условий (1) и (3) непосредственно следует из определения регулярности и наблюдения 1.2.1.

Таким образом, операция r преобразует любое слово над алфавитом 2 в регулярное.

3. Слово W называется A-целым, если оно r1 -редуцировано и любое подслово Y 1A входит в W только внутри подслова 12Y 21. Двойственным образом определяется B-целое слово. Наконец, назовем слово AB-целым, если оно одновременно A- и B-целое.

Понятие AB-целого слова, введенное в [2], играет весьма важную роль во всех последующих рассмотрениях. Подслова A-, B- и AB-целых слов мы называем, соответственно, потенциально A-, B и AB-целыми словами.

4. Сформулируем несколько наиболее часто используемых в диссертации утверждений, устанавливающих базовые свойства введенных выше понятий относительно конгруэнции Начнем со свойств операции r1 самой простой, но вместе с тем наиболее важной из всех операций редуцирования, входящих в определение r-редукции. Очевидно, для любого слова W мы имеем r1 (W ) W. Отсюда, в частности, следует, что условие U V влечет r1 (U ) r1 (V ). Оказывается, справедливо более сильное утверждение.

Предложение 1.2.2 ([2, 3]). Если (W1, W2 ), то (r1 (W1 ), r1 (W2 )).

Ввиду предложения 1.2.2, если мы рассмотрим ограничение r1 отношения соседства и ограничение r1 конгруэнции на множество всех r1 -редуцированных слов над алфавитом 2, то по-прежнему отношение r1 будет транзитивным замыканием r1. Действительно, ввиду равенства = +, для любых r1 -редуцированных слов U и V существует последовательность слов {Wi }n такая, что W0 = U, Wn = V и (Wi, Wi1 ) для всех i [1, n]. Применив операцию r1 ко всем членам последовательности, мы получим последовательность {r1 (Wi )}n, все члены которой r1 -редуцированы, при этом r1 (W0 ) = U, r1 (Wn ) = V и (r1 (Wi ), r1 (Wi1 )) для всех i [1, n].

ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) Таким образом, проблему равенства слов для полугруппы B(2, 2, 3) достаточно решить на множестве всех r1 -редуцированных слов. Поэтому далее почти все рассматриваемые слова над алфавитом 2 будут r1 -редуцированными. Множество всех r1 -редуцированных слов, эквивалентных слову W, мы обозначаем через [W ]r1. Легко видеть, что [U ]r1 = r1 ([U ]) для любого U.

Следующее предложение утверждает, что свойство слова быть AB-целым сохраняется конгруэнцией. Это означает, что свойство быть AB-целым присуще не только словам, но и классам эквивалентности элементам полугруппы B(2, 2, 3).

Предложение 1.2.3. Пусть U, V, слова U и V являются r1 -редуцированными и U V. Тогда если U [потенциально] A-целое (B-, AB-целое) слово, то и V [потенциально] A-целое (соответственно, B-, AB-целое) слово.

Доказательство. Доказательство проведем только для случая, когда U A-целое или потенциально A-целое слово. Случай, когда слово V является (потенциально) Bцелым, симметричен данному. Наконец, утверждение для (потенциально) AB-целых слов следует из этих двух случаев.

Ввиду равенства r1 = r1, достаточно рассмотреть соседнюю пару слов U и V : общее утверждение следует из данного частного случая по индукции. Пусть U = XY s Z, V = XY t Z, где X, Z, Y + и {s, t} = {2, 3}. Доказываемое утверждение равносильно тому, что если слово V не является (потенциально) A-целым, то и слово U не является таковым.

Предположим, что слово V не является потенциально A-целым. Тогда слово V содержит подслово 2211(21)l 1 или 11(21)l 122 для некоторого l 1. Без ограничения общности можно считать, что 2211(21)l 1 V (случай 11(21)l 122 V симметричен данному относительно прочтения слов справа налево). Ясно, что если 2211(21)l 1 XY Y или 2211(21)l 1 Y Y Z, то слово U также содержит подслово 2211(21)l 1, а потому не является A-целым. Если же вхождение подслова 2211(21)l 1 начинается в префиксе XY Y, а заканl 1 (этот чивается в суффиксе Y Y Z слова V, то мы имеем либо Y [|Y |]Y Y [1] случай возможен только, когда t = 3), либо Y Y 2211(21) 1. Мы видим, что в обоих случаях слово Y не содержит подслова 22.

Рассмотрим сначала случай t = 3 и Y [|Y |]Y Y [1] ситуация Y [1] = Y [|Y |] = 2 невозможна, так как слово 2211(21)l 1 содержит только одно вхождение подслова 22. Таким образом, слово Y Y не содержит подслова 22, поэтому подслово 2211(21)l 1 начинается в слове V внутри его префикса X, в результате мы приходим к случаю Y Y 2211(21)l 1.

Итак, пусть Y Y 2211(21)l 1. Заметим, что слово Y Y содержит не более одного вхождения подслова 11, поэтому 11 Y. Так как Y также не содержит и подслова 22, слово буквочередующееся. В этом случае мы имеем Y Y когда длина слова Y четна. Тогда оба слова Y Y и Y Y Y являются буквочередующимися, ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) а потому Y t 1(21)l, то есть замена Y t Y s происходит внутри подслова 2211(21)l слова V. Легко видеть, что слово U, получающееся из V после такой замены, содержит подслово 2211(21)m 1 для некоторого m 1. Следовательно, слово U не является A-целым, что и требовалось доказать.

Покажем теперь, что если слово V не является A-целым, то и слово U не является таковым. По доказанному выше, это верно в случае, когда V не потенциально A-целое слово.

Предположим теперь, что слово V является потенциально A-целым, но не является A-целым. Тогда V имеет префикс вида 1A1 или 21A1 и/или имеет суффикс вида 1A или 1A12. Пусть слово V имеет префикс P {1(12)l 11, 21(12)l 11} для некоторого l (случай с суффиксами рассматривается аналогично). Ясно, что если P XY Y, то слово P является также префиксом слова U, и, следовательно, слово U не является A-целым.

С другой стороны, если XY Y < P, то Y буквочередующееся слово, так как 22 P и любое собственное подслово слова P содержит не более одного вхождения подслова 11.

Легко проверить, что Y Y слово Y имеет четную длину. В этом случае слово Y Y Y также является буквочередующимся. Следовательно, XY t < P, причем замена Y t Y s происходит внутри подслова 1(21)l слова P. Мы видим, что слово U, полученное из слова V после такой замены, имеет префикс 11(21)m 1 (если P = 11(21)l 1) или 211(21)m 1 (если P = 211(21)l 1) для некоторого m 1, поэтому слово U не является A-целым.

Отметим, что предложение 1.2.3 в предположении, что U является A-, B или AB-целым словом, впервые было установлено в [2]. Мы привели альтернативное доказательство этого факта.

Очевидно, любой морфизм, в том числе и морфизм Туэ-Морса, сохраняет отношение, то есть из U V следует (U ) (V ) для любых слов U, V. Замечательное свойство морфизма Туэ-Морса состоит в том, что и обратная импликация (U ) (V ) U V также имеет место. Более общо этот результат формулируется следующим образом.

Предложение 1.2.4 ([2]). Пусть W (V ) и W регулярное слово. Тогда найдется слово U такое, что W = (U ) и U V.

Предложение 1.2.4 играет ключевую роль в построениях главы 2. В данной главе оно встречается эпизодически.

Наконец, в дальнейшем мы будем часто пользоваться (явно или без ссылки) следующим простым утверждением.

Предложение 1.2.5. Пусть U V для некоторых U, V и U имеет префикс (суффикс) W. Тогда если 1) слово W почти бесквадратно или ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) 2) слова U, V являются r1 -редуцированными и среди собственных подслов слова W нет квадратов, кроме квадратов букв, то W есть префикс (соответственно, суффикс) слова V.

Доказательство. Достаточно рассмотреть пару соседних слов U и V : общее утверждение следует из данного частного случая по индукции. Пусть U = XY s Z и V = XY t Z для некоторых слов X, Z, Y + и чисел {s, t} = {2, 3}. Если слова U и V являются r1 -редуцированными, подслово Y не может быть степенью буквы. В частности, в этом случае |Y | 2. По условию, Y Y не является собственным подсловом слова W, поэтому префикс (суффикс) W слова U не длиннее префикса XY Y (соотв., суффикса Y Y Z). Поскольку подслово XY Y является общим префиксом, а Y Y Z общим суффиксом слов U и V, мы получаем требуемое утверждение.

Построение отображения § 1. Нашей целью является построение такого отображения :, что для любых слов U, V + соотношение U V выполняется тогда и только тогда, когда выполняется (U ) (V ).

Естественно, казалось бы, в качестве выбрать какой-нибудь подходящий морфизм:

поскольку любой морфизм сохраняет отношение, импликация U V (U ) (V ) становится очевидной. Трудности, однако, возникают при попытке доказать обратное утверждение: из того, что морфизм сохраняет отношение, не следует, вообще говоря, что то же верно и для отображения 1. Более того, это отображение является частичным, и может оказаться, что 1 применимо не ко всем словам из [(U )]. Действительно, из соотношений (U ) (V ) и = + следует лишь существование последовательности {Wi }n такой, что W0 = (U ), Wn = (V ) и (Wi, Wi1 ) для всех i 1. При этом, если крайние члены последовательности (слова W0 и Wn ) имеют прообразы при действии, то промежуточные члены W1,..., Wn1 прообразов при действии могут и не иметь.

Более того, мы не можем гарантировать выполнение U V даже для пары соседних слов (U ) и (V ): если (U ) = XY Y Z и (V ) = XY Y Y Z для некоторых слов X, Z и Y +, то мы имеем U V в случае, когда слово Y имеет вид Y = (U [i+1])... (U [i+r]) для некоторых i, r 1. Однако подслово Y может входить в U другими способами: например, начинаться внутри подслова (U [i1]), заканчиваться внутри (U [i+r+1]) и иметь вид Y = P (U [i])... (U [i+r])Q; подслово Y (и даже Y Y ) может целиком входить в (U [i]) или лежать на стыке подслов (U [i]) и (U [i + 1]) для некоторого i. Во всех перечисленных случаях замена Y Y Y Y Y, превращающая слово (U ) в (V ), индуцирует в слове U замену, в общем случае не сохраняющую отношение, поэтому ((U ), (V )) не влечет U V.

Мы видим, что поиск подходящего отображения весьма непростая задача. Конечно, здесь уместно вспомнить о морфизме Туэ-Морса, который, по предложению 1.2.4, ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) удовлетворяет условию U V (U ) (V ) для любых слов U, V. К сожалению, морфизм определен только для слов над алфавитом 2, к тому же -образы букв имеют длину два, что почти полностью исключает описанные выше плохие случаи расположения подслов вида Y Y и Y Y Y, где Y +. Так как мы имеем дело с алфавитом k произвольной (конечной) мощности, ясно, что при больших значениях k образы букв при действии могут быть сколь угодно длинными.

Для построения функции нам потребуется следующее обобщение операции произведения слов. Зафиксируем некоторое слово S над произвольным алфавитом, и пусть X = X1 S и Y = SY1 для некоторых X1, Y1. Склейкой слов X и Y по слову S называется слово X S Y = X1 SY1. Таким образом, X S Y = XY1 = X1 Y. В частности, если в качестве S взять пустое слово, мы получим обычную операцию произведения слов, определенную на всем множестве. Зафиксируем теперь два слова S1, S2. Несложно убедиться, что если слово X заканчивается на S1, слово Y начинается на S1 и заканчивается на S2, а слово Z начинается на S2, имеет место равенство: (X S1 Y )S2 Z = X S1 (Y S2 Z).

В дальнейшем мы будем опускать скобки и писать просто X S1 Y S2 Z. Поскольку произведение слов есть склейка по пустому слову, в выражении, в котором встречаются только произведение слов и склейка, порядок действий не важен. Степень со склейкой слова W по слову S мы будем обозначать следующим образом:

(при этом предполагается, что W начинается и заканчивается на S). Так, например, Для любого S, склейка по слову S естественным естественным образом распространяется на языки.

Идея заключается в том, чтобы в качестве искать не морфизм, а отображение со схожими свойствами, используя вместо операции произведения слов операцию склейки по непустому слову. При этом образы букв (i) (где i = 1,..., k) нужно выбрать таким образом, чтобы подслова вида Y Y, где Y, не могли входить в слова из множества ( ) в произвольных позициях, а вынуждены были располагаться строго определенным образом, избегая случаев плохого расположения, описанных выше. Для этого мы воспользуемся свойством AB-целости слов и тем, что это свойство сохраняется конгруэнцией. Но сначала мы рассмотрим слова, не являющиеся потенциально AB-целыми.

Несложно проверить, что если r1 -редуцированное слово U не является потенциально AB-целым, то оно содержит по крайней мере одно из подслов 11(21)l 122, 1122(12)l 2, 22(12)l 211 или 2211(21)l 1 для некоторого l 1. Такие слова мы будем называть маркерами; в дальнейшем мы будем использовать только маркеры 1121122, 1122122, ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) и 2211211. Слова M 0 = 11211221122122, M 0 = 22122112211211 и все r1 -редуцированные слова, эквивалентные M 0 или M 0, называются двойными маркерами. Следующая лемма описывает двойные маркеры, эквивалентные слову M 0.

Лемма 1.3.1.

Доказательство. Обозначим через L язык, задаваемый регулярным выражением в правой части равенства (1.3). Несложно убедиться, что L [M 0 ]r1. Для доказательства обратного включения заметим, что M 0 L. Таким образом, достаточно показать, что если некоторое r1 -редуцированное слово U принадлежит L, то и любое r1 -редуцированное соседнее с U слово V также принадлежит L. Требуемое включение [M 0 ]r1 L следует из данного утверждения по индукции, поскольку r1 = r1.

Пусть (U, V ), где U, V +, и U = (112)2+l1 2(1122)l2 1(122)2+l3 для некоторых целых чисел l1, l2, l3 0. По определению соседства, U = XY s Z и V = XY t Z для некоторых слов В силу предложения 1.2.3, если слово Y 2 потенциально AB-целое, то и слово Y 3 является таковым. В этом случае замена Y s Y t происходит внутри одного из подслов (112)2+l1, 121122(1122)l2 112212 = 12(1122)2+l2 12 или (122)2+l3. Предположим, что Y s (112)2+l1. Легко видеть, что если Y [1] = 1 и Y [|Y |] = 2, то Y = (112)r а если Y [1] = 2 и Y [|Y |] = 1, то Y = (211)r для некоторого r 1. Наконец, если Y [1] = Y [|Y |] = 1, слово Y имеет вид Y = (121), где r 1. Случай Y [1] = Y [|Y |] = 2 невозможен, так как в противном случае слово Y содержало бы подслово 22, в то время как слово (112)2+l1 подслова не содержит. Легко проверить, что во всех трех случаях, после замены Y s Y t, слово (112)2+l1 преобразуется в слово (112)p, где p = 2 + l1 + r, если s = 2, t = 3, и p = 2 + l1 r, если s = 3, t = 2. Так как полученное таким образом слово содержит подслово Y Y, мы заключаем, что p 2, то есть слово (112)p имеет вид (112)2 (112).

Случай Y s (122)2+l3 симметричен только что рассмотренному с точностью до инвертирования букв и прочтения слов справа налево. Разберем оставшийся случай, когда Ys 12(1122)2+l2 12. Ясно, что Y s 12(1122)2+l2 12, так как слово 12(1122)2+l2 12 содержит единственное вхождение каждого из подслов 121 и 212. Нетрудно убедиться, что, в зависимости от того, с какой буквы начинается и на какую букву заканчивается слово Y, возможны четыре варианта: Y = (1122)r, Y = (2211)r, Y = (1221)r или Y = (2112)r.

Во всех четырех случаях замена Y s Y t в слове 12(1122)2+l2 12 приводит нас к слову 12(1122)p 21, где p = 2 + l2 + r, если s = 2, t = 3, и p = 2 + l2 r, если s = 3, t = 2. Так как слово 12(1122)p 21 содержит подслово Y t, мы имеем p 2, поэтому слово 12(1122)p имеет вид 121122(1122) 112221.

Мы видим, что слово V, полученное из U заменой Y s Y t, удовлетворяет регулярному выражению (1.3), поэтому V L.

Предположим теперь, что слово Y Y содержит маркер S. Поскольку U содержит в точности одно вхождение S, мы имеем s = 2, так как слово Y Y Y содержит как минимум ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) два различных вхождения S (внутри различных вхождений подслова Y Y ), и S Y.

Таким образом, маркер S входит в слово Y Y на стыке вхождений Y. Без ограничения общности, пусть S = 1121122 (случай S = 1122122 рассматривается симметрично). Тогда (112)2+l1, в частности, слово Y не содержит подслова 22. С другой стороны, имеет место 22 S. Следовательно, подслово 22 образуется в Y Y на стыке вхождений Y, то есть Y [|Y |] = Y [1] = 2. Легко видеть, что в этом случае Y = 2112 и слово V = XY Y Y Z удовлетворяет регулярному выражению (1.3), что и требовалось доказать.

Класс [M 0 ]r1 получается инвертированием всех слов из [M 0 ]r1. Важное свойство двойных маркеров состоит в следующем: если двойной маркер M является подсловом в Y Y, то слово Y содержит хотя бы один маркер и поэтому не является потенциально AB-целым.

Зафиксируем теперь некоторый набор C1,..., Ck попарно неэквивалентных AB-целых слов, каждое из которых начинается и заканчивается на 212212, но при этом Ci для всех i k. Определим отображение, положив для всех i kи для любого слова W +. Слова из (i) для всех i k называются блоками, а слова из (W ) для любого W + блочными словами. Мы говорим, что W прообраз слова U, и пишем W = 1 (U ), если U (W ).

Покажем, что для любого натурального числа k существует набор слов C1, C2,..., Ck, удовлетворяющий всем условиям из определения отображения. Оказывается, требуемый набор можно получить при помощи слов Туэ–Морса.

Лемма 1.3.2. Последовательность {2t2n 2} состоит из попарно неэквивалентных AB-целых слов, начинающихся и заканчивающихся на 212212.

Доказательство. Заметим, что слова tn начинаются с 1 при любом n 0, в то время как последний символ зависит от четности n: при четном n слово tn заканчивается на 1, при нечетном n на 2. В частности, слово t2n3 начинается с 1 и заканчивается на 2 для любого n 2. Так как t3 = 12212112 и t3 = 21121221, мы видим, что слово 2t2n начинается и заканчивается на 212212 для любого n 2. Очевидно, тем же свойством обладает и слово 2t2 2 = 212212.

Ввиду предложения 1.2.1, слова 2t2n 2 являются вполне редуцированными, и, следовательно, AB-целыми, при любом n 0.

Наконец, предположим, что 2t2n 2 2t2m 2 для некоторых целых чисел n, m 1, причем n < m. Среди всех таких пар (n, m)выберем пару с наименьшим значением n. Припишем в начало и конец слов 2t2n 2 и 2t2m 2 символ 1. Применяя предложение 1.2.4, мы получаем ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) Теперь припишем в начало слов 1t2n1 2 и 1t2m1 2 символ 2, а в конец символ 1. Повторное использование предложения 1.2.4 приводит нас к паре эквивалентных слов 2t2n2 2 и 2t2m2 2. Случай n 2 противоречит выбору пары (n, m) ввиду того, что 2t2n2 2 2t2m и 1 n 1 < n. С другой стороны, при n = 1 и n < m слова 2t2n2 2 = 212 и 2t2m2 2 не эквивалентны. Полученное противоречие завершает доказательство леммы.

Так как 2t2 2 = 212212, из леммы 1.3.2, в частности, следует, что 2t2n 2 212212 для любого n 2. Таким образом, в качестве Ci мы можем выбрать слово 2t2i+2 2 для каждого i = 1,..., k. Такой выбор слов C1,..., Ck, вероятно, не является оптимальным в плане минимизации суммарной длины слов, однако такая задача в диссертации не рассматривается, поскольку наша цель показать существование набора слов C1,..., Ck с требуемыми свойствами.

Заметим, что, в силу предложений 1.2.3 и 1.2.5, для любого i k все слова из [Ci ]r являются AB-целыми, начинаются и заканчиваются на 212212.

Следующая лемма дает описание структуры произвольных блоков.

Лемма 1.3.3. Для любого i = 1,..., k имеет место 1) [M 0 2122 Ci 2212 M 0 ]r1 = [M 0 ]r1 2122 [Ci ]r1 2212 [M 0 ]r1 ;

2) [M 0 2122 Ci 2212 M 0 1211 Ci ]r1 = [M 0 ]r1 2122 [Ci ]r1 2212 [M 0 ]r1 1211 [Ci ]r1.

Доказательство. Мы докажем утверждение 2 леммы, утверждение 1 доказывается аналогично. Пусть Очевидно, R [R]r1. Ввиду равенства r1 = r1, для доказательства обратного включения достаточно показать, что для произвольной пары r1 -редуцированных соседних слов U и V, если U R, то и V R. Так как R R, включение [R]r1 R будет следовать из этого утверждения по индукции.

{s, t} = {2, 3}. Предположим, что U R. Тогда для некоторых слов M1 [M 0 ]r1, M2 [M 0 ]r1, D1 [Ci ]r1 и D2 [Ci ]r1. По лемме 1.3.1, мы имеем M1 = (112)2+l1 2(1122)l2 1 (122)2+l3 и M2 = (221)2+l4 1(2211)l5 2 (211)2+l6, ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) Заметим, что (122)2+l3 2122 D1 2212 (221)2+l4 = 12 (212)l3 D1 (212)l4 21 = Слово D1 начинается и заканчивается на 212212, поэтому D1 D1 Ci. Таким образом, мы можем считать, что l3 = l4 = 0 (в противном случае заменим слово D1 в наших рассуждениях на слово D1 ). По схожим соображениям мы считаем, что l6 = 0.

Слово U содержит в точности по одному вхождению каждого из четырех маркеров.

Так как Y входит в U по крайней мере дважды, слово Y является потенциально ABцелым. Предположим, что S Y Y для некоторого маркера S. Тогда S образуется в Y Y на стыке вхождений Y, причем других маркеров слово Y Y не содержит. Следовательно, слово U совпадает с XY Y Z, поскольку XY Y Y Z содержит по крайней мере два различных вхождения S (внутри различных вхождений подслова Y Y ).

Если S = 1121122, то Y Y M1 ; очевидно, в этом случае слово V, полученное из U заменой Y Y Y Y Y, принадлежит R. Предположим, что S = 1122122. Слово D начинается с 212212, поэтому маркер S входит в U внутри подслова S12. Представим слово Y в виде Y = P S1 = S2 Q, где P, Q, S1, S2 + и S1 S2 = S. Заметим, что Y Y влечет |Y | 4. Легко видеть, что 212 Y. Действительно, если S12 Y Y, то слово Y содержит подслово S[7]12 = 212, в противном случае |Q| 1. Если Q =, то Y = S2 и длина S2 не меньше четырех. Так как, очевидно, Y = 1221, в случае |Q| = 1, то есть когда Q = 1, длина S2 также не меньше четырех. Но S2 является суффиксом маркера S, а всякий суффикс слова S длины четыре или более содержит подслово 212.

Итак, мы доказали, что 212 Y. С другой стороны, слово Y = P S1 целиком лежит в двойном маркере M1, а подслово 212 встречается в M1 только внутри S (ввиду того, что l3 = 0). Следовательно, S1 = 112212 и S2 = 2. Но тогда слово Y содержит лишь одно вхождение подслова 212, причем Y начинается и заканчивается на 212 (поскольку Y начинается с S2 12 и заканчивается на S1 ). Это возможно только, если Y = 212. Мы приходим к противоречию с тем, что |Y | 4.

Случаи S = 2212211 и S = 2211211 симметричны случаю S = 1122122 (относительно прочтения слов справа налево и операции инвертирования соответственно). Наконец, предположим, что слово Y Y не содержит маркеров, то есть является потенциально ABцелым. По предложению 1.2.3, оба слова Y s и Y t потенциально AB-целые. Тогда имеет место один из следующих четырех вариантов:

б) Y s 122122 2122 D1 2212 221221;

ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) г) Y s 211211 1211 D2.

В случаях а) и в) замена Y s Y t происходит внутри двойных маркеров, поэтому слово V, полученное при помощи такой замены, принадлежит языку R.

Пусть теперь U = X Y s Z = 122122 2122 D1 2212 221221, где X суффикс слова X, а Z префикс слова Z. Положим V = X Y t Z. Слова U и V эквивалентны, а потому, ввиду предложения 1.2.5, имеют общий префикс 122122 и общий суффикс 221221. Так как слово U потенциально AB-целое, то и слово V является потенциально AB-целым по предложению 1.2.3, следовательно, либо V = 1221221, либо V начинается на 12212212 и заканчивается на 21221221.

Рассмотрим теперь слово 2V 2. Ясно, что 2V 2 2U 2 = 212D1 212 D1 Ci, так как слово D1 имеет префикс 212212 и суффикс 212212. Заметим, что слово 2V 2 начинается и заканчивается на (212)3, при этом 2V 2 = 212212212 ввиду того, что Ci 212212 (по определению отображения ) и 2V 2 Ci. Поэтому слово D1 = V [3... |V |2], полученное из 2V 2 заменой префикса и суффикса (212)3 на слово (212)2, также эквивалентно D1.

Таким образом, и D1 [Ci ]r1, откуда V R.

Аналогично показывается, что и в случае Y s 211211 1211 D2 мы имеем V R. Таким образом, при любом расположении подслова Y s в слове U из языка R, слово V, полученное из U заменой Y s Y t, также принадлежит языку R; это завершает доказательство леммы.

Согласно лемме 1.3.3, любой блок B (i), где i k, можно представить в виде где M [M 0 ]r1, M2 [M 0 ]r1, D1 [Ci ]r1 и D2 [Ci ]r1 для некоторого i k. Слова D1 и D мы будем называть первым и вторым контентами блока B соответственно. Легко видеть, что блок B с точностью до эквивалентности определяется любым из своих контентов: для любого блока B и его контента D из D D1 или D D2 следует B B. Если B = P Q для некоторых слов P, Q, то либо D1 P, либо D2 Q. Таким образом, если блочное слово U содержит подслова P и Q, то хотя бы одно из этих подслов всегда будет входить в U внутри блока B (или эквивалентного ему блока).

Из доказательства леммы 1.3.3 следует, что можно выбрать такое представление блока B в виде (1.6), при котором M1 заканчивается маркером 1122122, а M2 начинается и заканчивается соответственно маркерами 2212211 и 2211211. Рассуждая аналогично (с точностью до операции инвертирования слов), можно показать, что блочное слово U можно разбить на блоки так, что каждый блок, начиная со второго, имеет префикс 1121122. Если слово U начинается маркером (112)2+l 2 (l > 0), то есть U = (112)2+l 2U для некоторого U то слово 1121122U является блочным, при этом его первый блок начинается с ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) маркера 1121122. Таким образом, для блочного слова U справедливо следующее представление:

где каждый блок Bj (j = 1,..., n) начинается с маркера 1121122. Префикс (112)l (где l 0) мы называем вводным префиксом слова U. Из однозначности разбиения (1.7) вытекает, что блочное слово U имеет только один прообраз 1 (U ).

Теперь построим функцию : + + : выберем из каждого блока (i) по одному слову Ti и положим (i) = Ti для любого i = 1,..., k и для любого слова W +. Поскольку всякое блочное слово U имеет только один прообраз 1 (U ), функция взаимно-однозначна, и притом 1 (U ) = 1 (U ) для всех U (+ ).

§ 1.4 Доказательство основных результатов Вхождения маркеров S1 и S2 в блочное слово U назовем соседними, если между S1 и S2 в слове U не содержится других вхождений маркеров. Отметим, что в блочном слове соседними могут являться только вхождения различных маркеров, тогда как вхождения одного и того же маркера не являются соседними.

Докажем основную техническую лемму главы 1.

Лемма 1.4.1 (Лемма о сведении). Для любых слов U, V +, U V тогда и только тогда, когда (U ) (V ).

Доказательство. Рассмотрим сначала пару соседних слов U = XY Y Z и V = XY Y Y Z, где X, Z и Y +. Очевидно, слова также являются соседними. Ввиду равенства = +, для произвольной пары эквивалентных слов U и V выполнимость соотношения (U ) (V ) устанавливается по индукции.

Справедливость обратной импликации вытекает из более общего утверждения:

ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) () Пусть U, V +, слова U и V являются r1 -редуцированными и U V. Тогда если блочное слово, то V также является блочным словом и 1 (U ) 1 (V ).

Ввиду равенства r1 = r1, утверждение () достаточно доказать для пары r1 -редуцированных соседних слов U = XY s Z и V = XY t Z, где X, Z, Y + и {s, t} = {2, 3}.

Для блочного слова U мы будем пользоваться представлением (1.7) в виде произведения блоков. Рассмотрим различные варианты расположения подслова Y s внутри U.

Предположим сперва, что слово Y потенциально AB-целое. Ясно, что в этом случае слово Y s содержит не более одного маркера (если на стыке вхождений Y в слове Y s образуется маркер, то s = 2, так как при s = 3 слово Y s = Y Y Y содержало бы два соседних вхождения одного и того же маркера, что невозможно). Тогда либо Y s Bp для некоторого блока Bp, либо Y s M2 1211 D2 1121 M1, причем слово M2 1211 D2 является суффиксом блока Bp (со вторым контентом D2 и двойным маркером M2 [M 0 ]r1 ), а слово M1 [M 0 ]r1 префиксом блока Bp+1. В силу леммы 1.3.3, в обоих случаях (во втором случае применяется утверждение 1 леммы с точностью до операции инвертирования слов), слово V получается из U заменой одного (Bp ) или двух (Bp и Bp+1 ) блоков на им эквивалентные, поэтому 1 (U ) = 1 (V ).

Пусть теперь 1121122 Y. Предположим, что Y содержит r различных вхождений маркера 1121122 (r 1). В этом случае слово Y можно представить в виде где Q префикс блока Bp+r, начинающийся с 1121122 (это последнее вхождение маркера 1121122 в Y ), а P или пустое слово, или суффикс вводного слова (при p = 0), или суффикс подслова Bp (1121)1. Тогда подслова U1 = X(Y Q1 )1121, U2 = Q(Y Q1 )1121 и U3 = QZ блочного слова U состоят из целого числа блоков. В силу равенств оба слова U и V являются блочными.

Подслово QP 1121122, входящее в Y Y, начинается и заканчивается маркером 1121122.

Если на стыке Q и P маркер 1121122 не образуется, слово QP 1121 совпадает с блоком Bp+r, причем хотя бы одно из слов Q или P 1121 содержит какой-нибудь из его контентов.

Если Q содержит какой-либо из контентов блока Bp+r, то первый блок слова U3 = QZ эквивалентен Bp+r, поэтому, с точностью до замены блоков на эквивалентные, где Z некоторый префикс слова Z. Дополнительно положим X =.

В случае, когда контент блока Bp+r содержится в слове P 1121, мы имеем p > 0 и Bp Bp+r, откуда, с точностью до эквивалентных блоков, ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) для подходящего суффикса X слова X. В этом случае положим Z =.

Наконец, если на стыке вхождений Q и P в слово Y Y образуется маркер 1121122, то слово QP 1121 состоит из двух блоков: QP 1121 = Bp+r 1121 Bp+r+1. При этом Q содержит первый контент блока Bp+r, а подслово P 1121 оба контента блока Bp+r+1, поэтому первый блок слова U3 эквивалентен Bp+r и Bp Bp+r+1. Таким образом, мы получаем для соответствующих суффикса X слова X и префикса Z слова Z.

Легко видеть, что во всех трех случаях замена X Y s Z X Y t Z в слове U приводит к одной из замен вида T s T t в слове W = 1 (U ), где Поэтому слово 1 (V ), получающееся после такой замены, оказывается соседним с 1 (U ).

Для завершения доказательства осталось рассмотреть вариант, при котором слово Y не является потенциально AB-целым, но при этом 1121122 Y. Пусть S какой-нибудь маркер, входящий в Y. Ясно, что слово Y содержит по крайней мере два различных вхождения S. Тогда, по построению отображения, слово Y s содержит все четыре маркера. Это возможно только, если маркер 1121122 образуется внутри слова Y s на стыке вхождений Y, в то время как остальные маркеры встречаются в Y по одному разу.

Представим Y в виде Y = P QR, где Q, P, R +, причем RP = 1121122. Слово RP Q является префиксом некоторого блока Bp слова U. Пусть где M1 и M2 двойные маркеры, а D1 и D2 соответственно, первый и второй контенты Bp. Поскольку в слове Y все вхождения маркеров встречаются внутри подслова Q, мы можем записать для некоторого префикса T контента D2.

С другой стороны, слово P Q1121 является суффиксом блока Bp1 и имеет вид где M1 и M2 двойные маркеры, D1 и D2 соответственно, первый и второй контенты блока Bp1, и T M1, причем T содержит маркер 1122122. В силу единственности вхождения каждого маркера в слово Y, мы заключаем, что D1 = D1, M2 = M2 и причем D2 D1 = D1.

ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) Таким образом, слово RP Q1121 является блоком, первый контент которого совпадает с первыми контентами блоков Bp и Bp1. Следовательно, Bp1 Bp RP Q1121. Заметим, что подслова XP Q1121 и RP QRZ блочного слова U состоят из целого числа блоков. Ввиду равенств оба слова U и V являются блочными. Преобразование Y s Y t в слове U индуцирует преобразование (W [p])s (W [p])t в его прообразе W = 1 (U ), поэтому прообразы слов U и V являются соседними, что и требовалось доказать.

Теорема 1.1 непосредственно следует из леммы о сведении.

Доказательство теоремы 1.2. Для доказательства нетривиальной импликации теоремы рассмотрим морфизм :, действующий на k по правилу: (i) = (i)(1121)1.

Несложно проверить, что (U ) = (U )1121 для любого слова U +. Если гипотеза Бжозовского справедлива для полугруппы B(2, 2, 3), то для любого слова U класс [(U )] является рациональным языком. Следовательно, класс [U ] = 1 ([(U )](1121)1 ) также является рациональным языком, поэтому гипотеза Бжозовского справедлива и для полугруппы B(k, 2, 3).

Обобщение результатов на полугруппы B(k, 2, 2+m) § 1. До сих пор мы рассматривали только полугруппы B(k, 2, 3). Оказывается, при небольших изменениях в доказательстве, теоремы 1.1 и 1.2 могут быть обобщены на полугруппы B(k, 2, 2 + m) с произвольным значением m. А именно, справедливы следующие две теоремы.

Теорема 1.3. Проблема равенства слов для полугруппы B(k, 2, 2 + m) ранга k 2 разрешима тогда и только тогда, когда проблема равенства слов разрешима для полугруппы B(2, 2, 2 + m).

Теорема 1.4. Гипотеза Бжозовского для полугруппы B(k, 2, 2 + m) при k 2 справедлива тогда и только тогда, когда гипотеза справедлива для полугруппы B(2, 2, 2 + m).

Зафиксируем параметры m > 1 и k 2 и рассмотрим полугруппу B(k, 2, 2 + m). В этом параграфе, при отсутствии индексов, под обозначениями, и [W ] (где W k ) мы ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) понимаем, соответственно, 2,m, 2,m и [W ]2,m. Эквивалентными (соседними) мы называем слова, эквивалентные относительно конгруэнции 2,m (соотв., лежащие в отношении 2,m ).

Для доказательства теорем 1.3 и 1.4 мы воспользуемся уже построенным в § 1.3 отображением, немного подправив его определение (точнее, мы подкорректируем определение отображения ). Но сначала проверим, какие утверждения остаются в силе при замене конгруэнции 2,1 на 2,m.

Существенной является утрата свойства r1 (W ) W для произвольного слова W, так как сокращения вида cl c2 (l 3) в слове W в общем случае могут выводить нас из класса [W ]. Конечно, можно было бы изменить определение операции r1 таким образом, чтобы сохранить свойство r1 (W ) W, однако такой подход делает невозможным использование понятия AB-целого слова, для которого необходимо отсутствие любых степеней букв в слове выше второй. Таким образом, от свойства r1 (W ) W нам придется отказаться. Тем не менее, предложение 1.2.2 остается в силе.

Предложение 1.5.1. Если (W1, W2 ) 2,m, то (r1 (W1 ), r1 (W2 )) 2,m.

и Y +. Так как степени букв можно сокращать в любом порядке, применим операцию r1 сначала к словам X, Y и Z. Поскольку слова r1 (X)r1 (Y )r1 (Y )r1 (Z) и r1 (X)r1 (Y )2+m r1 (Z), очевидно, являются соседними, мы можем считать, что слова X, Y и Z уже r1 -редуцированы. Заметим, что если Y является степенью буквы, то r1 (W2 ) = r1 (W1 ): в этом случае доказываемое утверждение очевидно. В дальнейшем мы будем считать, что Y = cl ни для каких c 2 и l 0.

суффикс слова X, оставляя слово Y нетронутым. Таким образом, если l2 = 2, слово XY редуцируется до X Y, а при l2 = 1 мы получаем r1 (XY ) = X cY. В обоих случаях, после сокращения cl1 +l2 c2, слова U и V остаются соседними. Аналогично показывается, что применение r1 к подслову Y Z сохраняет отношение соседства между словами U и V, поэтому мы можем считать, что подслова XY и Y Z уже r1 -редуцированы.

Осталось рассмотреть случай, когда степень буквы образуется на стыке вхождений Y.

Тогда Таким образом, (r1 (W1 ), r1 (W2 )) 2,m, что и требовалось доказать.

Ввиду предложения 1.5.1, если мы рассмотрим ограничения r1 и r1, соответственно, отношения соседства и конгруэнции на множество всех r1 -редуцированных слов над ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) алфавитом 2, то отношение r1 будет транзитивным замыканием r1. Множество всех r1 -редуцированных слов из класса [W ] мы по-прежнему обозначаем через [W ]r1.

Что касается свойства слов быть (потенциально) AB-целым, оно по-прежнему сохраняется конгруэнцией ввиду импликации U 2,m V U 2,1 V, тривиально выполнимой для любых U, V.

Определение двойных маркеров мы оставляем неизменным, при этом, как было сказано выше, под эквивалентностью мы подразумеваем отношение 2,m. Это несколько сужает множество двойных маркеров, как показывает следующая лемма (для сравнения, см. лемму 1.3.1).

Лемма 1.5.1.

Доказательство леммы 1.5.1 почти полностью повторяет доказательство леммы 1.3.1:

отличие состоит в том, что теперь {s, t} = {2, 2 + m}, а числа l1, l2 кратны m.

Определение отображения переносится на случай конгруэнции 2,m с одним небольшим изменением. Как было сказано выше, для любых слов U и V справедлива импликация U 2,m V U 2,1 V, которая, очевидно, равносильна импликации U 2,1 V U 2,m V.

Таким образом, замена конгруэнции 2,1 на 2,m ослабляет условия, наложенные на слова C1,..., Ck из определения отображения. Чтобы не допускать этого, мы потребуем, чтобы по-прежнему выполнялось Ci 2,1 Cj для любых i, j k, i = j, и Ci [212212]2,1 для любого i k. Позже мы увидим, для чего нам необходимо сохранить определение слов C1,..., Ck в таком виде. По лемме 1.3.2, которая, очевидно, остается в силе, такой набор слов существует.

Остановимся подробнее на доказательстве аналога леммы 1.3.3.

Лемма 1.5.2. Для любого i = 1,..., k имеет место 1) [M 0 2122 Ci 2212 M 0 ]r1 = [M 0 ]r1 2122 [Ci ]r1 2212 [M 0 ]r1 ;

2) [M 0 2122 Ci 2212 M 0 1211 Ci ]r1 = [M 0 ]r1 2122 [Ci ]r1 2212 [M 0 ]r1 1211 [Ci ]r1.

Доказательство. Как и в лемме 1.3.3, мы ограничимся доказательством утверждения 2. Для этого достаточно рассмотреть пару соседних r1 -редуцированных слов U и V и показать, что если U R, то и V R, где R обозначает язык, задаваемый соответствующим регулярным выражением из условия (см лемму 1.3.3).

{s, t} = {2, 2 + m}, и для некоторых слов M1 [M 0 ]r1, M2 [M 0 ]r1, D1 [Ci ]r1 и D2 [Ci ]r1. Разбор всех случаев расположения подслова Y s в слове U происходит так же, как и раньше, при доказательстве ГЛАВА 1. ПОЛУГРУППЫ B(k, 2, 3) леммы 1.3.3. Изменения касаются только случаев, когда слово Y Y потенциально AB-целое и либо Y s 122122 2122 D1 2212 221221, либо Y s 211211 1211 D2.

Предположим, что U = X Y s Z = 122122 2122 D1 2212 221221, где X суффикс слова X, а Z префикс слова Z. Положим V = X Y t Z. Слова U и V эквивалентны, поэтому, ввиду предложения 1.2.5, они имеют общий префикс 122122 и общий суффикс 221221. Так как слово U потенциально AB-целое, то и слово V является потенциально AB-целым по предложению 1.2.3, следовательно, либо V = 1221221, либо V начинается на 12212212 и заканчивается на 21221221.

Рассмотрим теперь слово V = (212)m1 2V 2(212)m1. Ясно, что (212)m1 2V 2(212)m1 (212)m1 2U 2(212)m1 = (212)m D1 (212)m D1 Ci, так как слово D1 имеет префикс 212212 и суффикс 212212. Заметим, что слово V начинается и заканчивается на (212)2+m. Покажем, что при одновременном сокращении (212)2+m 212212 и в префиксе, и в суффиксе слова V результирующее слово будет эквивалентно V. Это очевидно, если префикс (212)2+m и суффикс (212)2+m не пересекаются внутри слова V. При пересечении возможны два варианта: либо V = (212)r для 2 + m, либо V = (212)1+m (21212)(212)1+m. В первом случае, очевидно, некоторого r V 212(21212)212. Второй случай невозможен. Действительно, ранее мы показали, что V Ci, однако, по определению Ci, мы имеем Ci [212212]2,1.

Итак, мы убедились, что слово D1 = V [3... |V |2], которое получается из слова (212)m1 2V 2(212)m1 заменой префикса (212)2+m и суффикса (212)2+m на слово (212)2, эквивалентно слову D1. Следовательно, и D1 [Ci ]r1, откуда V R, что и требовалось доказать.

Случай Y s 211211 1211 D2 разбирается аналогично.

Доказательство леммы о сведении, теорем 1.3 и 1.4 с незначительными изменениями повторяет доказательство для полугрупп B(k, 2, 3).

Глава Проблема равенства слов для полугруппы B(2, 2, 3) § 2.1 Введение и формулировка результатов В этой и следующей главах мы рассматриваем только полугруппу B(2, 2, 3). В связи с этим, мы будем опускать индексы в обозначениях 2,1, 2,1 и [W ]2,1 (где W ) и писать просто, и [W ]. Всюду далее символ обозначает алфавит 2.

Один из возможных путей решения проблемы равенства слов в полугруппе B(2, 2, 3) состоит в том, чтобы в каждом классе конгруэнции выбрать подходящим образом канонического представителя. Тогда решение проблемы равенства слов сводится к нахождению по данному слову соответствующего его классу представителя. Естественно, казалось бы, выбрать в качестве канонических представителей бескубные слова, так как, очевидно, любое слово эквивалентно некоторому бескубному слову, однако, как показывает следующий пример, существуют классы эквивалентности, содержащие более одного бескубного слова:

Пример 2.1.1.

1212 2121 121212 212121 121212 21212 212121 1212 21212 2121.

Более того, как показал К. В. Костоусов (результат не опубликован), для любого наперед заданного числа N найдется класс, содержащий не менее N бескубных слов.

Таким образом, круг кандидатов в канонические представители необходимо сузить.

Разумно в качестве канонического представителя в каждом классе эквивалентности выбрать минимальное по длине слово, однако неясно, как находить такое слово в произвольном классе эквивалентности. К тому же до сих пор не известно, в каждом ли классе слово минимальной длины единственно (см. раздел 2 ).

Интересным представляется вопрос, как по классам эквивалентности распределены сильно бескубные и почти сильно бескубные слова. Е. В. Сухановым была выдвинута гипотеза, что каждый класс эквивалентности содержит не более одного сильно бескубного ГЛАВА 2. ПРОБЛЕМА РАВЕНСТВА СЛОВ ДЛЯ ПОЛУГРУППЫ B(2, 2, 3) слова. Косвенно эта гипотеза подтверждается результатами работ [2] и [30]: в [2] доказывается, что всякий класс эквивалентности содержит не более одного слова Туэ-Морса, а согласно [30], произвольное сильно бескубное слово в некотором смысле очень похоже на подходящее слово Туэ-Морса.

В данной главе мы докажем чуть более сильное утверждение.

Теорема 2.1. Всякий класс конгруэнции, за исключением классов [11] и [22], содержит не более одного почти сильно бескубного слова. Каждый из классов [11], [22] содержит в точности два почти сильно бескубных слова.

Класс [11] = 111 (класс [22] = 222 ) содержит два почти сильно бескубных слова и 111 (соответственно, 22 и 222), из них только одно слово является сильно бескубным.

Таким образом, из теоремы 2.1 непосредственно вытекает справедливость сформулированной выше гипотезы.

Следствие. Всякий класс конгруэнции содержит не более одного сильно бескубного слова.

Для решения проблемы равенства слов недостаточно выбрать в каждом классе эквивалентности элемент, служащий его каноническим представителем. Необходимо уметь находить такой элемент в классе [U ] для произвольного слова U. Эту задачу решает построенный нами алгоритм EqAOF, который за линейное от |U | время по данному слову U находит почти сильно бескубное слово V, эквивалентное U, или сообщает, что таких слов нет. Таким образом, алгоритм EqAOF позволяет получить частичное решение проблемы равенства слов для полугруппы B(2, 2, 3).

Теорема 2.2. В полугруппе B(2, 2, 3) проблема равенства слов разрешима за время O(max{|U |, |V |}) для всех пар (U, V ), в которых по крайней мере одно из слов эквивалентно почти сильно бескубному слову.

К сожалению, существуют классы, не содержащие почти сильно бескубных слов, например, класс [121211] = (12)2 (12) 111. Поэтому нами получено лишь частичное решение проблемы равенства слов.

Глава состоит из 7 параграфов. §§ 2.4–2.6 содержат вспомогательные утверждения, необходимые для доказательства теоремы 2.1 и для построения алгоритма EqAOF. Теорема 2.1 доказывается в § 2.5. Наконец, последние два параграфа посвящены построению и анализу алгоритма EqAOF.

Свойства r-редукции § 2. При доказательстве теорем 2.1 и 2.2 мы существенно опираемся на результаты работ [2] и [30], используя разработанные в них вспомогательные понятия и методы. Почти весь нужный нам инструментарий был введен в § 1.2.

ГЛАВА 2. ПРОБЛЕМА РАВЕНСТВА СЛОВ ДЛЯ ПОЛУГРУППЫ B(2, 2, 3) Ключевую роль в наших последующих построениях играет предложение 1.2.4. Ввиду того, что любой морфизм очевидным образом сохраняет отношение, из предложения 1.2.4 следует, что (U ) (V ) выполняется тогда и только тогда, когда U V. Мы видим, что, проблема равенства слов для пары -образов может быть сведена к проблеме равенства слов в два раза меньшей длины. Идея заключается в том, чтобы произвольную пару слов U и V превратить в пару -образов, а затем применить к ним отображение 1, обратное к морфизму Туэ-Морса. К полученной таким образом паре слов мы снова применяем описанную последовательность действий, и т. д. В силу конечной длины слов U и V, такой процесс не может продолжаться бесконечно долго: в конце концов, мы придем к паре коротких слов, для которых проблема равенства слов тривиально разрешима.

В этом и двух последующих параграфах мы рассмотрим следующие преобразования, которые позволяют привести произвольное слово U к -образу:

– введенная ранее r-редукция, которая преобразует AB-целое слово в эквивалентное ему регулярное слово;

– rT -редукция, применяемая к паре эквивалентных слов для получения пары эквивалентных AB-целых слов;

– функции and, каждая из которых трансформирует пару эквивалентных регулярных слов в пару эквивалентных -образов.

Заметим, что каждое из перечисленных преобразований сохраняет эквивалентность в одном их следующих двух смыслов: либо трансформация касается одного слова, которое заменяется на эквивалентное, либо преобразование применяется к паре эквивалентных слов (U, V ), сохраняя отношение эквивалентности между словами (исключение составляет разве что функция, но об этом речь пойдет позже, в соответствующих параграфах).

Мы начнем с изучения первой из перечисленных операций операции r.

Нередуцируемые хвосты. Свойство r(U ) U 2.2. Как мы знаем из § 1.2, операция r, в отличие от r1, в общем случае не сохраняет отношение эквивалентности в том смысле, что слово r(U ) не обязательно эквивалентно слову U.

Выясним, при каких условиях соотношение r(U ) U все же имеет место. Оказывается, простой ответ на этот вопрос можно получить, рассматривая операцию r на множестве AB-целых слов.

Предложение 2.2.1. Для AB-целого слова U, соотношение r(U ) U имеет место тогда и только тогда, когда, с точностью до инвертирования букв, слово U не имеет префикса вида 121(121) (12)2 (12) 11 и суффикса вида 11(21) (21)2 (121) 121.