«ПОСТРОЕНИЕ ЭКСТРЕМАЛЬНЫХ БЕСПОВТОРНЫХ СЛОВ И ОЦЕНКА ИХ КОЛИЧЕСТВА ...»

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

Уральский федеральный университет

имени первого Президента России Б.Н. Ельцина

На правах рукописи

Горбунова Ирина Анатольевна

ПОСТРОЕНИЕ ЭКСТРЕМАЛЬНЫХ БЕСПОВТОРНЫХ СЛОВ

И ОЦЕНКА ИХ КОЛИЧЕСТВА

01.01.09 – Дискретная математика и математическая кибернетика Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

профессор, доктор физ.-мат. наук А.М. Шур Екатеринбург Оглавление Введение Предварительные сведения............................ Обзор исследований по теме диссертации................... Обзор диссертации................................ Глава 1. Граничные слова 1.1. Структура граничных слов......................... 1.1.1. Кодировка Пансьё.......................... 1.1.2. Цилиндрическое представление.................. 1.1.3. Равномерные m-повторы...................... 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. Случай m=3............................. 1.2.4. Индекс роста двумерного языка.................. 1.2.5. Автоматы Ak и B k

1.2.6. Свойства автоматов Ak и Bk.................... 1.2.7. Связь между индексами роста граничных языков и языка D.. Глава 2. Циклические слова 2.1. Нижняя оценка для циклической границы повторяемости....... 2.2. Верхние оценки для циклической границы повторяемости....... 2.2.1. Случай k = 4............................ 2.2.2. Случай k = 5............................ 2.2.3. Случай k = 6............................ 2.2.4. Случай k = 7............................ 2.2.5. Случай k = 9............................ 2.2.6. Случай нечетных k 11...................... 2.3. Аналог гипотезы Дежан для циклических слов............. Литература Приложение А Введение Изучение свойств символьных последовательностей (слов) и множеств таких последовательностей (формальных языков) составляет важное направление в современной дискретной математике, имеющее обширные приложения в различных разделах математики, компьютерных науках, биологии и других областях знания. Интерес к символьным последовательностям у математиков появился более ста лет назад. Тому были как «внутренние» причины (становление теории групп), так и «внешние», например, активное использование двоичного кода (азбука Морзе) для передачи сообщений посредством телеграфа и радио. Первым математиком, систематически изучавшим свойства символьных последовательностей, был норвежец А.Туэ, которого по праву считают основоположником комбинаторики слов.

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

(ма) =мама.

алфавитом, которое не содержало повторов степени больше 7/4 [17].

Инфимум множества избегаемых экспонент для k-буквенного алфавита называется границей повторяемости и обозначается RT(k). Так, из работ Туэ следует, что RT(2) = 2. Дежан доказала, что RT(3) = 7/4, и высказала гипотезу о том, какие значения принимает RT(k) для k 4 (см. Граничную теорему на стр. 11). Слова над k-буквенным алфавитом, не содержащие повторов с экспонентой больше RT(k), являются экстремальными бесповторными словами, они избегают любую экспоненту, избегаемую над данным алфавитом. Такие слова представляют наибольший интерес в классе бесповторных слов и требуют к себе особого внимания.

Предварительные сведения В данном разделе приводятся основные определения комбинаторики слов, которые используются в последующих главах. Для более полной информации можно использовать, например, [7, 13, 28].

Слова Под алфавитом понимается непустое конечное множество, элементы которого называются буквами или символами. Через k будем обозначать произвольный kбуквенный алфавит.

Слово w – это конечная последовательность букв, т.е. w = a1 a2 · · · an, где a1, a2,..., an, а n = |w| – длина слова w. На слово w также можно смотреть как на функцию w : {1,..., n}. Числа из области определения этой функции называются позициями. Через w[i], где 1 i |w|, будем обозначать букву, стоящую на i-ой позиции в слове w. Слово длины 0 называется пустым и обозначается. Через (w) будем обозначать множество различных букв, входящих в слово w. Через (+, n ) обозначается множество всех слов (соответственно, всех непустых слов, всех слов длины n) над фиксированным алфавитом.

Слово u называется подсловом (соответственно, префиксом или суффиксом) слова w, если w можно представить в виде v u (соответственно, u, v u) для некоторых (возможно пустых) слов v и v. Подслово (соответственно, префикс, суффикс) слова w называется собственным, если оно не совпадает с w. Для обозначения подслова слова w, начинающегося с i-ой позиции и заканчивающегося в j-ой позиции, будем использовать обозначение w[i..j]. Реверсом слова w = a1 a2 · · · an будем называть слово = a · · · a a.

Два слова w1 и w2 называются сопряженными, если найдутся такие непустые слова u и v, что w1 = uv и w2 = vu (иначе говоря, слова w1 и w2 получаются друг из друга циклическими сдвигами на определенное число позиций).

Периодом слова w называется любой период соответствующей функции. Минимальный период слова w будем обозначать per(w). Экспонентой слова w называется отношение длины слова к его минимальному периоду: exp(w) = |w|/ per(w). На экспоненту можно смотреть как на рациональный показатель степени. Например, слово w = abcdabc имеет период 4 и exp(w) = 7/4, т.е. w = (abcd)7/4.

Помимо «обычных» мы будем использовать и другие виды слов.

-слово w – это бесконечное вправо слово, на которое можно смотреть как на функцию w : N. Z-слово w – это бесконечное в обе стороны слово, т.е.

w : Z. Конечные подслова -слов и Z-слов являются «обычными» словами, следовательно, к ним применимы данные выше определения. Через (соответственно, Z ) обозначается множество всех -слов (соответственно, всех Z-слов) над фиксированным алфавитом.

Один из простейших способов построения бесконечных слов – это метод итерации морфизма. Морфизмом называется отображение :, где и – произвольные алфавиты, такое, что u, v выполнено условие (uv) = (u)(v).

Легко заметить, что любой морфизм однозначно определяется образами символов алфавита. При этом, если длина каждого образа строго положительна, то морфизм называется нестирающим. Пусть a, : – нестирающий морфизм и n N0 n (a) является собственным префиксом n+1 (a). Тогда можно определить предел последовательности n (a) как -слово w, у которого префикс длины | (a)| совпадает с (a) для любого n N0. В этом случае говорят, что -слово w получено итерацией морфизма. Полученное -слово w удовлетворяет равенству (w ) = w, поэтому его называют также неподвижной точкой морфизма.

Циклическое слово (w) получается, если у «обычного» слова w «склеить» начало и конец, т.е. на множестве позиций задать не линейный, а циклический порядок:

Циклическое слово (w) можно также ассоциировать с классом сопряженности (легко проверить, что сопряженность является отношением эквивалентности), в котором содержится слово w. Подсловами циклического слова (w) являются слово w и все его циклические сдвиги со всеми своими подсловами. Таким образом, подслова циклических слов – это «обычные» слова, длина которых не превосходит |(w)| = |w|.

Двумерное слово W размера nq – это прямоугольная таблица размера nq из символов алфавита :

Подслова двумерного слова также являются двумерными словами (т.е. допускаются только «прямоугольные» подслова). В отличие от рассматриваемой в [21] модели двумерных слов, мы не будем использовать дополнительный символ для выделения границы двумерного слова. Через обозначается множество всех двумерных слов над фиксированным алфавитом.

Граница повторяемости Пусть > 1 – действительное число. Слово w -слово w, Z-слово w, циклическое слово (w) называется -свободным (соответственно, + -свободным), если все его подслова имеют экспоненту меньше (соответственно, не больше ). Например, слово w = abcdabc является (7/4)+ -свободным, но не 7/4-свободным (так как exp(w) = 7/4), а слово u = ababc является 3-свободным и даже 2+ -свободным, но не 2-свободным (так как содержит подслово abab с экспонентой 2).

Экспонента называется избегаемой над алфавитом k, если существует бесконечно много -свободных слов над алфавитом k. В противном случае экспонента называется неизбежной над k. Границей повторяемости RT(k) называется действительное число, отделяющее избегаемые экспоненты над алфавитом k от неизбежных:

Легко проверить, что сама экспонента RT(k) неизбежна над k, т.е. в алфавите k есть бесконечно много RT(k)+ -свободных слов, но лишь конечное множество RT(k)свободных.

Границу повторяемости можно определить несколькими эквивалентными способами, заменив в формуле (1) условие « – избегаемая экспонента над k » на одно из следующих условий:

(W) существует бесконечно много -свободных слов над алфавитом k ;

(I) существуют -свободные слова над алфавитом k любой достаточно большой (S) существуют -свободные слова над алфавитом k любой длины.

Однако при замене «обычных» слов на циклические эти три условия становятся попарно неэквивалентными, и соответствующие определения приобретают разный смысл. Действительно, если у нас есть -свободное слово w над алфавитом k, то и любое его подслово является -свободным. Но если взять циклическое -свободное слово (w), то любое его подслово является -свободным словом, но не -свободным циклическим словом. Так слово (abcdacb) – циклическое (3/2)+ -свободное слово, bcdacb – его (3/2)+ -свободное подслово, однако (bcdacb) не является циклическим (3/2)+ -свободным словом, так как содержит подслово bb с экспонентой 2. Поэтому при определении границы повторяемости для циклических слов мы получим три ее разновидности: слабую CRTW (k), среднюю CRTI (k) и сильную CRTS (k), соответственно.

В нашей работе исследуется только сильная граница повторяемости для циклических слов, поэтому будем называть ее просто циклической границей повторяемости и обозначать CRT(k).

RT(k)+ -свободные слова и CRT(k)+ -свободные циклические слова являются «экстремальными» бесповторными словами и представляют особый интерес среди слов, избегающих повторы. RT(k)+ -свободные слова [RT(k)+ -свободные Z-слова] будем называть граничными.

Языки, антисловари, автоматы Любое подмножество ( ) называется языком (соответственно, двумерным языком) над алфавитом. Язык (двумерный язык) называется факториальным, если он замкнут относительно взятия подслов, т.е. вместе с любым словом содержит все его подслова, и антифакториальным, если никакое его слово не является подсловом другого слова.

Языки, состоящие из всех -свободных ( + -свободных) слов, будем называть свободными ( + -свободными) языками над данным алфавитом или языками ограниченной экспоненты. Заметим, что такие языки являются факториальными. RT(k)+ свободные языки будем называть граничными и обозначать Tk.

Слово w (двумерное слово W ) запрещено в языке (соответственно, в двумерном языке) L, если оно не является подсловом ни одного элемента L (иначе говорят, что язык L избегает слово w). Множество всех минимальных в отношении подсловного порядка запрещенных слов для языка (двумерного языка) L называется антисловарем языка L. Антисловарь всегда является антифакториальным языком. Антисловарь граничного языка Tk будем обозначать через Ak.

Конечным автоматом называется пятерка объектов A = (Q,,, S, T ), где Q конечное множество состояний с подмножествами начальных состояний S и терминальных состояний T, - конечный алфавит, а Q Q - множество переходов.

Конечный автомат обычно рассматривается как помеченный орграф с множеством вершин Q и множеством помеченных дуг. Автомат A распознает слово w, если в нем для некоторых s S и t T существует ориентированный (s, t)-маршрут, помеченный w. Множество всех слов, распознаваемых автоматом A, образует язык L(A), распознаваемый этим автоматом. Языки, распознаваемые конечными автоматами, образуют в точности класс регулярных языков. Конечный автомат называется детерминированным, если в нем одно начальное состояние, и все переходы из любого фиксированного состояния имеют различные метки.

Факториальный язык является регулярным тогда и только тогда, когда регулярен его антисловарь. В частности, языки с конечным антисловарем образуют подкласс регулярных языков.

