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

004614452

РОССИЙСКАЯ АКАДими*ияуЛ УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

Шур Арсений Михайлович

КОМБИНАТОРНЫЕ ХАРАКТЕРИЗАЦИИ ФОРМАЛЬНЫХ ЯЗЫКОВ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

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

2 5 но Я 2010

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

004614452

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им. A.M. Горького.

Научный консультант: заслуженный деятель науки

Российской Федерации, академик Европейской академии наук ШЕВРИН Лев Наумович

Официальные оппоненты: доктор физ.-мат. наук, профессор

АБЛАЕВ Фарид Мансурович доктор физ.-мат. наук, профессор БОКУТЬ Леонид Аркадьевич доктор физ.-мат. наук ТРОФИМОВ Владимир Иванович Ведущая организация: Московский государственный

университет им. М.В. Ломоносова

Защита диссертации состоится 23 ноября 2010 г. в 14 часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу:

620219, г. Екатеринбург, ул. Софьи Ковалевской, 16. ' . ^^

А -

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

У/

Автореферат разослан ' октября 2010 г.

Ученый секретарь диссертационного совета Д 004.006.03 кандидат физ.-мат. наук

И. Н. Белоусов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Ключевой точкой пересечения всех подходов является количественная

характеристика формального языка над конечным алфавитом, называемая комбинаторной сложностью. Комбинаторная сложность Сх(гг) — это наиболее естественная «подсчитывающая» функция, связанная с языком Ь: она возвращает число слов длины п в Ь.

• При исследовании алгебр часто важно уметь оценивать рост алгебры, который есть ни что иное, как комбинаторная сложность языка минимальных термов. Подобные задачи ставились для групп, полугрупп, колец, модулей и других алгебр; их исследованием занимались, в том числе, Бабенко, Вольф, Говоров, Григорчук, Милнор, Трофимов, Уф-наровский. Самым известным результатом о росте групп является теорема Громова [23], гласящая, что конечнопорожденная группа имеет полиномиальный рост тогда и только тогда, когда она является конечным расширением нильпотентной группы; связи роста алгебр и такой важной характеристики, как размерность Гельфанда-Кириллова, посвящена, в частности, монография Краузе и Ленагана [28].

• Со стороны логического подхода, важной характеристикой формулы (т. е. свойства) является зависимость количества неизоморфных моделей от их размера; если модель — это слово, то указанная зависимость представляет собой комбинаторную сложность языка, определяемого формулой. Необходимо отметить, что такую характеристику часто вычисляют и для других типов моделей, например, для графов; упомянем работы Боллобаша, Колайтиса, Маковского, Реньи, Спенсера, Шелаха, Эрдёша. Работа Фейгина [20], в которой было установлено, что для любой формулы первого порядка множество задаваемых ею графов имеет либо плотность 1, либо плотность 0 во множестве всех графов, положила начало масштабному исследованию 0-1 законов на графах. Активно изучается рост наследственных (замкнутых относительно порожденных подграфов) классов графов. Такие классы являются аналогами факториальных языков — языков, наиболее часто рассматриваемых с точки зрения комбинаторной сложности. Например, доказано [6,7,40], что любой класс наследственных графов имеет один из шести типов роста: константный, полиномиальный, экспоненциальный или какой-либо из трех факториальных1.

1 Логический подход породил и другую важную количественную характеристику — дескриптивную сложность, равную размеру минимальной модели фиксированного типа, описывающей заданный язык, и восходящую к колмогоровскому определению сложности, см. монографию [29].

• Грамматики тоже тесно связаны с комбинаторной сложностью: еще на заре развития теории формальных языков Хомский и Шютценбер-же [11] установили, что если язык регулярен (порождается праволи-нейной грамматикой), то его комбинаторная сложность удовлетворяет линейному однородному рекуррентному соотношению с постоянными целыми коэффициентами, т.е., в частности, имеет рациональную производящую функцию, а для языков, порождаемых однозначными контекстно-свободными грамматиками, эта производящая функция является алгебраической. Позже этот результат был дополнен Флажоле [21], показавшим, что данная функция для языка, порождаемого неоднозначной контекстно-свободной грамматикой, может быть трансцендентной2.

• Структурный подход породил сложность по подсловам для бесконечных слов; она равна комбинаторной сложности языка конечных подслов такого слова3. Первые результаты о сложности по подсловам получили еще Морс и Хедлунд в 1938-1940 гг. [31,32] (это исторически первые результаты о комбинаторной сложности), а систематическое исследование началось с серии работ Эренфойхта, Ли и Г. Розенбер-га, см., например, [16,17,19]. В блестящей работе Пансьё [37] дается полная классификация и алгоритм распознавания классов сложности по подсловам для бесконечных слов, порожденных морфизмами.

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

Результатов о комбинаторной сложности языков немало. Достаточно хорошо изучена сложность по подсловам; помимо упоминавшихся выше исследователей, следует назвать Августиновича, Аллуша, Балоха, Боллоба-ша, Грилленбергера, Кассеня, Фрид, Шаллита. В то же время, результаты, касающиеся других классов языков, фрагментарны и не складываются в

2Примечательно, что в 2010 г. в рамках логического подхода был получен изящный результат «в обратную сторону»: любая функция / : N0 —► N0, удовлетворяющая линейному однородному рекуррентному соотношению с постоянными целыми коэффициентами, является разностью комбинаторных сложностей двух регулярных языков [27].

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

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

Программа исследований. Далее слово «сложность» применительно к языку всегда означает комбинаторную сложность. Для того, чтобы говорить о сложности языка L, необходимо наличие алгоритма, который по описанию L и произвольному слову w отвечает на вопрос о принадлежности w к L. Наличие такого алгоритма в точности означает, что язык L — рекурсивный. Все дальнейшие рассмотрения производятся внутри класса Ree рекурсивных языков; говоря о классе языков, мы имеем в виду пересечение его с Ree. Взаимное расположение классов языков, обсуждаемых в диссертации, приведено на рис. 1. Основные объекты исследования выделены на этом рисунке жирными линиями.

При исследовании сложности языка нас интересуют не точные ее значения, а асимптотическое поведение; в частности, конечные языки рассматриваются как вырожденный случай (пересечения классов по множествам конечных языков на рис. 1 не отражены). Важнейшим параметром асимптотического поведения является индекс роста языка Gr(L) — lim (Cr/n))1/".

n—»oo

Напомним, что 0(f) обозначает класс функций, ограниченных сверху произведением функции / на произвольную фиксированную константу, класс ü(f ) определяется аналогично для оценок снизу, а ©(/) = 0(f) П Q(/).

