Комбинаторика на бесконечных перестановках

• Автор: Макаров, Михаил Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 111 с. : ил.

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

Глава 1. Перестановки, порождённые лексикографическим порядком на суффиксах слов

1.1. Конечные лексикографически допустимые перестановки

1.2. Биекция между допустимыми перестановками и регулярными языками

1.3. Бесконечные перестановки, порождённые универсальными словами

Глава 2. Перестановки Штурма

2.1. Определения и предварительные замечания

2.2. Комбинаторная сложность

2.3. Максимальная шаблонная сложность

2.4. Обобщение на двумерный случай

2.5. Арифметическая сложность
2.6. Заключительные замечания
Глава 3. Перестановка удвоения периода
3.1. Предварительные определения
3.2. Знаки и типы вершин
3.3. Классификация ш-допустимых перестановок
3.4. Бинарные влево перестановки
3.5. Странные перестановки
3.6. Комбинаторная сложность
3.7. Технические леммы о го-допустимых перестановках маленькой длины
Глава 4. Перестановка Туэ-Морса
4.1. Два определения
4.2. Эквивалентность двух определений

4.3. Замечание о последовательностях Т(п) и Яш(п)
Глава 5. Антимонотонные перестановки
5.1. Определение
5.2. Комбинаторная сложность и графы Рози
5.3. Максимальная шаблонная сложность
5.4. Арифметическая сложность
Литература

Введение
Одним из разделов дискретной математики является комбинаторика на словах. Возникновение этого раздела восходит к работам Акселя Туэ в начале XX века [1], [2], [3]. Исторический очерк может быть найден, например, в статье [4]. Одними из основополагающих книг являются [5], [6].
Объектом исследования в комбинаторике на словах являются символьные последовательности над конечным алфавитом (или слова). Естественным образом определяется конкатенация конечных слов и операция взятия под-слов. Язык всех конечных подслов заданного бесконечного слова является факторным, то есть вместе с любым словом он содержит все его подслова. Среди исследуемых комбинаторных свойств бесконечных слов особенный интерес представляет функция комбинаторной сложности /г„(п), ставящая в соответствие каждому натуральному п количество различных подслов длины п бесконечного слова т. Обзор результатов по комбинаторной сложности слов дан в статье [7]. Классический результат Морса и Хедлунда [8] гласит, что для всякого бесконечного слова гг, являющегося существенно непериодическим (то есть никакой суффикс которого не является периодическим), выполнено /ш(п) > п + 1.
Помимо исследования общих свойств бесконечных слов, выделяются конкретные классы бесконечных слов или даже отдельные бесконечные слова, которые изучаются более подробно. Таковыми являются слово Туэ-Морса [9], слово удвоения периода [10], слова Штурма [11], слово Фибоначчи [12], слова Роте [13], слово Серпинского, и другие. Приведём несколько определений.
Слово Туэ-Морса
т = 0110100110010110
может быть задано рекуррентно условиями ю(0) = 0, ии(2п) = 'ш(п), т{2п + 1) = 1 — гс(гг) при всех гг. 0. Также слово Туэ-Морса можно определить как неподвижную точку морфизма. А именно, рассмотрим отображение /р: {0,1} —» {0,1}2, заданное равенствами <(0) = 01 и порождаемыми различными продолжениями слова а, и примитивными суффиксами слова а. А в силу леммы 3, разным словам а будут соответствовать разные перестановки. Следовательно, каждой допустимой перестановке 7Г длины п + 1 соответствует слово а длины п с выделенным примитивным суффиксом.
Заметим, между прочим, что этот последний результат можно использовать для получения альтернативного доказательства теоремы 2, не использующего теорему 1. В самом деле, для нахождения Р{п + 1) нам нужно просуммировать количество примитивных суффиксов по всем словам а длины п. Это делается так: ко всем ф{Р) примитивным словам длины £ приписываем слева n — t произвольных символов алфавита {0,1}, а затем суммируем всё по £ от 1 до п. В итоге получаем требуемую формулу Р(п +1) = "=1 ФФ) ' 2п-г.
Вернёмся к построению биекции между допустимыми перестановками и регулярными языками. Мы показали, что каждой допустимой перестановке 7Г длины п + 1 соответствует слово а длины п с выделенным примитивным суффиксом. Дальнейшая биекция восстанавливается по лемме 2 и теореме 1 из статьи [58], а также по теоремам 2, 3 и 4 из [57]. Каждому слову а длины п с выделенным примитивным суффиксом сопоставим детерминированный автомат А с п состояниями по следующему правилу. Состояниями автомата
Кроме того, в теореме 5 из [57] найдена асимптотическая оценка для