Бесконечные языки ограниченной экспоненты нерегулярны (в частности, антисловари Ak бесконечны). Действительно, достаточно длинные маршруты в автомате содержат циклы; заменив однократное прохождение цикла многократным, можно получить слово, распознаваемое автоматом, имеющее подслово сколь угодно большой экспоненты.

Минимальные запрещенные слова для граничного языка Tk при k 3 имеют вид u = ptp, где |pt| – это период слова u, а exp(u) = |u|/|pt| > RT(k), причем экспонента любого собственного подслова слова u не превосходит RT(k). Если |p| = m, то такое запрещенное слово u будем называть m-повтором. Например, слово abcdeab над алфавитом 5 является 2-повтором.

Через Ak будем обозначать подмножество в Ak, состоящее из всех r-повторов для любого r m. Заметим, что множество Ak является конечным для любого m граничного языка мы получим приближающую его последовательность регулярных Количественные характеристики языков Комбинаторной сложностью языка L называется функция CL (n), которая возвращает количество слов длины n в языке L. Комбинаторная сложность -слова или Z-слова есть комбинаторная сложность языка его подслов. Впервые комбинаторная сложность рассматривалась в [32]; с тех пор ее изучению было посвящено множество работ. О скорости роста комбинаторной сложности языка L можно судить по индексу роста, который задается формулой Если (L) > 1, то это свидетельствует об экспоненциальном росте функции CL (n), значение (L) = 1 говорит о «медленном» (субэкспоненциальном) росте комбинаторной сложности, а (L) = 0 означает, что язык L конечен. Так как комбинаторная сложность принимает целые значения, случай 0 < (L) < 1 очевидным образом невозможен.

Если язык L факториальный, то для его комбинаторной сложности выполняется неравенство CL (n1 +n2 ) CL (n1 )CL (n2 ) для любых n1, n2 N. А значит, можно воспользоваться следующей леммой, доказательство которой можно найти в [19, 53]:

Лемма Фекете. Пусть (an )n1 – последовательность действительных чисел такая, что для любых n1, n2 N выполнено неравенство an1 +n2 an1 +an2. Тогда предел ствование предела lim (следовательно, и lim (CL (n)) ). А значит, индекс роста факториального языка можно определить следующим образом:

Аналогичные понятия можно ввести и для двумерных языков (подробнее см. [26]).

Так, комбинаторную сложность двумерного языка L можно определить как функцию C(n, q), возвращающую количество слов размера nq в языке L. А индекс роста факториального двумерного языка – как двойной предел Аналогично одномерному случаю, существование предела (4) следует из многомерного аналога леммы Фекете, доказанного в [10].

Хорошо известно, что индекс роста любого регулярного языка можно вычислить с помощью детерминированного конечного автомата, распознающего этот язык. Автомат должен удовлетворять такому условию: любая вершина принадлежит некоторому маршруту из начальной вершины в терминальную. При этом условии, индекс роста языка является максимальным положительным корнем характеристического многочлена матрицы смежности этого автомата (этот результат, по-видимому, является фольклорным; короткое доказательство можно найти в [46]). Эффективный как с теоретической, так и с практической точки зрения алгоритм для нахождения индекса роста регулярных языков описан в [45, 47]. Стоит отметить, что распознающий автомат с требуемыми свойствами для языков с конечными антисловарями быстро строится по алгоритму [14]. К сожалению, для двумерных языков не известно эффективных алгоритмов вычисления или даже оценки сверху индекса роста.

Обзор исследований по теме диссертации Впервые понятие бесповторной символьной последовательности или бесповторного слова появилось в работах норвежского математика А.Туэ. В 1906 году он построил бесквадратное -слово над тернарным алфавитом [50]. А в 1912 году – бинарное слово, избегающее кубы и все дробные степени, большие 2 [51]. Бесконечные слова Туэ строил с помощью метода итерации морфизма. Так, в случае бинарного алфавита он использовал морфизм Морфизм имеет неподвижную точку w = (0) = 0110100110010110 · · · (или w = (1) = 1001011001101001 · · ·, если начинать с 1), которая и является 2+ свободным -словом.

К сожалению, обе работы Туэ были напечатаны в малоизвестном норвежском журнале, и не были известны специалистам до конца 1950-х годов. Поэтому многие из них были открыты и доказаны заново. Так, например, то же самое бинарное слово Морс построил в 1921 году [31], Эйве – в 1929 [18], Аршон – в 1937 [1] (на самом деле, еще в 1851 году в работе по теории чисел [37] Пруэ описал разбиение натурального ряда на два множества, неявно задававшее то же самое слово). Впоследствии -слово w получило название «слово Туэ-Морса».

Слово Туэ-Морса является граничным словом, в то время как все построенные Туэ бесквадратные слова над тернарным алфавитом граничными не являются. Это следует из результата Ф.Дежан 1972 года [17]. Дежан построила с помощью итерации морфизма тернарное (7/4)+ -свободное -слово и доказала, что никакое тернарное слово длины более 39 не является (7/4)-свободным, т.е. RT(3) = 7/4. В той же работе Дежан доказала нижнюю оценку для избегаемости экспонент в k-буквенных алфавитах при k 4 и предположила, что граница повторяемости совпадает с этой оценкой. Данное предположение получило название «гипотезы Дежан», а после завершения его доказательства – «граничной теоремы».

Граничная теорема (гипотеза Дежан; [11, 15–17, 30, 33, 36, 38, 51]). Экспонента избегаема над алфавитом k тогда и только тогда, когда > RT(k), где RT(k) принимает следующие значения:

Доказательство данной гипотезы заняло целых 37 лет (см. рис. 1). Ситуация осложнилась тем, что методом итерации морфизма (как это делали Туэ и Дежан) нельзя построить RT(k)+ -свободное -слово для k 4 (см. [9]). Решение нашел Пансьё. Он предложил идею бинарного кодирования граничных слов, о котором более подробно речь пойдет в пункте 1.1.1. Тем самым, он свел исходную задачу построения RT(k)+ -свободного -слова над k-буквенным алфавитом к построению кодового -слова над бинарным алфавитом, которое можно было получить методом итерации морфизма. Пансьё удалось построить подходящий бинарный морфизм для случая k = 4 [36].

Развивая идею Пансьё, Мулен-Оланье установил достаточные условия для того, чтобы слово, порожденное бинарным морфизмом, кодировало граничное слово. С помощью компьютера он подобрал бинарные морфизмы, удовлетворяющие найденным условиям, для 5 k 11 [33].

Мохаммад-Нури и Карри, также прибегнув к помощи компьютера, построили бинарные морфизмы для 12 k 14 [30]. Вместо проверки морфизмов по критерию Мулена-Оланье они использовали для генерации кодов граничных слов слова Штурма (-слово называется словом Штурма, если содержит ровно n + 1 различное подслово длины n для любого n N).

Прорыв в доказательстве совершил Карпи, ему удалось получить бескомпьютерное доказательство для k 33 [11]. Его метод включал в себя работу с некоторым вспомогательным алфавитом: сначала строилось -слово над вспомогательным алфавитом m, где m = (k3)/6, которое с помощью специального морфизма переводилось в бинарное кодовое -слово некоторого граничного слова над алфавитом k. Карпи удалось найти универсальную конструкцию для вспомогательных слов при Прибегнув к помощи компьютера, Карри и Рамперсад смогли построить вспомогательные слова из конструкции Карпи для m = 4, покрыв тем самым случаи 27 k 32 [15]. А несколько модернизировав конструкцию Мулена-Оланье, Карри и Рамперсад смогли с помощью компьютера подобрать бинарные морфизмы для оставшегося интервала 15 k 26 [16].

Примерно в то же время доказательство гипотезы завершил Рао [38], который искал кодовые бинарные слова в виде образов слова Туэ-Морса при подходящих морфизмах.

За долгие годы доказательства вокруг гипотезы Дежан возник целый круг «родственных» задач. Их можно условно разбить на четыре основные группы:

Опишем наиболее известные постановки задач и результаты для каждой из указанных групп.

I. В качестве усиления понятия границы повторяемости Бадкобех и Крошмор определили функцию FRT(k) = inf{R | существует + -свободное -слово над алфавитом k, которое содержит конечное число подслов с экспонентой RT(k)}, которая получила название «finite-repetition threshold». Из работы Кархумяки и Шаллита [23] известно, что если бинарное -слово является (7/3)-свободным, то оно содержит бесконечно много квадратов, а в работе [43] Шаллит построил бинарное (7/3)+ -свободное слово, содержащее всего 18 квадратов, откуда следует равенство FRT(2) = 7/3. Равенство FRT(3) = RT(3) доказано Бадкобех и Крошмором в работе [5], а в их совместной работе с Рао [6] были проанализированы -слова, полученные в доказательстве гипотезы Дежан при k 4 и установлено, что они удовлетворяют требуемому более сильному условию, т.е.

Все граничные языки бесконечны. Но насколько «большими» они могут быть?

Из [40] известно, что граничный язык над 2-буквенным алфавитом «небольшой», количество слов в нем с увеличением длины растет полиномиально. Для остальных алфавитов существует экспоненциальная гипотеза (происхождение которой считается фольклорным), согласно которой, начиная с 3-буквенного алфавита, граничные языки растут экспоненциально. Для k = 3, 4 экспоненциальную гипотезу доказал Ошем [35], для 5 k 10 – Колпаков и Рао [25].

Любое граничное слово длины больше k обязательно содержит подслова вида a1 a2 · · · ak1 a1. В работе [52] Туневым и Шуром для k 5 было введено понятие чистого граничного слова, т.е. граничного слова, все подслова которого с экспонентой RT(k) имеют вид a1 a2 · · · ak1 a1 ; тем самым, усиливается рассмотренное выше требование конечности числа подслов экспоненты RT(k).

Естественным образом возникает вопрос: конечно или бесконечно множество чистых граничных слов над алфавитом k ? Для 5-буквенного алфавита Бадкобех, Крошмор и Рао [6] доказали, что это множество бесконечно, построив граничное -слово, содержащее всего 60 подслов с экспонентой 5/4, период каждого из которых равен 4. Тунев и Шур для любого нечетного 7 k доказали более сильный результат [52]: множество всех чистых граничных слов над алфавитом k не только бесконечно, но и имеет экспоненциальный рост.

Как следствие, этот результат доказывает экспоненциальную гипотезу для любого нечетного 7 k 101.

II. Ограничения можно накладывать не только на экспоненту слов, но и на длину повторяющейся части. В [22] Илие, Ошем и Шаллит ввели понятие обобщенной границы повторяемости RT(k, l), которая учитывает только повторы с длиной повторяющейся части l. Если параметр l равен единице, то обобщенная граница повторяемости совпадает с обычной. На данный момент точных значений обобщенной границы повторяемости известно мало. Фиоренци, Ошем и Васле получили наилучшие верхние оценки для RT(k, l) [20], а Румянцев – наилучшие нижние оценки [41].

III. До этого момента мы считали, что «повторяющиеся» фрагменты слова должны полностью совпадать. Но можно рассматривать так называемые абелевы степени, когда повторяющиеся фрагменты являются анаграммами друг друга, т.е.

совпадают лишь набором (мультимножеством) входящих в них букв. Например, в слове «ротатор» фрагменты «рот» и «тор» равны в абелевом смысле, поэтому минимальный абелев период этого слова равен 4, а абелева экспонента – 7/4, хотя обычная – 7/6. Самсонов и Шур в [42] предложили абелев аналог гипотезы Дежан, согласно которому (сильная) абелева граница повторяемости ART(k) предположительно принимает следующие значения:

При этом в [42] доказано, что значения в таблице являются оценками снизу для ART(k).

