Комбинаторные характеризации формальных языков тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Шур, Арсений Михайлович

• Шур, Арсений Михайлович
• доктор физико-математических наук
• 2010

Оглавление диссертации доктор физико-математических наук Шур, Арсений Михайлович

Введение

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

1°.1 Слова.

1°.2 Языки и автоматы.

1°.3 Комбинаторная сложность

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

2°.1 Другие виды сложности.

2°.2 Сложность бесконечных слов.

2°.3 Общие результаты о комбинаторной сложности

2°.4 Языки, избегающие степени.

2°.5 Языки, избегающие шаблоны и абелевы степени.

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

3°.1 Цели работы.

3°.2 Основные проблемы

3°.3 Основные результаты

3°.4 Основные методы.

3°.5 Структура диссертации и организация текста

3°.6 Апробация и публикации

Глава 1. Сложность регулярных языков

§ 1 Инструментарий.

1.1 Оценки сложности.

1.2 Орграфы и линейная алгебра.

§ 2 Основные характеристики роста.

2.1 Проверка полиномиальности

2.2 Вычисление индекса роста.

§3 Детали асимптотического поведения.

3.1 Оценка числа арифметических прогрессий.

3.2 Вычисление полиномиального индекса.

3.3 Вычисление асимптотического представления

§ 4 Колебания комбинаторной сложности

Глава 2. Сложность факториальных языков. КАС-языки

§ 5 Основные конструкции.

5.1 Регулярные приближения факториальных языков.

5.2 КАС-автоматы

§ 6 Регулярные приближения языка Туэ-Морса.

6.1 Антисловарь языка Туэ-Морса.

6.2 Порядки точек относительно слов из ТМ.

6.3 Доказательство теоремы об индексах приближений.

§ 7 Полиномиальные КАС-языки.

7.1 Асимметричный случай, |Е| =

7.2 Асимметричный случай, |Е| > 2. Паутинные автоматы.

7.3 Симметричный случай. Обобщенные паутинные автоматы.

§ 8 Сходимость полиномиальных приближений.

8.1 Паутинные языки.

8.2 Расширение антисловарей.

§ 9 Две серии языков промежуточной сложности.

9.1 Суперполиномиальность.

9.2 Субэкспоненциальность.

§ 10 Продолжаемые подмножества языков

10.1 Сравнение индексов роста.

10.2 Суперполиномиальный скачок роста.

§11 Экспоненциальные КАС-языки.

11.1 Базовые свойства КАС-автоматов.

11.2 С-графы и редукция антисловарей.

11.3 Маленькие компоненты бинарных С-графов.

11.4 Алгоритм проверки кандидатов в компоненты.

11.5 Взаимное расположение компонент С-графа.

Глава 3. Языки, избегающие степени

§12 Стабильные экспоненты

12.1 Некоторые свойства морфизма в и языков ТМ и ОР.

12.2 Доказательство теоремы о 2-стабильных экспонентах.

12.3 (7/3)+-свободный морфизм

§ 13 Контекстная эквивалентность.

13.1 Классификация слов из ОР.

13.2 Сравнение сильно продолжаемых слов.

13.3 Сравнение продолжаемых вправо слов.

13.4 Алгоритм решения проблемы эквивалентности.

§ 14 Верхние оценки индекса роста.

14.1 Использование симметрии. Алгоритм U.

14.2 Построение фактор-антисловаря.

14.3 Построение фактор-автомата.

14.4 Существование особого случая.

14.5 Свойство вложенных степеней

14.6 Численные оценки индексов роста.

§ 15 Нижние оценки индекса роста.

15.1 Доказательство теоремы о нижней оценке.

15.2 Скорость вычисления нижней оценки.

15.3 Численные оценки индексов роста.

§ 16 Структура и сложность граничных языков.

16.1 Кодировка Папсьё и цилиндрическое представление.

16.2 Типы повторов.

16.3 Анализ уравновешенных повторов.

16.4 Численные оценки индексов роста.

§ 17 Индекс роста как функция двух параметров

17.1 Закономерности изменения индекса роста.

17.2 Асимптотические формулы для индекса роста при ß ^ 2.

17.3 Асимптотические формулы для индекса роста при ß <2.

17.4 Асимптотика индекса роста при ß яз RT(k).

§ 18 Оценка индекса роста для других классов языков.

18.1 Языки, избегающие шаблоны.

18.2 Языки, избегающие абелевы степени.

Глава 4. Сложность антифакториальных языков

§ 19 Минимальные квадраты в алфавите из трех букв

19.1 Сведение к бинарным словам.

19.2 Сведение к маршрутам в графе Кзз.

19.3 Построение маршрутов заданного веса.

§ 20 Существование минимальных /^-степеней

20.1 Случай бинарного алфавита.

20.2 Большие алфавиты и большие экспоненты.

20.3 Большие алфавиты и маленькие экспоненты.

Введение диссертации (часть автореферата) на тему «Комбинаторные характеризации формальных языков»

Теория формальных языков занимает важное место в современной математике. Она тесно связана с фундаментальными математическими дисциплинами — алгеброй, логикой и комбинаторикой — и неотделима от теории автоматов, рассматриваемых как распознаватели и преобразователи формальных языков. Многие фундаментальные алгоритмические проблемы сформулированы или легко могут быть переформулированы как проблемы о формальных языках. Не менее важны связи теории формальных язы-> ков с прикладными задачами. Здесь нужно упомянуть компьютерные науки (языки программирования и трансляторы к ним, верификация компьютерных программ и компьютерного «железа», сжатие данных, крипаография, компьютерная графика), лингвистику (обработка текстов на естественных языках, компьютерный анализ семантики текста, компьютерный перевод, словари) и биологию (расшифровка и сравнительный анализ последовательностей ДНК, структура белков, модели роста и размножения живых организмов и систем, нейронные сети, внутриклеточные вычисления).

Формальные языки изучаются с разных точек зрения. Здесь можно выделить пять подходов; исследования по формальным языкам чаще всего содержат элементы нескольких подходов. При алгебраическом подходе изучаются операции над языками, уравнения в словах и языках, а также связанные с языками отображения, конгруэнции и тождества; есть и специфически «алгебраические» языки, например, язык минимальных термов произвольной фиксированной алгебры. С точки зрения логического подхода формальные языки рассматриваются как формульные множества различных логик — как правило, логики первого или второго порядка с различными ограничениями/расширениями; соответственно, общую задачу можно сформулировать как описание свойств языков посредством логических формул. Третий подход описывает свойства языков через свойства порождающих систем (например, грамматик) и распознающих или преобразующих устройств (автоматов). Четвертый подход, структурный, исследует свойства слов, составляющих языки; язык при таком подходе часто рассматривается как множество всех слов, объединенных общим структурным свойством. И, наконец, при алгоритмическом подходе исследуегся разрешимость и/или вычислительная сложность алгоритмических проблем для языков или классов языков. Во всех пяти подходах активно используются комбинаторные методы.

Центральное место в обсуждаемой работе отведено важной количественной характеристике формального языка, называемой комбинаторной сложностью. Комбинаторная сложность — это наиболее естественная «подсчитывающая» функция, связанная с языком. Вместе с другими подобными функциями, такими как арифметическая и перестановочная сложность, сложность по подсловам, по подпоследовательностям, но палиндромам и по шаблонам, она характеризует «богатство» формального языка. Зная поведение данной функции, можно делать и некоторые выводы о структурных свойствах изучаемого языка; например, образует ли он свободную подполугруппу? является ли контекстно-свободным или даже регулярньш? порождается ли однозначной контекстно-свободной грамматикой?

Четыре из пяти перечисленных выше подходов к языкам связаны с изучением комбинаторной сложности. Первые результаты о ней были получены в конце 1930-х годов Морсом и Хедлундом [140,141] при изучении структуры бесконечных слов. Впервые систематическое исследование комбинаторной сложности класса языков было проведено Эренфойхтом и Розенбергом в 1973-83 гг. [81-89] для довольно узких, но важных классов БОЬ- и НБОЬ-языков; это исследование также лежит в рамках структурного подхода (и частично алгебраического). С конца 1960-х годов развивается исследование функций роста различных алгебр: фактически, изучается комбинаторная сложность языков минимальных термов для групп, полугрупп, колец, модулей1 и других типов алгебр, см., например, [1,4-6,14-16,43,58,105,138,167,170]. Самым известным алгебраическим результатом о функциях роста групп является теорема Громова [108]: конеч-нопорожденная группа имеет полиномиальный рост тогда и только. тогда, когда она являегся конечным расширением пилыююптной группы. Связи роста алгебр и такой важной характеристики, как размерность Гельфанда-Кириллова, посвящена, в частности, монография Краузе и Ленагана [128]. Отметим, что некоторые идеи, используемые в исследованиях по комбинаторной сложности, впервые появились именно в алгебраических работах.

