Введение к работе
Актуальность темы. Теория формальных языков занимает важное место в современной математике. Она тесно связана с фундаментальными математическими дисциплинами — алгеброй, логикой и комбинаторикой — и неотделима от теории автоматов, рассматриваемых как распознаватели и преобразователи формальных языков. Многие фундаментальные алгоритмические проблемы сформулированы или легко могут быть переформулированы как проблемы о формальных языках. Не менее важны связи теории формальных языков с прикладными задачами. Здесь нужно упомянуть компьютерные науки (языки программирования и трансляторы к ним, верификация компьютерных программ и компьютерного «железа», сжатие данных, криптография, компьютерная графика), лингвистику (обработка текстов на естественных языках, компьютерный анализ семантики текста, компьютерный перевод, словари) и биологию (расшифровка и сравнительный анализ последовательностей ДНК, структура белков, модели роста и размножения живых организмов и систем, нейронные сети, внутриклеточные вычисления).
Формальные языки изучаются с разных точек зрения. Здесь можно выделить пять подходов; исследования по формальным языкам чаще всего содержат элементы нескольких подходов. При алгебраическом подходе изучаются операции над языками, уравнения в словах и языках, а также связанные с языками отображения, конгруэнции и тождества; есть и специфически «алгебраические» языки, например, язык минимальных термов произвольной фиксированной алгебры. С точки зрения логического подхода формальные языки рассматриваются как формульные множества различных логик — как правило, логики первого или второго порядка с различными ограничениями/расширениями; соответственно, общую задачу можно сформулировать как описание свойств языков посредством логических формул. Третий подход описывает свойства языков через свойства порождающих систем (например, грамматик) и распознающих или преобразующих устройств (автоматов). Четвертый подход, структурный, исследует свойства слов, составляющих языки; язык при таком подходе часто рассматривается как множество всех слов, объединенных общим структурным свойством. И, наконец, при алгоритмическом подходе исследуется разрешимость и/или вычислительная сложность алгоритмических проблем для языков или классов языков. Во всех пяти подходах активно используются комбинаторные методы.
Ключевой точкой пересечения всех подходов является количественная
характеристика формального языка над конечным алфавитом, называемая комбинаторной сложностью. Комбинаторная сложность Сь(п) — это наиболее естественная «подсчитывающая» функция, связанная с языком L: она возвращает число слов длины п в L.
При исследовании алгебр часто важно уметь оценивать рост алгебры, который есть ни что иное, как комбинаторная сложность языка минимальных термов. Подобные задачи ставились для групп, полугрупп, колец, модулей и других алгебр; их исследованием занимались, в том числе, Бабенко, Вольф, Говоров, Григорчук, Милнор, Трофимов, Уф-наровский. Самым известным результатом о росте групп является теорема Громова [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 г. в рамках логического подхода был получен изящный результат «в обратную сторону»: любая функция / : No —> No, удовлетворяющая линейному однородному рекуррентному соотношению с постоянными целыми коэффициентами, является разностью комбинаторных сложностей двух регулярных языков [27].
3К бесконечным словам применяется также топологический подход; в нем также изучается количественная характеристика, называемая энтропией и тесно связанная с комбинаторной сложностью.
общую теорию комбинаторной сложности, которая описывала бы закономерности, связывающие рост языка с его структурой, давала общие алгоритмы и формулы для оценки параметров роста языка, предсказывала количественное влияние на язык тех или иных вариаций в задающих его свойствах. Необходимость в такой теории явно назрела и данная диссертация рассматривается нами как существенный шаг к ее созданию. С этой целью была намечена описываемая ниже
Программа исследований. Далее слово «сложность» применительно к языку всегда означает комбинаторную сложность. Для того, чтобы говорить о сложности языка L, необходимо наличие алгоритма, который по описанию L и произвольному слову w отвечает на вопрос о принадлежности w к L. Наличие такого алгоритма в точности означает, что язык L — рекурсивный. Все дальнейшие рассмотрения производятся внутри класса Rec рекурсивных языков; говоря о классе языков, мы имеем в виду пересечение его с Rec. Взаимное расположение классов языков, обсуждаемых в диссертации, приведено на рис. 1. Основные объекты исследования выделены на этом рисунке жирными линиями.
При исследовании сложности языка нас интересуют не точные ее значения, а асимптотическое поведение; в частности, конечные языки рассматриваются как вырожденный случай (пересечения классов по множествам конечных языков на рис. 1 не отражены). Важнейшим параметром асимптотического поведения является индекс роста языка Gr(L) = lim ((^(п))1/-.
П—s-OO
Напомним, что 0(f) обозначает класс функций, ограниченных сверху произведением функции / на произвольную фиксированную константу, класс 17(/) определяется аналогично для оценок снизу, а в(/) = 0(f) П Г2(/).
Регулярные языки имеют множество эквивалентных определений (задаются регулярными выражениями, распознаются конечными моноидами, выражаются формулами монадической логики второго порядка, порождаются праволинейными грамматиками, распознаются конечными автоматами и др.) и образуют один из важнейших классов языков. Основной результат о сложности регулярных языков, полученный А. Саломаа и Соиттолой [39], можно, немного упростив, выразить так: для языка L найдется число г Є N, а для каждого j = 0,..., г—1 — полиномы pj (п) и алгебраические числа ay, т?, такие что ay = т? = О или 0 ^ 7j < aji и ПРИ этом
Сь(п) = рп>(п)а, + 0(7^/), где п! = п mod г. (1)
Rec Рекурсивные
CS Контекстно-зависимые
CF Контекстно-свободные
Reg Регулярные
Pref Префиксные
Fact Факториальные
FAD С конечным антисловарем
AFact Антифакториальные
АР Избегающие степени
APt Избегающие шаблоны
ААР Избегающие абелевы степени
W Языки подслов бесконечных слов
MP Языки минимальных степеней
Рис. 1: Классы языков, рассматриваемые в данной работе. Основные объекты исследования изображены жирными линиями, второстепенные — тонкими, два класса иерархии Хомского, непосредственно в работе не изучаемые, — пунктиром.
Единственным, но очень серьезным недостатком приведенного описания сложности является отсутствие связи со свойствами и параметрами задания языка L, а значит, и отсутствие алгоритмов для вычисления параметров сложности. Исключение составляет лишь фольклорный алгоритм для вычисления Gr(L) (т.е. максимума из чисел ау), имеющий полиномиальную временную сложность, но малоэффектив-
ный на практике. Взяв самый естественный способ задания регулярных языков — конечные автоматы, естественно поставить следующие проблемы.
Regl: описать свойства детерминированных конечных автоматов, отвечающие за параметры асимптотического поведения сложности;
Reg2: описать возможные колебания сложности;
Reg3: разработать алгоритмы вычисления сложности (с точностью до в-класса) по распознающему язык автомату.
Факториалъные языки определяются свойством замкнутости относи
тельно взятия под слов. Класс факториальных языков достаточно об
ширен. К нему относятся и языки минимальных термов алгебр, и язы
ки подслов бесконечных слов, и языки, задаваемые различными запре
щающими свойствами слов. Факториальный язык однозначно опре
деляется антисловарем — множеством минимальных по включению
запрещенных, т.е. не содержащихся в языке слов4. В работах [5,18]
обсуждаются факториальные языки ограниченной сложности, других
общих результатов о сложности факториальных языков нет. Для ис
следования сложности языков этого класса будем применять метод
«регулярных приближений», использующий регулярные языки, ло
кальная структура слов в которых такая же, как и в исходном языке.
Соответственно, возникают следующие проблемы.
Factl: исследовать вопросы сходимости и границы применимости метода регулярных приближений;
Fact2: найти пример языка, для которого индексы роста всех регулярных приближений можно задать формулой;
Fact3: найти преобразования языков, сохраняющие индекс роста.
Языки с конечным антисловарем лежат в пересечении двух предыду
щих классов. Именно они выступают в роли регулярных приближений
факториальных языков; основным способом задания является анти
словарь. Заслуживает упоминания алгоритм Гоулдена-Джексона [22],
позволяющий построить по антисловарю производящую функцию для
сложности языка, но слишком трудоемкий, чтобы получать хорошие
приближения сложности факториальных языков методом регулярных
приближений. Естественно возникают следующие проблемы.
4Дополнение факториального языка есть идеал свободного моноида, а антисловарь является минимальным порождающим множеством этого идеала.
FAD1: выяснить, какие функции, с точностью до в-эквивалентности, могут являться комбинаторной сложностью языка с конечным антисловарем;
FAD2: описать преобразования антисловарей, сохраняющие параметры комбинаторной сложности;
FAD3: охарактеризовать автоматы, распознающие языки с конечным антисловарем.
Языки, избегающие степени, составляют один из самых известных классов факториальных языков и рассматривались еще в работах Туэ [42,43]. Если w — слово длины п, а [3 > 1, то [3-степенью слова w называется слово
wr = w .. .ww' длины \[3п\, где w' — начальный отрезок w.
L/3J раз
Слово называется (3-свободным [(3^-свободным], если среди его под-слов нет /3-степеней [соответственно, /З'-степеней с условием [3' > (3]. Язык L{k,(3) [L(fc,/3+)] состоит из всех /3-свободных [соответственно, /3+-свободных] слов в fc-буквенном алфавите5. Поскольку при фиксированном алфавите и растущей [3 язык увеличивается, существует функция RT(fc) {граница повторяемости), разделяющая конечные и бесконечные языки рассматриваемого класса. Гипотезу о значениях функции RT(fc) (j при fc=3; ^ при k=4; -j—[ в остальных случаях) высказала Дежан в 1972 г. [15]; усилиями ряда авторов [10,13,14,30,33, 36,38] доказательство гипотезы было завершено в 2009 г. Результаты о сложности языков, избегающих степени, касаются лишь нескольких конкретных языков, см. обзор [8]. Так, оценке индекса роста языка 1_(3,2) посвящено более десяти работ; наилучшая верхняя оценка получена Ошемом и Рэем [35], а нижняя — Колпаковым [26]. Наиболее интересным результатом в этом направлении является обнаруженное Кархюмяки и Шаллитом [25] в случае бинарного алфавита «полиномиальное плато» сложности: от 1_(2, 2+) до 1_(2, 7/3) сложность остается полиномиальной и меняется очень незначительно. Сложность первого из этих языков последовательно оценивали Рестиво и Салеми, Кобаяси, Кассень, Леписто; окончательный результат получен в [24].
5Удобно считать /3+ «числом», постулируя равносильность неравенств х ^ /3 и х < /3+. Расширив таким образом множество степеней, мы далее используем только обозначение Цк,/3).
Перейдем к постановке проблем, относящихся к данной линии исследований.
API: найти свойство степеней, объясняющее наличие «полиномиального плато»;
АР2: доказать связь низкой комбинаторной и низкой алгоритмической сложности, решив проблему контекстной эквивалентности6 для языка 1_(2,2+), находящегося на «полиномиальном плато»;
АРЗ: разработать универсальные алгоритмы для получения как верхних, так и нижних оценок индекса роста;
АР4: описать индекс роста языков L(fc,/3) как функцию от к и /3;
АР5: описать структурные свойства «граничных», т.е. минимальных бесконечных для каждого алфавита языков.
Языки минимальных степеней являются антисловарями языков,
избегающих степени; они антифакториалъны (никакие два слова не
являются подсловами друг друга). Антифакториальные языки очень
тесно связаны с факториальными, но комбинаторная сложность анти-
факториальных языков ведет себя гораздо менее регулярно и совер
шенно не изучена. Здесь мы ограничимся постановкой одной пробле
мы, значительно обобщающей проблему 1.12 из [4].
MP: описать множества нулей комбинаторной сложности для языков минимальных степеней.
Цель работы. Основная цель диссертации состоит в систематическом развитии методов исследования комбинаторной сложности и применении их к ряду взаимосвязанных классов формальных языков для
определения влияния на комбинаторную сложность свойств языков и связанных с языками производных объектов;
разработки алгоритмов и получения формул оценки комбинаторной сложности для широких классов языков;
поиска связей между комбинаторной сложностью и сложностью решения алгоритмических проблем.
Конкретные цели состоят в решении пятнадцати сформулированных выше проблем.
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-68], в том числе 15 работ [44-48,50-53,56,58,60,61,63,64] — в изданиях из списка, рекомендованного ВАК. Четыре работы [44,59,63,68] являются совместными. Из работы [44] в диссертацию вошел только результат, принадлежащий автору. В статьях [59,63] автору принадлежат все доказательства и основная гипотеза (а соавтору — экспериментальная часть). Статья [68] написана в нераздельном соавторстве с А. В. Самсоновым.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, разделенных на 20 параграфов, и списка литературы (199 наименований), а также предметного указателя и указателя обозначений. Общий объем работы составляет 287 страниц.
Автор считает приятным долгом выразить глубокую благодарность Льву Наумовичу Шеврину за постоянное стимулирующее внимание и всестороннюю поддержку. С благодарным чувством я вспоминаю своего пер-
вого научного руководителя Евгения Витальевича Суханова, многолетнее сотрудничество с которым сыграло неоценимую роль в моем научном становлении. Я благодарен М. В. Волкову, А. А. Булатову и Ю. Кархюмяки за многочисленные полезные обсуждения, в немалой степени способствовавшие исследованиям, отраженным в диссертации.
