Построение экстремальных бесповторных слов и оценка их количества тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

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

01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата фтпко-математических наук

21 НОЯ 2013

Екатеринбург - 2013

005539149

005539149

Работа выполнена на кафедре алгебры н дискретной математики Института математики и компьютерных наук ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина».

Научный руководитель: Шур Арсений Михайлович,

доктор физико-математических наук, профессор

Официальные оппоненты: Ушаков Владимир Николаевич,

Защита состоится «11» декабря 2013 года в 140<| часов на заседании диссертациониого совета Д 004.006.04 в Институте математики и механики им. H.H. Красовского УрО РАН по адресу: 620990 г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики им. H.H. Красовского УрО РАН.

Автореферат разослан «_» ноября 2013.

Ученый секретарь

диссертационного совета Д 004.006.04,

доктор физико-математических наук, член-корреспондент РАН, заведующий отделом динамических систем Института математики и механики им. H.H. Красовского УрО РАН, г. Екатеринбург

Фрид Анна Эдуардовна,

доктор физико-математических наук, старший научный сотрудник лаборатории теории графов Института математики им. С.Л. Соболева СО РАН, г. Новосибирск

Ведущая организация: ФГБУН «Санкт-Петербургское отделение

Математического института им. В.А. Стеклова РАН», г. Санкт-Петербург

доктор физ.-мат. наук

Общая характеристика работы

Актуальность темы

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

Одной из центральных тем комбинаторики слов является изучение слов и языков, не содержащих повторов - идущих подряд одинаковых фрагментов. Понятие повтора легко проиллюстрировать и в естественных языках. Например, слово «мама» - это повтор, называемый квадратом (состоит из двух одинаковых фрагментов). Иногда само слово не является повтором, по повтор находится внутри него, как, например, в слове «банан» (фрагмент «ан» повторился 2 раза). Любой повтор характеризуется экаюнентой - отношением длины слова к длине повторяющейся части. Так, слово «заноза» - это повтор с экаюнентой 3/2 (фрагмент «запо» повторился лишь до половины). Экспонента обобщает понятие показателя степени на дробные значения.1

Экспонента в называется избегаемой над данным алфавитом, если существует бесконечное слово (или. что эквивалентно, бесконечно много конечных слов) над данным алфавитом, не содержащее повторов с эксионентой, не меньшей в. Начало исследованиям в этой области также положил Туэ. Он доказал, что квадраты избегаемы над 3-буквепным алфавитом [30], а кубы и все дробные степени, большие 2, избегаемы над 2-буквениы.м алфавитом [31]. Результат Туэ для 2-буквенного алфавита неулучшаем, поскольку любое слово длины не меньше 4 в таком алфавите содержит квадрат. Однако для 3-буквенного алфавита найденное Туэ значение не было оптимальным: в 1972

'Здесь «степень» относится к ассошптншон операции умножения (конкатенации) слон, т.е. (мп)' =мама.

году Ф.Дежан построила бесконечное слово над 3-буквеиным алфавитом, которое не содержало повторов степени больше 7/4 [9].

Инфимум множества избегаемых экспонент для ¿-буквенного алфавита называется границей повторяемости и обозначается !П ;/■ ¡. Так, из работ Туэ следует, что КГ(2) = 2. Дежан доказала, что Г1Т(3) = 7/4, получила нижнюю оценку для избегаемое™ экспонент в ¿-буквенных алфавитах при к > 4 и предположила, что граница повторяемости совпадает с этой оценкой. Данное предположение получило название «гипотезы Дежан», а после завершения его доказательства - «граничной теоремы».

Граничная теорема (гипотеза Дежан; [6 -9,18,19,22,23,31]). Экспонента 0 избегаема над к-буквенным алфавитом Ед. тогда и только тогда, когда ¡3 > Г!Т(А:), где 11Т(А;) принимает следующие значения:

к 2 3 4 5 6 г

ГЩк) 2 7/4 7/5 5/4 (¡/5 ¿/(¿-1)

Доказательство данной гипотезы заняло целых 37 лет (см. рис. 1). Основная идея получения недостающих верхних оценок для границы повторяемости при к > 4 заключается в построении бесконечного КГ(к)+ -свободного (т.е. не содержащего подслов с экспонентой больше КГ(&)) слова над алфавитом Ед.. КТ(А:) +-свободные слова над /¡.-буквенным алфавитом мы будем называть граничными.

Туэ (1912 г.)

2 3 4 5 6 7 8 9 1011 1213141516171819202122232425262728293031323334 к

Рис. I. Доказательство гипотезы Дежан.

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

II. Обобщения

III. Аналога для других понятий степени

\

Z

I. Усиления

IV. Аналога для других видов слов

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

I. В качестве усиления понятия границы повторяемости Бадкобех и Крош-мор определили функцию

FRT(fc) = mf{/ieIR | существует ¿¡+-свободное бесконечное слово над Е/г. содержащее конечное число подслов с экспоиентон RT(/;)},

которая получила название «finite-repetition threshold». Из работы Карху-мяки и Шаллита [12] известно, что если бесконечное бинарное слово является (7/3)-свободным, то оно содержит бесконечно много квадратов, а в работе [27] Шаллиг построил бинарное (7/3)1 -свободное слово, содержащее всего 18 квадратов, откуда следует равенство FRT(2) = 7/3. Равенство FRT(3) = RT(3) доказано Бадкобех и Крошмором в работе [3], а в их совместной работе с Рао [4] были проанализированы бесконечные слова, полученные в доказательстве гипотезы Дежан при к > 1 и установлено, что они удовлетворяют требуемому более сильному условию, т.е. FRT(A-) = К Г (к) при к > 1.

Все граничные языки бесконечны. Но насколько «большими» они могут быть? Из [24] известно, что граничный язык над 2-буквенным алфавитом «небольшой», количество слов в нем с увеличением длине,i растет полиномиально. Для остальных алфавитов существует экспоненциальная гипотеза (происхождение которой считается фольклорным), согласно которой, начиная с 3-буквенного алфавита, граничные языки растут экспоненциально. Для к = 3,4 экспоненциальную гипотезу доказал Ошем [21], для 5 < к < 10 - Колпаков и Рао [14].

Любое граничное слово длины больше к обязательно содержит полслова вида й]ct'2 ■ ■ ■ сц - iiii. В работе [32] Туневым и Шуром для к > 5 было введено понятие чистого граничного слова, т.е. граничного слова, все подслова которого с экспонентой КТ(к) имеют вид «j«2 • • -я/.^аь тем самым, усиливается рассмотренное выше требование конечности числа подслов экспоненты RT(fc). Естественным образом возникает вопрос: конечно или бесконечно множество чистых граничных слов над алфавитом E¿? Для 5-буквенного алфавита Бадкобех, Крошмор и Pao [4] доказали, что это множество бесконечно, построив бесконечное граничное слово, содержащее всего 60 подслов с экспонентой 5/4, период каждого из которых равен 4. Тунев и Шур для любого нечетного 7 < к < 101 доказали более сильный результат [32]: множество всех чистых граничных слов над алфавитом Ед. не только бесконечно, но и имеет экспоненциальный рост. Как следствие, этот результат доказывает экспоненциальную гипотезу для любого нечетного 7 < к < 101.