Связь свойств грамматик с комбинаторной сложностью порождаемых языков отмечалась еще в классической работе Хомского и Шютценберже [65]; более подробно об этой связи см. ниже в п. 2°.3. Что касается логического подхода, то важной характеристикой формулы (т.е. свойства) являв!ся зависимость количества неизоморфных моделей от их размера; если модель — это слово, то указанная зависимость представляет собой комбинаторную сложность языка, определяемого формулой. Необходимо отметить, что такую характеристику вычисляю г и для других типов моделей, чаще всего для графов. Например, работа Фейгина [93], в которой было установлено, что для любой формулы первого порядка множество задаваемых ею графов имеет либо плотность 1, либо плотность 0 во множестве всех графов, положила начало масштабному исследованию 0-1 законов на графах. Активно изучается рост наследственных, т. е. замкнутых относительно порожденных подграфов, классов графов. Такие классы являются прямыми аналогами факториальных языков — языков, наиболее часто рассматриваемых с точки зрения комбинаторной сложности. В частности, известно [33,34,161], что для наследственного класса возможны шесть типов роста: константный, полиномиальный, экспоненциальный и три сверхэкспоненциальных.

Комбинаторная сложность активно изучалась для регулярных и контекстно-свободных языков, для языков подслов бесконечных слов, а также для языков, избегающих степени, абелевы степени и шаблоны. Достаточно информативные подборки результатов о комбинаторной сложности можно найти в [63, разд. 9] и в [38]. При этом количество нерешенных проблем по-прежнему весьма велико. Некоторые из них решены в данной диссертации.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Шур, Арсений Михайлович

выход

В результате получим бор, изображенный на рис. 14.1 слева. Теперь рассмотрим работу процедуры РА (полученный фактор-автомат изображен на рис. 14.1, справа): вершина и с действия

А (строка 01) 2 д добавлены дуги (А —» 1) и (А —> 1)

1 1 никаких (существующая дуга в терминальную вершину)

2 <т 12 (0,0,0), й «- 1а51(А)+1 = 1, затем сг12 <- (0,1,0)

12) <- 1, поскольку № (1) = А, й = 1, А.1 = I условный цикл пропускается

3 добавлена дуга Ц 12) (строка 26)

12 1 <7121 (0,1,0), й <- 1ай(1)+1 = 2, затем аш «- (2,1,0)

К(121) <- 12, поскольку №(12) = 1, й = 2, 1.1 = 12 условный цикл пропускается

2 добавлена дуга (12,2,0), поскольку №(12) = 1, й = 1, (1 —► 0)

Васк12[2] <- 1

3 й <- 1ай(1)+1 = 2 добавлена дуга (12,3,12), поскольку №(12) = в, = 2, (1 12)

Васк12[3] 4- 1

121 дуги (121.1,0) и (121,3,12) добавляются по тем же правилам, что и выше

14.4 Существование особого случая

Следующий пример демонстрирует ситуацию, когда используется условный цикл в процедуре ЕА. з о 1 А

1,2,3 1

2,3

Рис. 14.1. Фактор-бор Т1' (слева) и фактор-автомат А/тт (справа) для 2-прпближения языка

Пример 14.2. Рассмотрим (7/4)+-свободный язык в трехбуквенном алфавите. Это один из граничных языков (РТ(3) = 7/4), поэтому он представляет значительный интерес. Антисловарь М24(3, (7/4)+) содержит слово

Рассмотрев корень ху слова и, можно обнаружить интересную деталь: правый циклический сдвиг слова ху (т. е. слово, полученное из ху перемещением первой буквы в конец) не является корнем минимальной (7/4)-степени. Действительно, слово имеет запрещенный суффикс длины 20 с периодом 11, выделенный в приведенной записи жирным шрифтом. Заметим, что наидлиннейший собственный префикс у является наидлиннейшим собственным суффиксом слова и, т.е. первым кандидатом на f(u). Но оказывается, что длиннейший префикс слова у, являющийся вершиной бора для рассматриваемого приближения языка 1(3, (7/4)+), имеет длину всего лишь 18. Если мы обозначим 19-буквенный префикс слова и за и', а 18-буквенный префикс у — за у', мы получим ^-ц') = у'. В то же время, дуга из и' с меткой 1 является прямой, в то время как дуга из у' с той же меткой будет обратной. Следовательно, дуга из вершины Щг/') = 1ех(г/) с меткой 2 = аи' [1] также является обратной, и для слова и' выполняется условие в строке 19 процедуры ЕА.

Эффект, продемонстрированный в примере 14.2, может иметь место только в случае Р <2. Чтобы показать это, докажем следующее свойство сопряженных слов.

Предложение 14.2. Пусть (3^2, /З-степень го'3 является минимальной, а V — слово, сопряженное с и). Тогда у@ также является минимальной (З-степенью.

Доказательство. В силу минимальности иА слово го примитивно; тогда, очевидно, примитивным является и слово у. Пусть ю = хс и у = сх, где с — буква. Достаточно доказать, что у — корень минимальной /^-степени и = у13 = ту'. (Не имеет значения, длиннее слово у', чем у, короче, или вообще пусто.) Наидлиннейший собственный суффикс слова и не содержит ^-степеней, поскольку совпадает с наидлиннейшим собственным префиксом минимальной ^-степени гиги го'. Следовательно, все /3-степени, содержащиеся

Ц3,2). и = хух = 121321232131213212 31323 121321232131213212 у = 213212321312132123 13231 213212321312132123 в и, являются префиксами и. Тогда и либо является минимальной /^-степенью, либо содержит /^-степень в качестве собственного префикса. Предположим, что у и есть такой префикс ххх' и получим противоречие для всех случаев его расположения относительно частей слова и.

Пусть ¡3 = 2 + г, е ^ 0. Если \ххх'\ ^ (1+е)|ги|, то суффикс vv' слова и также содержит ххх', противоречие с минимальностью www'. Значит, \ххх'\ > (1 + е)|го|. С другой стороны, |ж'| < |го'| по определению /3-степени. Таким образом, \хх\ > |го|, и взаимное расположение частей слова и можно представить следующим образом (не имеет значения, пересекаются ли х' и г/, или нет).

I ¿2 ¿з | г2| | v v у'

Пусть у = хг\ и х = . Так как у начинается с г2 и \х\ > \г2\, можно записать х — г2г3. По свойству сопряжения равенства х = г\г2 и х = г2г3 влекут = в у, г2 = (зу)пз, 23 = ув для некоторых слов я ф А и у, и некоторого п ^ 0. Тогда х = (зу)п+1з, у = (5у)п+15зу. Второе подслово г; начинается с ггж' = (зу)пзх', откуда следует, что одно из слов ув, х' является префиксом другого. С другой стороны, х' — префикс х, а значит, одно из слов ву, х' является префиксом другого.

Если ^ |ж'|, то оба слова ву и у в являются префиксами х'. Тогда ву = ув, откуда по свойству коммутирования в и у являются целыми степенями одного и того же слова; тогда у — тоже степень этого слова, что невозможно, так как у — примитивно. Пусть теперь \х'\ < Тогда \х'\ < |ж| и е < 1. Заметим, что уу содержит подслово зяув. Так как х' — префикс в уз, это подслово, в свою очередь, начинается с ввх'. Вспомним, что х' — префикс также в ву. Если в — префикс в х', слово и содержит 53, что невозмол^но, так как е < 1. Если же х' — префикс в в, то ввх' — дробная степень, экспонента которой очевидно больше экспоненты слова ххх'. Следовательно, взх' содержит /^-степень, которая лежит в слове и, но не является его префиксом, что невозможно. Данное противоречие завершает доказательство. □