Понятие t-абелевой степени служит промежуточным звеном между обычными и абелевыми степенями. Слово u1 u2 · · · un называется t-абелевой n-степенью, если в словах u1, u2, · · ·, un совпадает количество вхождений любых подслов длины t. Нетрудно заметить, что при t = 1 определение t-абелевой степени совпадает с целой абелевой степенью, а с ростом t становится все более похожим на обычную степень. Керянен доказал, что абелевы (а значит, и t-абелевы для любых t 1) квадраты избегаемы над 4-буквенным алфавитом [24]; над 3-буквенным алфавитом неизбежны 2-абелевы квадраты и есть гипотеза о том, что 3-абелевы квадраты избегаемы [27]; над бинарным алфавитом избегаемы 3-абелевы кубы [29] и предполагается избегаемость 2-абелевых кубов (в то же время абелевы кубы неизбежны, см. выше про ART(k)).

IV. Повторы можно искать не только в «обычных» словах, но и в циклических, у которых склеены начало и конец. Тогда, оставив прежнее определение повтора, можно получить аналог границы повторяемости для циклических слов (точнее целых три аналога: для слабой, средней и сильной циклической границы повторяемости). Значения всех трех видов циклической границы повторяемости для бинарного алфавита установили Аберкане и Карри [3, 4], а для тернарного алфавита – Шур [48]:

Кроме того, для слабой и средней циклической границы повторяемости Карри выдвинул гипотезу, что, начиная с 3-буквенного алфавита, их значения совпадают с «обычной» границей повторяемости, т.е. CRTW (k) = CRTI (k) = RT(k) Обзор диссертации Объект исследования и цели диссертации Объектом исследования являются экстремальные бесповторные слова. Причем помимо «обычных» слов, на позициях которых задан линейный порядок, рассматриваются также циклические слова. В качестве вспомогательных объектов возникают двумерные слова, а также цилиндрические слова, имеющие как линейную, так и двумерную структуру.

Основной целью является развитие теории бесповторных слов в двух основных направлениях: структурный и количественный анализ экстремальных бесповторных слов и нахождение границы повторяемости для циклических слов.

Основные проблемы, рассматриваемые в диссертации:

1. Описать строение экстремальных бесповторных слов и выявить структурные закономерности, общие для всех алфавитов.

2. Оценить количество экстремальных бесповторных слов заданной длины.

3. Найти значение циклической границы повторяемости.

Основные методы Для доказательства результатов, представленных в диссертации, в основном используются методы комбинаторики слов, основанные на свойствах периодических слов, кодировании, циклических и двумерных словах. Также используется метод регулярных приближений и комбинаторные алгоритмы для вычисления индекса роста регулярных языков (модификации А.М. Шура). Практически все численные результаты получены с помощью компьютера.

Структура диссертации и основные результаты Диссертация состоит из введения, двух глав, списка литературы и приложения. Общий объем диссертации составляет 107 страниц. Библиографический список содержит 60 наименований.

Во введении определяются основные используемые понятия, а также приводится краткий обзор исследований в области бесповторных последовательностей.

Первая глава посвящена «обычным» экстремальным бесповторным словам и состоит из двух разделов. В первом разделе приводятся два способа кодирования граничных слов: бинарное (Пансьё) и цилиндрическое (Шур), описание которых можно найти в пунктах 1.1.1 и 1.1.2, соответственно. Идея цилиндрического кодирования граничных слов оказалась весьма плодотворной и позволила выявить закономерности в строении граничных слов, общие для всех алфавитов. Основным результатом этого раздела является полное описание m-повторов для всех m 7 (см. теоремы 1.1,1.2,1.3 и 1.4). Описание m-повторов универсально для всех алфавитов, содержащих не менее 2m 2 букв и представляет из себя конечный список Qm двумерных слов, каждое из которых является «маркером» цилиндрического представления mповтора. Отсутствие таких маркеров является необходимым условием того, что слово является граничным.

Во втором разделе найденные множества Qm используются для построения регулярных приближений граничных языков и получения верхних оценок для их индексов роста (см. таблицу 1.1). Основываясь на результатах вычислительных экспериментов, нами было сделано предположение, что равномерные m-повторы не только одинаково устроены для всех алфавитов, но и привносят практически одинаковый вклад в индексы роста граничных языков над различными алфавитами. Таким образом, была сформулирована гипотеза о существовании пределов lim (Tk ) = (m) для любого m 3 (см. гипотезу 1.1). Стоит отметить, что в случае m = 2 последовательность В ключевом с точки зрения оценки индексов роста граничных языков случае m = удалось доказать не только существование данного предела ((3) 1.242096777), но и то, что он совпадает с индексом роста двумерного языка, заданного множеством запрещенных подслов Q3, полученным в первом разделе для цилиндрических представлений. Соответствующий результат (теорема 1.6) является основным в данном разделе и позволяет усилить гипотезу 1.1 (см. замечание 1.15). Кроме того, сравнивая вклад 3-, 6- и 7-повторов, можно предположить, что с ростом m влияние m-повторов на индекс роста граничных языков убывает. Следовательно, можно сформулировать гипотезу, что индексы роста граничных языков мало отличаются от индексов роста уже исследованных приближений, т.е. lim (Tk ) = 1.242 (см. гипотезу 1.2).

Вторая глава посвящена циклическим экстремальным бесповторным словам. Получен и практически полностью доказан аналог гипотезы Дежан для циклических слов (см. гипотезу 2.1). Нижняя оценка для циклической границы повторяемости получена для любого k 4 (см. предложение 2.1). Для получения верхних оценок была предложена общая конструкция бесповторных циклических слов, корректность которой обеспечивается граничной теоремой. Детали реализации данной конструкции существенно различаются для разных алфавитов, поэтому пришлось отдельно рассмотреть случаи k = 4, 5, 6, 7, 9 и нечетные k 11 (см. теоремы 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, соответственно). В результате было доказано, что CRT(k) = для любого k 6, а также установлено, что 3/2 CRT(4) 7/4 и 4/3 CRT(5) 3/2 (гипотеза 2. утверждает, что в обоих случаях точной является нижняя оценка).

Апробация результатов работы Результаты диссертации были представлены на 12-й международной конференции по теоретическим компьютерным наукам (Монс, 2008), 8-й международной конференции по комбинаторике слов (Прага, 2011), втором российско-финском симпозиуме по дискретной математике (Турку, 2012), а также на семинарах «Алгебраические системы» и «Дискретная математика» (УрГУ/УрФУ, 2008-2012).

Ссылки на результаты диссертации присутствуют в работах других авторов: [6, 8, 16, 25, 34].

Публикации Основные результаты диссертации опубликованы в работах [54–60], среди которых три работы [56, 58, 60] опубликованы в рецензируемых изданиях из списка, рекомендованного ВАК. В совместных работах [59, 60] А.М. Шуром было введено цилиндрическое кодирование и доказан ряд общих свойств цилиндрических представлений граничных слов, а автором было получено описание структуры цилиндрических представлений равномерных m-повторов для 3 m 6 и выполнена экспериментальная часть. В совместных работах [57, 58] А.М. Шуру принадлежат постановки задач, а также усовершенствование ряда предложенных автором доказательств и вспомогательных конструкций; доказательство основных результатов принадлежит автору.

Глава Граничные слова В данной главе речь будет идти о RT(k)+ -свободных словах над алфавитом k, где k 5. Случаи k = 3, k = 4 выбиваются из общей формулы RT(k) = k/(k1), и структура граничных слов для них во многом специфична и нехарактерна для больших алфавитов. Поэтому мы исключили их из рассмотрения. Что касается случая k = 2, то для него структура граничных слов хорошо изучена (см., в частности, [12, 40, 49]).

1.1. Структура граничных слов Целью данного раздела является поиск общих закономерностей в строении граничных слов над разными алфавитами. Вполне естественно для решения этой задачи использовать некоторую кодировку граничных слов, которая позволит работать над одним алфавитом.

1.1.1. Кодировка Пансьё Пытаясь доказать гипотезу Дежан, Пансьё в [36] предложил идею бинарного кодирования (k1)/(k2)-свободных слов (граничные слова над любым алфавитом являются (k1)/(k2)-свободными). Конструкция, описанная Пансьё, основывается на том, что любое (k1)/(k2)-свободное слово над алфавитом k удовлетворяет двум условиям:

(1) в любом подслове длины k1 все буквы различны;

(2) двум соседним вхождениям одной буквы предшествуют разные символы.

Любое слово (Z-слово), удовлетворяющее условиям (1) и (2), будем называть словом Пансьё. Предположим, что в слове Пансьё w встречается символ a, котороk му предшествует цепочка a1... ak1. В силу (1) все буквы a1,..., ak1 различны, более того, в подслове a2... ak1 a также не должно быть повторяющихся символов. Значит возможны всего два варианта: либо a = a1, либо a = ak, где ak {a1,..., ak1 }.

Будем символ a кодировать нулем в первом случае и единицей во втором (кодировать начинаем с k-го символа в слове), тогда слову w можно поставить в соответствие характеристическое слово Bin(w) над бинарным алфавитом B = {0, 1}, построенное по следующему правилу:

Так, например, для некоторого w :

Отметим, что каждое характеристическое слово длины nk+1 определяет единственное с точностью до переименования букв слово длины n с заданными свойствами (таким образом, вместо k! слов над алфавитом k можно рассматривать одно слово над бинарным алфавитом).

Cформулируем ряд важных свойств слов Пансьё и их бинарных кодов.

Замечание 1.1. Множество всех слов Пансьё над алфавитом k совпадает с языком Tk. Действительно, условие (1) обеспечивает отсутствие 1-повторов, а условие (2) – отсутствие 2-повторов.

Замечание 1.2. Расстояние между двумя соседними вхождениями одной буквы в слове Пансьё w может принимать только три значения: k1, k и k+1. Действиk тельно, пусть a1 a2 · · · ak1 – подслово слова w. Найдем расстояние до следующего вхождения буквы a1. Для этого достаточно рассмотреть всевозможные варианты продолжения этого префикса без нарушения правил (1) и (2):

Замечание 1.3. Если w – слово Пансьё, то Bin(w) не содержит подслов 00 и 111.

Действительно, предположим, что это не так. Тогда получим противоречие со свойством (2):

Замечание 1.4. Непосредственно из замечания 1.3 следует, что любое характеристическое слово разбивается на блоки 1 и 01 (с возможно нецелыми блоками в начале и/или конце слова), причем блок 1 может появляться только в окружении блоков 01.

Таким образом, при переходе к характеристическим словам нам сразу удалось найти нечто общее между граничными словами над разными алфавитами (см. замечания 1.3 и 1.4). А именно: для множества бинарных кодов слов языка Tk антисловарем является множество {00, 111} независимо от значения k. Все прочие структурные закономерности непосредственно зависят от мощности исходного алфавита, что заставляет нас продолжить поиски более подходящего способа кодирования граничных слов.

1.1.2. Цилиндрическое представление Начиная с этого пункта и до конца раздела, речь будет идти о Z-словах Пансьё.

Продолжая идею кодирования, можно рассмотреть графическое представление слов Пансьё, которое было предложено А.М. Шуром и впервые описано в работе [59].

Представим, что у нас есть некоторый бесконечный цилиндр, а слово – это нить с нанизанными на неё буквами. Тогда слово можно «наматывать» на цилиндр так, чтобы количество букв в одном витке равнялось мощности алфавита k (см. рис. 1.1 a) ). Теперь соединим одинаковые символы в соседних витках отрезками. По замечанию 1. соседние вхождения одного символа можно соединить тремя способами (считаем, что отрезок идет от нижней буквы к верхней): (буква осталась на той же позиции), (сместилась на одну позицию вправо) и (сместилась на одну позицию влево) (см. рис. 1.1 b) ), которые эквивалентны расстояниям k, k1 и k+1, соответственно.