II. Ограничения можно накладывать не только на экспоненту слов, но и на длину повторяющейся части. В [11] Илие, Ошем и Шаллит ввели понятие обобщенной границы повторяемости RT(A:,Z), которая учитывает только повторы с длиной повторяющейся части > I. Если параметр I равен единице, то обобщенная граница повторяемости совпадает с обычной. На данный момент точных значений обобщенной границы повторяемости известно мало. Фиоренцн, Ошем и Васле получили наилучшие верхние оценки для RT(A\ I) [10], а Румянцев - наилучшие нижние оценки [25].

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

жительпо принимает следующие значения:

к 2 4 5 г

Л1!Т(/г) 11/:! 9 0/5 3/2 (¿-2 )/(,-3)

При этом в [26] доказано, что значения в таблице являются опенками снизу для АГГГ(/г).

Понятие I-абелевой степени служит промежуточным звеном между обычными и абелевыми степенями. Слово • ■ ■ и„ называется /-абелевой «-степенью, если в словах иь«2, • • • , м„ совпадает количество вхождении любых подслов длины < Нетрудно заметить, что при f = 1 определение ¿-абелевой степени совпадает с целой абелевой степенью, а с ростом I становится все более похожим на обычную степень. Ке-рянен доказал, что абелевы (а значит, и /-абелевы для любых /> 1) квадраты избегаемы над 4-буквенным алфавитом [13]; над 3-буквенным алфавитом неизбежны 2-абелевы квадраты и есть гипотеза о том, что 3-абелевы квадраты избегаемы [16]; над бинарным алфавитом избегаемы 3-абелсвы кубы [17] и предполагается пзбегаемость 2-абелевых кубов (в то же время абелевы кубы неизбежны, см. выше про ЛНТ(А;)).

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

к СИТ,, (/,:) С1?Т,(*:) СНТЯ(/,:)

2 2 7':! 5/2

3 7/4 7/4 2

Кроме того, для слабой и средней циклической границы повторяемости Карри выдвинул гипотезу, что, начиная с 3-буквенного алфавита, их значения совпадают с «обычной» границей повторяемости, т.е. CR.Tu.-a-) = СЛТГ,(/,') = ПТ(/,:) для любого к > 3.

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

Цель работы

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

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

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

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

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

Основные методы исследовании

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

Научная новизна

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

Теоретическая и практическая ценность

Работа носиг теоретический характер. Полученные результаты могут быть использованы в дальнейших исследованиях по комбинаторике слов и при чтении специальных курсов для студентов математических специальностей. Ссылки на результаты диссертации присутствуют в работах других авторов: [4,5,8,14.20].

Апробация результатов работы

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

Публикации

Результаты диссертации опубликованы в работах [33-39], среди которых три работы [33-35] опубликованы в рецензируемых изданиях из списка, рекомендованного ВАК. В совместных работах [35,39] A.M. Шуру принадлежат идея цилиндрического кодирования и доказательства общих свойств цилиндрических представлений граничных слов, а автором было получено описание структуры цилиндрических представлений равномерных 7п-повторов для 3 < т < 6 и выполнена экспериментальная часть. В совместных работах [34,38] A.M. Шуру принадлежат постановки задач, а также усовершенствование ряда предложенных автором доказательств и вспомогательных конструкций; доказательство основных результатов принадлежит автору.

Структура и объем диссертации

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

Содержание работы

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

На слово w длины п над алфавитом Е мы будем смотреть как на функцию w : {1, • • • , п} —> Е. Экспонентой слова w называется отношение длины слова к его минимальному периоду: ехр(ш) = |w|/per(n>). На экспоненту можно смотреть как на рациональный показатель степени. Например, слово w = abcda.bc имеет период 4 и схр(ш) = 7/4, т.е. w = (abed)7'/4.

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

Через Е^ будем обозначать /.-буквенный алфавит. Экспонента ¡3 называется /¿-избегаемой, если существует бесконечно много /¡-свободных слов над алфавитом Е^, и /. -неизбежной в противном случае. Границей повторяемости ТЩА:) называется действительное число, отделяющее /.-избегаемые экспоненты от /¿-неизбежных:

RT(k) = inf{/i е М | ¡3 — /.--избегаемая экспонента}

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

Z-слоев w - это бесконечное в обе стороны слово, т.е. w : Z —> Е.

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

Двумерное слово II' размера нх</ - это прямоугольная таблица размера п х</ из символов алфавита Е:

порядок:

h а ь а ь а h а

а h а ь а Ь а Ь

h а Ь а Ь ч Ь а

а Ъ и ь а ь а Ь

Подслова двумерного слова также являются двумерными словами (т.е. допускаются только «прямоугольные» подслова).

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

Языки, состоящие из всех ¿(-свободных (,3 '-свободных) слов, будем называть /3-свободными (3f -свободными) языками над данным алфавитом. Заметим, что такие языки являются факториальными. 11Т(А;)+-свободные языки будем называть граничными и обозначать Т), .

Слово и' (двумерное слово 11'') запрещено в языке (соответственно, в двумерном языке) L. если оно не является полсловом ни одного элемента L (иначе говорят, что язык L избегает слово «>).

Минимальные запрещенные слова для граничного языка 7},. при к > 3 имеют вид и. = ptp, где \р!.\ - что период слова и, a exp(u) = |u|/|pi| > RT(fc), причем экспонента любого собственного подслова слова и не превосходит RT(Ä-). Если = ш, то такое запрещенное слово и будем называй, т-повтором. Например, слово nbc.de.ah над алфавитом £5 является 2-повтором. ш-повтор ptp G Ед. называется равномерным, если т < к и каждая буква слова р встречается в pip одинаковое число раз.

Комбинаторной сложностью языка L называется функция CL(n), которая возвращает количество слов длины п в языке L. О скорости роста комбинаторной сложности языка L можеео судить но индексу роста, который задается формулой

a(L) = 1шi(CL(n))i/n

А для факториального языка индекс роста можно определить следующим образом:

«(L) = 1*111 {('/ !"))' "

/?->ОС

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

a(L)= lim {CLtn,q))ll'">

Первая глава посвящена «обычным» экстремальным бесповторным словам и состоит из двух разделов, первый из которых посвящен структурным, а второй - количественным аспектам.

Результаты первого раздела опираются на цилиндрическое кодирование, предложенное A.M. Шуром и впервые описанное в работе [39]. Данное кодирование применяется к словам, удовлетворяющим следующим двум условиям:

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

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

Такие слова мы будем называть словами Пансьё. Отметим, что любое граничное слово является словом Пансьё.

Опишем основную идею цилиндрического кодирования слов Пансьё. Представим, что у нас есть бесконечный цилиндр, а слово - это нить с нанизанными на неё через равные промежутки буквами. Тогда слово можно «наматывать» на цилиндр так, чтобы количество букв в одном витке равнялось мощности алфавита к (см. рис. 2 а)). Теперь соединим одинаковые символы в соседних витках отрезками. Соседние вхождения одного символа можно соединить тремя способами (считаем, что отрезок идет от нижней буквы к верхней): i (буква осталась на той же позиции), / (сместилась на одну позицию вправо) и \ (сместилась на одну позицию влево) (см. рис. 2 Ь) ).

Полученное графическое изображение из отрезков будем называть цилиндрическим представлением слова w и обозначать через Cyl(w). Па самом деле, цилиндрическое представление слова Пансьё является комбинацией блоков I / \ и / \. «Траекторию» движения каждой буквы в цилиндрическом представлении будем называть её следом. Таким образом, цилиндрическое представление имеет горизонтальную (слово над алфавитом { i . / . \ }), вертикальную (совокупность следов) и двумерную структуру.

■л) Наматываем слой» 1М шелшмр (А — '-'I

с1

Ь) Соединяем иципакоиыс йукьи

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

Идея цилиндрического кодирования слов Пансьё оказалась весьма плодотворной и позволила выявить закономерное™ в строении граничных слов, общие для всех алфавитов.

Предложение 1. Пусть т > - фиксированное число. Тогда для любого натурального к > 2т—3 Z-слова Пансьё над алфавитом Е*. избегающие г-повторы для всех г < т, имеют идентичное описание па языке цилиндрических представлений. А именно, существует конечное множество С}1п фрагментов размера 0(тп)х0(т) такое, что слово является подсловом 2-слова Пансьё тогда и только тогда, когда его цилиндрическое представление не содержит фрагментов из (}т.

Отметим, что условие отсутствия 1- и 2-повторов уже вшито в цилиндрический код (за счет выполнения условий (1) и (2)), поэтому легко строится множество С)2 = {м / / ЧЧ ]Ч /1}

Основным результатом этого раздела является полное описание множеств ~~ (теоремы 1.1-1.4). Приведем здесь полученные множества.

<Эз = = (Зо = Ск и{1,Н}

На рис. 3 а) изображено 5 различных допустимых следов для равномерных б-повторов. Обозначим их 1. 2,3,4, 5, как показано на рисунке, а их зеркальные отражения относительно вертикальной оси обозначим, соответственно, 1', 2', 3', 4', 5'. Фрагмент, состоящий из нескольких идущих подряд следов, будем обозначать последовательностью номеров этих следов. Например, фрагмент на рис. 3 а) обозначается как 12345.

12 3 4 5

а)

Рис. 3. Допустимые следы для 6- и 7-повторов.