Следствие 14.1. Пусть А — КАС-автомат, распознающий регулярное приближение некоторого ¡З-свободного языка, где (3^2. Тогда для любой вершины и ф X автомата А функция отката ^ вернет наидлиннейший собственный суффикс и. В 'частности, если из и выходит прямая дуга с меткой с, то из вершины ^и) также выходит прямая дуга с этой меткой. Следовательно, при построении фактор-автомата тело условного цикла процедуры ГА никогда не будет выполняться.

Доказательство. Пусть с — первая буква слова и. Так как и — вершина, и является префиксом минимальной /3-степени, корень которой имеет вид его. Тогда по предложению 14.2 в антисловаре рассматриваемого приближения есть /^-степень с корнем шс.

Наидлиннейший собственный суффикс и является префиксом этой /^-степени, а значит, вершиной в А. Следовательно, этот суффикс равен по определению. □

Таким образом, при /3^2 можно упростить процедуру РА, отбросив неиспользуемый условный цикл.

14.5 Свойство вложенных степеней

Для регулярных приближений большинства языков L(/c,/3) основной расход памяти при применении алгоритма U связан с фактор-автоматом (построение автомата из бора, разбиение на компоненты, размещение счетчиков). Однако для языков, близких к граничным, явное большинство потенциальных корней, попавших в бор, оказывается непригодным; в результате, размер бора оказывается намного меньше размера очереди. Такая ситуация, когда критической по памяти является вспомогательная, а не целевая структура данных, конечно является нежелательной. Мы покажем, как значительно улучшить ситуацию, используя следующее комбинаторное свойство степеней.

Теорема 14.2. Пусть 1 < ¡3 < 2, ху £ !(&,/?). Тогда если (З-степень (хуне является минимальной, то (ху)Р содержит 0-степенъ (zt)@ такую, что \(ztY\ < \ху\; более того, \zt\ ^ \у\ при ¡3 ^ (4/3)+ и \zt\ < \у\ при (3 < (5/4)+.

Замечание 14.3. В общем случае первая оценка в теореме 14.2 неулучшаема. Например, при (3 = (3/2)+, х = abeda, у = bad получаем \{zt)P\ = \ху\ — 1, см. рисунок.

Z t Z

I-П-1

I abeda \ bad\abeda \ х у х

С учетом теоремы 14.2 построение фактор-бора для m-приближения языка L(к, (3) можно организовать следующим образом:

Г |(m—1)//3J, если ¡3 > (4/3)

• выбрать число т' = < т - fm(/?-l)], если (5/4)+ < (3 ^ (4/3)+, т - [m()S-l)l - 1, если ¡3 < (5/4)+;

• построить очередь и бор для m'-приближения при помощи процедуры FB;

• для каждого слова w из очереди перебрать обходом в глубину все слова длины ^ т с префиксом ш; для каждого такого слова и проверить, используя текущий бор, является ли и запрещенным,

- если и — разрешенное, проверить на текущем боре /?-степень с корнем и (и добавить ее в бор, если она минимальна), после чего продолжить поиск из слова и.

Заметим, что поиск в глубину не требует затрат памяти, кроме хранения текущего слова. Однако без теоремы 14.2 поиск в глубину был бы очень трудоемким по времени, так как проверку слов на запрещенность пришлось бы проводить по определению. Применение указанного способа построения фактор-бора позволило значительно продвинутся в построении приближений граничных языков, в частности, получить наилучшие (в смысле, обсуждавшемся в начале параграфа) приближения таких языков для алфавитов из 4-7 букв.

Доказательство теоремы Ц-2. По условию теоремы, слово хух содержит собственные подслова вида и13. Пусть г1г = — кратчайшее из таких подслов. Тогда, очевидно, уЛх — минимальная /3-степень и \гЬ\ < \ху\.

Рассмотрим вначале случай 2 < х. В этом случае г входит в хух как минимум трижды: помимо пары вхождений на расстоянии \ху\ (в префиксе жив суффиксе х), есть еще пара вхождений на расстоянии \zt\- Вхождения 2 не могут перекрываться, так как хух — 2+-свободное слово. Значит, хух содержит подслово гщгщг, причем t совпадает с более коротким из слов щ, и2 (если £ = щ и \щ\ > то ехр(;ги^;г) > /3 и \zujzl < \ztzl, что противоречит выбору гЬг). Следовательно, ^ |жу|/2, равенство достигается при |«1| = \и2\. Заметим, что второе и третье утверждение теоремы следуют отсюда немедленно, а первое следует всегда, кроме особого случая щ = и2 = I = А.7 Пусть в этом случае \г\ = |жу|/2. Тогда слово г1 сопряжено с ху, откуда немедленно следует, что слово ху само является квадратом, что противоречит условию ху € Ц/с, в). Значит, < |жу|/2, и первое утверждение теоремы выполняется.

Пусть теперь г; ^ .т. Поскольку ztz ^ ху по условию теоремы, а из условия гЬг < ух немедленно следуют все утверждения теоремы, то всюду в оставшейся части доказательства мы полагаем взаимное расположение частей слова хух таким, как представлено на рисунке. z Ь г хух

Первое утверждение теоремы равносильно тому, что \г\\ + < \х\. Докажем это неравенство от противного. Пусть + \г2\ ^ |ж|. Вначале заметим, что в этом случае 1 -Ь1^2! > \г\. Действительно, если ¡г^ + ^г! = |ж| = \г\, то г = г^2, х = 2221. Поскольку 21^221,22^1^2 ^ ХУХ 0 |212221|, |222122| < \гЬг\, получаем z^íz2zl, z2z\z2 6 Ц/с, /3), откуда (3 > 3/2, т.е. |ж| > |у|. Учитывая, что ^ [у| — 2, оценим экспоненту длиннейшего

7Никакого противоречия в предположении £ = А нет, так как = г2 при малой \г\ и (3 и 2. собственного префикса слова ztzl - 1 , Ы - 1 ^ , , \х\ - 1 , \х\ —г~,— = 1 + , > 1 + III,—г > 1 + |,|, = ехр(жуж), N И " \х\ + \у\-2 И + \у\ что противоречит выбору слова гЬг.

Итак, [ 4- \г2\ > Тогда у слова Zl есть непустой суффикс у, являющийся префиксом в Кроме того, по предположению ^ + \г2\ ^ |ж| у слова г2 есть (возможно, пустой) суффикс 5, являющийся префиксом в Тогда найдутся слова у, и ги такие, что z^ = зиу, г2 = ушв, г = эиушз, х = угивиу, откуда хух = ушзиушз1зи тивиу. При этом и>я, ей ф А, так как г ^ х, и ^ |в|, так как |ж| ^ \г\. Без ограничения общности можно считать, что |ю| ^

Очевидно, ^гийгхгмоз! < \ztz\j откуда ехр(тизиугиз) < exp(ztz) по выбору слова гЬг. В частности,

V< м • (14л)

Минимальность гЬг дает также неравенство

14 2)

Для облегчения чтения последующих выкладок, мы длину слова будем обозначать той же буквой, что и само слово, но прямого начертания. Из (14.1) и (14.2) получаем следующие оценки для ф + у + \у) < и(2з + и + У + \У), (14.3)

Цу - з + 1) > (2в + и + + и + у + \у) - (38 + 2и + 2у + 2\у). (14.4)

Умножив (14.3) на (у — в + 1), (14.4) на (в + у + \у) и исключив общую часть неравенств, получим и(2в + и + у + \у)(у - э + 1) >

2з4-и4^)(28 + и + у4- \у) - (38 + 2и + 2у + 2\у))(8 + у4^), или, после преобразований,

Зв + 2и + 2у + 2w)(s + у 4- ду) >

2в 4- и + у 4- \у)(2в2 + 2вУ + Зsw + 2ви + и\у 4- у\у + ду2 - и). (14.5)

Предположим, что в > 0. Увеличим первую скобку в левой части на в и сократим с первой скобкой правой части. В результате получим явно неверное неравенство

2(в + у + \у) > 28(в + у + \у) 4- Д, где А ^ 0. Получили противоречие.

Теперь предположим, что 8 = 0. Тогда в (14.5) первые скобки слева и справа сокращаются, оставляя

2(у + \у) > \у(у + \у) + ичу — и. (14.6)

Напомним, что шз, ей ф А, т. е. в данном случае V/, и > 0, и \у ^ и. Следовательно, (14.6) верно только при V/ = и = 1. Подставляя полученные значения в (14.3) и помня, что V > 0, получаем t = 1. Чтобы получить противоречие, осталось рассмотреть неравенство ехр^гивиыиз) < ехр(хух), которое преобразуется к неверному неравенству (у + 1)^ + 2) < 2у + 2. Тем самым, мы показали, что + \г2\ < |ж|, и первое утверждение теоремы доказано.

Для доказательства второго и третьего утверждении теоремы введем обозначение 7 = (здесь ¡3 — рациональное число). Заметим, что для произвольного слова иьи с минимальным периодом \иу\ условия ехр(шш) < /3 [=/3; >/3] и |и| < |г>|/7 [соответственно, = [г»|/7; >М/7] равносильны. Ниже мы проведем доказательство для рациональной экспоненты /3; доказательство для экспоненты «с плюсом» полностью аналогично: при определении 7 мы не учитываем плюс, все сравнения производятся между рациональными числами, а единственное отличие состоит в строгости/нестрогости неравенств. Отметим сразу, что 7^2 при /3 ^ (4/3)+ и 7 ^ 3 при ¡3 ^ (5/4)+.

Второе утверждение теоремы равносильно неравенству |г1|+|^2| ^ \г\. Рассуждая от противного, предположим, что |г1|+|г2| > С учетом доказанного неравенства Ы+|22|<|а:|, можно записать г\ = иу, г2 = ыи, г — иуги, х = ууовиу, причем и,у,т,в ф А. Итак, хух = уювиотЬи ишвиу. Из ограничения на /3 следует, что ywsuvwl, \uvwsuvl < 2\х\ < \у | < \ztz\j т. е. ушвиуги, иугавиу е ЦА;, /?) по выбору гЬг. Тогда V + < (э + и)/7, V + и < (в + \у)/7. Без ограничения общности, ^ и. Следовательно, 1 + < (в + \у)/7, и, в итоге,

