Введение
1 Введение 4
1.1 Основные теоремы диссертации. 4
1.2 Актуальность темы
1.2.1 Символическая динамика и комбинаторика слов 8
1.2.2 Слова Штурма 9
1.2.3 Графы Рози 12
1.2.4 Морфические последовательности и теоремы типа Вер-шика-Лившица 14
1.2.5 Алгоритмические проблемы
1.3 Цель работы 19
1.4 Научная новизна 20
1.5 Краткое содержание диссертации 20
1.6 Основные методы исследования 25
1.7 Аппробация работы 25
1.8 Теоретическая и практическая ценность работы 26
1.9 Публикации 26
1.10 Структура и объем диссертации 26
1.11 Благодарности
2 Основные определения, обозначения и технические утверждения . 28
3 Схемы Рози
3.1 Определение схем Рози. 31
3.2 Свойства схем Рози. 33
3.3 Получение схем Рози из графов Рози
3.4 Эволюция схем Рози. 40
3.5 Свойства слов, порожденных примитивными морфизмами. 51
3.6 Свойства схем Рози для слов, порожденных примитивными морфизмами. 54
3.7 Построение оснасток. 59
3.8 Переход к произвольным почти периодичным подстановочным словам 67
4 Периодичность морфических последовательностей 71
4.1 Сведение общего случая к примитивному 71
4.2 Графы и схемы Рози. 77
4.3 Элементарная эволюция схем Рози. 87
4.4 Эволюция схем Рози. 96
4.5 Схемы Рози слов с не более чем линейным показателем рекуррентности . 98
4.6 Оснастки и построение алгоритма для морфического случая. 105
5 Почти периодичность морфических последовательностей 117
5.1 Приведение морфизмов к удобному виду. 117
5.2 Порядок роста букв 122
5.3 Схемы Рози. 128
5.4 Построение алгоритма для теоремы 5.2.1 134
6 Более короткие доказательства алгоритмической разрешимо
сти. 144
6.1 Проверка периодичности в примитивном случае 144
6.1.1 Схемы расположений подслов. 145
6.1.2 Схемы вхождений подслов, связанные с итерациями подстановки. 146
6.1.3 Алгоритм 150
6.2 Альтернативный алгоритм для проверки почти периодичности. 151
7 Заключение. 154
Список литературы
