Комбинаторные свойства факторных языков перестановок

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

Оглавление
Введение
1 Основные определения
1.1 Слова и языки
1.2 Морфизмы
1.3 Конечные перестановки
1.4 Бесконечные перестановки
1.5 Бесконечные перестановки, порожденные бесконечными словами
2 Перестановки, порожденные неподвижными точками сравнимых равноблочных морфизмов
2.1 Введение
2.2 Необходимые сведения и определения
2.3 Общая схема
2.4 Класс <3;
2.5 Сопряженные перестановки
2.6 Алгоритм для вычисления /(и)
2.7 Специальные вправо слова
2.8 Вычисление перестановочной сложности
2.9 Перестановочная сложность слова Туэ-Морса
2.10 Заключительные замечания
3 Перестановки, порожденные неподвижными точками обобщенного морфизма Фибоначчи
3.1 Введение
3.2 Предварительные сведения и определения
3.3 Общая схема
3.4 Оценка /(и) <
3.5 Вклад специальных слов

3.6 Случай /(и) = 1 ,}{иа) =
3.7 Характеризация и перечисление плохих слов
3.8 Основная теорема
3.9 Связи с комбинаторной сложностью
4 Морфизмы на перестановках
4.1 Введение
4.2 Основные определения
4.3 Общая схема
4.4 Существование предка
4.5 Основная теорема
4.6 Алгоритм вычисления комбинаторной сложности
4.7 Пример вычисления комбинаторной сложности
4.8 Связь с перестановками, порожденными бесконечными словами
5 Рамочные паттерны в перестановках
5.1 Введение
5.2 Основные определения
5.3 Гипотеза Стэнли-Вильфа для рамочных паттернов
5.4 Мультиизбегание классических и рамочных паттернов
Литература

Введение
В данной работе исследуются свойства факторных языков перестановок: мы изучаем языки подперестановок бесконечных перестановок; а также языки конечных перестановок, избегающих подпоследовательностей с определенными свойствами. Эти задачи относятся к комбинаторике слов, бесконечных перестановок, а также теории паттернов в перестановках. Основы комбинаторики слов и теории паттернов в перестановках изложены в монографиях [4,13] и [16,41] соответственно; недавний обзор по бесконечным перестановкам может быть найден в работе [36].
Приведем основные определения. Алфавитом называется конечное (непустое) множество элементов, которые будем называть символами или буквами. Далее алфавит будем обозначать через Е. Конечным словом длины п над алфавитом Е называется последовательность и = И...ип из п символов алфавита Е. Длину конечного слова и, то есть число символов в нем, обозначим через |«|. Слово длины 0 называется пустым и обозначается через г. Множество всех конечных слов над алфавитом Е обозначается через Е*.
Бесконечным словом над алфавитом Е называется бесконечная вправо последовательность си — ачшашз... символов алфавита Е. Конкатенацией конечного слова и и слова V (конечного или бесконечного) называется слово х — ХХ2 ... такое, что = щ для г < |ц| и XI = г^_|и| для г > |и|. Конкатенация слов и и V обозначается через иу. Слово V называется подсловом конечного или бесконечного слова и, если существуют слова и з2 такие, что и = в1ьв2- Если при этом вц = г (во = е)> то V называется префиксом (.суффиксом) слова и. Вхождением слова и 6 Е" в слово ш называется пара (и,т) такая, что и = шт^1и>гп+2 ■ ■ ■ и>т+п. Комбинаторной сложностью сш(п) бесконечного слова ш называется число его различных подслов длины п. Бесконечное слово вида и = усу... обозначается через Vй. Бесконечное слово ш называется периодическим, если ш = иуш для некоторых конечных слов и и у. Бесконечное слово и называется непериодическим, если его нельзя представить в виде и = иг-“1 для некоторых конечных слов и И V. Языком называется произвольное подмножество Е*. Язык называется факторным, если он с каждым своим элементом содержит все его подслова, то есть замкнут относительно операции взятия подслова. Нетрудно видеть, что язык подслов Д(п’) произвольного

(см. ниже схему правильного разбиения слова ш на блоки).
ш = ... хшгу'1г'... r'ujjij'
1— ----1 1——J11—rrr
Ті г2 vW
Если = 0, то R^(i + у' + 1) > Ru{j + I ~ f + 1) (см. ниже схему правильного
разбиения слова ш на блоки).
Ы = . . . ХШгу' 1г' . . . x'tOjll' 0.
1------1 1——|L~TTJ

Таким образом, в этом случае всегда выполняется неравенство Ru{i) > Ru{j).

Проиллюстрируем лемму 2.2 на следующем примере:
Пример. Рассмотрим морфизм <£>(0) = 011, <р{ 1) = 100 из класса Qi. Его неподвижная точка ш = ір(ш) имеет следующее правильное разбиение на блоки:
ш = wiш2шз ... = 011 100 100 100 011 011 100 011 011
і и и и и и и и и і
¥=(0) ¥(1) ¥(1) ¥>(1) Р(0) ¥(0) ¥3(1) ¥>(0) ¥,(0)
Рассмотрим отношения 7(/?ы(1), /?ш(6)) и y(Rul(16), Ru(12)). Имеем 1 s 16 (mod 3), 6 s 12 (mod 3), и 1 ф б (mod 3). Кроме того, шг и (ш1б и ш12) лежат в блоках у)(0) и <у>(1) в правильном разбиении lj. Поэтому по лемме 2.2 должно быть выполнено равенство 7(/?ш(1),/?ы(6)) = 7(1?Ш(1С), Лш(12)). С другой стороны, имеем
Ru( 1) = 0,011..., ДД6) = 0,010..., 7?ы(12) = 0,001... и ДД16) = 0,011.... Таким
образом, 7(ЛШ(1), ДД6)) ='t{Ru(16),Ru(12)) =>.
Лемма 2.3. Пусть (и, mi) и (и,т2) — два вхождения подслова и длины п > Ьы,
(и',т[) и {и',т'2) — предки этих вхождений. Тогда для 1 < t < s < п либо выполнено
равенство
f (Ra(m, + t). Raimi + s)) = 7(ДДт2 + t). ДДотг + *))-
либо ni + t = [m'i + t' — 1)/ + r, mj + s = (m + s' — 1)1 + r, m2 + t = (m'2 + t' — 1)1 + r, m2 + і = (m'2 + s' - 1)1 + r для некоторого 1 < r < l и
Шт'і-rt' = ^n'j+s' = = Wm'34V-
Доказательство. Пусть 1 < t < s < п. Рассмотрим отношения -/(R^inii+t), Ru{nii+s)) и т(Ли,(т2 +1). ДДт2 + s)). Если wmi_f Ф и wm2+t Д wm2_s, то
7(ДДmj + f). ]î„(mi + .s)) = 7(wmiTt,wmi_5)