Б — 1 и ^ ™ < ^гу ~(14-7)

Теперь оценим t. Из условия ехр(гЬг) ^ ¡3 выводим и + V + \\г ^ t/7, а равенство хух = (ху)13 влечет з-|-и-}-2у + "кг — 1 < (и + \\г-М + 1)/7. После преобразований получаем

7(и + у + \у) + 7(э + у - 1) <и + \у-К + 1^ 7(и + у + \\г) + и + \у + 1, откуда и + +1 > 7(э + V - 1) ^ те. (14.8)

С учетом (14.7), из (14.8) следует квадратное относительно 7 неравенство

872 + (1 - в)7 + 1 - 2э < 0, решая которое, получаем 7 < (2 — 1/з). Противоречие с условием 7^2 доказывает второе утверждение теоремы.

Для доказательства третьего утверждения осталось показать невозможность случая + 1^1 = N при ¡3 < (5/4)+. Представление слов г и х в этом случае такое же, как и в предыдущем, только v = А. Итак, хух = шеи иЛи vj.su. Запишем оценки, аналогичные полученным при доказательстве второго утверждения: в t и + + 1 + 1 и ^ ту <-, и + ту^ —, в + и + — 1 <-.

7 — 1 7 7

Заметим, что из первой оценки следует, что э > 2. Как и выше, исключаем ^ при этом получается неравенство и +\у + 1 > (в - 1)7, из которого с учетом ограничений на и, \у следует квадратное неравенство в - 1)72 - .47 + 1 - 2в < 0.

Из последнего неравенства находим 7 < 2 + что противоречит условию 7^3. Доказательство теоремы завершено. □

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

