Построение экстремальных бесповторных слов и оценка их количества

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

Оглавление
Введение

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

Обзор исследований по теме диссертации

Обзор диссертации

Глава 1. Граничные слова

1.1. Структура граничных слов

1.1.1. Кодировка Пансьё

1.1.2. Цилиндрическое представление

1.1.3. Равномерные ш-повторы

1.1.4. 3-повторы

1.1.5. 4-и 5-повторы
1.1.6. 6-повторы
1.1.7. 7-повторы
1.2. Оценка количества граничных слов
1.2.1. Верхние оценки для индексов роста граничных языков
1.2.2. Развёртки цилиндров
1.2.3. Случай ш=
1.2.4. Индекс роста двумерного языка
1.2.5. Автоматы Лк и В к
1.2.6. Свойства автоматов Лк и Вк
1.2.7. Связь между индексами роста граничных языков и языка Б
Глава 2. Циклические слова
2.1. Нижняя оценка для циклической границы повторяемости
2.2. Верхние оценки для циклической границы повторяемости
2.2.1. Случай к =
2.2.2. Случай к —
2.2.3. Случай к =
2.2.4. Случай к =

2.2.5. Случай к =
2.2.6. Случай нечетных к > И
2.3. Аналог гипотезы Дежан для циклических слов
Литература
Приложение А

Введение
Изучение свойств символьных последовательностей (слов) и множеств таких последовательностей (формальных языков) составляет важное направление в современной дискретной математике, имеющее обширные приложения в различных разделах математики, компьютерных науках, биологии и других областях знания. Интерес к символьным последовательностям у математиков появился более ста лет назад. Тому были как «внутренние» причины (становление теории групп), так и «внешние», например, активное использование двоичного кода (азбука Морзе) для передачи сообщений посредством телеграфа и радио. Первым математиком, систематически изучавшим свойства символьных последовательностей, был норвежец А.Туэ, которого по праву считают основоположником комбинаторики слов.
Одной из центральных тем комбинаторики слов является изучение слов и языков, не содержащих повторов - идущих подряд одинаковых фрагментов. Понятие повтора легко проиллюстрировать и в естественных языках. Например, слово «мама» - это повтор, называемый квадратом (состоит из двух одинаковых фрагментов). Иногда само слово не является повтором, но повтор находится внутри него, как, например, в слове «банан» (фрагмент «ан» повторился 2 раза). Любой повтор характеризуется экспонентой - отношением длины слова к длине повторяющейся части. Так, слово «заноза» - это повтор с экспонентой 3/2 (фрагмент «зано» повторился лишь до половины). Экспонента обобщает понятие показателя степени на дробные значения.
Экспонента в называется избегаемой над данным алфавитом, если существует бесконечное слово (или, что эквивалентно, бесконечно много конечных слов) над данным алфавитом, не содержащее повторов с экспонентой, не меньшей (3. Начало исследованиям в этой области также положил Туэ. Он доказал, что квадраты избегаемы над 3-буквенным алфавитом [50], а кубы и все дробные степени, большие 2, избегаемы над 2-буквенным алфавитом [51]. Результат Туэ для 2-буквенного алфавита неулучшаем, поскольку любое слово длины не меньше 4 в таком алфавите содержит квадрат. Однако для 3-буквенного алфавита найденное Туэ значение не было оптимальным: в 1972 году Ф.Дежан построила бесконечное слово над 3-буквенным
'Здесь «степень» относится к ассоциативной операции умножения (конкатенации) слов, т.е. (ма)2 =мама.

01101101^,1101101101^011011011^1101101101^,01101101^,11011011,
fc_g__________fc________g А—10 A—9 к—О
01101101^ 1101101101^—,011011011^1101101101^011011011^,0110110,
к—9 к-9 к-10 к-Я к-
11011011^01101101^011011011^1101101101^011011011^01101101,
к—8 к~ 9 А’—10 к— 9 А’—
01101101^01011011^01101101^01011011^,01101101^0101101,
к-8 к—8 к—8 к-S к-
0101101^01101101^01011011^01101101^01011011^0110110,
к-7 к-8 к—8 к—8 к-
110101101^01101011^110101101^01101011^110101101^0110101,
к—8 /г—9 А—-8 к—9 А—
0101101 ■■■ 01101011 ■■■ 110101101 ■■■01101011 ■■■ 110101101 ••■ 01101011,
к—8 к~9 к—8 к—9 к—
01011011^,0110101101 110101101101 ^—^01101011011 ^,0101101101 11010110,
к—9 А—11 А—11 А—10 А—
11010101^^01101101^^ 110101011^^01101101^ 110101011^,0110110,
А—7 А—9 А—8 к—9 к—
0101011^01101101^110101011^01101101^110101011^01101101,
к—8 к—9 к-8 к—9 к-
010101101^0110110110^110101011011^01101101101^010101101^11011011,
к-10 к—11 к—11 к—10 к—
0110101^_, 110101101 01101011^ 110101101^, 01101011 ^llOiUllü,
А—8 А—8 А—9 А—8 А—
01101011ч^-_, ÎIOIOIIOI^-^, OllOlOll,^ 110101101^, 01101011ч_^_, 0101101,
к—9 к—8 к-9 к—8 к-
110101101 0101101101 ■■■ 01101011011 ■■■ 110101101101 •■■0110101101 ■••01011011,
jç g_________fc_______A— 12 A—11 A —
01101101^110101011^01101101^110101011^01101101^11010101.
A—9 A—8 A—9 A—8 A—
01101101^110101011 ^01101101^ 110101011^01101101^0101011,
k-9 k-8 fc-9 k—8 k-
11011011^-^ 010101101 ^-^OllOllOllO ^-^110101011011 ^OllOllOllOl ^,01010110,
k-8 k—10 k —11 к-ll k—
110110101 ^01101101 ^110110101 ^01101101^ 110110101 0110110,
A—8 A—9 A—8 A—9 A—-
0110101 -■• 01101101 s—,110110101 ^-^OllOllOl^-^llOllOlOl^, 01101101,
k-8 k-9 k-8 k-9 k-
01101011^0110110101 , 110110101101^01101101011 ^,0110101101 11011010,
k-9 fc—11 k-n fc-10 k—
011010101ч_-_,0110110110ч-^110110101011ч_^01101101101ч_^011010101^ 11011011,
k —10 fc—11 k—11 k—10 k—
01101101,^ 110110101 01101101 110110101^, 01101101 ^-^11011010.
k-9 k-8 k-9 k-8 k-
01101101^110110101^01101101^110110101^01101101^0110101,
k-9 k-8 k-9 k-8 fc-
110110101^0110101101^01101101011^110110101101^0110110101^,01101011,
A—9 A— П A —12 A—11 A —
11011011^,011010101 ^_,0110110110^^ll0110101011 ^01101101101 ^,01101010,
fc-S k—10 fc—11 k—11 k—
0110101 ••• 0101101 ■■■ 0110101^0101101 ■•• 0110101 •■• 0101101,
A—7 A—7 A—7 A—7 A—
0101101 .^OllOlOl.^OlOllOl ^0110101 s_^,0101101 ^0110101,
A—7 A—7 A—7 A—7 A—