• Регулярные языки имеют множество эквивалентных определений (задаются регулярными выражениями, распознаются конечными моноидами, выражаются формулами монадической логики второго порядка, порождаются праволинейными грамматиками, распознаются конечными автоматами и др.) и образуют один из важнейших классов языков. Основной результат о сложности регулярных языков, полученный А. Саломаа и Соиттолой [39], можно, немного упростив, выразить так: для языка L найдется число г £ N, а для каждого j = 0,..., г— 1 — полиномы Pj(n) и алгебраические числа Qj, 7j, такие что Qj = 7^ — О или 0 < 7j < aj, и при этом

Сi(n) - рп'(п)а+ 0(7"/), где п' = п mod г. (1)

Яес Рекурсивные АЕа« Антифакториальные

сэ Контекстно-зависимые АР Избегающие степени

СР Контекстно-свободные АР1 Избегающие шаблоны

Ией Регулярные ААР Избегающие абелевы степени

Рте! Префиксные V Языки подслов бесконечных слов

Расг Факториальные МР Языки минимальных степеней

РАО С конечным антисловарем

Рис. 1: Классы языков, рассматриваемые в данной работе. Основные объекты исследования изображены жирными линиями, второстепенные — тонкими, два класса иерархии Хомского, непосредственно в работе не изучаемые, — пунктиром.

Единственным, но очень серьезным недостатком приведенного описания сложности является отсутствие связи со свойствами и параметрами задания языка Ь, а значит, и отсутствие алгоритмов для вычисления параметров сложности. Исключение составляет лишь фольклорный алгоритм для вычисления Сг(£) (т.е. максимума из чисел а^), имеющий полиномиальную временную сложность, но малоэффектив-

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

Regí: описать свойства детерминированных конечных автоматов, отвечающие за параметры асимптотического поведения сложности;

Reg2: описать возможные колебания сложности;

Reg3: разработать алгоритмы вычисления сложности (с точностью до ©-класса) по распознающему язык автомату.

• Факториалъные языки определяются свойством замкнутости относительно взятия подслов. Класс факториальных языков достаточно обширен. К нему относятся и языки минимальных термов алгебр, и языки подслов бесконечных слов, и языки, задаваемые различными запрещающими свойствами слов. Факториальный язык однозначно определяется антисловарем — множеством минимальных по включению запрещенных, т.е. не содержащихся в языке слов4. В работах [5,18] обсуждаются факториальные языки ограниченной сложности, других общих результатов о сложности факториальных языков нет. Для исследования сложности языков этого класса будем применять метод «регулярных приближений», использующий регулярные языки, локальная структура слов в которых такая же, как и в исходном языке. Соответственно, возникают следующие проблемы.

Facti: исследовать вопросы сходимости и границы применимости метода регулярных приближений;

Fact2: найти пример языка, для которого индексы роста всех регулярных приближений можно задать формулой;

Fact3: найти преобразования языков, сохраняющие индекс роста.

• Языки с конечным антисловарем лежат в пересечении двух предыдущих классов. Именно они выступают в роли регулярных приближений факториальных языков; основным способом задания является антисловарь. Заслуживает упоминания алгоритм Гоулдена-Джексона [22], позволяющий построить по антисловарю производящую функцию для сложности языка, но слишком трудоемкий, чтобы получать хорошие приближения сложности факториальных языков методом регулярных приближений. Естественно возникают следующие проблемы.

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

РА01: выяснить, какие функции, с точностью до ©-эквивалентности, могут являться комбинаторной сложностью языка с конечным антисловарем;

РА02: описать преобразования антисловарей, сохраняющие параметры комбинаторной сложности;

РАЪЗ: охарактеризовать автоматы, распознающие языки с конечным антисловарем.

• Языки, избегающие степени, составляют один из самых известных классов факториальных языков и рассматривались еще в работах Туэ [42,43]. Если гу — слово длины п, а /3 > 1, то /3-степенью слова ю называется слово

и)13 = ■ик^лиги1 длины [/Зп], где к/ - начальный отрезок IV.

!Д| раз

Слово называется (3- свободным [у3+-свободным], если среди его под-слов нет /3-степеней [соответственно, /З'-степеней с условием /3' > /3]. Язык Ц/г,/3) [ЦА;, /3+)] состоит из всех /3-свободных [соответственно, /3+-свободных] слов в /г-буквенном алфавите5. Поскольку при фиксированном алфавите и растущей ¡3 язык увеличивается, существует функция РТ(/с) (граница повторяемости), разделяющая конечные и бесконечные языки рассматриваемого класса. Гипотезу о значениях функции (| при к=3; | при к—4; в остальных случаях) вы-

сказала Дежан в 1972 г. [15]; усилиями ряда авторов [10,13,14,30,33, 36,38] доказательство гипотезы было завершено в 2009 г. Результаты о сложности языков, избегающих степени, касаются лишь нескольких конкретных языков, см. обзор [8]. Так, оценке индекса роста языка ЦЗ, 2) посвящено более десяти работ; наилучшая верхняя оценка получена Ошемом и Рэем [35], а нижняя — Колпаковым [26]. Наиболее интересным результатом в этом направлении является обнаруженное Кархюмяки и Шаллитом [25] в случае бинарного алфавита «полиномиальное плато» сложности: от 1(2,2+) до Ц2,7/3) сложность остается полиномиальной и меняется очень незначительно. Сложность первого из этих языков последовательно оценивали Рестиво и Салеми, Кобаяси, Кассень, Леписто; окончательный результат получен в [24].

'Удобно считать /3+ «числом», постулируя равносильность неравенств х ^ /3 и х < £!+.

Расширив таким образом множество степеней, мы далее используем только обозначение

ЦМ).

Перейдем к постановке проблем, относящихся к данной линии исследований.

API: найти свойство степеней, объясняющее наличие «полиномиального плато»;

АР2: доказать связь низкой комбинаторной и низкой алгоритмической сложности, решив проблему контекстной эквивалентности6 для языка L(2,2+), находящегося на «полиномиальном плато»; АРЗ: разработать универсальные алгоритмы для получения как верхних, так и нижних оценок индекса роста; АР4: описать индекс роста языков L(Ar, ¡3) как функцию от к и /3; АР5: описать структурные свойства «граничных», т.е. минимальных бесконечных для каждого алфавита языков.

• Языки минимальных степеней являются антисловарями языков, избегающих степени; они антифакториалъны (никакие два слова не являются подсловами друг друга). Антифакториальные языки очень тесно связаны с факториальными, но комбинаторная сложность анти-факториальных языков ведет себя гораздо менее регулярно и совершенно не изучена. Здесь мы ограничимся постановкой одной проблемы, значительно обобщающей проблему 1.12 из [4].

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

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

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

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

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

Конкретные цели состоят в решении пятнадцати сформулированных выше проблем.

6 Она представляет собой вариант проблемы равенства слов и будет описана во второй части автореферата.

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

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

• Методы теории автоматов, в первую очередь — предложенные автором конструкции паутинных и обобщенных паутинных автоматов, использованные для доказательства нескольких на вид не связанных друг с другом теорем, и некоторые другие оригинальные разработки.