Предложение 14.3. Пусть /3 ^ 2, х € !(/;,/?). Тогда если (3-степень не является минимальной, то содержит {3-степень такую, что |у| ^ М/2.

Доказательство. Пусть х13 содержит подслово у/3, причем \у\ > \х\/2. Если слово у не примитивно, т.е. у = з", где п > 1, то х содержит и подслово в0, для которого < \х\/2. Поэтому в дальнейшем мы считаем у примитивным.

Среди сопряженных с х слов выберем такое х, что у13 является префиксом . Слово у'1 имеет периоды \у\ и |ж|, но поскольку оно примитивно, свойство взаимодействия выполняться не может, т. е. ж| + м-нод(И,М), откуда \у0\ — |.т| < \у\ и, в частности, ¡3 < 3. Следовательно, взаимное расположение слов х13 и у13 выглядит так, как показано на рисунке.

У У у' и v ии\и у го|и| uvwuv\uvwuv\ х х

Более короткое из слов и, w является префиксом более длинного. Рассмотрим оба случая.

Случай 1: и — префикс и>. Здесь слово uvuvw содержит префикс uvuvu, экспонента которого не меньше ß, а период — меньше, чем ¡ж|/2. Поскольку слово uvuvw сопряжено с х, оно сопряжено и с ж, а значит, является подсловом в х2, а х2, в свою очередь, в ж'3. Итак, xß содержит /3-степень с периодом меньшим |ж|/2.

Случай 2: w — собственный префикс и. Поскольку оба слова uvw и wu являются префиксами ж и |ш| < |и|, то два указанных вхождения и в ж пересекаются. Тогда по свойству сопряжения существуют слова z Ф А и s, такие что w = zs, wu = (zs)nz для некоторого п ^ 2, и, кроме того, слово sz является префиксом vw. Тогда слово ivuvu, являющееся подсловом в у1', а значит, и в х1>, начинается с (zs)3z, т.е. содержит ^-степень с периодом меньшим |ж|/2. Предложение доказано. □

14.6 Численные оценки индексов роста

Алгоритм U дает возможность оценивать индексы роста языков, избегающих степени, над любыми алфавитами. При этом для каждого языка L(k, ß) можно построить достаточно много членов последовательности {Gr(Lj(A;, ß))} и экстраполировать полученные результаты, получая предполагаемое значение Gr(L(A;,/?)). Компьютерная программа, реализующая алгоритм U, написана учениками автора: первая версия принадлежит PI.А. Горбуновой, последняя, наиболее оптимальная, — A.B. Самсонову. Некоторые численные результаты приведены ниже в табл. 14.1. Все эксперименты выполнялись на персональном компьютере с частотой ЗГГц и памятью объемом 2Гб, а общее их количество превысило десять тысяч. При этом обоснованность перехода к более мощным вычислительным ресурсам не очевидна, поскольку такой переход вряд ли добавит приниципиально новое знание к уже полученному: размер автомата экспоненциально зависит от номера регулярного приближения, так что количество новых приближений индекса роста языка, получаемых при любом увеличении объема памяти, ограничено константой, а временной ресурс, как показывают результаты экспериментов, некритичен.

Мы вначале отметим две интересные нечисленные закономерности, касающиеся фактор-автоматов, построенных в ходе эксперимента.

Закономерность 14.1. Все построенные фактор-автоматы имеют единственную компоненту, не являющуюся синглетоном.

Закономерность 14.2. Все построенные фактор-автоматы примитивны, за исключением случая к = 2, 2+ ^ ß ^ 7/3.

Доказать эти экспериментально обнаруженные закономерности в виде теорем — одна из естественных целей дальнейшей работы в этой области. Однако доказательство не обещает быть простым: например, для абелевых степеней первая закономерность нарушается, см. § 18. Что касается исключений во второй закономерности, то они снова выделяют «полиномиальное плато» — подробно обсуждавшуюся аномалию сложности для бинарных языков. Заметим, что эти исключения легко предсказуемы, поскольку двусторонняя продолжаемая часть любого из языков-исключений совпадает с языком Туэ-Морса, а компоненты КАС-автоматов (которые легко преобразовать в компоненты фактор-автоматов), распознающих регулярные приближения языка Туэ-Морса, имеют число импримитивности N/4, где N — размер компоненты, см. рис. 6.4 в п. 6.3. Кроме того, отметим, что регулярные приближения языков-исключений действительно демонстрируют колебания сложности, возможность которых обусловлена неиримитивностью автомага (см. §4).

Перейдем к обсуждению численных результатов. Вначале заметим, что наши результаты улучшают известные ранее оценки: 1.4576 для Gr(L(2,3)) (Эдлин [80]), 1.3017886 для Gr(L(3,2)) (Ошем, Рей [147]), 1.2299 для Gr(L(2, (7/3)+)) (Кархюмяки, Шаллит [119]). Рихард и Гримм [155] использовали для оценки Gr(L(3, 2)) метод дифференциальных аннроксимантов на основе предположения о «регулярности» поведения комбинаторной сложности этого языка и получили оценку 1.301762± 2-Ю-6; наша наилучшая оценка равна 1.301761876, что блестяще согласуется с оценкой из [155].

Для оценки скорости сходимости последовательности {Gr(Lm(fc, /3))}^=i индексов роста приближений фиксированного /3-свободного языка, будем сравнивать различные члены этой последовательности. Мы предполагаем, что абсолютная погрешность приближения |Gr(Lm(£;, (3)) — Gr(L(/c, /3))| мультипликативно зависит от размера фактор-автомата (замечание 6.1 и результаты экспериментов подтверждают это предположение). Языку LOT (к и /3 считаем фиксированными) поставим в соответствие величину Д(/то) = Gr(Lm/) — Gr(Lm), где фактор-автомат Ат' приблизительно вдвое меньше, чем Ат. Абсолютные значения и поведение функции A (m) дают хорошее представление о точности полученных верхних оценок. В предпоследнем столбце табл. 14.1 приведены значения А(т) для наилучших построенных приближений. Экстраполируя поведение функции А, мы приводим гипотетические значения индексов роста /^-свободных языков в последнем столбце (цифры, данные в скобках, определяются неточно).

Приведем некоторые закономерности, касающиеся сходимости приближений:

1) наиболее медленная сходимость последовательности {Gr(Lm(A;, (3))}n=i наблюдается для приближений граничных языков L(4, (7/5)+), L(5,(5/4)+) и L(6, (6/5)+); но мере роста алфавита сходимость приближений граничных языков ускоряется;

2) наихудшие абсолютные значения A (m) для наилучших построенных приближений наблюдаются для языков L(к,

3) точность приближений при (3^2 значительно выше, чем при ¡3 < 2.

Список литературы диссертационного исследования доктор физико-математических наук Шур, Арсений Михайлович, 2010 год

1. И. К. Бабенко. Проблемы роста и рациональности в алгебре и топологии // Успехи Мат. Наук. 1986. Т.41, №2(248). С. 95-142.

2. Ф. Р. Гаптмахер. Теория матриц. Изд. 4-е: М.: Физматлит, 1988. 552 с.

3. С. Гинзбург. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 326 с.

4. В.Е. Говоров. Градуированные алгебры // Мат. Заметки. 1972. Т.12. С. 197-204.

5. Р. И. Григорчук. Степени роста конечно-порожденных групп и теория инвариантных средних // Изв. АН СССР. Сер. Матем. 1984. Т.48. С. 939-985.

6. Р. И. Григорчук. О степенях роста р-групп и групп без кручения // Мат. Сб. 1985. Т.126(168), №2. С. 194-214.

7. А. А. Евдокимов. О сильно асимметричных последовательностях, порожденных конечным числом символов // Докл. АН СССР. 1968. Т.179, №6. С. 1268-1271.

8. А.И. Зимин. Блокирующие множества термов // Мат. Сб. 1982. Т.119(161), №3(11). С. 363-375.

9. A.B. Клепинин. О синтаксических конгруэнциях равномерно рекуррентных языков // Известия УрГУ. 2006. Т.43 (Сер. Компьютерные науки, Вып. 1). С. 38-44.

10. Р. М. Колпаков. Об оценке числа бесповторных слов // Дискр. анализ и исслед. операций. Сер. 1. 2006. Т.13, №2. С. 21-37.

11. М. А. Макаров. О перестановках, порожденных бесконечными бинарными словами // Сиб. Электрон. Мат. Изв. 2006. Т.З. С. 304-311.

12. А. Н. Маслов. Оценки числа состояний конечных автоматов // Докл. АН СССР. 1970. Т.194, №6. С. 1266-1268.

13. Б. Г. Миркин. О дуальных автоматах // Кибернетика. 1966. Т.2. С. 7-10.

14. В. И. Трофимов. Функции роста некоторых классов языков // Кибернетика. 1981. №6. С. 9-12.

15. В. И. Уфнаровский. Критерий роста графов и алгебр, заданных словами // Мат. заметки. 1982. Т.31, №3. С. 465-472.

16. Д. Цветкович, М. Дуб, X. Захс. Спектры графов. Киев: Наукова думка, 1984. -384с.

17. A. Aberkane, J.D. Currie. The Thue-Morse word contains circular (5/2)+-power-free words of every length // Theor. Comput. Sci. 2005. Vol. 332. P. 573-581.

18. A. Aberkane, J.D. Currie. Attainable lengths for circular binary words avoiding k-powers // Bull. Belg. Math. Soc. Simon Stevin. 2005. Vol. 12, №4. P. 525-534.

19. A. Aberkane, J.D. Currie, N. Rampersad. The number of ternary words avoiding Abelian cubes grows exponentially // J. Int. Seq. 2004. Vol. 7. #04.2.7 (electronic).

20. O. Aberth. Introduction to Precise Numerical Methods. 2nd ed. San-Diego: Academic Press, 2007. 272p.

21. A. V. Aho, M. J. Corasick. Efficient string matching: An aid to bibliographic search // Communications of the ACM. 1975. Vol. 18. P. 333-340.

22. J.-P. Allouche. Sur la complexité des suites infimes // Bull. Belg. Math. Soc. 1994. Vol. 1. P. 133-143.

23. J.-P. Allouche, M. Baake, J. Cassaigne, D. Damauik. Palindrome complexity // Theor. Comput. Sci. 2003. Vol. 292(1). P. 9-31.

24. J.-P. Allouche, J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge Univ. Press, 2003. 588p.

25. N. Alon, J. Grytczuk, M. Haluszczak, O. Riordan. Non-repetitive colorings of graphs // Random Structures and Algorithms. 2002. Vol. 21(3-4. P. 336-346.

26. M.-C. Anisiu, J. Cassaigne. Properties of the complexity function for finite words // Rev. Anal. Numér. Théor. Approx. 2004. Vol. 33(2). P. 123-139.

27. M. Anselmo, D. Giammarresi, M. Madonia. Tiling automaton: a computational model for recognizable two-dimensional languages // Proc. 12th Int. Conf. on Implementation and Application of Automata. 2007. P. 290-302. (LNCS Vol. 4783).

28. S. V. Avgustinovich, J. Cassaigne, A. E. Frid. Sequences of low arithmetical complexity H RAIRO Inform. Theor. Appl. 2006. Vol. 40. P. 569-582.

29. S.V. Avgustinovich, D.G. Fon-der-Flaass, A. E. Frid. Arithmetical complexity of infinite words // Words, Languages and Combinatorics III. Singapore: World Scientific, 2003. P. 51-62.

30. J. Balogh, B. Bollobäs. Hereditary properties of words // RAIRO Inform. Theor. Appl. 2005. Vol. 39. R 49-65.

31. J. Balogh, B. Bollobäs, D. Weinreich. The speed of hereditary properties of graphs // J. Comb. Theory, Ser. B. 2000. Vol. 79. R 131-156.

32. J. Balogh, B. Bollobäs, D. Weinreich. The penultimate rate of growth for graph properties // European J. Comb. 2001. Vol. 22. R 277-289.

33. D. R. Bean, A. Ehrenfeucht, G. McNulty. Avoidable patterns in strings of symbols // Pacific J. Math. 1979. Vol. 85. P. 261-294.

34. J. P. Bell, T. L. Goh. Exponential lower bounds for the number of words of uniform length avoiding a pattern // Information and Computation. 2007. Vol. 205. P. 12951306.

35. J. Bernoulli. Sur une nouvelle espeee de caleul // Recueil pour les Astronomes, V.l. Berlin, 1772. P. 255-284.

36. J. Borstel. Groiuth of repetition-free words a review // Theor. Comput. Sei. 2005. Vol. 340(2). P. 280-290.

37. J. Berstel, J. Karhumäki. Combinatories on words: A tutorial fj Bull. Eur. Assoc. Theor. Comput. Sei. 2003. Vol. 79. P. 178-228.

38. J. Berstel, P. Seebold. A characterization of overlap-free morphisms // Discrete Appl. Math. 1993. Vol. 46(3). P. 275-281.

39. V.D. Blondel, J. Cassaigne, R. Jüngers. On the number of a-power-free binary words for 2 < a ^ 7/3 // Theor. Comput. Sei. 2009. Vol. 410. P. 2823-2833.

40. F.-J. Brandenburg. Uniformly growing k-th power free homomorphisms // Theor. Comput. Sei. 1983. Vol. 23. P. 69-82.

41. M. Brazil. Calculating growth functiojis for groups using automata // Computational algebra and number theory. Dordrecht: Kluwer Academic Publ., 1995. P. 1-18.

42. J. Brinkhuis. Non-repetitive sequences on three symbols // Quart. J. Math. Oxford. 1983. Vol. 34. P. 145-149.

43. S. Brlek. Enumeration of factors in the Thue-Morse word // Discrete Appl. Math. 1989. Vol. 24. P. 83-96.

44. J. Brzozowski. Open problems about regular languages // Formal language theory: perspectives and open problems. NY: Academic Press, 1980. P. 23-47.

45. J. Brzozowski. Quotient complexity of regular languages // Proc. 11th International Workshop on Descriptional complexity of formal systems. Otto-von-Guericke Universität, Magdeburg, 2009. P. 25-42.

46. J. Brzozowski, G. Jirâskovâ, C. Zou. Quotient complexity of closed languayes // Proc. 5th International Computer Science Symposium in Russia. Berlin: Springer, 2010. P.84-95. (LNCS Vol. 6072).

47. A. Carpi. On the number of Abelian square-free words on four letters // Discr. Appl. Math. 1998. Vol. 81. P. 155-167.

48. A. Carpi. On the repetition threshold for large alphabets // Proc. 31st Int. Syinp. on Mathematical Foundations of Computer Science. Berlin: Springer, 2006. P. 226-237. (LNCS Vol. 4162)

49. A. Carpi. On Dejean's conjecture over large alphabets // Theor. Comput. Sci. 2007. Vol. 385. P. 137-151.

50. J. Cassaigne. Unavoidable binary patterns // Acta Inf. 1993. Vol. 30(4). P. 385-395.

51. J Cassaigne. Counting overlap-free binary words // Proc. 10th Int. Symp. on Theoretical Aspects of Computer Science. Berlin: Spiinger, 1993. P. 216-225. (LNCS Vol. 665).

52. J. Cassaigne. Special factors of sequences with linear subword complexity // Developments in Language Theory, II. Singapore: World Scientific, 1996. P. 25-34.

53. J. Cassaigne. Complexité et facteurs spéciaux // Bull. Belg. Math. Soc. 1997. Vol. 4. P. 67-88.

54. J. Cassaigne. Double sequences with complexity mn+1 // J. of Autom. Lang. Comb. IV. 1999. Vol. 3. P. 153-170.

55. J. Cassaigne. Constructing infinite words of intermediate complexity // Proc. 6th Int. Conf. Developments in Language Theory. Berlin: Springer, 2002. P. 173-184. (LNCS Vol. 2450).

56. T. Ceccherini-Silberstein, R. I. Grigorchuk. Amenability and growth of one-relator groups // Enseign. Math. 1997. Vol. 43. P. 337-354.

57. T. Ceccherini-Silberstein, W. Woess. Growth and ergodicity of context-free languages // Trans. Amer. Math. Soc. 2002. Vol. 354. P. 4597-4625.

58. T. Ceccherini-Silberstein, W. Woess. Growth sensitivity of context-free languages // Theor. Comput. Sci. 2003. Vol. 307. P. 103-116.

59. T. Ceccherini-Silberstein. Growth and ergodicity of context-free languages II: the linear case // Trans. Amer. Math. Soc. 2007. Vol. 359. P. 605-618.

60. J. Chalopin, P. Ochem. Dejean's conjecture and letter frequency // Electronic Notes in Discr. Math. 2007. Vol. 28. P. 501-505.

61. C. Choffrut, J. Karhumâki. Combinatorics of words // Handbook of formal languages, Vol.1, Ch.6. Berlin: Springer, 1997. P. 329-438.

62. N. Chomsky, G. A. Miller. Finite state languages // Inf. and Control. 1958. Vol. 1 (2). P. 91-112.

63. N. Chomsky, M. Scliutzenberger. The algebraic theory of context-free languages // Computer Programming and Formal System. Amsterdam: North-Holland, 1963. P. 118-161.

64. J. Cocke, J.T. Schwartz. Programming languages and their compilers: Preliminary notes // Technical report. Courant Institute of Mathematical Sciences, New York Univeisity. 1970.

65. T. H. Corxnen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. 2nd Ed. MIT Press, 2001. 1184 pp.

66. E. M. Coven, G.A. Hedlund. Sequences with minimal block growth // Math. Syst. Theory. 1973. Vol. 7. P. 138-153.

67. M. Crochemore, F. Mignosi, A. Restivo. Automata and forbidden words // Inform. Processing Letters. 1998. Vol. 67. P. 111-117.

68. M. Crochemore, F. Mignosi, A. Restivo, S. Salemi. Data compression using antidictionaries // Lossless data compression. Proc. of the I.E.E.E. 88-11. 2000. P. 1756-1768.

69. J.D. Currie. There are ternary circular square-free words of length n for n ^ 18 // Electron. J. Combin. 2002. Vol. 9. #N10.

70. J.D. Currie. The number of binary words avoiding Abelian fourth powers grows exponentially // Theor. Comput. Sci. 2004. Vol. 319 (1-3). P. 441-446.

71. J.D. Currie, N. Rampersad. Dejean's conjecture holds for n > 27 // RAIRO Inform. Theor. Appl. 2009. Vol. 43. P. 775-778.

72. J. D. Currie, N. Rampersad. A proof of Dejean's conjecture // 2009. Available at http://arxiv.org/PS cache/arxiv/pdf/0905/0905.1129v3.pdf

73. J.D. Currie, N. Rampersad. Infinite words containing squares at every position // RAIRO Inform. Theor. Appl. 2010. Vol. 44. P. 113-124.

74. F. D'Alessandro, B. Intrigila, S. Varricchio. On the structure of counting function of sparse context-free languages // Theor. Comput. Sci. 2006. Vol. 356. P. 104-117.

75. F. Dejean. Sur un Theoreme de Thue // J. Comb. Theory, Ser. A. 1972. Vol. 13. P. 90-99.

76. F. M. Dekking. Strongly non-repetitive sequences and progression-free sets // J. Combin. Theory Ser. A. 1979. Vol. 27. P. 181-185.

77. R. Deviatov. On subword complexity of morphic sequences // Proc. 3rd International Computer Science Symposium in Russia. Berlin: Springer, 2008. P. 146-157. (LNCS Vol. 5010).

78. A. Edlin. The number of binary cube-free words of length up to 47 and their numerical analysis // J. Diff. Eq. and Appl. 1999. Vol. 5. P. 153-154.

79. A. Ehrenfeucht, K. P. Lee, G. Rozenberg. Subword complexities of various classes of deterministic developmental languages without interactions // Theor. Comput. Sci. 1975. Vol. 1. P. 59-75.

80. A. Ehrenfeucht, K. P. Lee, G. Rozenberg. Subword complexities of various classes of deterministic developmental languages with interactions // Int. J. Comput. Information Sci. 1975. Vol. 4. P. 219-236.

81. A. Ehrenfeucht, K.P. Lee, G. Rozenberg. On the number of subwords of everywhere growing DTOL languages // Discrete Math. 1976. Vol. 15. P. 223-234.

82. A. Ehrenfeucht, G. Rozenberg. A limit theorem for sets of subwords in deterministic TOL languages // Inform. Process. Lett. 1973. Vol. 2. P. 70-73.

83. A. Ehrenfeucht, G. Rozenberg. On the subword complexity of square-free DOL languages // Theor. Comput. Sci. 1981. Vol. 16. P. 25-32.

84. A. Ehrenfeucht, G. Rozenberg. On the subword complexity of DOL languages with a constant distribution // Inform. Process. Lett. 1981. Vol. 13. P. 108-113.

85. A. Ehrenfeucht, G. Rozenberg. On subword complexities of homomorphic images of languages // RAIRO Inform. Theor. 1982. Vol. 16. P. 303-316.

86. A. Ehrenfeucht, G. Rozenberg. On the size of the alphabet and the subword complexity of square-free DOL languages // Semigroup Forum. 1983. Vol. 26(3-4). P. 215-223.

87. A. Ehrenfeucht, G. Rozenberg. On the subword complexity of in-free DOL languages // Inform. Process. Lett. 1983. Vol. 17(3). P. 121-124.

88. A. Ehrenfeucht, H. P. Zeiger. Complexity measures for regular expressions // J. Comp. Syst. Sci. 1976. Vol. 12(2). P. 134-146.

89. S.B. Ekhad, D. Zeilberger. There are more than 2n/17 n-letter ternary square-free words // J. Integer Sequences. 1998. Vol. 1. #98.1.9 (electronic).

90. P. Erdos. Some unsolved problems // Magyar Tud. Akad. Mat. Kutato Int. Kozl. 1961. Vol. 6. P. 221-264.

91. R. Fagin. Probabilities on Finite Models // J. Symbolic Logic. 1976. Vol. 41 (1). P. 50-58.

92. F. Fiorenzi, P. Ochem. More on generalized repetition thresholds // Proc. 7th Int. Conf. on Words. Salerno, Italy 2009. #16.

93. P. Flajolet. Analytic models and ambiguity of context-free languages // Theor. Comput. Sci. 1987. Vol. 49. P. 283-309.

94. A. E. Frid. On uniform DOL words // Proc. 15th Int. Symp. on Theoretical Aspects of Computer Science. Berlin: Springer, 1998. P. 544-554. (LNCS Vol. 1373).

95. A. E. Frid. Sequences of linear arithmetical complexity // Thcor. Comput. Sci. 2005. Vol. 339. P. 68-87.

96. A. E. Frid, S.V. Avgustinovich. On bispccial words and subword complexity of DOL sequences // Sequences and Their Applications. London: Springer, 1999. P. 191-204.

97. P Gawrychowski, D. Krieger, N. Rampersad, J. Shallit. Finding the growth rate of a regular or context-free language in polynomial time // Proc. 12th Int. Conf. Developments in Language Theory. Berlin: Springer, 2008. P. 339-358. (LNCS Vol. 5257).

98. D. Giammarresi, A. Restivo. Two-dimensional languages // Handbook of formal languages, V.3, Ch.4. NY: Springer, 1997. P. 215-267.

99. C. D. Godsil. Algebraic combinatorics. NY: Chapman and Hall, 1993. 368pp.

100. W. H. Gottschalk, G. A. Hedlund. A characterization of the Morse minimal set // Proc. of Amer. Math. Soc. 1964. Vol. 15. P. 70-74.

101. I. Goulden, D. M. Jackson. An inversion theorem for cluster decompositions of sequences with distinguished subsequences // J. London Math. Soc. 1979. Vol. 20. P. 567-576.

102. R. L. Graham, D.E. Knuth, O. Patashnik. Concrete mathematics. 2nd Ed. Reading, MA: Addison-Wesley, 1994. xiii+657p.

103. R.I. Grigorchuk, P. de la Harpe. On problems related to growth, entropy, and spectrum in gjoup theory // J. Dynam. Contiol Systems. 1997. Vol. 3. P. 51-89.

104. C. Grillenberger. Constructions of strictly ergodic systems. I. Given entropy // Z. Wahr. verw. Geb. 1973. Vol. 25. P. 323-334.

105. U. Grimm. Improved bounds on the number of ternary square-free xoords // J. Integer Sequences 2001. Vol. 4. #01.2.7 (electronic).

106. M. Gromov. Groups of polynomial growth and expanding maps // Inst. Hautes Études Sci. Publ. Math. 1981. Vol. 53. P. 53-78.

107. H. Gruber, M. Holzer. Finite automata, digraph connectivity, and regular expression size // Proc. 35th Int. Colloq. on Automata, Languages and Programming, Part II. Heidelberg: Springer, 2008. P. 39-50. (LNCS Vol. 5126).

108. H. Gruber, M. Holzer. Tight Bounds on the Descriptional Complexity of Regular Expressions // Proc. 13th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2009. P. 276-287. (LNCS Vol. 5583).

109. J. Grytczuk. Nonrepetitive colorings of graphs a survey // Int. J. Math, and Math. Sci. 2007. Vol. 2007. Article ID 74639.

110. A. Hof, 0. Knill, B. Simon. Singular continuous spectrum for palindromic Schrddinger operators // Commun. Math. Phys. 1995. Vol. 174. P. 149-159.

111. J.E. Hopcroft. A n n log n algorithm for minimizing the states in a finite automaton // Theory of Machines and Computations. NY: Academic Press, 1971. P. 189-196.

112. L. Ilie, P. Ochem, J. Shallit. A generalization of repetition threshold // Theor. Comput. Sci. 2005. Vol. 345 (2-3). P. 359-369.

113. T. Jiang and B. Ravikumar. Minimal NFA problems are hard // SIAM Journal on Computing. 1993. Vol. 22. P. 1117-1141.

114. R. M. Jungers, V.Y. Protasov, V.D. Blondel. Overlap-free words and spectra of matrices // Theor. Comput. Sci. 2009. Vol. 410. P. 3670-3684.

115. T. Kamae and L. Zamboni. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory and Dynamical Systems. 2002. Vol. 22. P. 1191-1199.

116. T, Kamae and L. Zainboni. Maximal pattern complexity for discrete systems // Ergodic Theory and Dynamical Systems. 2002. Vol. 22. P. 1201-1214.

117. J. Karhumaki, J. Shallit. Polynomial versus exponential growth in repetition-free binary words // J. Combin. Theory. Ser. A 2004. Vol. 104. P. 335-347.

118. T. Kasami. An efficient recognition and syntax-analysis algorithm for context-free languages // Scientific report AFCRL-65-758. Air Force Cambridge Research Lab. Bedford, MA, 1965.

119. V. Keranen. Abelian squares are auoidable on 4 letters // Proc. 19th Int. Colloq. on Automata, Languages and Programming. Berlin: Springer, 1992. P. 41-52. (LNCS Vol. 623).

120. A. J. Kfoury. A linear-time algorithm to decide whether a binary word contains an overlap // RAIRO Inform. Theor. Appl. 1988. Vol. 22. P. 135-145.

121. Y. Kobayashi. Repetition-free words // Theor. Comput. Sci. 1986. Vol. 44. P. 175-197.

122. Y. Kobayashi. Enumeration of irreducible binary words // Discr. Appl. Math. 1988. Vol. 20. P. 221-232.

123. R. Kolpakov. Efficient lower bounds on the number of repetition-free words // J. Int. Sequences. 2007. Vol. 10. #07.3.2 (electronic).

124. R. Kolpakov, G. Kucherov, Y. Tarannikov. On repetition-free binary words of minimal density // Theor. Comput. Sci. 1999. Vol. 218. P. 161-175.

125. T. Kotek, J. A. Makowsky. Definability of combinatorial functions and their linear recurrence relations // Preprint. 2010. Available online at http://www.cs.teclinion.ac.il/~tkotek/pubfiles/YG70.pdf

126. G. Krause, T. H. Lenagan. Growth of Algebras and Gelfand-Kirillov Dimension. Research Notes in Math. Vol. 116. London: Pitman, 1985. 212pp.

127. D. Krieger, J. Shallit. Every real number greater than 1 is a critical exponent // Theor. Comput. Sci. 2007. Vol. 381. P. 177-182.

128. S.-Y. Kuroda. Classes of languages and linear-bounded automata // Information and Control. 1964. Vol. 7(2). P. 207-223.

129. A. P. do Lago, I. Simon. Free Burnside Semigroups // Theor. Informatics Appl. 2001. Vol. 35. P. 579-595.

130. A. Lepisto. A characterization of 2+-free words over a binary alphabet // Technical Report. Turku Centre for Computer Science, 1996. # 74.

131. M. Li, P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. 3rd Ed. Berlin: Springer, 2008. xxiii+792pp.

132. K. Lindgren, C. Moore, M. Nordahl. Complexity of two-dimensional patterns // J. Stat. Physics. 1998. Vol. 91. P. 909-951.

133. M. Lothaire. Combinatorics on words. Reading, MA: Addison-Wesley, 1983. 262p.

134. A. Mandelbrot. An informational theory of the statistical structure of language // Proc. 2nd London Symposium on Communication Theory. 1953. P. 486-504.

135. A. Mateescu, A. Salomaa. Aspects of classical language theory // Handbook of formal languages, V.l, Ch.4. Berlin: Springer, 1997. P. 175-251.

136. J. Milnor. Growth of finitely generated solvable groups // J. Diff. Geom. 1968. Vol. 2. P. 447-450.

137. M. Mohammad-Noori, J.D. Currie. Dejcan's conjecture and Sturmian words // European. J. Combin. 2007. Vol. 28. P. 876-890.

138. M. Morse, G. A. Hedlund. Symbolic dynamics // Amer. J. Math. 1938. Vol. 60. P. 815-866.

139. M. Morse, G. A. Hedlund. Symbolic dynamics II. Sturrnian trajectories // Amer. J. Math. 1940. Vol. 62. P. 1-42.

140. J. Moulin-Ollagnier. Proof of Dejean's Conjecture for Alphabets with 5, 6, 7, 8, 9, 10 and 11 Letters // Theor. Comput. Sci. 1992. Vol. 95. P. 187-205.

141. J. Noonan, D. Zeilberger. The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations // J. Difference Eq. Appl. 1999. Vol. 5. P. 355377.

142. P. Ochem. A generator of morphisms for infinite words // Proc. Workshop on words avoidability, complexity and morphisms. Turku, 2004. LaRIA Tech. Report 2004-07, P. 9-14.

143. P. Ochem. Letter frequency in infinite repetition-free words // Theor. Comput. Sci. 2007. Vol. 380. P. 388-392.

144. P. Ochem. Binary words avoiding the pattern AABBCABBA // RAIRO Inform. Theor. Appl. 2010. Vol. 44. P. 151-158.

145. P. Ochem, T. Reix. Upper bound on the number of ternary square-free words // Proc. Workshop on words and automata (WOWA'06). S.-Petersburg, 2006. #8 (electronic).

146. A.M. Odlyzko. Asymptotic enumeration methods // Handbook of combinatorics, V. 2, Ch. 22. Amsterdam: Elsevier, 1995. P. 1063-1230.

147. J.-J. Pansiot. A propos d'une conjecture de F. Dejean sur les répétitions dans les mots // Discr. Appl. Math. 1984. Vol. 7. P. 297-311.

148. J.-J. Pansiot. Complexité des facteurs des mots infinis engendrés par morphismes itérés // Proc. 11 th Int. Colloq. on Automata, Languages and Programming. Heidelberg: Springer, 1984. P. 380-389. (LNCS Vol. 172).

149. J.-E. Pin. Syntactic semigroups // Handbook of formal languages, V.l, Ch.10, Berlin: Springer, 1997. P. 679-746.

150. A.N. Plyushchenko, A.M. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x2 = x3 // Proc. 6th Int. Conf. on Words. Marceille, France. 2007. 10pp.

151. M. Rao. Last Cases of Dejean's Conjecture // Proc. 7th Int. Conf. on Words. Salerno, Italy. 2009. #115.

152. N. Rampersad. Words avoiding (7/3) -powers and the Thuc-Morse morphism // Int. J. Foundat. Comput. Sci. 2005. Vol. 16. P. 755-766.

153. C. Richard, U. Grimm. On the entropy and letter frequencies of ternary square-free words // Electronic J. Combinatorics. 2004. Vol. 11. #R14.

154. A. Restivo, S. Salemi. Overlap-free words on two symbols // Automata on Infinite Words. Ecole de Printemps d'Informatique Theorique, Le Mont Dore, 1984. P. 196206. Heidelberg: Springer, 1984. (LNCS Vol. 192).

155. A. Restivo, S. Salemi. Words and Patterns // Proc. 5th Int. Conf. Developments in Language Theory. Heidelberg: Springer, 2002. P. 117-129. (LNCS Vol. 2295).

156. P. Roth. Every binary pattern of length six is avoidable on the two-letter alphabet // Acta Inf. 1992. Vol. 29. P. 95-107.

157. G. Rozenberg. On subwords of formal languages // Proc. Int. Conf. on Fundamentals of Computation theory. Berlin: Springer, 1981. P. 328-333. (LNCS Vol. 117).

158. A. Salomaa, M. Soittola. Automata-theoretic aspects of formal power series. Texts and Monographs in Computer Science. NY: Springer, 1978. -16Spp.

159. Б. R. Scheinerman and J. S. Zito. On the size of hereditary classes of graphs // J. Comb. Theory, Ser. B. 1994. Vol. 61. P. 16-39.

160. M. P. Schutzenberger. On finite monoids having only triuial subgroups // Information and Computation. 1965. Vol. 8. P. 190-194.

161. P. Seebold Overlap-free sequences // Automata on Infinite Words. Ecole de Printeinps d'Informatique Theorique, Le Mont Dore, 1984. P. 207-215. Heidelberg: Springer, 1984. (LNCS Vol. 192).

162. R. Tarjan. Depth-first search and linear graph algoritms // SIAM J. Computing. 1972. Vol. 1. P. 146-160.

163. A. Thue. Uber unendliche Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. I. Mat-Nat. Kl. №7. Christiana, 1906. P. 1-22.

164. A. Thue. Ubcr die gegenseitige Lage gleicher Teile gewisser Zeichentreihen // Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. №1. Christiana, 1912. P. 1-67.

165. V. I. Trofimov. Growth functions of finitely generated semigroups // Semigroup Forum. 1980. Vol. 21. P. 351-360.

166. E. Vaslet. Bounds for the generalized repetition threshold // Proc. 7th Int. Conf. on Words. Salerno, Italy. 2009. #28.

167. S. Widmer. Permutation complexity of the Thuc-Morse word // 2010. Available at http://arxiv.org/PScache/arxiv/pdf/1003/1003.6123v2.pdf

168. J. Wolf. Growth of finitely generated groxips and curvature of Riemannian manifolds // J. Differential Geom. 1968. Vol. 2. P. 421-446.

169. D. H. Younger. Recognition and parsing of context-free languages in time n3 // Information and Control. 1967. Vol. 10. P. 189-208.

170. S. Yu. Regular languages // Handbook of formal languages, V.l, Ch.2. Berlin: Springer, 1997. P. 41-110.

171. S. Yu. State complexity of regular languages // J. Autom. Lang. Comb. 2001. Vol. 6. P. 221-234.

172. S. Yu. Q. Zuang, K. Salomaa, On the state complexity of some basic operations on regular languages // Theor. Comput. Sci. 1994. Vol. 125. P. 315-328.

173. Работы автора по теме диссертации

174. Е.В. Суханов, A.M. Шур. Об одном классе формальных языков // Алгебра и логика. 1998. Т.37, Ш. С. 478-492.

175. A.M. Шур. Синтаксические полугруппы избегаемых языков // Сиб. мат. журнал. 1998. Т.39, №3. С. 683-702.

176. А. М. Шур. Структура множества бескубных Z-слов в двухбуквенпом алфавите // Изв. РАН. Сер. матем. 2000. Т.64, №4. С. 201-224.

177. А. М. Шур. Комбинаторная сложность рациональных языков // Дискр. анализ и иселед. операций, Сер. 1. 2005. Т.12, Ш. С. 78-99.

178. A.M. Шур. Индексы роста языков ограниченной экспоненты // Изв. вузов. Математика. 2009. №9. С. 82-88.

179. А. М. Шур. Языки с конечным антисловарем: индексы роста и свойства графов // Известия УрГУ, Сер. Математика, Механика, Информатика. 2010. Т.12 (74). С. 220-245.

180. А. М. Шур. О вычислении параметров и типов поведения комбинаторной сложности регулярных языков // Труды ИММ УрО РАН. 2010. Т.16, №2. С. 270-287.

181. А. М. Шур. Рост языков с ограничениями на cmeiienu подслое: численные и асимптотические оценки // Докл. РАН. 2010. Т.432, №3. С. 315-317.

182. A.M. Shur. Overlap-free words and Thue-Morse sequences // Int. J. Alg. and Сотр. 1996. Vol. 6. P. 353-367.

183. A. M. Shur. Binary words avoided by the Thue-Morse sequence // Semigroup Forum. 1996. Vol. 53. P. 212-219.

184. A. M. Shur. Factorial Languages of Low Combinatorial Complexity // Proc. 10th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2006. P. 397-407. (LNCS Vol. 4036).

185. A. M. Shur. Comparing complexity functions of a language and its extendable part // Proc. 11th Mons Days of Theoretical Computer Science. IRISA-Rennes, Rennes, 2006. P. 784-788.

186. A. M. Shur. Rational approximations of polynomial factorial languages // Int. J. Foundat. Comput. Sci. 2007. Vol. 18. P. 655-665.

187. A. M. Shur. Combinatorial complexity of regular languages // Proc. 3rd International Computer Science Symposium in Russia. Berlin: Springer, 2008. P.'289-301. (LNCS Vol. 5010).

188. A.M. Shur. Comparing complexity functions of a language and its extendable part // RAIRO Inform. Theor. Appl. 2008. Vol. 42. P. 647-655.

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

190. A. M. Shur. Polynomial languages with finite antidictionaries // RAIRO Inform. Theor. Appl. 2009. Vol. 43. R 269-280.

191. A. M. Shur. On intermediate factorial languages // Discr. Appl. Math. 2009. Vol. 157. R 1669-1675.

192. A. M. Shur. Two-sided bounds for the growth rates of power-free languages // Proc. 13th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2009. P. 466-477. (LNCS Vol. 5583).

193. A.M. Shur, I. A. Gorbunova. On the growth rates of complexity of threshold languages // RAIRO Inform. Theor. Appl. 2010. Vol. 44. P. 175-192.

194. A. M. Shur. Growth rates of complexity of power-free languages // Theor. Comput. Sci. 2010. Vol. 411. P. 3209-3223.

195. A.M. Shur. Growth of power-free languages over large alphabets // Proc. 5th International Computer Science Symposium in Russia. Berlin: Springer, 2010. P. 350361. (LNCS Vol. 6072).

196. A.M. Shur. On the existence of minimal (3-powers // Proc. 14th Int. Conf. on Developments in Language Theory. Berlin: Springer, 2010. P. 411-422. (LNCS Vol. 6224).

197. A. M. Shur. On ternary square-free circular words // Electronic J. Combinatorics. 2010. (Submitted). 10PP.

198. Алгоритм А, 66, 152 А1, 154 Аг, 154 С, 124 Е, 175 О, 127 К, 63 II, 43и, 180и0, 176 Тарьяна, 35

199. Алфавит, 7 Анаграмма, 8 Антисловарь, 12редуцированный, 112 чистый, 113 языка Туэ-Морса, 65 Асимптотическое множество, 33

200. Бесповторная раскраска графа, 247 Блоковая длина, 157 Блочное представление, 85 Бор, 111. Вектор Париха, 8 Вершиназ-префиксная, 82 крайняя, 114 уровня 5, 81 Вершины эквивалентные, 110

201. Гипотеза Дежан, см. Теорема VII Граница повторяемости, 23 обобщенная, 23 экспоненциальная, 23 Граничная точка, 67 Граф компонент, 341. Дубликат, 110

202. Индекс корневого роста, 245 Индекс орграфа, 35 Индекс роста, 14

203. Равновесное разбиение, 177 Реверс слова, 8 Реверс языка, 11 Регулярные приближения, 61 Редукция антисловаря, 110 двойная,112

204. Теорема I, 14 Теорема II, 14 Теорема III, 20 Теорема IV, 20 Теорема V, 21 Теорема VI, 22 Теорема VII, 23 Теорема VIII, 24 Теорема IX, 34 Теорема X, 34 Теорема XI, 39 Теорема XII, 217 Трасса буквы, 209