a) Наматываем слово на цилиндр (k = 9) b) Соединяем одинаковые буквы Полученное графическое изображение из отрезков будем называть цилиндрическим представлением слова w и обозначать через Cyl(w). «Траекторию» движения каждой буквы в цилиндрическом представлении будем называть её следом. Таким образом, след буквы – это ломаная, составленная из отрезков, соответствующих перемещениям буквы между витками. Если говорить о следе буквы в цилиндрическом представлении некоторого подслова u слова w, то это будет ломаная, начинающаяся в первом вхождении данной буквы в u и заканчивающаяся в последнем. Например, след буквы a в подслове abcde · · · bcade Z-слова Пансьё, изображенном на рис. 1.1, Перечислим ряд свойств цилиндрических представлений слов Пансьё.

Замечание 1.5. Пусть w – Z-слово Пансьё, тогда двум соседним буквам в w могут соответствовать только следующие пары отрезков в Cyl(w):,, и (2), а в остальных случаях происходит «наложение» букв (разные буквы переходят на одно и то же место). Следовательно, цилиндрическое слово Z-слова Пансьё является комбинацией палочек и крестиков, причем палочка может появляться только в окружении крестиков (т.е. на самом деле можно говорить о блоках Замечание 1.6. Легко заметить соответствие между блоком 1 в характеристическом слове и блоком в цилиндрическом представлении, а также между блоками 01 и. Действительно 0 в характеристическом слове говорит о том, что предыдущее вхождение соответствующей буквы находится на расстоянии k1 от данного, а значит согласно замечанию 1.5 в цилиндрическом представлении эта буква будет. Появление 1 после 0 говорит о том, что между двумя вхождениязакодирована ми соответствующей ей буквы находится подслово ограниченное двумя вхождениями буквы, соответствующей 0, т.е. расстояние будет равно k+1, а в цилиндрическом коИ наконец, 1, идущая после 1, эквивалентна появлению буквы на де получим расстоянии k от предыдущего ее вхождения, что дает нам в цилиндрическом представлении.

Таким образом, если для некоторого Z-слова Пансьё w мы «размотаем» его цилиндрическое представление Cyl(w) и вытянем его в одну линию, то получим в точности перекодированное (согласно найденному в замечании 1.6 соответствию) характеристическое слово Bin(w). Например, для некоторого фрагмента Z-слова Пансьё w над алфавитом 5 :

Для множества цилиндрических представлений (как и для множества характеристических слов) слов Пансьё выполняются общие закономерности, которые выражаются в одном и том же не зависящем от k множестве запрещенных объектов (следует из замечания 1.5). Однако за счет двумерной структуры цилиндрическое представление позволяет выявить и другие общие закономерности, о чем будет изложено далее.

1.1.3. Равномерные m-повторы Среди m-повторов можно выделить два класса: короткие (m < k) и длинные или ядерные (m k) (такое разделение было впервые введено в [33]). Подробнее о длинных повторах можно найти в [11, 33], далее речь пойдет только о коротких повторах.

Пусть ptp – короткий m-повтор, тогда все буквы в слове p различны в силу условия (1). Более того, за счет выполнения условия m < k слово p всегда целиком укладывается в один виток на цилиндре. Короткий m-повтор ptp называется равномерным, если каждая буква a (p) встречается в ptp одинаковое число раз. Следующие четыре свойства m-повторов будут весьма полезны в дальнейшем (их доказательство принадлежит А.М. Шуру и может быть найдено в [59, 60]).

Лемма 1.1. Пусть ptp – m-повтор такой, что m < (k+3)/2. Тогда данный повтор является равномерным, а именно, каждая буква a (p) входит в слово ptp ровно m раз.

Лемма 1.2. Пусть ptp – равномерный m-повтор. Тогда каждая буква a входит в слово pt ровно m1 раз.

Следствие 1.1. Если ptp – равномерный m-повтор, то при наматывании слова ptp на цилиндр оба вхождения слова p окажутся одно под другим, причем длина следа (т.е. количество отрезков в нем) любой буквы a (p) будет равна m1, а количество отрезков и в нем одинаково.

Утверждение следствия 1.1 можно обратить, получая следующее предложение:

Предложение 1.1. Пусть m 3 – фиксированное число. Тогда для любого натуральm) имеют идентичное описание на языке цилиндрических представлений. А именно существует конечное множество Qm фрагментов размера O(m)O(m) такое, что слово является подсловом Z-слова Пансьё wk тогда и только тогда, когда его цилиндрическое представление не содержит фрагментов из Qm.

Действительно, если из цилиндрического представления равномерного m-повтора ptp «вырезать» фрагмент размера O(m)O(m), ограниченный сверху и снизу словом p, то независимо от мощности исходного алфавита он должен состоять из m следов длины m1, которые начинаются и заканчиваются в одинаковых позициях. Так, задача построения цилидрического представления 3-повтора (а из леммы 1.1 следует, что все они равномерны при любом k 5) сводится к нахождению подходящих следов длины 2, которые бы соединили буквы a, b и c в верхнем и нижнем ряду на рис. 1.2.

Чтобы буква через два шага вернулась на ту же позицию, ее след должен иметь один из трех видов:,,. на рис. 1.3 показаны всевозможные комбинации этих следов, не противоречащие замечанию 1.5.

Рис. 1.3. 3-повторы. Пунктиром показаны следы соседних букв, которые однозначно достраиваются по имеющимся следам.

Таким образом, основными целями наших исследований в данном направлении являются:

нахождение множеств Qm для малых значений m;

поиск закономерностей в структуре множеств Qm для различных значений m, если таковые имеются;

использование найденных множеств Qm для получения численных оценок для индексов роста соответствующих граничных языков.

1.1.4. 3-повторы Описание множества Q3 можно легко получить, исходя из представленных на рис. 1. фрагментов.

Теорема 1.1. Для Z-слова Пансьё w Z cледующие условия эквивалентны:

1) w содержит 3-повтор;

3) характеристическое слово Bin(w) содержит подслова вида 1101 · · · 1011 или 0101 · · · 1010 (для k = 5 первое слово имеет вид 1101011).

Доказательство. 1) 2). Пусть 3-повтор u = abc · · · abc является подсловом в w. Тогда Cyl(w) содержит один из фрагментов, изображенных на рис. 1.3. Так как Cyl(w) является Z-словом, то u имеет продолжение в w как влево, так и вправо. Тогда следы букв a, b и c могут быть однозначно дополнены следами соседних букв, которые показаны на рис. 1.3 пунктиром. В каждом случае Cyl(w) обязательно содержит или 2) 1). Заметим, что если в w встречается фрагмент, то слева и справа от него обязательно находятся столбики из крестиков (см. замечание 1.5). Значит мы всегда можем найти три буквы, без ограничения общности a, b и c, которые конструкциями возвращаются на свои места. Это означает, что w содержит подслово u вида abc · · · abc, которое по определению является 3-повтором.

2) 3). Согласно замечанию 1.6 появление в Cyl(w) означает, что бинарное представление некоторого подслова из w имеет вид 11 · · · 11 1 (и наоборот, подслово 11 · · · 11 в Bin(w) соответствуют в цилиндрическом представлении). По замечаk нию 1.4 в бинарном коде слова Пансьё перед 11 всегда стоит 10, а после – 01. В результате получаем требуемое подслово 1101 · · · 1011. Аналогично, появление в Cyl(w) эквивалентно 0101 · · · 0101 в Bin(w). А так как перед 0 может быть только 1, то получаем слово 0101 · · · 10101, которое содержит искомое подслово.

1.1.5. 4- и 5-повторы Следующая лемма будет неоднократно использоваться в доказательстве последующих результатов.

Лемма 1.3. Пусть ptp – равномерный m-повтор; a (p). Тогда след любой буквы b = a пересекает след буквы a четное число раз.

Еще одна единица нужна, чтобы подчеркнуть, что перед нами блок 1, а не часть блока 01.

Доказательство. Предположим обратное. Если первое и последнее вхождения буквы a занимают позиции i и i+(m1)k, а буквы b, соответственно, позиции j1 и j2 +(m1)k, где j1 < i < j2 или j2 < i < j1, то несложно заметить, что b не может принадлежать p (после переходов b оказывается по другую сторону от a, а в слове p порядок букв сохраняется). Тогда |p| < |j2 j1 |, но |j2 j1 | m1, так как буква b встречается в ptp ровно m1 раз по лемме 1.2 и каждый раз может смещаться влево или вправо не более чем на 1. Получаем |p| < m, что противоречит определению m-повтора.

Замечание 1.7. Пусть след S длины m1 подходит для равномерного m-повтора, т.е. входит в состав фрагмента Q Qm включающего m следов длины m1, возвращающих буквы на те же позиции. Тогда следы, симметричные S относительно вертикальной или горизонтальной оси, также подходят для равномерных m-повторов.

Действительно, они будут входить в состав фрагментов, симметричных Q относительно вертикальной или горизонтальной оси, соответственно.

Теперь перейдем к основному результату данного пункта.

Теорема 1.2. Не существует равномерных 4- и 5-повторов.

Доказательство. Предположим, что существует равномерный 4-повтор ptp. Тогда для следа буквы a (p) есть всего два варианта с точностью до симметрии, которые изображены на рис. 1.4 (выделены жирными линиями). Но в случае a) след пересекает соседние следы всего по одному разу (см. рис. 1.4 a) ), что по лемме 1. невозможно. А в случае b) соседний справа след однозначно достраивается до симметричного, но вот следующий за ним не возвращает букву на место (нельзя соединить точки b3 и c3 на рис. 1.4 b) ). Следовательно, слева достроить след также не получится (нельзя попасть из точки b1 в точку c1 ). Таким образом не удалось найти подходящие следы для 4 последовательных букв в слове p, что доказывает отсутствие равномерных 4-повторов.

Теперь предположим, что существует равномерный 5-повтор ptp. Возможные с точностью до симметрии варианты следа буквы a (p) представлены на рис. 1. (выделены жирными линиями). В случаях a) и b) след пересекает соседние нечетное число раз, что невозможно по лемме 1.3. В случае c) соседний слева след однозначно достраивается до симметричного, а справа достроить не удается (нельзя попасть из точки b1 в точку c1, см. рис. 1.5 c) ). Значит в силу симметрии левая сторона также не может быть дальше достроена. В остальных случаях требуется соединить точки b1 и c1 ; b2 и c2 (см. рис. 1.5 d),e) ), но тогда появятся конструкции или, которые по теореме 1.1 эквивалентны наличию 3-повтора в слове ptp, что противоречит определению 5-повтора.

1.1.6. 6-повторы Лемма 1.4. Пусть ptp – равномерный 6-повтор. Тогда обязательно найдется буква a (p), след которой в цилиндрическом представлении слова ptp начинается или Доказательство. В Cyl(ptp) 6 букв должны вернуться на свои места. Предположим, что все 6 следов начинаются и заканчиваются не на. Тогда имеет место один из случаев, изображенных на рис. 1.6.

Первый случай, когда каждый след начинается и заканчивается разными отрезками, невозможен, так как мы должны соединить точки b1, c1 ; b2, c2 ; b3, c3 ; b4, c4, а это приведет к появлению равномерного 4-повтора, что невозможно по теореме 1.2.

Теперь рассмотрим случай, когда каждый след начинается и заканчивается на одинаковые отрезки. Например, пусть след начинается и заканчивается на. Тогда по в следе равен, то это испортит соседние следы, так как в них окажется три одинаковых отрезка (следы букв b и c на рис. 1.6). Если же вторые символы всех следов не равны, то получим фрагмент теореме 1.1, что невозможно по условию.

На рис. 1.7 изображено 5 различных допустимых следов для равномерных 6повторов. Обозначим их 1, 2, 3, 4, 5, как показано на рисунке, а их зеркальные отражения относительно вертикальной оси обозначим, соответственно, 1, 2, 3, 4, 5.