• Методы теории матриц, главным образом — теорема Перрона-Фробе-ниуса и близкие свойства неотрицательных матриц. В доказательствах используются также нормальная форма Жордана, теорема Гамильтона-Кэли и вычисление определителей переменного порядка.

• Методы теории графов, включая равновесные разбиения, анализ компонент сильной связности и графа компонент, а также некоторые спектральные свойства графов.

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

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

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

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

Апробация работы. Результаты диссертации были представлены на международной конференции по теории полугрупп и ее приложениям (Санкт-Петербург, 1999), международном симпозиуме по теории полугрупп (Сегед, 2000), всероссийской конференции по дискретному анализу и исследованию операций (Новосибирск, 2004), международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина (Екатеринбург, 2005), международных конференциях по теории формальных языков (Санта-Барбара, 2006; Штутгарт, 2009; Лондон, Онтарио, 2010), международных конференциях по теоретическим компьютерным наукам (Ренн, 2006; Монс, 2008; Амьен, 2010), международных симпозиумах по компьютерным наукам в России (Москва, 2008; Казань, 2010), Российско-Индийских семинарах по компьютерным наукам (Москва, 2008; Екатеринбург, 2008), Международной конференции по комбинаторной алгебре (Гуанчжоу, 2009), международном симпозиуме «Теоретические компьютерные науки — от оснований к приложениям» (Ниш, 2009), Северной конференции по комбинаторике (Рейкьявик, 2010). Автор выступал с докладами о результатах диссертации на семинарах университета Турку (2005) и университета Саймона Фрейзера (2007), на семинаре «Алгоритмические вопросы алгебры и логики» кафедры математической логики МГУ (1998, 2009) и на екатеринбуржском семинаре «Алгебраические системы» (1998—2010).

Публикации. По теме диссертации опубликовано 25 статей [44-58], в том числе 15 работ [44-48,50-53,56,58,60,61,63,64] — в изданиях из списка, рекомендованного ВАК. Четыре работы [44,59,63,68] являются совместными. Из работы [44] в диссертацию вошел только результат, принадлежащий автору. В статьях [59,63] автору принадлежат все доказательства и основная гипотеза (а соавтору — экспериментальная часть). Статья [68] написана в нераздельном соавторстве с А. В. Самсоновым.

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

Автор считает приятным долгом выразить глубокую благодарность Льву Наумовичу Шеврину за постоянное стимулирующее внимание и всестороннюю поддержку. С благодарным чувством я вспоминаю своего пер-

вого научного руководителя Евгения Витальевича Суханова, многолетнее сотрудничество с которым сыграло неоценимую роль в моем научном становлении. Я благодарен М. В. Волкову, А. А. Булатову и Ю. Кархюмяки за многочисленные полезные обсуждения, в немалой степени способствовавшие исследованиям, отраженным в диссертации.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 посвящена регулярным языкам. Согласно приведенной выше формуле (1), асимптотическое поведение сложности определяется набором из г асимптотических функций р_,(п)а™ (или, с точностью до Э-класса, пт'о£). Параметр а3 самой быстрорастущей из таких функций есть &х(Ь), а параметр т^ = Рс1 (называется полиномиальным индексом.

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

Теорема 1. Пусть А — плотный ДК А, распознающий язык Ь. Тогда

(1) если автомат А ацикличен, то язык Ь конечен;

(2) если в А найдется вершина, принадлежащая не менее чем двум циклам, то сложность Ь экспоненциальна;

(3) если в А есть циклы, но нет циклов с общей вершиной, то сложность Ь полиномиальна, причем Рс1(^) = ш—1, где т — максимальное число различных циклов, которые может пересекать маршрут в А.

Следствие 1. Для регулярного языка над к-буквенным алфавитом, распознаваемого плотным ДК А с N вершинами, за время 0(Ык) можно определить полиномиальность/жспоненциальность сложности и вычислить полиномиальный индекс в первом случае.

Затем рассматривается задача о вычислении индекса роста. Напомним, что индекс графа С? (обозначается 1пс1(С)) есть корень Фробениуса его мат-

рицы смежности7. Известно (фольклор), что индекс роста регулярного языка L равен индексу любого плотного ДКА, распознающего L. В общем случае корень Фробениуса нельзя найти точно, но можно приблизить с любой степенью точности. Соответствующее вычисление через характеристический многочлен требует fl(iV4) операций и память объемом fi(iV3). Следующая теорема исправляет ситуацию.

Теорема 2. Пусть язык L над k-буквенным алфавитом распознается плотным ДКА А с N вершинами. Существует алгоритм, который по А и числу S такому, что 0 < 5 < I, вычисляет Gr(L) с абсолютной погрешностью не более S за время 0(log(l/5)-Nk), используя дополнительную память объемом Q{}og(l/8)-N).

Упомянутый алгоритм (Алгоритм R) играет в диссертации очень важную роль. Отметим, что он пригоден для вычисления индекса произвольного орграфа, как показывает

Теорема 3. Существует алгоритм, который по орграфу Gen вершинами и то рёбрами, а также числу 5 такому, что 0 < д < 1, вычисляет Ind(G) с абсолютной погрешностью, не превосходящей 6, за время B(log(l/á)-m), используя дополнительную память объёмом 0(log(l/<$)-n).

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

Теорема 4. Пусть язык L распознается плотным ДКА А, г — наименьшее общее кратное чисел импримитивности всех значимых компонент из А. Тогда сложность языка L можно описать г асимптотическими функциями.

Найти полиномиальный индекс в общем случае позволяет

Теорема 5. Пусть язык L распознается плотным ДКА А, ат — максимальное количество компонент сильной связности индекса Gr(L), которые может пересекать маршрут в А. Тогда Pd(L) =: т—1.

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

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

до погрешности вычисления. Алгоритм вычисления Pd (L) опирается на

Предложение 1. Пусть А и В — плотные ДКА над алфавитом Е, N — максимум из количеств вершин в Л и В. Тогда сравнить числа lnd(»4) и Ind(B) можно за время 0(N4 + log(l/5(N))-N2), где 5(N) — минимальная ненулевая разность индексов ДКА с не более чем N вершинами над алфавитом Е.

Доказательство теоремы 4 позволяет вычислить параметр г, а также свести вычисление всех чисел aj и rrij к вычислению индекса и полиномиального индекса для некоторых подграфов автомата Л. Тем самым полностью решены проблемы Regí и Reg3.

