*** Научная проблема ***

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

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

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

Одна из основных тем проекта — вопросы сложности в классических семействах конечных автоматов: двухсторонних конечных автоматах (2DFA, 2NFA), древоходных автоматах и графоходных автоматах. Двухсторонние автоматы — широко известная модель вычисления, распознающая только регулярные языки. Древоходные автоматы — это обобщение двухсторонних: они ходят уже не по строке, а по дереву. Наконец, графоходные автоматы ходят по графам произвольного вида — это модель робота в лабиринте, а также более общая модель в теории автоматов. В качестве меры сложности выступает прежде всего число состояний, нужное автомату, чтобы решать ту или иную задачу; другая возможная мера сложности — размер наименьшего объекта (строки, дерева, графа), принимаемого данным автоматом. Немало вопросов о сложности этих автоматов остаются открытыми. Например, знаменитая задача о числе состояний, необходимом для детерминизации двухсторонних автоматов, поставленная Сакодой и Сипсером (1978), остаётся нерешённой, несмотря на продолжающиеся исследования в этой области. Для древоходных и для графоходных автоматов остаётся неизвестным ряд теоретических свойств, таких как замкнутость или незамкнутость класса недетерминированных автоматов относительно дополнения, вопросы, связанные с однозначностью вычислений, и др. В проекте предполагается развить теорию таких автоматов, получить результаты об их сложности, сравнить распознавательную силу разных моделей и подобраться к решению известных задач в этой области.

Другое направление проекта относится к автоматам на бесконечных строкаx — моделям вычислительных устройств, работающих вечно и взаимодействующих со внешней средой — так называемых _реактивных систем_. Эти модели важны в теории и технологии разработки аппаратных и программных систем с конечным множеством состояний, опирающейся на логические и алгоритмические методы анализа поведения таких систем. Теория реактивных систем основана на логических и топологических классификациях соответствующих языков. Логические классификации используются как языки спецификаций поведения систем, а топологические классификации описывают особенности их поведения на бесконечных строках. Одна из задач проекта — исследование взаимосвязей между логическими и топологическими классификациями.

Ещё одна разновидность сложности в теории формальных языков — это комбинаторная сложность конечных и бесконечных строк, изучаемая в _комбинаторике слов_. Современное состояние этой области изложено в ряде книг, написанных группой авторов под псевдонимом Lothaire (Combinatorics on Words, 1997; Algebraic Combinatorics on Words, 2002; Applied Combinatorics on Words, 2005). Комбинаторика слов имеет много связей с разными областями, не только в математике и информатике, но также и с другими науками. В математике такие области включают алгебру (например, комбинаторная теория групп и полугруппы), символьные динамические системы и теорию чисел. Области применения в других науках включают, например, кристаллографию и биохимию (последовательности ДНК). Комбинаторика слов особенно связана с теоретической информатикой, в частности, с теорией автоматов и формальных языков, строковыми алгоритмами (поиск подстрок, сжатие данных и т.д) и биоинформатикой.

Следующая часть проекта посвящена сложности различных классов формальных грамматик. Для основной модели грамматик, известной под названием бесконтекстных грамматик, известно много (и немало преподаётся в университетских курсах). Но теория формальных грамматик не стоит на месте: изучаются разнообразные родственные модели, позволяющие выразить конструкции, невыразимые в обыкновенных грамматиках, а также обладающие хорошими сложностными свойствами — и для них многое остаётся неизвестным. Например, для семейства _конъюнктивных грамматик_ (Охотин, 2001), расширяющего базовую (бесконтекстную) модель операцией конъюнкции, пока не удалось найти методы доказательства непредставимости ими конкретных языков. В то же время и для классического семейства _однозначных грамматик_, изучаемого с 1960-х гг., до сих пор остаётся открытым вопрос о разрешимости задачи эквивалентности двух данных грамматик. Наконец, даже для обыкновенных (бесконтекстных) грамматик пока не удалось установить отдельные сложностные свойства — например, остаётся неизвестной параллельная сложность задачи подсчёта количества деревьев разбора данной строки. Задача проекта — рассмотреть эти и некоторые другие сложностные свойства наиболее интересных семейств грамматик.

Наконец, последняя часть проекта посвящена сложности вероятностных моделей в теории формальных языков. Вероятностные автоматы — это модель алгоритмов, использующих случайные числа. Вероятностные грамматики — модель синтаксиса, оценивающая синтаксическую правильность предложений количественно, что оказывается весьма полезным в приложениях к лингвистике. Сложность вероятностных конечных автоматов и их преобразования к детерминированным хорошо известна из классических работ Рабина (1963) и Фрейвальдса (2008). В данном проекте предполагается изучить аналогичную задачу для ранее не изучавшихся вероятностных автоматов, управляемых входом (input-driven automata; также автоматов с видимым магазином, visibly pushdown automata).



*** Актуальность ***

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