Фрагмент, состоящий из нескольких идущих подряд следов, будем обозначать последовательностью номеров этих следов. Например, фрагмент на рис. 1.7 обозначается как 12345.

Теорема 1.3. Пусть k 10. Тогда слово Пансьё w Z, избегающее 3-повторы, содержит 6-повтор тогда и только тогда, когда Cyl(w) содержит один из фрагментов: 123451, 234512, 345123, 451234, 512345, 1 5 4 3 2 1, 2 1 5 4 3 2, Доказательство. По лемме 1.1, начиная с k = 10, все 6-повторы (а стало быть и все m-повторы с m < 6) над алфавитом k являются равномерными. Поскольку 6-повтор по определению является минимальным запрещенным словом, то условие отсутствия 3-повторов является излишним при доказательстве необходимости, однако оно играет ключевую роль при доказательстве достаточности. Равномерные 4- и 5-повторы в слове w отсутствуют по теореме 1.2.

(). Пусть a1 a2 a3 a4 a5 a6 · · · a1 a2 a3 a4 a5 a6 – равномерный 6-повтор. Все возможные следы (без учета симметричных и полученных циклическим сдвигом 2 ) букв a1, a2, a3, a4, a5, a6 представлены на рис. 1.8.

Согласно замечанию 1.7 можно не рассматривать следы, симметричные данным, а по лемме 1.4 можно не рассматривать циклические сдвиги следов a)c) (циклические сдвиги следа d) содержат фрагмент, соответствующий наличию 3-повтора, поэтому и так не участвуют в рассмотрении). В случае c) перед нами в точности след 1, всевозможные фрагменты, построенные с его помощью (включая симметричный ему след 1 ), перечислены во втором пункте условия теоремы. Проверим, что следы a), b) и d) нельзя достроить до нужного фрагмента.

В случае a) по лемме 1.3 необходимо соединить точки b1 и c1, но тогда появится что невозможно по условию. В случае b) получаем, что справа находится недопустимый для 6-повтора след. А слева достроить можно двумя способами, причем в каждом случае мы не можем попасть из точки b1 в c1, что также не дает возможность получения фрагмента, возвращающего 6 букв на те же позиции. След d) имеет по одному пересечению с соседними следами, что по лемме 1.3 недопустимо для 6-повтора.

Подразумевается, что на след можно смотреть как на вертикально записанное слово над алфавитом ={,, } (). Наличие перечисленных конструкций в цилиндрическом представлении слова w свидетельствует о наличие у него подслова u вида которое по определению является 6-повтором. Действительно, exp(u)=(5k+6)/(5k)> k/(k1) и оно не содержит других повторов меньшей длины, так как 1-, 2-, 3-повторы запрещены по условию, равномерные 4- и 5-повторы не существуют по теореме 1.2, а неравномерных 4- и 5-повторов над алфавитом k для k 10 нет по лемме 1.1.

Замечание 1.8. Аналогично случаю m = 3 можно получить описание характеристических слов 6-повторов, используя соответствие, найденное в замечании 1.6. Тогда Bin(w), где w из условия теоремы 1.3, содержит подслово одного из следующих видов (перечислены в том же порядке, что и их цилиндрические аналоги из пункта теоремы 1.3):

11010110 · · · 0110101 · · · 0101101 · · · 0110101 · · · 0101101, 0101101 · · · 01101011 · · · 01011010 · · · 110101101 · · · 011010, 0101101 · · · 01101011 · · · 01011010 · · · 110101101 · · · 0110101, 0110101 · · · 0101101 · · · 0110101 · · · 0101101 · · · 1101011, 0110101 · · · 0101101 · · · 1101011 · · · 10110101 · · · 010110, 1101011 · · · 0101101 · · · 0110101 · · · 10101101 · · · 011010, 0110101 · · · 110101101 · · · 010110101 · · · 01101011 · · · 0101101, 0110101 · · · 110101101 · · · 010110101 · · · 01101011 · · · 010110, 0101101 · · · 0110101 · · · 10101101 · · · 0110101 · · · 1101011, 0101101 · · · 011010 · · · 1101011 · · · 0101101 · · · 0110101.

1.1.7. 7-повторы Лемма 1.5. Пусть ptp – равномерный 7-повтор. Тогда обязательно найдется буква a (p), след которой в цилиндрическом представлении слова ptp либо начинается (заканчивается) на, либо начинается и заканчивается одинаковыми наклонными Доказательство. В Cyl(ptp) 7 букв должны вернуться на свои места. Предположим, что все 7 следов начинаются и заканчиваются не на. Тогда выполняется один из случаев, изображенных на рис. 1.10.

Первый случай, когда каждый след начинается и заканчивается разными отрезками, невозможен, так как мы должны соединить точки b1, c1 ; b2, c2 ; b3, c3 ; b4, c4 ; b5, c5, а это приведет к появлению равномерного 5-повтора, что невозможно по теореме 1.2.

Теперь рассмотрим случай, когда каждый след начинается и заканчивается на одинаковые наклонные отрезки. Предположим, что второй отрезок каждого из 7 следов не равен. Если второй отрезок в следе не совпадает с первым, то получим фрагмент (см. рис. 1.10 случай 2.1) ) в Cyl(ptp), а значит и 3-повтор в слове ptp по теореме 1.1, что невозможно поскольку 7-повтор по определению является минимальным запрещенным словом. Если же второй отрезок в следе совпадает с первым (а значит и с последним) и равен б.о.о., то по следствию 1.1 остальные три отрезка должны быть равны. И снова получим фрагмент что невозможно.

На рис. 1.11 показаны возможные варианты следов для равномерного 7-повтора, обозначенные 1, 2, 3, 4, а также симметричные им – 1, 2, 3, 4.

Теорема 1.4. Пусть k 12. Тогда слово Пансьё w Z, избегающее 3- и 6-повторы, содержит 7-повтор тогда и только тогда, когда Cyl(w) содержит один из фрагментов:

Доказательство. Отметим, что по лемме 1.1, начиная с k = 12, все 7-повторы (а стало быть и все m-повторы с m < 7) над алфавитом k являются равномерными.

(). Пусть a1 a2 a3 a4 a5 a6 a7 · · · a1 a2 a3 a4 a5 a6 a7 – равномерный 7-повтор. Возможные следы (без учета симметричных и полученных циклическим сдвигом) букв a1, a2, a3, a4, a5, a6, a7 представлены на рис. 1.12.

В силу замечания 1.7 можно не рассматривать симметричные случаи, а по лемме 1.5 достаточно рассмотреть только случаи d) o) и циклические сдвиги следов e) g), m), o), начинающиеся и заканчивающиеся одинаковыми наклонными отрезна втором (или предпоследнем) месте. Отметим, что f ) – это в точности ками с след 2, а его подходящий циклический сдвиг – след 3. Всевозможные фрагменты, подходящие для 7-повтора, с участием этих и симметричных им следов описаны в пункте 2 условия теоремы. Проверим, что остальные следы на эту роль не подходят.

Следы d), i), k), m), o) имеют нечетное число пересечений с соседними следами (см. рис. 1.13), поэтому не подходят по лемме 1.3.

Рассмотрим следы e) и g) (см. рис. 1.14). Соседний справа от них след единственным образом можно продолжить так, чтобы он имел четное число пересечений с исходным следом, но тогда он не возвращает букву на место (точки b3 и c3 нельзя соединить), а соседний слева след можно достроить двумя способами, но тогда соседний с ним след будет неправильным (точки b1 и c1 нельзя соединить).

В случаях h) и j) (см. рис. 1.15), соседние слева и справа следы являются неподходящими (не получается соединить точки b1 и c1 ; b3 и c3 ). Как и в случаях l) и n) (см. рис. 1.15), невозможно соединить точки b1 и c1 ; b2 и c2 так, чтобы не получить фрагмент соответствующий наличию 3-повтора в слове.

Все следы, начинающиеся на, разобраны. Теперь займемся следами, которые втором месте у них стоит. Таких следов всего два с точностью до симметрии (см.

рис. 1.16 случаи e ), f )). След f ) – это в точности след 3, являющийся циклическим сдвигом следа f, а след e ) – это с точностью до симметрии циклический сдвиг следов e), g), m) и o). Все возможные фрагменты с участием следа f ) перечислены в пункте 2 условия теоремы. А след e ) имеет нечетное число пересечений с соседними следами, поэтому не подходит по лемме 1.3.

(). Пусть в Cyl(w) встретился один из перечисленных фрагментов. Это эквивалентно тому, что слово w имеет подслово u вида которое по определению является 7-повтором. Действительно, exp(u)=(6k+7)/(6k)> k/(k1) и оно не содержит других повторов меньшей длины, так как 1-, 2-, 3- и 6-повторы запрещены по условию, равномерные 4- и 5-повторы не существуют по теореме 1.2, а неравномерных 4- и 5-повторов над алфавитом k для k 12 нет по лемме 1.1.

Замечание 1.9. Для слова w из условия теоремы 1.4 Bin(w) содержит подслово одного из следующих видов:

11011011 · · · 01101101 · · · 1101101101 · · · 011011011 · · · 1101101101 · · · 0110110, 01101101 · · · 011011011 · · · 1101101101 · · · 011011011 · · · 1101101101 · · · 01101101, 01101101 · · · 011011011 · · · 1101101101 · · · 011011011 · · · 01101101 · · · 11011011, 01101101 · · · 1101101101 · · · 011011011 · · · 1101101101 · · · 01101101 · · · 11011011, 01101101 · · · 1101101101 · · · 011011011 · · · 1101101101 · · · 011011011 · · · 0110110, 11011011 · · · 01101101 · · · 011011011 · · · 1101101101 · · · 011011011 · · · 01101101, 01101101 · · · 01011011 · · · 01101101 · · · 01011011 · · · 01101101 · · · 0101101, 0101101 · · · 01101101 · · · 01011011 · · · 01101101 · · · 01011011 · · · 0110110, 110101101 · · · 01101011 · · · 110101101 · · · 01101011 · · · 110101101 · · · 0110101, 0101101 · · · 01101011 · · · 110101101 · · · 01101011 · · · 110101101 · · · 01101011, 01011011 · · · 0110101101 · · · 110101101101 · · · 01101011011 · · · 0101101101 · · · 11010110, 11010101 · · · 01101101 · · · 110101011 · · · 01101101 · · · 110101011 · · · 0110110, 0101011 · · · 01101101 · · · 110101011 · · · 01101101 · · · 110101011 · · · 01101101, 010101101 · · · 0110110110 · · · 110101011011 · · · 01101101101 · · · 010101101 · · · 11011011, 0110101 · · · 110101101 · · · 01101011 · · · 110101101 · · · 01101011 · · · 11010110, 01101011 · · · 110101101 · · · 01101011 · · · 110101101 · · · 01101011 · · · 0101101, 110101101 · · · 0101101101 · · · 01101011011 · · · 110101101101 · · · 0110101101 · · · 01011011, 01101101 · · · 110101011 · · · 01101101 · · · 110101011 · · · 01101101 · · · 11010101, 01101101 · · · 110101011 · · · 01101101 · · · 110101011 · · · 01101101 · · · 0101011, 11011011 · · · 010101101 · · · 0110110110 · · · 110101011011 · · · 01101101101 · · · 01010110, 110110101 · · · 01101101 · · · 110110101 · · · 01101101 · · · 110110101 · · · 0110110, 0110101 · · · 01101101 · · · 110110101 · · · 01101101 · · · 110110101 · · · 01101101, 01101011 · · · 0110110101 · · · 110110101101 · · · 01101101011 · · · 0110101101 · · · 11011010, 011010101 · · · 0110110110 · · · 110110101011 · · · 01101101101 · · · 011010101 · · · 11011011, 01101101 · · · 110110101 · · · 01101101 · · · 110110101 · · · 01101101 · · · 11011010, 01101101 · · · 110110101 · · · 01101101 · · · 110110101 · · · 01101101 · · · 0110101, 110110101 · · · 0110101101 · · · 01101101011 · · · 110110101101 · · · 0110110101 · · · 01101011, 11011011 · · · 011010101 · · · 0110110110 · · · 110110101011 · · · 01101101101 · · · 01101010, 0110101 · · · 0101101 · · · 0110101 · · · 0101101 · · · 0110101 · · · 0101101, 0101101 · · · 0110101 · · · 0101101 · · · 0110101 · · · 0101101 · · · 0110101, 010110101 · · · 011010110 · · · 11010110101 · · · 0110101101 · · · 010110101 · · · 11010110, 010101101 · · · 011011010 · · · 11010101101 · · · 0110110101 · · · 010101101 · · · 11011010, 110101101 · · · 010110101 · · · 011010110 · · · 11010110101 · · · 0110101101 · · · 01011010, 110110101 · · · 010101101 · · · 011011010 · · · 11010101101 · · · 0110110101 · · · 01010110.