Функция / колеблется, если предел limn_,00(/(n+l)//(n)) не существует. Если Bmn-oo(/(n+l)//(n)) = оо или Дшп^00(/(п+1)//(п)) = 0, то / колеблется резко. Напомним, что язык называется префиксным, если он замкнут относительно взятия префиксов слов. Колебания сложности регулярных языков (проблема Reg2) описывает

Теорема 6. Все возможные виды колебательного поведения комбинаторной сложности с различными параметрами а — Gr(L), т = Pd(L) для произвольных, префиксных и факториальных регулярных языков перечислены в следующей таблице (Р — резкие колебания, К — колебания, Н — нет колебаний):

Регулярные языки а=1, т=0 а=1,ш>0 а> 1,т=0 а>1,тп>0

Произвольные Р,К,Н р,к,н Р,К,Н Р,К,Н

Префиксные к,н к,н к,н К,Н

Факториальные к,я н к,н К,Н

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

Предложение 2. Любой регулярный язык Ь имеет тот же индекс роста и полиномиальный индекс, что и его замыкания относительно префиксов, суффиксов и подслое. Более того, из-за невозможности резких колебаний каждое из этих замыканий имеет сложность &(пРд^Сг(Ь)п).

В главе 2 изучаются общие проблемы о факториальных языках, а также языки с конечным антисловарем (КАС-языки). Начнем с описания метода регулярных приближений (§ 5). Каждый факториальный язык Ь над алфавитом Е имеет антифакториальный антисловарь М = М(£). Выбира-

ется последовательность {А^} конечных подмножеств из М такая, что

оо

Мг С М2 С ... С Мг С ... С М, I) М> = М

г=1

(например, М^ = М П и через обозначается КАС-язык с антисловарем М{. Языки Li названы регулярными приближениями языка Ь, для них выполняются условия

оо 1=1

Далее проверяется, что Сг(¿¿) -» Сг(£). Тогда ввиду теоремы 2 су-

г—»оо

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

Тем самым, частично исследована проблема РасЫ. В ней можно выделить еще два конкретных вопроса: если язык Ь полиномиален, можно ли найти степень полинома при помощи регулярных приближений? можно ли использовать для оценки сложности приближения факториального языка регулярными языками снизу? В частном случае отрицательный ответ дает

Предложение 3. Если Ь — бесконечный факториальный язык, все слова в котором являются /3-свободными для некоторого /3, то все регулярные приближения Ь экспоненциальны и все регулярные подмножества из Ь конечны.

Затем мы определяем для КАС-языков «канонические» ДКА, удобные как для построения, так и для анализа, и доказываем их основные свойства. После этого мы переходим к решению проблемы Ра^2 (§6); в качестве приближаемого языка служит язык Туэ-Морса ТМ, состоящий из всех подслов бесконечного слова Туэ-Морса, которое порождается морфизмом, действующим над бинарным алфавитом по правилу в [а) = аЬ, в(Ь) = Ьа. Антисловарь языка Туэ-Морса описывает

Предложение 4. Антисловарем языка ТМ является множество

М = {ааа, ЪЪЪ) и {св\аЬа)а, ¿вг(ЬаЬ)Ь, св\ЬаЬ)а, (1в\аЬа)Ь | г ^ 0}, где с, й — последние буквы слов вг(а) и вг(Ь) соответственно.

Антисловарь М содержит слова длины 3 и слова длины 3-2г+2 для всех г ^ 0. Обозначим Mi = М П {а, 6}^3'2'+2 и дополнительно М_i = {aaa,bbb}. Индексы роста соответствующих регулярных приближений описывает простая формула (ф обозначает золотое сечение).

Теорема 7. Пусть Li язык с антисловарем Mi. Тогда Gr(Lj) = 01/2'41.

В § 7 мы строим две двухпараметрические серии автоматов, распознающих КАС-языки — паутинные и обобщенные паутинные автоматы. С их помощью доказаны теоремы 8-10. Симметричным мы называем язык, замкнутый относительно всех автоморфизмов свободного моноида. Проблему FAD2 для языков полиномиальной сложности решает

Теорема 8. Для любого неодноэлементного алфавита Е и целого числа ш > 0 существуют как симметричные, так и несимметричные КАС-языки над £ сложности 6(пт).

Общий отрицательный ответ на упомянутый выше вопрос о вычислении полиномиального индекса дает приводимая в § 8 весьма неожиданная

Теорема 9. Для любого неодноэлементного алфавита Е и любых натуральных чисел s и т, где 1 < s ^ т, существует факториалъный язык сложности 0(п") над такой что почти все члены любой последовательности регулярных приближений этого языка имеют сложность 0(nm).

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

Предложение 5. Почти все регулярные приближения любого факто-риалъного языка сложности 0(1) имеют сложность 0(1).

Наконец, в § 9 КАС-языки, распознаваемые паутинными и обобщенными паутинными автоматами, удалось использовать для приближения фак-ториальных языков снизу, тем самым положительно решив второй вопрос о границах применимости регулярных приближений и завершив исследование проблемы Facti. А именно, мы доказали Теорему 10, гласящую, что некоторые языки, заданные весьма естественными условиями, имеют промежуточную (т. е. более чем полиномиальную, но менее чем экспоненциальную) сложность. Факториальные языки такой сложности редко за-

даются простыми условиями, так что полученные нами две серии языков представляют немалый интерес. Опишем одну из них. Любое слово можно разбить на минимальное число блоков, состоящих из одинаковых букв. Языки упомянутой серии состоят из всех слов над фиксированным алфавитом, разбиения которых удовлетворяют двум условиям:

- буквы, образующие блоки, сменяют друг друга в соответствии с каким-либо циклическим порядком;

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

В § 10 описываются преобразования, требуемые в проблеме ГасгЗ, а именно, сужение языка до его продолжаемого (вправо, влево или в обе стороны) подмножества. Слово ю £ Ь продолжаемо в Ь, если существуют сколь угодно длинные слова и и и такие, что иьт е Ь. Правая и левая продолжаемость определяются аналогично. Множества таких слов ги обозначаются через е(£), ге(£) и 1е(£) соответственно.

Теорема 11. Сг(Ь) = Сг(ге(£)) = Сг(е(£)) для любого факториалъного языка Ь.

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

Теорема 12. Каждая из функций Сх/(тг)/Сге^)(п), Сх,(тг)/Се(£)(тг) может быть ограниченной, функцией полиномиального роста или функцией промежуточного роста.

Последний во второй главе параграф, § 11, посвящен КАС-языкам экспоненциальной сложности и распознающим их каноническим автоматам. В центре внимания находится понятие С-графа — объединения нетривиальных компонент сильной связности канонического автомата.

Мы нашли два преобразования (редукция и чистка), сокращающие общий размер антисловаря и сохраняющие ©-класс сложности экспоненциального КАС-языка, тем самым частично решив проблему ЕА02. Далее, мы построили Алгоритм С, который по любому нетривиальному сильно связному орграфу определяет, является ли он компонентой сильной связности некоторого канонического автомата, а в случае положительного ответа

строит соответствующий КАС-язык. Таким образом, получено алгоритмическое описание канонических автоматов для любого фиксированного алфавита на языке запрещенных объектов — компонент сильной связности (проблема FAD3). Используя это описание, для бинарного алфавита и «маленьких» канонических автоматов мы перечисляем все возможные С-графы и, следовательно, все возможные индексы роста (Теорема 13, решающая проблему FAD1 для узкого частного случая).