= д., и {123451.234512, 345123,451234,512345.

1'5'4'3'2Т, 2Т5'4'3'2\ 3'2'1'5'4'3', 4'3'2'1'5'4', 5'4'3'2'1'5'}

На рис. 3 Ь) показаны возможные варианты следов для равномерного 7-повтора, обозначенные 6, 7, 8, 9, а также симметричные им - 0', 7', 8', 9'.

(¿1 = Ян и {7897897, 8978978, 9789789,9'8'7'9'8'7'9', 8'7'9'8'7'9'8', 7'9'8'7'9'8'7': «'078978, б'б9'8'7'9'8', 789б'б78, 89С'6789: 9б'б7897, 7890'09'8', 89б'09'8'7', 9б'09'8'7'9', 9'8'7'б'09'8'; 8'7'б'б9'8'7', 7'б'б9'8'7'9', 9'8'7'б'б78, 8'7'6,6789! 7'б'б7897,

7897896', 897896'6, 9789б'б7, 9789в'б9', 9'8'7'9'8'7'б', 8'7'9'8'7'6'6, 7'9'8'7'Г,'69', 7'9'8'7'б'67, 6'67896'в, б'б9'8'7'6'б, 90'С7890'. 90'69'8'7'С', 7'б'09'8'7'б'; 7'0'б7890'}

Во втором разделе найденные множества (],„. используются для получения верхних оценок индексов роста граничных языков (см. табл. 1). Мы используем метод регулярных приближений, состоящий в замене целевого языка на его надмножество, являющееся регулярным языком, с последующим вычислением индекса роста этого регулярного языка. В качестве регулярных приближений мы использовали языки = {¡<> £ ¡г не содержит »--повторов для любого г < т}. Для вычисления индексов роста приближении мы написали компьютерную программу, реализующую алгоритм Шура [28].

Результаты вычислений, приведенные в табл. 1, убедительно демонстрируют, что равномерные ш-повторы не только одинаково устроены для всех алфавитов, по и привносят практически одинаковый вклад в индексы роста граничных языков над различными алфавитами. Как следствие, мы можем высказать следующую гипотезу.

Таблица 1. Верхние оценка индексов роста граничных языков; Цж = а(Т£'>)—а{Т}?'\ 4т =

п(Т^)-ааГ).

к «Ю ¿<¡7

5 1,2149529259

С 1,2525850156

7 1,2419872870

8 1,2365057034

9 1,2468689328

10 1,2393801408 1,2393569373 2,35-10"

11 1,2426566183 1,2426131641 4,35-10 -5

12 1,2429286087 1,2428815613 4,70-10- 1,2428793902 2,17-10 в

13 1/2409226614 1,2408787655 4,39-10 5 1,2108729371 5,83-10 о

14 1,2428289279 1,2427804533 4,85-10 Г. 1,2427767435 3.71-10-

15 1,2118774954 1,2418379960 3,95-10' -Г> 1,2118340131 3.98-10- <>

16 1,2420000807 1,2419572202 4,29-10" -5 1,2419536019 3,62-10-

17 1,2423210470 1,2122793681 4,17-10 -5 1,2122759823 3,39-10-

18 1,2418973834 1,2418553246 1,2М1)- -3 1,2418514866 3,84-10" -с

19 1,2421895750 1,2421451712 1,11-10 -5 1,2421416402 3,53-11)- -с,

20 1,2420949436 1,2420520022 4,29-10" 1,2420483333 3,67-10 г.

21 1,2420552103 1,2420123323 4,29-10 3

22 1,2421449456 1,2421012197 4,37-10 3

58 1,2420967776

59 1,2420967762

60 1,2420967771

Гипотеза 1. Для любого т > 3 существует предел Нш о = а'"1'.

Так, по табл. 1 можно предположить, что г» 1.242090777. Причем раз вклад 0- и 7-новторов невелик по сравнению с З-повторами и предположительно с ростом т влияние /п-повторов убывает, индекс роста граничных языков должен мало отличаться от индекса роста их ириолнжении .

Гипотеза 2. Последовательность (о(Т).))Аиндексов роста граничных языков стремится к числу а- « 1.242 при к —>• сю.

В ключевом с точки зрения оценки индексов роста граничных языков случае т = 3 удалось доказать не только существование предела « 1.242096777, но и то, что он совпадает с индексом роста двумерного языка О, заданного множеством запрещенных подслов <7ь полученным в первом разделе для цилиндрических представлений. Точнее, двумерное слово IV принадлежит языку О тогда и только тогда, когда любое его подслово размера 2x2 попадает п множество

1 /

/ N

1 /

\ /

1 /

N 1

/ \

1

/ \

/ \

/ \

\ /

/ \

\ 1

\ 1

/ \

\ 1

1 /

\ 1

\ /

\ /

/ \

\ /

1 /

\ /

\ 1

Тогда основной результат данного раздела можно сформулировать следующим образом:

Теорема 1.6. Предел lim а(7д.'") существует и равен индексу роста двумер-наго языка D, т.е. а'-^ = a(D).

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

Замечание 1. Для любого т > 3 предел а1'"' = Шщ-»^ пе только

существует, но и совпадает с индексом роста двумерного языка над алфавитом { I , / , \ }, множество разрешенных подслое которого избегает фрагментов из множества Qm. описанного в предложении 1.

Вторая глава посвящена циклическим экстремальным бесповторным словам. Для циклических слов можно определить три границы повторяемости: слабую CRTjr(A'), среднюю CRT/(fc) н сильную CRTs(fc), которые задаются как инфимум действительных чисел /3, удовлетворяющих соответствующему условию:

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

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

(Б) существуют /^-свободные слова над алфавитом любой длины.

Для обычных слов условия (\У), (I) и (Б) эквивалентны. В диссертации изучается только сильная граница повторяемое™; мы будем обозначать ее просто СКГ(/с).

Нижняя оценка для циклической границы повторяемости получена для любого к > 4 благодаря несложному наблюдению:

Предложение 2. Для любого к > 4 не существует ^щп-свободного циклического слова над алфавитом Ед,- длины А,-+1.

Откуда непосредственно следует, что СКГ(к) > для любого к > 1.

Чтобы получить верхнюю оценку для циклической границы повторяемости СНТ(А;)< В, необходимо для любого и е N построить /^-свободное циклическое слово (¡л) над алфавитом Ед. длины и. Основная идея построения подходящего слова («.») длины п заключается в следующей процедуре (корректность предложенной конструкции обеспечивается граничной теоремой):

• выбираем к е N такое, что к = пшф € N | 3 > ИТ(г)};

• берем произвольное ПТ(А:)1 -свободное (а значит и ¡Т* -свободное в силу выбора А;) слово и над ¿-буквенным алфавитом А длины [(п—2г.-)/2~|, где с - некоторая константа (такое слово всегда существует согласно граничной теореме);

• берем произвольное ИТ;/.')' -свободное слово у над ¿-буквенным алфавитом В длины [(»—2с)/2_|. причем А и В = Е/,:;

• склеиваем слова и и о с помощью двух вставок и Ь2 длины с, состоящих из чередующихся букв алфавитов и В\Л (слова читаем по часовой стрелке);

1-1

• с помощью определенных перестановок на алфавитах А и В добиваемся, чтобы полученное слово (ш) = {Ь\и1^) было ¿^-свободным.

Детали реализации данной конструкции существенно различаются для разных алфавитов, поэтому пришлось отдельно рассмотреть случаи к = ■1,5,6,7,9 и нечетные к > 11 (теоремы 2.1-2.6). Принимая во внимание тот факт, что для четных к > 8 верхняя оценка для циклической 1раницы повторяемости получается благодаря выполнению неравенства СКТ(/с) < С1{"Г(/,'-1), мы получаем основной результат второй главы.

Теорема 2.7. Для любого к > 6 СКЦк) =

Кроме того, справедливо следующее замечание:

Замечание 2. Для любого п < 50 существует циклическое (|/'|-'^2|1) -свободное слово длины п над к-буквенным алфавитом, где 4 < к < 5.

Тем самым, почти полностью доказан аналог гипотезы Дежан для циклических слов.

Гипотеза 3. Циклические ¡3-свободные слова любой длины над алфавитом Х^ существуют тогда и только тогда, когда $ > С11Т(/с), где СГ$Т(7с) принимает следующие значения:

к 2 4 5 с, i

СП ! [¡:\ 5/2 2 .4/2 1/3 (Г;/21+1)/Г»721

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

Заключение

Подводя итог, перечислим основные результаты, полученные в диссертации.

Получено описание коротких запрещенных подслов (ш-повторов) для граничных слов над произвольными алфавитами; описание дано на языке двумерных запрещенных подслов в цилиндрических представлениях граничных слов и не зависит от размера алфавита, если этот размер больше порогового значения.

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

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

Для циклических слов сформулирован аналог гипотезы Дежап о границе повторяемости и приведено полное доказательство для всех алфавитов, начиная с 6-буквенного, а также нижние и верхние оценки для 4- и 5-буквенных алфавитов.

Список литературы

[1] Aberkane A., Ciurie J. D. There exist binary circular 5/2+ power lice words of every length // Electronic J. Combinatorics. 2004. Vol. 11(1). Article RIO.

[2] Aberkane A., Currie J. D. Attainable lengths for circular binary words avoiding ¿-powers // Bull. Belg. Math. Soc. Simon Stevin. 2005. Vol. 12(4). P. 525-534.

[3] Badkobeh G., Crochemorc M. Finite-repetition threshold for infinite ternary words // Proc. 8th Intemat. Conf. Words 2011 (WORDS 2011). Vol. 63 of EPTCS. 2011. P. 37-43.

[4] Badkobeh G., Crochemore M., Rao M. Finite-repetition threshold for large alphabets // Proc. 14th Mons Days of Theoretical Computer Science. 2012.

[5] Blondel V. D., Cassaignc J., Jungers R. M. On the number of a-power-free binary words for 2 < n < 7/3 /7 Theoret. Comput. Sci. 2009. Vol. 410. P. 2823-2833.

[6] Caqii A. On Dejean's conjecture over large alpliabets // Theoret. Comput. Sci. 2007. Vol. 385. P. 137-151.

[7] Currie J. D., Rampersad N. Dejean's conjecture holds for n > 27 // RAIRO Inform. Thcor. App. 2009. Vol. 43. P. 775-778.

[8] Currie J. D., Rampersad N. A proof of Dejean's conjecture // Math. Comp. 2011. Vol. 80. P. 1063 1070.

[9] Dejean F. Sur un théorème de Thue // J. Combin. Theory. Ser. A. 1972. Vol. 13. P. 90-99.

[10] Fiorenzi F., Ochem P.. Vaslet E. Bounds for the generalized repetition threshold // Theoret. Comput. Sci. 2011. Vol. 412. P. 2955-2963.

[11] Hie L.. Ochem P.. Shallit J. A generalization of repetition threshold // Theoret. Comput. Sci. 2005. Vol. 345. P. 359-369.

[12] Karhumaki J., Shallit J. Polynomial versus exponential growth in repetitionfree binary words // J. Combin. Theory. Ser. A. 2004. Vol. 104. P. 335-347.

[13] Kerancn V. Abelian squares are avoidable on 4 letters // Proc. 19th Int'l Conf. on Automata, Languages, and Programming (ICALP) / Ed. by W. Kuich. Springer-Verlag. 1992. Vol. 623 of LNCS. P. 41-52.

[14] Kolpakov R., Rao M. On the number of Dejean words over alphabets of 5, 6, 7, 8. 9 and 10 letters // Theoret. Comput. Sci. 2011. Vol. 412. P. 6507-6516.

[ 15] Lindgren K„ Moore C.. Nordahl M. Complexity of two-dimensional patterns // J. Stat. Physics. 1998. Vol. 91. P. 909-951.

[16] Local squares, periodicity and finite automata / M. Huova, J. Karhumaki, A. Saarela, K. Saari // Rainbow of Computer Science / Ed. by C. Calude, G. Rozenberg, A. Salomaa. 2011. P. 90-101.

[17] Mercas R., Saarcla A. 3-abelian cubes are avoidable on binary alphabets // Proc. 17th Developments in Language Theory (DLT 2013). Vol. 7907 of LNCS. Springer, 2013. P. 374-383.

[18] Mohanimad-Noori M., Currie J. D. Dejean's conjecture and Stunnian words // European J. Combinatorics. 2007. Vol. 28. P. 876-890.

[19] Moulin-Ollagnier J. Proof of Dejean's conjecture for alphabets with 5,6,7,8,9,10 and 11 letters // Thcorct. Comput. Sci. 1992. Vol. 95. P. 187205.

[20] Mousavi H., Shallit J. Repetition avoidance in circular factors // Proc. 17th Developments in Language Theory (DLT 2013). Vol. 7907 of LNCS. Springer, 2013. P. 384-395.

[21] Ochem P. A generator of morphisms for infinite words // RAIRO Inform. Theor. App. 2006. Vol. 40. P. 427-441.

[22] Pansiot J.-J. A propos d'line conjecture de F. Dejean stir les repetitions dans les mots // Discrete Appl. Math. 1984. Vol. 7. P. 297-311.

[23] Rao M. Last cases of Dejean's conjecture // Theoret. Comput. Sci. 2011. Vol. 412. P. 3010-3018.

[24] Restivo A., Salemi S. Overlap free words on two symbols // Automata on Infinite Words. Ecole de Printemps d'lnformatique Theorique, Le Mont Dore, 1984 / Ed. by M. Nivat, D. Perrin. Springer-Verlag, 1985. Vol. 192 of LNCS. P. 198-206.

[25] Rumyantsev A. Upper bound for the generalized repetition threshold. 2010. Electronic. URL: http://arxiv.org/pdf/1009.4454v2.pdf

[26] Samsonov A. V., Shur A. M. On Abelian repetition threshold // RAIRO Inform. Theor. App. 2012. Vol. 46. P. 147-163.

[27] Shallit J. Simultaneous avoidance of large squares and fractional powers in infinite binary words // Intcmat. J. Found. Comp. Sci. 2004. Vol. 15. P. 317327.

[28] Sliur A. M. Growth rates of complexity of power-free languages // Theoret. Comput. Sei. 2010. Vol. 411. P. 3209-3223.

[29] Sliur A. M. On the existence of minimal /5-powers // Internat. J. Found. Comp. Sei. 2011. Vol. 22. P. 1683-1696.

[30] Thue A. Über unendliche Zeichenreihen // Norske vid. Selsk. Skr. Mat. Nat. Kl. 1906. Vol. 7. P. 1-22.

[31] Tliue Л. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Norske vid. Selsk. Skr. Mat. Nat. Kl. 1912. Vol. 1. P. 1-67.

[32] Tunev 1. N.. Sliur A. M. On two stronger versions of Dejean's conjecture // Proc. 37th Symposium, Mathematical Foundations of Computer Science 2012. Vol. 7464 of LNCS. Springer, 2012. P. 800-812.

Публикации автора но теме диссертации Статьи в рецензируемых журналах из списка ВАК

[33] Ciorbunova I. A. Repetition threshold for circular words // Electronic J. Combinatorics. 2012. Vol. 19(4). Article Pll.

[34] Gorbunova I. A„ Sliur A. M. On Pansiot words avoiding 3-repetitions // Internat. J. Found. Comp. Sei. 2012. Vol. 23(8). P. 1583-1594.

[35] Sliur A. M., Gorbunova I. A. On the growth rates of complexity of threshold languages // RAIRO Inform. Theor. App. 2010. Vol. 44. P. 175-192.

Другие публикации

[36] Горбунова И. А. Структура равномерных 7-новгоров и их влияние на индекс роста граничных языков / Уральский федеральный университет имени первого Президента России Б. Н. Ельцина. Екатеринбург, 2013. 20 с. Библ.: 16 назв. русский. Деп. в ВИНИТИ РАН 05.03.2013 № 63-В2013.

[37] Gorbunova I. A. Repetition threshold for circular words // Proc. 2nd Russian Finnish Symposium on Discrete Mathematics. Vol. 17 of TUCS Lecture Notes. Turku, 2012. P. 76-78.

[38] Gorbunova I. A., Shur A. M. On Pansiot words avoiding 3-repetitions // Proc. 8th Internat. Conf. Words 2011 (WORDS 2011). Vol. 63 of EPTCS. 2011. P. 138-146.

[39] Shur A. M.. Gorbunova I. A. On the growth rates of complexity of threshold languages // Proc. 12th Mons Days of Theoretical Computer Science. Mons : Univ. de Mons-Hainaut, 2008. P. 1-10.

Федеральное государственное автономное образовательное учреждение высшего профессионального образования Уральский федеральный университет имени первого Президента России Б.Н. Ельцина

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

04201450760

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

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

01.01.09 - Дискретная математика и математическая кибернетика

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

Научный руководитель: профессор, доктор физ.-мат. наук А.М. Шур

Екатеринбург 2013

Оглавление

Введение 4

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

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

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

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

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

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

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

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

1.1.4. 3-повторы............................................................24

1.1.5. 4-и 5-повторы........................................................25

1.1.6. 6-повторы............................................................27

1.1.7. 7-повторы............................................................30

1.2. Оценка количества граничных слов........................................36

1.2.1. Верхние оценки для индексов роста граничных языков .... 36

1.2.2. Развёртки цилиндров................................................39

1.2.3. Случай ш=3..........................................................40

1.2.4. Индекс роста двумерного языка....................................42

1.2.5. Автоматы Ли и В^ ..................................................43

1.2.6. Свойства автоматов Лк и Бк........................................45

1.2.7. Связь между индексами роста граничных языков и языка Б . . 47

Глава 2. Циклические слова 52

2.1. Нижняя оценка для циклической границы повторяемости ..............52

2.2. Верхние оценки для циклической границы повторяемости..............53

2.2.1. Случай А; = 4 ........................................................54

2.2.2. Случай к = 5 ........................................................57

2.2.3. Случай к = 6 ........................................................60

2.2.4. Случай к = 7 ........................................................70

2.2.5. Случай к = 9 ........................................................75

2.2.6. Случай нечетных к > 11............................................81

2.3. Аналог гипотезы Дежан для циклических слов ..........................94

Литература 96

Приложение А 101

Введение

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

Одной из центральных тем комбинаторики слов является изучение слов и языков, не содержащих повторов - идущих подряд одинаковых фрагментов. Понятие повтора легко проиллюстрировать и в естественных языках. Например, слово «мама» - это повтор, называемый квадратом (состоит из двух одинаковых фрагментов). Иногда само слово не является повтором, но повтор находится внутри него, как, например, в слове «банан» (фрагмент «ан» повторился 2 раза). Любой повтор характеризуется экспонентной - отношением длины слова к длине повторяющейся части. Так, слово «заноза» - это повтор с экспонентой 3/2 (фрагмент «зано» повторился лишь до половины). Экспонента обобщает понятие показателя степени на дробные значения.1

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

'Здесь «степень» относится к ассоциативной операции умножения (конкатенации) слов, т.е. (ма)2 =мама.

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

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

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

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

Слова

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

Слово XV - это конечная последовательность букв, т.е. и> = 0\а2 ■ ■ ■ ап, где а\. а2,... .ап Е Е, а п = |гу| - длина слова уо. На слово го также можно смотреть как на функцию ю : {1...., п} —» Е. Числа из области определения этой функции называются позициями. Через ъи[г], где 1 < г < |у;\, будем обозначать букву, стоящую на г-ой позиции в слове го. Слово длины 0 называется пустым и обозначается Л. Через Е(ги) будем обозначать множество различных букв, входящих в слово ю. Через Е* (Е+, Е") обозначается множество всех слов (соответственно, всех непустых слов, всех слов длины п) над фиксированным алфавитом Е.

Слово и называется подсловом (соответственно, префиксом или суффиксом) слова ги, если го можно представить в виде гшг) (соответственно, ий, ьи) для некоторых (возможно пустых) слов V и V. Подслово (соответственно, префикс, суффикс) слова IV называется собственный, если оно не совпадает с ги. Для обозначения полслова слова ги, начинающегося с г-ой позиции и заканчивающегося в ?-ой позиции, будем использовать обозначение Реверсом слова т = а,а2 ■ ■ ■ ап будем называть сло-

во %о = ап ■ ■ ■ а2й\.

Два слова гог и и>2 называются сопряженными, если найдутся такие непустые слова и и V, что п)\ = иь и = ии (иначе говоря, слова и:\ и ю2 получаются друг из

друга циклическими сдвигами на определенное число позиций).

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

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

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

Один из простейших способов построения бесконечных слов - это метод итерации морфизма. Морфизмом называется отображение ф : Е* —>■ А*, где Е и Д -произвольные алфавиты, такое, что \/u,v £ Е* выполнено условие ф(т') = ф(и)ф(ь). Легко заметить, что любой морфизм однозначно определяется образами символов алфавита Е. При этом, если длина каждого образа строго положительна, то морфизм называется нестирающим. Пусть а £ Е, ф : Е* —> Е* - нестирающий морфизм и Vn € N0 фп(а) является собственным префиксом фп+1(а). Тогда можно определить предел последовательности (Фп{а))пеПо как cu-слово wу которого префикс длины |0п(а)| совпадает с Ф" (а) для любого п Е N0. В этом случае говорят, что си-слово wф получено итерацией морфизма ф. Полученное си-слово wi/; удовлетворяет равенству ф(~Юф) = wф, поэтому его называют также неподвижной точкой морфизма ф.

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

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

Двумерное слово IV размера пхд - это прямоугольная таблица размера пхд из символов алфавита Е:

ги = abcdacb

я

ъ а Ь а Ь а Ь а

а Ъ а Ь а Ь а Ь

Ъ а Ь а Ъ а Ь а

а Ъ а Ь а Ь а Ь

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

Граница повторяемости

Пусть (3 > 1 - действительное число. Слово ги [с^-слово Z-cлoвo циклическое слово (?<;)] называется /3-свободным (соответственно, в+-свободным), если все его подслова имеют экспоненту меньше в (соответственно, не больше В). Например, слово и) = abcda.bc является (7/4)+-свободным, но не 7/4-свободным (так как ехр(ад) = 7/4), а слово и = аЬаЬс является 3-свободным и даже 2+-свободным, но не 2-свободным (так как содержит подслово аЬаЬ с экспонентой 2).

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

КГ(А;) = т£{/3 е К | В - избегаемая экспонента над Т,к} (1)

Легко проверить, что сама экспонента КГ(А:) неизбежна над Еь т.е. в алфавите Е^. есть бесконечно много КГ(А;)+-свободных слов, но лишь конечное множество КТ(к)-свободных.

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

(\\0 существует бесконечно много /^-свободных слов над алфавитом Ек;

(I) существуют /^-свободные слова над алфавитом Е*. любой достаточно большой длины;

(Б) существуют /^-свободные слова над алфавитом Т,к любой длины.

Однако при замене «обычных» слов на циклические эти три условия становятся попарно неэквивалентными, и соответствующие определения приобретают разный

смысл. Действительно, если у нас есть /3-свободное слово 'ш над алфавитом £/.,, то и любое его подслово является /3-свободным. Но если взять циклическое ,/3-свободное слово (ы), то любое его подслово является /3-свободным словом, но не /3-свободным циклическим словом. Так слово (аЬсЛасЬ) - циклическое (3/2)+-свободное слово, ЬсйасЬ - его (3/2)+-свободное подслово, однако (ЬсАасЬ) не является циклическим (3/2)+-свободным словом, так как содержит подслово ЬЬ с экспонентой 2. Поэтому при определении границы повторяемости для циклических слов мы получим три ее разновидности: слабую С КГц/(/,;), среднюю С КТ/(/с) и сильную (ЖТ^ (к), соответственно.

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

КГ(/с)+-свободные слова и С КГ (к)4 -свободные циклические слова являются «экстремальными» бесповторными словами и представляют особый интерес среди слов, избегающих повторы. КТ(/,;) -свободные слова [КГ(/с)+-свободные ¿"-слова] будем называть граничными.

Языки, антисловари, автоматы

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

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

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

Конечным автоматом называется пятерка объектов А = ((¡). Е, д. 5, Т), где С} -конечное множество состояний с подмножествами начальных состояний 5 и терминальных состояний Т, Е - конечный алфавит, а 5 С хТ-хС} - множество переходов. Конечный автомат обычно рассматривается как помеченный орграф с множеством

вершин <5 и множеством помеченных дуг д. Автомат А распознает слово т, если в нем для некоторых в Е 5 и £ £ Т существует ориентированный (в, £)■-маршрут, помеченный го. Множество всех слов, распознаваемых автоматом А, образует язык Ь(А), распознаваемый этим автоматом. Языки, распознаваемые конечными автоматами, образуют в точности класс регулярных языков. Конечный автомат называется детерминированным, если в нем одно начальное состояние, и все переходы из любого фиксированного состояния имеют различные метки.

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

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

Минимальные запрещенные слова для граничного языка 1). при к > 3 имеют вид и = где \рЬ\ - это период слова и, а ехр (и) = |и|/|р£| > ВТ (к), причем экспонента любого собственного подслова слова и не превосходит ВТ(к). Если \р\ = иг, то такое запрещенное слово и будем называть т-повтором. Например, слово аЬсйеаЬ над алфавитом Е5 является 2-повтором.

Через А^ будем обозначать подмножество в Ак, состоящее из всех г-повторов для любого г < т. Заметим, что множество является конечным для любого т £ N. Кроме того, выполнена следующая цепочка вложений: А^ С • • ■ С А^ С • ■ • с Ак- Языки с антисловарями будем обозначать Таким образом, для каждого граничного языка мы получим приближающую его последовательность регулярных языков: Тк с • ■ • С С • • • С .

Количественные характеристики языков

Комбинаторной сложностью языка Ь называется функция Сь{п), которая возвращает количество слов длины п в языке Ь. Комбинаторная сложность си-слова или ^-слова есть комбинаторная сложность языка его подслов. Впервые комбинаторная сложность рассматривалась в [32]; с тех пор ее изучению было посвящено множество работ. О скорости роста комбинаторной сложности языка Ь можно судить по индексу роста, который задается формулой

а(Ь)= IШ1(Сх(п))1/та (2)

п—> ОС

Если а(Ь) > 1, то это свидетельствует об экспоненциальном росте функции Сь(п), значение а(Ь) = 1 говорит о «медленном» (субэкспоненциальном) росте ком-

бинаторной сложности, а a(L) = 0 означает, что язык L конечен. Так как комбинаторная сложность принимает целые значения, случай 0 < a(L) < 1 очевидным образом невозможен.

Если язык L факториальный, то для его комбинаторной сложности выполняется неравенство Сь(п1+п2) < С¡{пх )С^щ) для любых щ, п> е N. А значит, можно воспользоваться следующей леммой, доказательство которой можно найти в [19,53]:

Лемма Фекете. Пусть (an)n>i ' последовательность действительных чисел такая, что для любых П]. 112 € N выполнено неравенство аП1^П2 fi аП1-\-яП2. Тогда предел lim — существует и равен inf —.

„^оо п - ' f neN n

Применяя данную лемму к последовательности (logC7,(n)) >]} получим существование предела lim (следовательно, и lim {Crin))1- ")- А значит, индекс

ге—>оо п п—> оо

роста факториального языка можно определить следующи