Полученное описание множеств Q3 –Q7 (см. теоремы 1.1, 1.2, 1.3 и 1.4) свидетельствует о том, что между строением множеств Qm для разных значений m не прослеживается никакой закономерности. Поэтому не представляется возможным предложить некую общую схему для их построения. К тому же с ростом m мощность множества Qm, а также сложность входящих в него структур, быстро возрастает, что делает нецелесообразным получение описания структуры m-повторов для m > 7.

Однако естественным образом возникает вопрос, как сказывается «одинаковость» в строении равномерных m-повторов на количественных характеристиках граничных языков.

1.2. Оценка количества граничных слов Как уже упоминалось ранее, для оценки количества слов длины n в языке L используется комбинаторная сложность CL (n). Но сама по себе эта величина не очень информативна. Лучше оценивать не количество слов, а скорость их прироста с увеличением длины, т.е. вычислять индекс роста (L). Но граничные языки не являются регулярными, поэтому для получения верхних оценок для их индексов роста мы будем использовать последовательность индексов роста языков Tk (подробнее о методе регулярных приближений см. в [44]).

1.2.1. Верхние оценки для индексов роста граничных языков Обозначим через Tk – множество всех подслов Z-слов wk Z, не содержаk совпадают. При переходе от слов к их бинарным кодам комбинаторная сложность уменьшается в k! раз, при этом индекс роста не изменится. Обозначим через Pk множество всех бинарных кодов слов языка T. Тогда справедливо следующее соk отношение между индексами роста описанных языков:

Получим верхние оценки для индексов роста граничных языков, используя стандартный алгоритм, который применяется не к самим граничным языкам, а к соответствующим бинарным языкам. Как происходит вычисление индекса роста для языков Pk продемонстрируем на примере m = 2. В этом случае для любого k антисловарь состоит из 2 слов {00, 111}. Построим автомат, распознающий язык Pk :

Как известно, количество слов длины n в языке равно количеству маршрутов длины n в распознающем этот язык автомате. Используя этот факт, легко вычислить значение индекса роста по автомату, распознающему данный язык (например, составив для числа путей рекуррентное соотношение C(n) = C(n2) + C(n3)). Так для m = 2 получаем, что для любого k 5 (Tk ) 1.324718.

полученное в теореме 1.1 и замечаниях 1.8 и 1.9 описание структуры характеристических слов запрещенных повторов в языках T (k 5), T (k 10) и T (k 12), соответственно (ограничения на k вытекают из леммы 1.1). Затем по алгоритму из работы [14] для каждого языка строим распознающий его автомат. А по автомату вычисляем индекс роста с любой наперед заданной степенью точности, используя алгоритм 1 из работы [47]. В таблице 1.1 приведены полученные значения Анализируя данные значения, можно сделать несколько выводов:

1. значения индексов роста языков Tk с ростом k быстро стабилизируются, что позволяет предположить существование предела lim (Tk ) и его примерное значение 1.242096777;

2. величина 36 = (Tk )(Tk ), описывающая вклад 6-повторов в индекс роста языка Tk, с ростом k стабилизируется в районе значения 4.3 · 105, что значительно меньше вклада 3-повторов;

3. величина 67 = (Tk )(Tk ), описывающая вклад 7-повторов в индекс роста языка Tk, с ростом k стабилизируется в районе значения 3.6·106, что позволяет предположить, что с ростом m влияние m-повторов на индекс роста языка не зависит от мощности алфавита и быстро убывает;

Естественным образом напрашивается следующая гипотеза:

Гипотеза 1.1. Для любого m 3 существует предел lim (Tk ) = (m).

Таблица 1.1. Верхние оценки индексов роста граничных языков; 36 = (Tk )(Tk ), 67 = (Tk )(Tk ).

10 1,2393804408 1,2393569373 2,35· 11 1,2426566183 1,2426131641 4,35· 12 1,2429286087 1,2428815613 4,70·105 1,2428793902 2,17· 13 1,2409226614 1,2408787655 4,39·105 1,2408729371 5,83· 14 1,2428289279 1,2427804533 4,85·105 1,2427767435 3,71· 15 1,2418774954 1,2418379960 3,95·105 1,2418340134 3,98· 16 1,2420000807 1,2419572202 4,29·105 1,2419536019 3,62· 17 1,2423240470 1,2422793681 4,47·105 1,2422759823 3,39· 18 1,2418973834 1,2418553246 4,21·105 1,2418514866 3,84· 19 1,2421895750 1,2421451742 4,44·105 1,2421416402 3,53· 20 1,2420949436 1,2420520022 4,29·105 1,2420483333 3,67· 21 1,2420552103 1,2420123323 4,29· 22 1,2421449456 1,2421012197 4,37· 58 1, 59 1, 60 1, Так, например, (3) 1.242096777. Причем раз вклад 6- и 7-повторов невелик по сравнению с 3-повторами и предположительно с ростом m влияние m-повторов убывает, можно сделать предположение, что индекс роста граничных языков Tk не сильно отличается от индекса роста их приближений Tk.

Гипотеза 1.2. Последовательность (Tk ) индексов роста граничных языков стремится к числу 1.242 при k.

Отметим, что гипотеза 1.2 является усилением экспоненциальной гипотезы, обсуждавшейся на стр. 13.

1.2.2. Развёртки цилиндров Теперь попробуем использовать для вычисления индекса роста найденное соответствие между m-повторами и наличием определенных двумерных конструкций в цилиндрических представлениях. Как уже упоминалось ранее, индексы роста языков Tk и Tk совпадают. Обозначим через Cylk множество цилиндрических предm) ставлений слов из T.

Отметим, что мы не случайно работаем с подсловами Z-слова, т.е. с языком Tk.

Представим, что у нас есть некоторое слово w. Построение его цилиндрического представления начинается с буквы w[k+1] = a (буквы из верхнего витка не с чем соединять). По замечанию 1.2 либо это первое появление буквы a в слове w, либо она уже появлялась на 1 или 2 позиции. В двух последних случаях нам ничего не мешает закодировать букву a отрезками или, соответственно. А вот с первым случаем дело обстоит сложнее. Если w – «обычное» слово, то в его цилиндрическом коде появится «дырка». Но если w является подсловом Z-слова, то оно имеет продолжение влево любой длины. Причем начинается любое продолжение с буквы a (дальше находится она не может по замечанию 1.2). С учетом этого мы кодируем букву w[k+1] отрезком.

Рассмотрим произвольное слово W Cylk длины l. Количество слов длины l задается значением комбинаторной сложности CCyl(m) (l). Теперь выделим множество Cylk, которые имеют длину nk, где n N. Цилиндрические слова слов в языке с целым числом витков можно представить в виде двумерных слов. Для этого мы должны цилиндрическое слово «разрезать» по образующей цилиндра как показано на рис. 1.18 и развернуть на плоскости. Тогда получим прямоугольную таблицу с символами алфавита = {,, }, которую будем называть развёрткой цилиндра.

Пусть w Tk такое, что |w| = (n+1)k. Тогда его развёртка цилиндра имеет размер n k, а в i-ой строке на j-ом месте в ней стоит отрезок, соединяющий букву w[ik+j] = a с ее предыдущим вхождением. Например, для слова w = abcdaecbdeacdba над алфавитом 5 развёртка цилиндра имеет вид:

Найденные в теоремах 1.1, 1.3 и 1.4 закономерности переносятся и на развёртки цилиндров, только с небольшими изменениями.

1.2.3. Случай m= Остановимся подробнее на случае m = 3. Наш выбор основан не только на том, что цилиндрическое представление 3-повторов имеет более простую структуру. Согласно результатам пункта 1.2.1, языки Tk являются наиболее «ценным» приближением языков Tk. Действительно:

не существует равномерных 4- и 5-повторов;

вклад 6- и 7-повторов, как показывает таблица 1.1, мал по сравнению с вкладом 3-повторов;

с ростом m влияние m-повторов на индекс роста предположительно быстро убывает.

Подмножество языка Cylk, состоящее из слов с целым числом витков, обозначим Cylk. Причем на элементы языка Cylk будем смотреть сразу как на развёртки цилиндров. Количество слов в Cylk длины nk (т.е. количество развёрток цилиндров размера nk) обозначим C (n, k).

Замечание 1.10. Пусть w Tk таково, что Cyl(w) Cylk. Из теоремы 1.1 следует, что наличие 3-повтора в слове w эквивалентно появлению в его развёртке цилиндра следующих подслов:

Объединяя замечания 1.10 и 1.5, получим полный список запрещенных подслов для развёрток цилиндров языка Cylk. Отметим, что каждый запрет целиком укладывается в блок 22. Таким образом, разрешенных блоков размера 22 остается всего 13 из 34 = 81 (состоящее из них множество обозначим Q3 ):

Определим двумерный язык D следующим образом: двумерное слово W принадлежит языку D тогда и только тогда, когда любое его подслово размера 22 попадает в множество Q3. В [21] языки, определяемые подобным образом, т.е. списком разрешенных подслов заданного размера, названы локальными. Через Dk обозначим множество слов языка D ширины k.

Замечание 1.11. Любое слово W языка Cylk принадлежит множеству Dk. Действительно, любое слово в Cylk имеет ширину k и по замечаниям 1.10 и 1.5 не содержит подслов размера 22 не из множества Q3.

Однако обратное утверждение неверно. Дело в том, что наличие разрешенных подслов размера 22 у двумерного слова проверяется только внутри самого слова, а у развёрток цилиндров этому условию удовлетворяет также стык – место бывшего «разреза» цилиндра (см. рис. 1.19).

Рис. 1.19. Отличие развёрток цилиндров от двумерных слов.

1.2.4. Индекс роста двумерного языка Язык D является факториальным, так как если слово W D не содержит блоков не из множества Q3, то и любое его подслово тем более. Следовательно, можно вычислить индекс роста языка D как двойной предел: (D) = lim (CD (n, k))1/nk. В дальнейшем комбинаторную сложность языка D будем обозначать через C(n, k).

Эффективного алгоритма для вычисления индекса роста двумерного языка не известно. Но любая подпоследовательность последовательности (C(n, k))1/nk сходится к тому же пределу (D) (см. [2]). Можно рассмотреть, например, диагональную подпоследовательность (C(n, n))1/n, в которой фигурирует всего одна переменная. Для нахождения пределов иногда бывает полезна следующая теорема, доказательство которой можно найти в [2].

Теорема 1.5 (Теорема Штольца). Пусть (an )n1 и (bn )n1 – две числовые последовательности, причем (bn )n1 неограничена и строго возрастает с некоторого момента. Тогда при условии, что предел справа существует.