Для более широких частных случаев перечислительное описание индексов роста уже вряд ли возможно, и здесь целесообразно обратиться к алгоритмическому описанию. На основе алгоритма С построен Алгоритм G, который по нетривиальному сильно связному орграфу позволяет выяснить, можно ли этот орграф достроить до канонического автомата, не увеличив индекс роста. С помощью этого алгоритма можно построить КАС-язык с заданным индексом роста (частное алгоритмическое решение проблемы FAD1). Вопрос об алгоритме, доказывающем, что данное алгебраическое число не является индексом роста КАС-языка, остается открытым. Более того, этот вопрос, по-видимому, очень сложен. Он не может быть решен перебором орграфов при помощи алгоритма G ввиду следующего найденного нами «неприятного» свойства.

Предложение 6. Алгебраическое число степени г может являться индексом роста КАС-языка над алфавитом Б, но при этом не быть индексом никакого г-вершинного орграфа, являющегося компонентой сильной связности плотного ДКА, распознающего КАС-язык над Е.

В конце § 11 изучается взаимное расположение компонент сильной связности в канонических автоматах. Напомним, что взаимное расположение этих компонент определяет, в частности, полиномиальный индекс регулярного языка (теорема 5). С помощью ряда примеров мы доказываем следующие предложения, демонстрирующие, что с точки зрения комбинаторной сложности КАС-языки образуют представительный подкласс класса Reg.

