Шаблоны, избегаемые антицепями слов, и их алгебраические приложения

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

Содержание
Введение

1 Предварительные сведения

1.1 Избегаемые шаблоны

1.2 Свободные стирания и морфизмы

1.3 Последовательность, которая избегает все избегаемые шаблоны над п-буквениым

алфавитом

1.4 Некоторые сведения о многообразиях полугрупп

и их решетках

2 Шаблоны, избегаемые палиндромами

2.1 Последовательность палиндромов

2.2 Лемма о маркерах
2.3 Последовательности свободных стираний
2.4 Основная теорема
2.5 Индексы избегаемости
3 Избегаемые тождества и антицепи слов
3.1 Антицепи слов и избегаемые шаблоны
3.2 Решеточная универсальность многообразий полугрупп, заданных О-приведенными
тождествами
3.3 Изотермы и избегаемые тождества
3.4 Антицепи слов и избегаемые тождества
4 Классификация решеточно универсальных многообразий
Предметный указатель
Список литературы

Введение
В данной работе под алфавитом понимается непустое множество. Как правило, мы рассматриваем конечные алфавиты; в случае, когда возникает бесконечный алфавит, это будет оговариваться особо. Элементы алфавита называются буквами. Основным объектом наших исследований будут слова, которые мы рассматриваем, с одной стороны, как конечные последовательности букв некоторого алфавита 2, а с другой — как элементы свободной полугруппы £+ над этим алфавитом. В качестве примера источника задач, связанных с изучением таких последовательностей, можно привести молекулярную биологию. Как известно, генетическая информация в любом живом организме зашифрована в молекулах ДНК, которые представляют собой конечные (хотя и очень длинные) цепочки-слова над алфавитом из четырех букв-нуклеотидов. Важнейшими (по не единственными) комбинаторными вопросами в этой области будут расшифровка способов кодирования, хранения, восстановления, считывания и записи генетической информации. Другая, даже более обширная область, которая использует изучение свойств слов, — это компьютерные науки. Вся информация в современных компьютерах организована в виде файлов, а каждый файл в конечном счете представляет собой некоторое слово, состоящее из нулей и единиц. Среди направлений информатики, в которых применяется комбинаторика слов, можно отметить криптографию, сжатие и восстановление данных, теорию формальных языков и теорию автоматов.
Норвежский математик Аксель Туэ (1863-1922), который одним из первых начал изучать свойства последовательностей букв, считается основателем современной комбинаторики слов. В своих работах 1906 года [53] и 1912 года [54] он исследовал выразительные возможности алфавитов из двух и трех символов (в первую очередь на выбор размера алфавитов повлияло появление таких средств коммуникации, как телеграф и радио). Туэ принадлежит ряд крупных достижений в различных разделах математики, однако его статьи по комбинаторике слов оставались незамеченными в течение почти полувека после публикации, поэтому многие результаты из этих статей переоткрывались иногда не по одному разу. В качестве примера такого «открытия» можно привести наиболее известное множество слов во всей комбинаторике — это слова Туэ-Морса. Туэ в [53] построил эти слова и показал, что они не содержат трех последовательно входящих одинаковых блоков. Почти через 40 лет