Если прологарифмировать выбранную диагональную последовательность и полоlog C(n,n) После потенцирования получим три последовательности, которые (при существовании пределов двух последних) сходятся к одному пределу (D). При помощи компьютера нам удалось сосчитать количество двумерных слов размера nn в языке D до n = 36 включительно и вычислить несколько первых членов этих последовательностей (см. таблицу 1.2). Судя по полученным результатам первые две последовательности являются монотонными и сходятся очень медленно (вторая чуть быстрее), а вот третья последовательность осциллирует вокруг значения 1.242097, очень похожего на предсказанное ранее значение (3).

Так как существование двух последних пределов формально не доказано, к предложенному методу нельзя относиться как к способу вычисления индекса роста двумерного локального языка. Однако, полученные численные оценки являются сильным свидетельством в пользу того, что значение (D) действительно очень близко к (3).

В качестве альтернативного способа оценки индекса роста языка D можно рассмотреть двумерные слова специальной формы, изображенной на рис. 1.20, и оценить, как Таблица 1.2. Оценки индекса роста двумерного языка D.

меняется количество таких слов при добавлении одной клетки к последнему столбцу.

Полученные результаты подтверждают найденную раннее оценку. Так, например, для n = 100, r = 34, l = 50 добавление клетки дает приращение числа двумерных слов примерно в 1.24209673 раза.

Рис. 1.20. Вычисление индекса роста двумерного языка.

1.2.5. Автоматы Ak и Bk У языков Cylk и Dk много общего в структуре слов. Но можно ли как-то связать их численные характеристики?

На язык Dk можно смотреть как на одномерный регулярный язык над алфавитом k с индексом роста (Dk )k. Тогда индекс роста языка Dk над алфавитом вполне естественно определить как (Dk ) = lim (C(n, k))1/nk, причем этот предел существует. Следовательно, (D) = lim (Dk ) = lim lim (C(n, k))1/nk, так как поk n следний предел является повторным пределом существующего двойного (про связь между двойными и повторными пределами можно найти в [2]).

Для Dk как языка над алфавитом k можно построить распознающий его автомат Ak :

(A1) вершинами автомата Ak являются слова размера 1k языка Dk (они совпадают со словами длины k языка Cylk );

принадлежит языку Dk, такое ребро будем помечать словом v;

(A3) каждая вершина является как начальной, так и заключительной.

Построенный автомат является так называемым однозначным недетерминированным автоматом (начальная вершина, конечная вершина и метка однозначно определяют маршрут в автомате). Для таких автоматов функция, возвращающая количество маршрутов длины n, имеет тот же индекс роста, что и комбинаторная сложность распознаваемого языка (см. [47]). Обозначим через Pk (u, n) количество путей длины n в всех маршрутов длины n в автомате Ak. А значит Pk (n) = C(n+1, k).

На язык Cylk можно смотреть как на одномерный регулярный язык «размотанных» цилиндрических кодов слов языка T. Причем, так как количества слов и их цилиндрических кодов отличаются в k! раз, то индексы роста этих языков совпадают:

(Cylk ) = lim (CCyl(3) (n))1/n = lim (CT (3) (n))1/n = (Tk ) = (Tk ) = (3) (1.2) Последовательность (C (n, k))1/nk является подпоследовательностью сходящейся последовательности (CCyl(3) (n)), а значит сходится к тому же пределу:

Для языка Cylk построим так называемый граф Рози порядка k+1 (см. [39]);

обозначим его через Rk. Вершинами этого графа являются слова языка Cylk длины k+1:

Ребро u v существует тогда и только тогда, когда найдется слово w Cylk длины k+2 таково, что u является его префиксом, а v – суффиксом. Каждое ребро u v будем помечать последней буквой слова v, тогда автомат Rk будет распознавать язык Cylk и может быть использован для вычисления его индекса роста.

Теперь рассмотрим автомат Rk. Вершины у него те же, что и у Rk, а ребро u v существует тогда и только тогда, когда найдется слово w Cylk длины 2k+1 такое, что u является его префиксом, а v – суффиксом. Меткой такого ребра служит наибольший собственный суффикс слова v. Отметим, что можно вычислить все слова v, в которые из u выходит ребро, зная только последние k символов слова u. Исключение составляет лишь случай, когда суффикс длины k слова u имеет вид как на рис. 1.21. В случае b) суффикс слова v может начинаться с или, тогда как в случае a) только с, чтобы избежать появления запрещенного фрагмента.

Рис. 1.21. Вычисление индекса роста двумерного языка.

Построим автомат B k следующим образом:

(B1) вершинами автомата Bk являются слова длины k языка Cylk (т.е. наибольшие собственные суффиксы вершин автомата Rk );

(B2) ребро u v существует тогда и только тогда, когда в Rk существует ребро au bv для некоторых a, b, с единственным исключением: если u имеет вид как на рис. 1.21, то v начинается ;

(B3) каждая вершина является как начальной, так и заключительной.

Обозначим через Pk (u, n) количество путей длины n в автомате B k, начинающихся в вершине u. Тогда Pk (n) = Pk (u, n) – количество всех путей длины n в автомате Bk. Причем Pk (n) C (n+1, k) за счет того, что мы выкинули из рассмотрения слова языка Cylk, имеющие на стыке фрагмент.

Замечание 1.12. Если смотреть на Ak и Bk как на орграфы, то легко заметить, что B k является суграфом Ak. Действительно, множества вершин у них совпадают, а любой маршрут в B k определяет некоторое слово языка Cylk, которое по замечанию 1.11 является словом языка Dk, а значит аналогичный маршрут существует и в Следствие 1.2. Для любого n N и k 5 cправедливо следующее соотношение:

Pk (n) C (n+1, k) C(n+1, k) = Pk (n).

1.2.6. Свойства автоматов Ak и B k Пусть k > 11. Две вершины u и v (автомата Ak или Bk ) будем называть подобными и обозначать u v, если у них совпадают суффиксы длины k11 > 0. Легко проверить, что отношение подобия на множестве всех вершин автомата Ak (B k ) является отношением эквивалентности.

Замечание 1.13. Отношение подобия разбивает множество всех вершин автомата Ak (B k ) на классы эквивалентности, мощность которых не зависит от k и не превышает константы N = 28. Действительно, самыми «большими» являются классы, точности равно 28.

Лемма 1.6. Пусть k > 12. Тогда для любой вершины u = u1 · · · uk и для любого такое, что 12-й символ в x равен a.

Доказательство. Пусть x = x1 · · · xk. Сначала покажем, что, если условие леммы выполняется для некоторого i-ого символа в слове x, то оно также будет справедливо и для каждого j-ого символа, где i j k. Достаточно проверить справедливость данного утверждения для j = i+1. Действительно, слово состоит из блоков размера 22, входящих в множество Q3, а значит каждая буква в нем зависит только от трех соседних с ней символов. В частности, xi+1 зависит от ui, ui+1 и xi. Поэтому, доказав для i+1-ого символа, по индукции можно дойти до любого j-ого символа. Для ui ui+ существует 4 возможных варианта. на рис. 1.22 показано, что для любого из этих 4 вариантов, если xi может быть любым символом алфавита, удовлетворяющим условию леммы, то xi+1 тоже. Для этого просто перебираем возможные варианты для xi xi+1 так, чтобы блок xi xi+ допустимые по условию значения.

Для каждой вершины u автомата Bk обозначим через iu минимальный номер, обладающий свойством, что для любого символа a, кроме случая a = uiu =, существует вершина x такая, что в Bk есть дуга u x и xiu = a. Если для каждой вершины u значение iu будет не больше 12, то лемма будет доказана. Отметим, что нам необязательно перебирать все вершины u, достаточно рассмотреть лишь их всевозможные префиксы длины не больше 12, так как xiu -ый символ зависит только от uiu 1, uiu и xiu 1. И еще одно важное замечание: в цилиндрическом слове символ uk предшествует символу x1, а значит непосредственно влияет на его значение. Чтобы избежать рассмотрения символа uk (и не делать наши рассуждения зависящими от k) будем искать подходящий номер для каждого значения x1 (разумеется кроме случая u1 = x1 = ), а максимум из них и будет искомым значением iu.

на рис. 1.23 показаны возможные префиксы для слова u, начинающиеся с (случаи 1) 3)) и (случаи 4) 11)). Для каждого префикса слова u и для любого допустимого x1 строим возможные префиксы слова x пока не найдем позицию, удовлетворяющую условию леммы. Так, например, в случае 2) для u(2) = · · · нужно рассмотреть x1 = и x1 =. В первом подслучае получим позицию номер 5, во и x1 = искомая позиция также равна 5. За счет того, что первые пять символов в словах u(2) и u(3) совпадают, этот случай полностью повторяет случай 2) при x1 =, поэтому на рис. 1.23 он не изображен. Аналогично в случае 6) при x1 = ссылаемся на случай 7); а в случае 11) при x1 = или x1 = ссылаемся на случай 10).

Максимум среди iu в случаях 1) 11) равен 11, он достигается в случае 9). Если слово u начинается с, то его подслово u2 · · · uiu попадает в один из случаев 1)11).

Следовательно, максимальное iu в этом случае увеличится не более, чем на единицу.

Отсюда для любой вершины u iu 12, что доказывает лемму.

Лемма 1.7. Пусть u v и u x – ребро в Ak. Тогда существует ребро v y в Bk такое, что x y.

Доказательство. Пусть u = u1 · · · uk, v = v1 · · · vk и x = x1 · · · xk, причем по условию u12 · · · uk = v12 · · · vk. Заметим, что если мы знаем только u12 · · · uk и x12, то можем восстановить все возможные варианты для x13 · · · xk независимо от u1 · · · u и x1 · · · x11 (об этом уже говорилось в доказательстве леммы 1.6).

Теперь рассмотрим множество вершин y = y1 · · · yk таких, что в Bk существует ребро v y и y12 = x12. По лемме 1.6 данное множество не пусто. Так как u12 · · · uk = v12 · · · vk и x12 = y12, то множество возможных вариантов для x13 · · · xk и y13 · · · yk совпадают, а значит можно выбрать y, у которого y13 · · · yk = x13 · · · xk. Тогда получим, что v y – ребро в Bk и y12 · · · yk = x12 · · · xk, т.е. y – искомая вершина.

1.2.7. Связь между индексами роста граничных языков и языка D Договоримся через deg+k (u) обозначать полустепень исхода вершины u в автомаA те Ak.

Теорема 1.6. Предел lim (Tk ) существует и равен индексу роста двумерного языk ка D, т.е. (3) = (D).

Рис. 1.23. Возможные префиксы слов u и x. Показаны 11 префиксов для слова u (первая строка в каждом случае) и для каждого из них возможные префиксы слова x до искомой позиции, удовлетворяющей условию леммы 1.6.

Доказательство. Напомним сначала то, что нам уже известно об индексах роста вышеупомянутых языков:

Таким образом, необходимо доказать, что предел lim lim (C (n, k))1/nk существует и равен пределу lim lim (C(n, k))1/nk. Идея доказательства заключается в том, чтоk n бы получить двухсторонние оценки для отношения C (n, k)/C(n, k)) 1/nk. В силу следствия 1.2:

Значит осталось получить нижнюю оценку для отношения Pk (n)/Pk (n). Для этого обратимся к автоматам Ak и Bk.

Зафиксируем произвольную вершину u (вместе с ней фиксируем k = |u|) и построим для нее дерево Ak (u) по следующим правилам:

метками вершин дерева Ak (u) являются вершины автомата Ak ;

вершина u является меткой корня дерева Ak (u);

каждая вершина в Ak (u) с меткой v имеет ровно deg+k (v) детей, метками котоA рых являются все вершины автомата Ak, в которые идет дуга из вершины v.

Таким образом существует биекция между множеством вершин n-ого уровня в дереве Ak (u) и множеством путей длины n в автомате Ak, начинающихся в вершине u. А значит n-ый уровень в дереве Ak (u) содержит в точности Pk (u, n) вершин. Заменяя Ak на Bk, аналогично построим для вершины u дерево Bk (u), на n-ом уровне которого содержится Pk (u, n) вершин.