Предложение 7. (1) Над бинарным алфавитом существуют как симметричные, так и несимметричные КАС-языки сложности вида Q(na"), где а > 1.

(2) Над k-буквенным алфавитом при к > 3 существуют КАС-языки сложности вида Q(nk~2ап), где а > 1.

Предложение 8. (1) Над бинарным алфавитом существует КАС-язык, С-граф канонического автомата которого имеет не является слабо связным.

(2) Над бинарным алфавитом существует КАС-язык, в каноническом автомате которого нетривиальные компоненты сильной связности образуют ромб относительно достижимости.

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

В § 12 мы решаем проблему API. Экспонентой слова называется отношение его длины к его минимальному периоду8. Экспоненту мы называем k-стабильной, если над к-буквенным алфавитом существует слово экспоненты /3, которое можно продолжить до бесконечного в обе стороны /3-свободного слова. Связь fc-стабильности и сложности иллюстрируется следующим замечанием: если экспонента (3 не fc-стабильна, то e(L(fc,/3+)) = e(L(A;,/3)), откуда Gr(k, /3+) = Gr(fc,/3) по теореме 11. Следующая теорема показывает, что не 2-стабильные экспоненты в точности выделяют «полиномиальное плато» (экспоненты /3 < 2 соответствуют случаю конечных языков). Тем самым, проблема API решена.

Теорема 14. Экспонента /3 является 2-стабильной тогда и только тогда, когда (3 = 2 или (3 ^ 7/3.

Следствие 2. Для любого (3 € [2+, 7/3] язык L(2, ¡3) имеет субэкспоненциальную сложность.

Последнее утверждение впервые было доказано Кархюмяки и Шалли-том [25]. Также в [25] доказано, что сложность языка L(2, (7/3)+) экспоненциальна, т. е. «плато» заканчивается с переходом через степень 7/3. Однако последний результат немедленно вытекает из следующей теоремы, опубликованной в [46] на 4 года раньше.

Теорема 15. Существует морфизм / : {1,2,3}* —> {а, Ь}*, отображающий любое 2-свободное слово в (7/3)+-свободное.

В § 13 приведено решение проблемы АР2. Контекстом слова и в факто-риальном языке L называется пара слов (iui, w<z) такая, что w\uw^ е L. Слова и, v G L по определению эквивалентны, когда множества их контекстов совпадают. Проблема контекстной эквивалентности состоит в проверке

8Слово длины п в алфавите Е есть функция w : {1,...,п} —<■ Е; периоды и> суть периоды этой функции.

эквивалентности заданных слов ину9. Эта проблема сложна и мало изучена, за исключением регулярных языков и языков подслов некоторых бесконечных слов. Решение проблемы контекстной эквивалентности для языка 1(2,2+) (язык бинарных сильно бескубных слов) оказывается технически сложным и вскрывает нетривиальную структуру данного языка, но получаемый в итоге Алгоритм Е очень быстр.

Теорема 16. Контекстная эквивалентность двух произвольных бинарных сильно бескубных слов может быть проверена за линейное время от суммы их длин.

Следствие 3. Проблема равенства слов в синтаксическом моноиде языка Ц2,2+) решается за линейное время от суммы длин слов.

Доказательство теоремы 16 опирается на линейный алгоритм проверки односторонней и двусторонней продолжаемости сильно бескубного слова (Теорема 17), на Предложение 9 о неэквивалентности двусторонне продолжаемых слов, на критерий эквивалентности односторонне продолжаемых слов (Теорема 18) и на ряд технических утверждений, обеспечивающих сравнение множеств контекстов двух слов за линейное время в случае, когда известно, что эти множества конечны. Ключевая роль в доказательстве принадлежит морфизму Туэ-Морса.

Данные проблемы имеют столь низкую временную сложность во многом благодаря тому, что морфизм Туэ-Морса является единственным нетривиальным морфизмом, сохраняющим язык Ц2,2+) (т.е. полугруппа всех морфизмов, сохраняющих Ц2,2+), порождается морфизмом Туэ-Морса и автоморфизмами, см. [9,41]). Это свойство выполняется для всех бинарных /3-свободных языков при /3 € [2+,7/3], поэтому идею решения проблемы контекстной эквивалентности можно перенести на любой из указанных языков. При этом описание решения станет еще более громоздким, но низкая временная сложность сохранится.

Разработке алгоритмов оценки сложности (проблема АРЗ) посвящены §§ 14-15. Алгоритм для верхней оценки, использующий регулярные приближения, должен состоять из трех шагов:

(1) вычисление антисловаря регулярного приближения;

(2) построение плотного автомата по антисловарю;

(3) вычисление индекса роста регулярного приближения по автомату.

9Эта проблема близка к проблеме равенства слов в моноиде, называемом синтаксическом моноидом языка Ь.

Эффективное выполнение третьего шага обеспечивает алгоритм R, а второго — модификация известного алгоритма Ахо-Корасик для поиска в тексте. Разумно организовав перебор для выполнения первого шага, мы получаем алгоритм, вычисляющий значительно лучшие верхние оценки, чем известные аналоги [34,35]. Основной недостаток этого прямолинейного алгоритма состоит в том, что размер алфавита отражается множителем к\ на требуемой памяти и времени работы, что ограничивает применимость алгоритма алфавитами в 2-4, максимум 5 букв.

Главным достижением, отраженным в § 14, является построение Алгоритма U для вычисления верхних оценок, опережающего прямолинейный алгоритм как по времени, так и по памяти примерно в к\ раз. Выигрыш достигается за счет использования симметрии изучаемых языков: вместо автомата оказывается возможным эффективно построить «фактор-автомат» — гораздо меньший орграф с тем же индексом. Практическую эффективность алгоритма U демонстрирует, например, табл. 1, а теоретическую описывает

Теорема 19. Пусть М — аптисловарь языка L(/c, 0), Мт — его подмножество, состоящее из всех слов с периодом, не превосходящим т, а N = (т/ЗСц/с1(з) (тп))/к\. Тогда фактор-автомат для вычисления индекса роста регулярного приближения Lт (&,/?) содержит 0(N) вершин и может быть построен по тройке чисел (m,(3,k) за время 0(N log N), используя дополнительную память объемом O(N).

Для оптимизации построения антисловаря дополнительно используется

Теорема 20. Пусть 1 < /3 < 2, ху € L(к,(3). Тогда если /3-степень (ху)13 не является минимальной, то (хусодержит (3-степень (zt)13 такую, что \(ztf\ < [а;у[; более того, \zt\ < \у\ при 0 < (4/3)+ и \zt\ < |у| при 0<(5/4)+.

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

Теорема 21. Пусть /3 > 2, Lm - регулярное приближение языка L(&,/3), а построенный по нему алгоритмом U фактор-автомат имеет лишь одну неодноэлементную компоненту сильной связности10. Тогда для любого

10Вычисление индекса, роста языка t*m алгоритмом U включает в себя разбиение фактор-автомата на компоненты сильной связности, так что проверка этого условия не требует дополнительных вычислений. Представляется вероятным, что это условие выполняется всегда, но пока этот факт не доказан.

числа 7 такого, что 7 + ^ Сг(Ьт), выполняется неравенство

Идея подобной «конвертации» верхней оценки впервые была предложена Колпаковым; в [1,26] были получены неплохие нижние оценки индексов роста языков 1(3,2) и 1(2,3). Недостатками метода Колпакова являются, в частности, большая вычислительная сложность и отсутствие универсальности (каждый язык требует отдельного вывода формулы для нижней оценки). Наш метод лишен этих недостатков: он универсален (для вычисления 7 даже не нужно знать, сложность какого языка мы оцениваем; нужен только параметр то и верхняя оценка, полученная для этого параметра), а значение оценки с любой наперед заданной степенью точности можно вычислить за почти константное время. В частных случаях, рассмотренных Колпаковым, мы получили в несколько раз более точные оценки.

Практическая реализация алгоритма и и приложения к нему для вычисления нижних оценок позволила значительно улучшить все известные оценки индексов роста языков, избегающих степени, и получить очень много ранее не известных оценок. Выборка численных результатов, полученных с помощью персонального компьютера с тактовой частотой ЗГГц и 2Гб памяти, приведена в табл. 1. Все оценки округлены с точностью до 7 знаков после запятой. Если приведена только одна оценка, значит, эти 7 знаков у верхней и нижней оценок совпадают.

Таблица 1: Оценки индексов роста языков, избегающих степени /3^2.

к /3 оценки 2 2+ 3 3+

2 (7/3)+ 1.2206318-1.2206448 4 2.6215080 3.7284944 3.7789513 3.9487867

2 (5/2)+ 1.3662971-1.3663011 5 3.7325386 4.7898507 4.8220672 4.9662411

2 3 1.4575732-1.4575773 6 4.7914069 5.8277328 5.8503616 5.9760100

2 3+ 1.7951246-1.7951264 7 5.8284661 6.8537250 6.8705878 6.9820558

2 4 1.8211000 8 6.8541173 7.8727609 7.8858522 7.9860649

2 4+ 1.9208015 9 7.8729902 8.8873424 8.8978188 8.9888625

3 2 1.3017597-1.3017619 10 8.8874856 9.8988872 9.9074705 9.9908932

3 2+ 2.6058789-2.6058791 11 9.8989813 10.9082635 10.9154294 10.9924142

3 3 2.7015614-2.7015616 12 10.9083279 11.9160348 11.9221106 11.9935831

3 3+ 2.9119240-2.9119242 13 11.9160804 12.9225835 12.9278022 12.9945010

3 4 2.9172846 14 12.9226167 13.9281788 13.9327109 13.9952350

3 4+ 2.9737546 15 13.9282035 14.9330157 14.9369892 14.9958311

малые алфавиты большие алфавиты

Из всех языков, избегающих степени, наибольший интерес с точки зрения сложности представляют граничные языки; при этом на основе полу-

ченных численных оценок можно с уверенностью сказать, что именно для таких языков последовательность индексов регулярных приближений демонстрирует самую медленную сходимость. Граничным языкам посвящен § 16. Для их анализа удобно ввести понятие т-повтора — слова вида и13 из антисловаря, такого что \vP\ — |u| = m. Через [Sm\k) будем обозначать то регулярное приближение граничного языка L(к,0), чей антисловарь состоит из всех r-повторов при г < т.

Вначале мы замечаем, что индексы роста всех языков L1-2' (к) равны, а схожесть структуры этих языков наглядно проявляется при помощи предложенного нами цилиндрического представления слов. Эта схожесть сохраняется и для более точных регулярных приближений, как показывает

Теорема 22. Для любого фиксированного натурального m ^ 3 существует конечный набор двумерных слов размера 0(т) х 0(т) над вспомогательным алфавитом таких, что для любого к > 2т—3 слово принадлежит языку L*-"1' (к) тогда и только тогда, когда его цилиндрическое представление не имеет подслое из данного набора.

Мы вычисляем этот набор для т = 3,4,5,6ис его помощью вычисляем индексы роста языков для разных к. Анализируя как эти резуль-

таты, так и численные оценки, полученные общим способом при помощи алгоритма U, мы в итоге формулируем следующую гипотезу.

Гипотеза 1. Последовательность индексов роста, граничных языков над k-буквенными алфавитами имеет предел à та 1.242 при к —► оо.

Гипотеза 1, вытекающая из полученного нами решения проблемы АРБ, усиливает гипотезу Дежан11 и опровергает существовавшее предположение о том, что с ростом алфавита индексы роста граничных языков стремятся к единице. Авторы работы [14] прямо указывают, что полученные ими в ходе проверки гипотезы Дежан результаты говорят в пользу гипотезы 1.

С помощью алгоритма U и теоремы 21 были получены численные оценки индексов роста языков L(fc, /9) для широкого спектра алфавитов и степеней. В результате появилась возможность представить поведение индекса роста как функции а(к, /3), отметив ряд закономерностей. Эти закономерности мы описали и объяснили в § 17, выведя несколько асимптотических формул для а(к, (3) и тем самым решив проблему АР4. Для случая ¡3 > 2 верна

11Гипотеза 1 впервые опубликована в [59], до того, как гипотеза Дежан была полностью подтверждена.

Теорема 23. Пусть (3 € [п+, п+1], где п ^ 2 - целое число. Тогда

а

ги а\ / ^ ~ А-п-1 + рг — А-1П-5 + ^( — 1 )>

Следствие 4. Для любого фиксированного ¡3 ^ 2+ разность (к—а(к, (3)) стремится к нулю с полиномиальной скоростью при к —» оо. Для любого фиксированного к > 2 эта же разность стремится к нулю с экспоненциальной скоростью при ¡3 —> оо.

Следствие 5. Дри фиксированном к изменение индекса роста внутри промежутка [п+, п+1] мало по сравнению со скачками на краях этого промежутка, а именно,

Следствие 6. При любом к величина скачка функции а(к,/3) в точке (3 — 2 больше единицы, а именно, а(к, 2+) - а(к,2) = 1 + р- + О(р-).

Следствие 7. В точке (к, 2) увеличение к на единицу и добавление «+•» к степени влияют на индекс роста почти одинаково, а именно,

Приведенные выше асимптотические формулы пригодны и для небольших к: они очень хорошо предсказывают значения из табл. 1. Для /3 < 2 основными результатами § 17 являются две гипотезы, высказанные на основе доказанных частных результатов и численных оценок.

Гипотеза 2. Для фиксированного целого п > 3 и произвольного целого к > п выполнены равенства

а(к,п+)-а(к,п) = ^ а(к,п+1) - а(к,п+) = р^пг

Проанализируем поведение функции а(к, (3) в точке [3 — 2. Предложение 10. Справедливы равенства

а{к+1,2)-а(к,2+) =

та—1 к

Гипотеза 2 предсказывает, что свойствами, найденными для точки /?=2, обладают все точки ¡3 = ПРИ 2 < п < к: из гипотезы 2 вытекает

Следствие 8. Пусть п,к — натуральные числа, 2 < п < к. Тогда

-а(к=1+0(£)

Вторая гипотеза описывает поведение функции а (к, ¡3) в случае, когда ¡3 зависит от к таким образом, что получается язык, близкий к граничному.

Гипотеза 3. Для произвольного целого п ^ 0 существуют пределы

ап = и ^ = иЙ0а(к>

При этом а'п+1 = ап и ап+1 — а„ > 1.

Заметим, что согласно гипотезе 1 ао « 1.242.

В § 18, заключительном в главе 3, мы демонстрируем, что описанный в данной главе метод оценки индекса роста можно применить, с незначительными модификациями, для изучения классов факториальных языков, родственных классу АР. Мы имеем в виду класс APt языков, избегающих шаблоны, и класс ААР языков, избегающих абелевы степени. Оба этих класса состоят из симметричных языков, поэтому для получения верхних оценок индекса роста можно применять алгоритм II; нужно только модернизировать его первый шаг, предложив эффективную процедуру перебора кандидатов в антисловарь соответствующего языка взамен использовавшейся для языков класса АР. При этом в случае абелевых степеней можно вести речь об универсальной процедуре перебора, которую мы и приводим. В случае шаблонов требуется «индивидуальный подход» к каждому языку, поэтому мы сосредоточили внимание на языке, для которого оказалось возможным задействовать механизм двусторонней оценки, доказав аналог теоремы 21.

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

Чтобы не рассматривать «тривиальные» нули комбинаторной сложности языков минимальных степеней (например, не бывает квадратов нечетной длины), удобно рассматривать вариант комбинаторной сложности, который мы назвали корневой сложностью и обозначили за Нк,р(п): вместо подсчета слов и" подсчитываются слова и (их столько же). Если слово и13 принадлежит антисловарю языка \-(к,(3), то очевидно и € 1_(/с, ¡3), поэтому корневая сложность антисловаря не превосходит сложности самогб языка. Накопленный экспериментальный материал свидетельствует о близости индексов роста этих функций для всех языков, избегающих степени.

Корневая сложность антисловаря изменяется намного менее регулярно, чем комбинаторная сложность соответствующего факториального языка, поэтому мы в основном ограничиваемся изучением ее в рамках проблемы МР. Нули функции В.к,р(п) — это в точности те периоды, которые не может иметь минимальная /^-степень в /с-буквенном алфавите.

В § 19 изучается функция Я3)2(п), поведению и нулям которой посвящена проблема 1.12 из [4]. Минимальные квадраты тесно связаны с 2-свободными циклическими словами, как показывает

Предложение 11. Слово и2 является минимальным квадратом тогда и только тогда, когда циклическое замыкание слова и 2-свободно.

Поэтому основной результат параграфа мы сформулировали и в терминах циклических слов, и в терминах корневой сложности.

Теорема 24. (1) 2-свободное циклическое слово длины п в трехбуквенном алфавите

(1а) существует тогда и только тогда, когда п {5,7,9,10,14,17};

(16) единственно с точностью до переименования букв тогда и только тогда, когда п € {1,2,3,4,6,8,11,12,13,15,16,21}.

(2) Число 2-свободных циклических слов длины п в трехбуквенном алфавите зависит от п экспоненциально.

Следствие 9. Функция экспоненциальна, причем

и Е-з^п) ^ 12 в остальных случаях.

Утверждение (1а) теоремы 24 впервые доказано Карри [12] с использованием довольно длинного компьютерного перебора. Соответственно, доказа-

тельство Карри практически ничего не говорит ни о структуре тернарных 2-свободных циклических слов, ни о причинах того, что именно приведенные в (1а) длины являются «исключительными». Мы приводим бескомпьютерное доказательство, которое, во-первых, позволяет параллельно доказать все утверждения теоремы, а во-вторых, сводит поиск 2-свободных циклических слов к поиску маршрутов заданного веса во взвешенном графе наглядно демонстрируя все исключения.

В завершающем диссертацию § 20 описаны нули произвольной функции Як,1з{п) (результаты сформулированы в терминах разрешенных/запрещенных периодов минимальных степеней). Напомним, что слова и и V называются сопряженными, если и = у г, V = гу для некоторых у и г. Степени над бинарным алфавитом описывает

Теорема 25. Бинарная минимальная (З-степенъ с периодом р

(1) существует для любого натурального р, если ¡3 > (5/2)+;

(2) существует для любого натурального р кроме 5,9,11,17 и 18, если е [(7/3)+, 5/2];

(3) является степенью слова, сопряженного с одним из слов вт(а), вт(Ь), вт{аЬа), вт{ЬаЪ) для некоторого то ^ 0, где в — морфизм Туэ-Морса, если /3 £ [2+ (7/3)]; в частности, р - 2т или р = 3 • 2т.

Доказывая второе, самое сложное утверждение теоремы 25, мы попутно завершаем описание возможных длин бинарных /?-свободных циклических слов, дополнив результаты Аберкане и Карри [2,3] для других значений 0. Отметим, что списки исключений в утверждении (2) теоремы 25 и в приводимом ниже следствии немного не совпадают.

Следствие 10. Пусть ¡3 € [(7/3)+, 5/2]. Бинарное /?-свободное циклическое слово длины п существует для всехп, кроме 5,9,11,18.

Далее мы переходим к алфавитам из более чем двух букв.

Теорема 26. Любое натуральное число является периодом минимальной ¡3-степени в к-буквенном алфавите, если (1) к ^ 4 и ¡3 = 2; или (2) к ^ 3 и 0 ^ 2+; или (3) ¡3 > ИТ([/Ь/2]).

С другой стороны, при /3 » РТ(/с) запрещенные периоды существуют. Некоторые из них перечислены в следующей теореме.

Теорема 27. В к-буквенном алфавите не существует минимальных ¡З-степеней с периодом р, если выполнено какое-либо из трех приводимых ниже условий.

(1) Р € а Р удовлетворяет одному из условий

(а) к <р < С^1] (fc-1) и р mod к ф О,

(б) р £ [{т—2)(к+1)+1,т(к—1)-1] для некоторого целого т > и р mod к ф О,

(в) р — 3fc или р = 4к;

(2) ß € |г|]> аре [(m-l)(fc+l)+l,m(A;-2)-l] для некоторого целого т. £ [2, к-2];

(3)k>9,ßG [Цг|+, frf] ир = 2к-7.

Следствие 11. Я^и ß 6 fr^], а также при ß е [fr|+> frf] е

случае к ^ 7, минимальные ß-степени с периодом р в к-буквенном алфавите не существуют для Q(k2) различных значений р.

Поскольку для любой тройки (k,ß,p) существование /^-степени в к-буквенном алфавите с периодом р алгоритмически проверяемо, к доказанным теоремам можно добавить результаты компьютерной проверки, получая в итоге следующую общую гипотезу о существовании и распределении запрещенных периодов.

Гипотеза 4. Пусть к ^ 3 и ß > RT(/c).

(1) Для пары (к, ß) существует хотя бы один запрещенный период если и только если выполнено одно из условий

(а)

(б) к = 6 и ß G f], или к > 7 u ß G |г|];

(2) Множество запрещенных периодов для пары (к, ß) конечно.

(3) При k ^ 9 запрещенный для пары (к, ß) период не превосходит к(к—1)—1.

Заметим, что, во-первых, в первом утверждении гипотезы 4 указаны те же интервалы значений ß, что и в теореме 27, а во-вторых, по теореме 27 (1) период fc(fc-l)-l запрещен для любого ß <

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

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

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

[3] 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.

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

[5] J. Balogh, B. Bollob&s. Hereditary properties of words // RAIRO Inform. Theor. Appl. 2005. Vol. 39. P. 49-65.

[6} J. Balogh, B. Bollobas, D. Weinreich. The speed of hereditary properties of graphs // J. Comb. Theory, Ser. B. 2000. Vol. 79. P. 131-156.

[7] J. Balogh, B. Bollobas, D. Weinreich. The penultimate rate of growth for graph properties // European J. Comb. 2001. Vol. 22. P. 277-289.

[8] J. Berstel. Growth of repetition-free words - a review // Theor. Comput. Sci. 2005. Vol. 340(2). P. 280-290.

[9] J. Berstel, P. S6£bold. A characterization of overlap-free morphisms // Discrete Appl. Math. 1993. Vol. 46(3). P. 275-281.

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

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

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

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

[14] 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

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

[16] 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.

[17] 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.

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

[19] 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.

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

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

[22] 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.

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

[24] 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.

[25] J. Karhumâki, J. Shallit. Polynomial versus exponential growth in repetition-free binary words // J. Combin. Theory. Ser. A 2004. Vol. 104. P. 335-347.

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

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

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

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

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

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

[32] M. Morse, G. A. Hedlund. Symbolic dynamics II. Sturmian trajectories // Amer. J. Math. 1940. Vol. 62. P. 1-42.

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

[34] J. Noonan, D. Zeilberger. The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations // J. Difference Eq. Appl. 1999. Vol. 5. P. 355-377.

[35] P. Ochem, T. Reix. Upper bound on the number of ternary squarefree words // Proc. Workshop on words and automata (WOWA'06). S.Petersburg, 2006. #8 (electronic).

[36] 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.

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

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

[39] A. Salomaa, M. Soittola. Automata-theoretic aspects of formal power series. Texts and Monographs in Computer Science. NY: Springer, 1978. -168pp.

[40] E. R. Scheinerman, J. S. Zito. On the size of hereditary classes of graphs // J. Comb. Theory, Ser. B. 1994. Vol. 61. P. 16-39.

[41] P. Séébold. Overlap-free sequences // Automata on Infinite Words. Ecole de Printemps d'Informatique Theorique, Le Mont Dore, 1984. P. 207-215. Heidelberg: Springer, 1984. (LNCS Vol. 192).

[42] A. Thue. Über unendliche Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. №7. Christiana, 1906. P. 1-22.

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

[44] Е. В. Суханов, А. М. Шур. Об одном классе формальных языков Ц Алгебра и логика. 1998. Т.37, №4. С. 478-492.

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

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

[47] A.M. Шур. Комбинаторная сложность рациональных языков Ц Дискр. анализ и исслед. операций, Сер. 1. 2005. Т.12, №2. С. 78-99.

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

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

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

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

[52] А. М. Shur. Overlap-free words and Thue-Morse sequences // Int. J. Alg. and Сотр. 1996. Vol. 6. P. 353-367.

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

[54] 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).

[55] 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.

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

[57] 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).

[58] A.M. Shur. Comparing complexity functions of a language and its extendable part // RAIRO Inform. Theor. Appl. 2008. Vol. 42. P. 647655.

[59] 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.

[60] A. M. Shur. Polynomial languages with finite antidictionaries // RAIRO Inform. Theor. Appl. 2009: Vol. 43. P. 269-280.

[61] A. M. Shur. On intermediate factorial languages // Discr. Appl. Math. 2009. Vol. 157. P. 1669-1675.

[62] 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).

[63] 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.

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

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

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

[67] A.M. Shur. On ternary square-free circular words // Electronic J. Combinatorics. 2010. Vol. 17 (to appear). 11PP. Available at http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.5759vl.pdf

[68] A.V. Samsonov, A.M. Shur. On Abelian repetition threshold // Proc. 13th Mons Days of Theoretical Computer Science. Univ. de Picardie Jules Verne, Amiens, 2010. P. 1-11.

Подписано в печать 04.10.2010. Формат 60 x 84'/ю- Бумага офсетная. Усл. печ. л. 2,0. Тираж 100 экз. Заказ

№

Издательство Уральского университета. 620083, Екатеринбург, пр.Ленина, 51. Отпечатано в ИПЦ «Издательство УрГУ». 620083, Екатеринбург, ул.Тургенева, 4.

Введение

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.

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