Морс и Хедлунд [45], ничего не зная о работах Туэ, переоткрыли этот результат в своих исследованиях по динамическим системам.
Туэ считал, что развитие комбинаторики слов приведет к появлению интересных результатов не только внутри самой теории, но и в различных ее приложениях. Как оказалось позднее, эти ожидания более чем подтвердились. В последние несколько десятков лет комбинаторика слов разрослась в самостоятельную математическую дисциплину, содержащую большое количество разделов (подробнее с ними можно ознакомиться, например, в монографиях [31,42,43]). Свидетельством определенной зрелости этой дисциплины является выделение ей отдельного кода 68Я15 в широко используемой в математической литературе классификации МЗС2010.
Уже в пионерских работах по комбинаторике слов рассматривается одно из важнейших свойств слов — избегаемость. Будем говорить, что непустое слово ги над алфавитом Е содержит слово и над (возможно другим) алфавитом Д, если существует такой морфизм Л : Л+ н-+ Е+, что слово к(и) является подсловом и). Слово V £ Д+ избегаемо, если найдется такой конечный алфавит Е и бесконечная последовательность слов С Е+ таких, что все слова не содержат и. Например,
как следует из упомянутых выше результата Туэ, слово з? избегаемо, а соответствующее множество слов — это последовательность Туэ-Морса. С последними достижениями в теории избегаемых слов .можно ознакомиться, например, по обзору [35]. Именно феномен избегаемое и его алгебраические приложения играют ключевую роль а данной работе.
Как и предсказывал Туэ, новые идеи постепенно нашли применение в различных областях математики. Так с 50-х годов прошлого века Шют-цепберже (см. [24]) начал использовать комбинаторику слов в своих основополагающих работах по теории кодирования.
Особенно важными оказались приложения комбинаторики слов и, в частности, теории избегаемое в алгебре. В 1902 году Бернсайд сформулировал следующую проблему: верно ли, что любая конечнопорожден-ная группа, в которой у каждого элемента конечный порядок, конечна? Проблема Бернсайда и связанные с ней задачи во многом определили развитие алгебры в двадцатом веке. Долгое время усилия были направ-
1 Справедливости ради следует отметить, что сами слова, называемые теперь сло-вами-Туэ-Морса, впервые появились в работе Пруэ [47] по теории чисел, но отмеченное вьгше ключевое свойство этих слов обнаружил именно Туэ.

р(хт) = /1ра1{хт) = 2, где т > 3. Более того, каждый четный член последовательности примера 1.3, избегающей квадраты, также будет палиндромом, поэтому индексы р{х2) и цРа1(х2) равны 3.
Возникает следующий вопрос: верно ли, что для каждого шаблона эти индексы совпадают? Другими словами, верно ли, что всегда можно построить бесконечную последовательность палиндромов, избегающих шаблон р над тем же алфавитом, в котором р избегаем?
Следующий пример дает отрицательный ответ на эти вопросы.
Пример 2.2. Рассмотрим шаблоны ру = хугхгу и р2 = р = угхгух. Известно [46], что оба эти шаблона 2-избегаемы. Но, в то же время, существует лишь конечное число слов над алфавитом из двух букв, которые не содержат одновременно р и р2 [34]. Если мы предположим, что существует последовательность палиндромов шш над двухбуквепным алфавитом, которая избегает рь то получим, что слова гит = шт избегают Р2. Таким образом, р{рг) = 2, тогда как рра1{р1) = 3 [46].
Далее приведем некоторые оценки для индекса избегаемое палиндромами.
Как уже отмечалось ранее, для любого избегаемого шаблона р существует последовательность палиндромов, которая его избегает. Используя построенную выше последовательность, получим следующую оценку
Рра1 (р) ■
Предложение 2.3. Пусть р — произвольный избегаемый шаблон над алфавитом из п переменных. Тогда дра/(р) < 22^°^6п+2^ + 1.
Рассмотрим класс шаблонов К, каждый шаблон р 6 К обладает следующим свойством: каждая переменная встречается в р по крайней мере дважды. Для этого класса слов оценку для дра1(р) можно улучшить.
Предложение 2.4. Рассмотрим шаблон р £ К такой, что | а1рЬ(р)| = = п. Тогда рра((р) < (6л + 2)2 + 1.
Доказательство. Сначала заметим, что р — избегаемый шаблон [43]. Следовательно, для него можно построить последовательность 7т(ац) с длиной блока г = 6л + 2. В [18] показано, что так построенная последовательность будет избегать все избегаемые слова над алфавитом, состоящим из л букв, если длина блока г больше 6л + 1. Тогда можно взять |Е| = (6л 4- 2)2.