Про двухсторонние конечные автоматы, детерминированные (2DFA) и недетерминированные (2NFA), известно, что они задают один и тот же класс языков — регулярные языки. Поэтому всякий недетерминированный двухсторонний автомат можно детерминизировать, однако число состояний, необходимое для этого, остаётся неизвестным: нет нижней оценки лучше, чем \Omega(n^2), а верхняя — 2^{n^2}. При этом Капуцис и Пиггиццини (Kapoutsis, Pighizzini, "Two-Way Automata Characterizations of L/poly Versus NL", 2015), развивая идеи Бермана и Лингаса (Berman, Lingas, "On complexity of regular languages in terms of finite automata", 1977) доказали, что возможность детерминизировать такие автоматы с полиномиальным ростом числа состояний тесно связана с фундаментальным вопросом о включении класса вычислительной сложности NL в класс L/poly, а также с вопросом о равенстве L и NL — классическими нерешёнными вопросами теории сложности. Поэтому решение задачи о сложности преобразования 2NFA в 2DFA повлечёт за собой большие результаты в теоретической информатике — однако имеющихся методов пока не хватает, чтобы получить ответ на этот вопрос. Потому необходимо исследовать сложность двухсторонних автоматов дальше, решать другие задачи об этой модели и разработать новые методы, которые, возможно, помогут решить эту задачу.

Среди других важных задач по 2DFA стоит отметить сложность преобразования произвольного 2DFA к 2DFA, останавливающемуся на любом входе, где известна верхняя оценка порядка 4n (Geffert, Mereghetti, Pighizzini, "Complementing two-way finite automata", Inf. Comput., 2007), однако никакой нижней оценки пока не было получено. Для сложности преобразования 2DFA к обратимому 2DFA есть верхняя оценка порядка 4n (Kunc, Okhotin, "Reversibility of computations in graph-walking automata", Inf. Comput., 2020), и нижняя порядка 2n (Kunc, Okhotin, "Reversible Two-Way Finite Automata Over a Unary Alphabet", 2011). Точная сложность остаётся неизвестной в обоих случаях.

Про длину кратчайшей строки, принимаемой 2DFA, из знаменитой работы Козена (D. Kozen, "Lower bounds for natural proof systems", FOCS 1977) известно, что существуют автоматы с кратчайшими строками экспоненциальной длины от числа состояний. Одновременно из работ Капуциса (Kapoutsis, "Removing Bidirectionality from Nondeterministic Finite Automata", MFCS 2005) следует верхняя оценка порядка 4^n. При этом точная асимптотика остаётся неизвестной, а найти её — значит узнать что-то новое о сложности двухсторонних автоматов, и это может помочь в дальнейших исследованиях этой модели.

Древоходные автоматы — это модель обхода иерархических структур данных, изучающаяся, начиная с 1970-х гг. Боянчик и Колькомбе (Bojanczyk, Colcombet, "Tree-walking automata cannot be determinized", 2006; Bojanczyk, Colcombet, "Tree-walking automata do not recognize all regular languages", 2008) доказали, что детерминированные древоходные автоматы слабее недетерминированных, а те в свою очередь задают не все регулярные древесные языки. В их работе сформулирована открытая задача: замкнуты ли недетермированные древоходные автоматы относительно дополнения? Также изучались варианты древоходных автоматов, оснащённые камешками: они введены Энгельфритом и Хоогебоомом (Engelfriet, Hoogeboom, "Tree-walking pebble automata", 1999), и свойства нескольких вариантов таких автоматов изучались Мушолл и др. (Muscholl, Samuelides, Segoufin, "Complementing deterministic tree-walking automata", 2006) и Боянчиком и др. (Bojanczyk, Samuelides, Schwentick, Segoufin, "Expressive power of pebble automata", 2006). Дальнейшее исследование этой модели и её вариантов поможет развить теорию древоходных автоматов.

Графоходные автоматы также изучаются более полувека. В 1967 г. Рабин высказал предположение, что для всякого графоходного автомата с конечным числом камешков есть граф, который он не обойдёт полностью — эта гипотеза была доказана в работах Будаха (1978) и Роллика (1980). С другой стороны, Блум и Козен (Blum, Kozen, "On the power of the compass (or, why mazes are easier to search than graphs)", FOCS 1978) построили графоходный автомат с двумя камешками, который обходит любой плоский граф на прямоугольной решётке с помеченными направлениями. Задача обхода графа общего вида с n вершинами была решена Диссером и др. (Disser, Hackfeld, Klimm, "Tight bounds for undirected graph exploration with pebbles and multiple agents", J. ACM, 2019) с помощью автомата с \log\log n камешками и \log\log n битами дополнительной памяти; также они показали, что этот объём ресурсов необходим. В области графоходных автоматов осталось немало нерешённых вопросов: совсем не изучены недетерминированные и вероятностные автоматы; для автоматов с камешками не изучались ограничения на действия с камешками; подробно изучавшиеся для древоходных автоматов, и т.д. Поэтому область графоходных автоматов, несмотря на яркие результаты, остаётся в целом недостаточно изученной, и систематическое рассмотрение стандартных вопросов для указанных моделей позволит развить эту теорию и сформулировать новые вопросы для исследования.

Основное понятие сложности, изучаемое в комбинаторике слов — это _комбинаторная сложность бесконечной строки_, считающая для всякого натурального числа n число различных подстрок длины n в этой строке. Изучение сложности строк и ее связей со структурными свойствами строк — одна из основных областей современной комбинаторики слов (см., например, обзор Cassaigne, FNicolas, "Factor complexity", Encyclopedia Math. Appl., vol. 135, 2010, 163–247). В частности, хотелось бы отметить исследования о возможных значениях и порядках роста функции сложности, а также исследования строк линейной сложности (J. Cassaigne, Special factors of sequences with linear subword complexity, DLT 1995; Leroy, J.: Some improvements of the S-adic conjecture. Adv. Appl. Math., 2012). Из ранних работ следует также отметить фундаментальные работы М. Морса и Г. Хедлунда (M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 1921; M. Morse, G. Hedlun