Индуктивно применяя лемму 1.7, получим, что метка каждой вершины уровня n в дереве Ak (u) подобна метке некоторой вершины уровня n в дереве Bk (u). Через parent(s) обозначим родителя вершины s. Построим отображение µ : Ak (u) Bk (u) по следующим правилам:

образ корня дерева Ak (u) равен корню дерева Bk (u);

если s – вершина n-ого уровня дерева Ak (u), помеченная словом x, то µ(s) – это вершина уровня n дерева Bk (u), помеченная словом y x;

µ(parent(s)) = parent(µ(s)).

Рис. 1.24. Доказательство теоремы 1.6. Пунктиром показано действие отображения µ.

Существование такого отображения непосредственно вытекает из леммы 1.7 и структуры деревьев Ak (u) и Bk (u).

Рассмотрим произвольную вершину t уровня n в дереве Bk (u) и оценим мощность множества µ1 (t). Предположим, что |µ1 (parent(t))| = K. Пусть s – вершина уровня n дерева Ak (u) такая, что µ(s) = t. Тогда согласно определению отображения µ parent(s) µ1 (parent(t)) (см. рис. 1.24). Так как все дети вершины parent(s) различны, то по замечанию 1.13 не более N из них могут служить прообразами вершины t относительно отображения µ. Таким образом |µ1 (t)| KN.

Если повторить эти рассуждения по индукции, то для корня получим |µ1(u)| = 1, а для вершины t : |µ1 (t)| N n. Суммируя по всем вершинам уровня n, получим Pk (u, n) N n Pk (u, n). Объединяя результаты для всех вершин u, в итоге имеем:

Pk (n) N n Pk (n).

Теперь перейдем снова к оценке отношения комбинаторных сложностей:

В каждой части неравенства перейдем к пределу при n :

Наконец, устремим k и, применяя правило двух милиционеров, получим, что предел limk (Tk )/(Dk ) существует и равен 1 (напомним, что N не зависит от k). Так как предел limk (Dk ) = (D) также существует, то получим:

Значит предел limk Tk существует как предел произведения (см. [2]) и равен индексу роста языка D.

Замечание 1.14. Как показывают численные эксперименты, настоящее значение N такое, что Pk (n) N n Pk (n), намного меньше 28, а именно, примерно 2.119.

Теорема 1.6 не только доказывает гипотезу 1.1 для случая m = 3, но и позволяет усилить ее:

Замечание 1.15 (Усиление гипотезы 1.1). Для любого m 3 предел (m) = limk Tk не только существует, но и совпадает с индексом роста локального двумерного языка над алфавитом, множество разрешенных подслов которого избегает фрагментов из множества Qm, описанного в предложении 1.1.

Глава Циклические слова Циклические слова образуют очень интересный и важный класс комбинаторных объектов. Циклические слова описывают циклы в графах и автоматах, а также подходят для описания любого циклического процесса, от производственных циклов до циклов солнечной активности. Кроме того, циклические слова взаимно однозначно соответствуют классам сопряженности обычных слов и неявно присутствуют во всех связанных с такими классами задачах. Поэтому получение оценок для циклической границы повторяемости также является немаловажной задачей. Напомним, что для 2и 3-буквенного алфавита значение циклической границы повторяемости уже известно. Поэтому далее мы полагаем k 4.

У циклических слов есть одна особенность. В «обычном» слове расстояние между двумя вхождениями одного символа определяется как разность между номерами их позиций. А в циклическом слове расстояние можно измерять в двух направлениях:

2.1. Нижняя оценка для циклической границы Предложение 2.1. Для любого k 4 не существует -свободного циклического слова над алфавитом k длины k+1.

Доказательство. Рассмотрим циклическое слово (w) над алфавитом k длины k+1.

По принципу Дирихле в слове (w) обязательно найдется хотя бы одна буква, б.о.о. x, rоторая появляется в (w) по крайней мере дважды. Следовательно, (w) = (xw1 xw2 ), причем min{|w1 |, |w2|} (k1)/2 < k/2. Но тогда max{exp(xw1 x), exp(xw2 x)} Следствие 2.1. Из предложения 2.1 непосредственно следует, что CRT(k) k/ для любого k 4.

Замечание 2.1. Для алфавитов из 2 и 3 букв данная оценка тоже справедлива, но может быть улучшена до точной при рассмотрении более длинных циклических слов (длины 5).

2.2. Верхние оценки для циклической границы Чтобы получить верхнюю оценку для циклической границы повторяемости CRT(k), необходимо для любого n N построить + -свободное циклическое слово (w) над алфавитом k длины n. Основная идея построения подходящего слова (w) длины n заключается в следующем:

берем произвольное RT(k)+ -свободное (а значит и + -свободное в силу выбора k) слово u над k-буквенным алфавитом A длины (n2c)/2, где c – некоторая константа (такое слово всегда существует согласно граничной теореме);

берем произвольное RT(k)+ -свободное слово v над k-буквенным алфавитом B склеиваем слова u и v с помощью двух вставок L1 и L2 длины c, состоящих из чередующихся букв алфавитов A B и B A (слова читаем по часовой стрелке);

с помощью определенных перестановок на алфавитах A и B добиваемся, чтобы полученное слово (w) = (L1 uL2 v) было искомым (т.е. + -свободным).

Далее рассматриваются несколько случаев в зависимости от мощности исходного алфавита, в каждом из которых с помощью изложенной выше идеи (возможно с некоторыми модификациями) получаются верхние оценки для циклической границы повторяемости.

2.2.1. Случай k = Теорема 2.1. Над 4-буквенным алфавитом существует циклическое (7/4)+-свободное слово любой длины.

Доказательство. Для любого n N построим циклическое (7/4)+ -свободное слово (w) длины n над алфавитом 4 = {1, 2, 3, 4}. Выделим три случая относительно значения n:

если n 4, то требуемое слово (w) получается тривиально (берем слово, в котором все буквы различны);

если 5 n 9, то искомое слово (w) изображено на рис. 2.1;

если n 10, то слово (w) будем искать в виде w = L1 uL2 v.

Рис. 2.1. (7/4)+ -свободное слово (w) длины n, где 5 n 9 (длина слова указана внутри круга).

Остановимся подробнее на последнем случае. Здесь u – произвольное (7/4)+ свободное слово над алфавитом A = {1, 2, 3}, длина которого равна (n4)/2, дополнительно потребуем, чтобы u[1] = u[3]1; v – произвольное (7/4)+ -свободное слово над алфавитом B = {2, 3, 4}, длина которого равна (n4)/2; L1 = 14; L2 = 41.

Обозначим через u1 (соответственно, v1 ) – префикс длины 2 слова u (соответственно, v), а через u2 (соответственно, v2 ) – суффикс длины 1 слова u (соответственно, v). Заметим, что в u1 (соответственно, v1 ) обе буквы различны. Кроме того, существует всего три способа распределения одинаковых букв в u1 и u2 (соответственно, v1 и v2 ), все они изображены на рис. 2.2. Каждый способ определяет тип слова u, который будем обозначать тем же номером.

Пусть биекция f : A B такая, что f (1) = 4, f (2) = 2, f (3) = 3. Тогда, если n четно, то |v| = |u| и в качестве слова v можно взять f (u) (это гарантирует, что слова u и v будут одного типа); а если n нечетно, то |v| = |u|1 и в качестве слова v можно взять слово f (u) без первой буквы (в этом случае тип слова v также будет однозначно определен за счет условия равенства первой и третьей буквы в слове u).

(7/4)+ -свободное Z-слово над алфавитом A содержит подслово вида a1 a2 a1, которое можно продолжить вправо до любой длины, в частности до длины (n4)/2, полученное слово и возьмем в качестве u.

Рис. 2.2. Варианты расположения общих символов в словах u1 и u2 (k = 4). Общий символ обозначен.

Для каждого типа слова u и для разной четности n рассмотрим варианты перестановок в словах u и v, позволяющие сделать слово (L1 uL2 v) (7/4)+ -свободным (см.

рис. 2.3). Например, когда слово u имеет тип 1, то независимо от четности n слово v также будет иметь тип 1, поэтому перестановки для любого n будут одинаковы:

необходимо переименовать буквы u[1] и 2 (т.е. все вхождения буквы u[1] в слове u заменить на 2 и наоборот), u[2] и 1, u[|u|] и 3 в слове u, а также v[1] и 2, v[2] и 4, v[|v|] и 3 в слове v.

Рис. 2.3. (7/4)+ -свободное слово (w) длины n, где n 10 (внутри круга указан тип u и четность n).

Прежде чем перейти к проверке того, что в каждом случае получилось (7/4)+ свободное слово, сделаем несколько общих наблюдений.

Наблюдение 2.1. Каждое из слов u1 и v1 обязательно содержит букву из A B и B A, соответственно.

Наблюдение 2.2. Если ptp – подслово u или v, то exp(ptp) 7/4 в силу выбора u и v. Причем, если (w) = (ptpt ), то |pt p| > |ptp|, а значит exp(pt p) < exp(ptp) 7/4.

Наблюдение 2.3. Пусть ptp – подслово (w) такое, что одно вхождение p целиком содержится в u, а другое в v. Так как |A B| = 2, то максимальная длина слова p в этом случае равна 3 (если p = 232 или 323). Если p захватывает одну из вставок L или L2, то в силу их строения и наблюдения 2.1 p также будет коротким.

Наблюдение 2.4. В силу перестановок, сделанных в словах u и v, (u1 ) (v2 ) = Проверим, что экспонента любого подслова слова (w) не превосходит 7/4. Согласно наблюдению 2.2 можно не рассматривать подслова вида ptp, когда оба вхождения p целиком находятся в u (соответственно, v). Остальные возможные варианты расположения «опасных» подслов и их экспоненты представлены ниже (здесь h {2, 3} – общее подслово u и v, и |h| 3):

здесь мы воспользовались тем, что min{|u|, |v|} = (n4)/2 3;

здесь мы использовали наблюдения 2.1 и 2.4;

в этом случае |h| = 1 благодаря наблюдению 2.1;

Отметим, что подслова вида 141 · · · 141, 414 · · · 414, h14 · · · h14, 14h · · · 14h, h41 · · · h41, 41h · · · 41h в построенных словах не появляются, значит все «подозрительные» подслова ptp проверены. Следовательно, для любого n N существует циклическое (7/4)+ -свободное слово длины n над 4-буквенным алфавитом.

Следствие 2.2. CRT(4) 7/4.

2.2.2. Случай k = Теорема 2.2. Над 5-буквенным алфавитом существует циклическое (3/2)+-свободное слово любой длины.

Доказательство. Аналогично случаю k = 4 для любого n N построим циклическое (3/2)+ -свободное слово (w) длины n над алфавитом 5 = {1, 2, 3, 4, 5}. Выделим три случая относительно значения n:

если n 5, то требуемое слово (w) получается тривиально;

если 6 n 15, то искомое слово (w) изображено на рис. 2.4;

если n 16, то слово (w) будем искать в виде w = L1 uL2 v.

Рис. 2.4. (3/2)+ -свободное слово (w) длины n, где 6 n 15 (длина слова указана внутри круга).

Разберем последний случай. Здесь u – произвольное (7/5)+ -свободное слово над алфавитом A = {1, 2, 3, 4}, длина которого равна (n4)/2 и u[1] = u[4]; v – (7/5)+ свободное слово над алфавитом B = {2, 3, 4, 5}, которое равно f (u) (в случае четного n) или f (u) без первой буквы (когда n нечетно) для биекции f : A B такой, что f (1) = 5, f (2) = 2, f (3) = 3, f (4) = 4; L1 = 15; L2 = 51.