*** Научная проблема ***
Теория формальных языков — это классическая область теоретической информатики, изучающая такие объекты, как символьные строки, конечные автоматы и формальные грамматики. Изначально эти модели вдохновлены задачами обработки информации — они формализуют представление информации, модели вычисления ограниченной мощности, определения характерных для синтаксиса языков вложенных конструкций. Изучение этих объектов со временем оформилось в самостоятельный раздел математики, задействующий методы логики, алгебры, комбинаторики и теории вероятностей, а также развивающий свои собственные математические методы. Эта математика, однако, сохраняет связь со своими первоначальными приложениями, и новые математические теоремы, доказывающие абстрактные свойства объектов теории формальных языков, нередко имеют значение для инженерной деятельности, использующей эти объекты.
В современных исследованиях в области формальных языков речь очень часто идёт о разнообразных видах _сложности_. Среди прочего, рассматриваются меры сложности языков по числу состояний в распознающих их автоматах, комбинаторная сложность строк по количеству различных подстрок, вычислительная сложность задач распознавания свойств тех или иных моделей — все подобные аспекты сложности имеют значение для практического применения этих объектов. Предметами научных работ всё чаще становятся оценки сложности различных объектов, рост размера описания при переходе от одной модели к другой, взаимоотношения между различными мерами сложности.
Проект направлен на изучение различных аспектов сложности в формальных языках и объединяет специалистов в разных видах сложности.
Одна из основных тем проекта — вопросы сложности в классических семействах конечных автоматов: двухсторонних конечных автоматах (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. Hedlund, Symbolic dynamics. Amer. J. Math., 1938; M. Morse, G. Hedlund, Symbolic dynamics II: Sturmian sequences. Amer. J. Math., 1940), давшие начало новой области математики, называемой символьной динамикой, базирующейся на идее дискретизации классических динамических систем. Среди прочего, они доказали классическую теорему о связи комбинаторной сложности и периодичности: если сложность строки p(n) не превосходит n для некоторого n, то строка — периодическая. В двумерном случае утверждение, аналогичное теореме Морса и Хедлунда, известно как гипотеза Нива (Nivat, приглашенный доклад на ICALP 1997), которая утверждает, что если для двумерной строки существуют два натуральных числа n и m, такие что сложность p(n,m)<=nm, то строка имеет вектор периодичности. Был найден ряд слабых версий гипотезы (V. Cyr and B. Kra, Nonexpansive Z^2-subdynamics and Nivat’s conjecture, Transactions of the AMS, 2015; J. Kari, M. Szabados: An Algebraic Geometric Approach to Nivat's Conjecture. ICALP 2015), но гипотеза остается недоказанной.
Один из важнейших предметов исследования в комбинаторике слов — это _слова Штурма_, то есть периодические строки минимально возможной сложности n+1. (см., например, Lothaire, Algebraic Combinatorics on Words, 2002). Тема слов Штурма связывает комбинаторику слов, теорию чисел и динамические системы. Слова Штурма широко изучались из-за своей теоретической значимости и приложений к различным областям науки. Они обладают рядом характеризаций геометрической природы (режущие строки, механические строки), а также могут быть охарактеризованы посредством моноида морфизмов Штурма; кроме того, они представляют собой простейшую модель квазикристаллов. Важность изучения квазикристаллов в современной науке подтверждается тем, что Нобелевская премия по химии в 2011 году была присуждена за их открытие.
Для различных семейств формальных грамматик прежде всего интересна вычислительная сложность задачи синтаксического анализа — именно она определяет полезность семейства для практического применения. Столь же важна выразительная мощность семейства — какие конструкции оно способно задавать — и алгоритмическая разрешимость свойств данной грамматики. В частности, вопрос о разрешимости задачи эквивалентности для _однозначных грамматик_, остающийся открытым уже более полувека — это один из самых знаменитых открытых вопросов о грамматиках.
Автоматы, управляемые входом (автоматы с видимым магазином) — одна из самых известных моделей в теории автоматов, введённая Мельхорном (Mehlhorn, "Pebbling Moutain Ranges and its Application of DCFL-Recognition", ICALP 1980) и позже Алуром и Мадхусуданом (Alur, Madhusudan, "Visibly pushdown languages", STOC 2004), и активно изучавшаяся в последние два десятилетия. Их вероятностная разновидность до сих пор никем не изучалась, и изучить её будет важно для развития этой части теории автоматов.
*** Конкретная задача ***
Изучаемые в проекте вопросы сложности двухсторонних автоматов вдохновлены классической задачей о сложности преобразования двухсторонних недетерминированных конечных автоматов (2NFA) к детерминированным (2DFA) по числу состояний. Это одна из самых известных открытых проблем в теории автоматов, и любое продвижение в сторону её решения будет ценным. Ряд родственных задач о сложности двухсторонних автоматов, по мнению участников проекта, могут быть решены, и их решения дадут новые подходы к сложности двухсторонних автоматов как таковой. Для задачи о сложности преобразования 2NFA к одностороннему однозначному автомату (UFA) известна грубая верхняя оценка 2^{n^2}, однако нижних оценок пока никаких не получено — предполагается их получить. Известные результаты о длине кратчайших строк в 2DFA неточны, и ставится задача улучшить как нижние, так и верхние оценки. Также важно изучить подкласс обратимых двухсторонних автоматов (2RFA) и сложность его преобразования к односторонним автоматам (DFA, NFA). Наконец, предполагается рассмотреть двухстороннее обобщение известного класса так называемых перестановочных односторонних автоматов (частный случай обратимых), определив сложность его преобразования такого двухстороннего автомата к одностороннему. Наконец, для сложности преобразования односторонних недетерминированных автоматов (NFA) к 2DFA известны лишь квадратичная нижняя и экспоненциальная верхняя оценки — и эти оценки хотелось бы сблизить.
Для древоходных автоматов есть известная задача Боянчика и Колькомбе (2006): замкнуты ли недетерминированные древоходные автоматы относительно дополнения? Предполагается, что ответ отрицательный — и в этом случае для более общей модели графоходных автоматов построить контрпример проще, так как можно использовать графы с циклами. Поэтому предполагается вначале исследовать эту задачу для недетерминированных графоходных автоматов (NGWA). Далее, планируется изучить варианты NGWA с конечной неоднозначностью и проверить существовании иерархии таких автоматов в зависимости от количества неоднозначности (подобные исследования проводились для односторонних автоматов — см., например, Hing Leung, "Descriptional complexity of NFA of different ambiguity", 2005). Кроме того, планируется изучать графоходные автоматы с камешками, рассматривая различные ограничения на камешки; кроме известного понятия "вложенных камешков", ранее изучавшихся для древоходных автоматов, предполагается рассмотреть "разбрасываемые камешки", которые можно только класть, но нельзя поднимать.
В теории автоматов на бесконечных строках основными объектами изучения будут классификации распознаваемых ими языков (регулярных языков на бесконечных строках) и соответствующие проблемы разрешимости. В случае разрешимости, т.е. существования решающего алгоритма, встает задача найти эффективный алгоритм или доказать его отсутствие. Основные инструменты классификации регулярных языков — это иерархии и сводимости. Известные иерархии регулярных языков могут быть описаны разными способами: с помощью логики первого порядка, теории конечных полугрупп и регулярных выражений подходящего вида. Наиболее известные иерархии такого рода — это иерархии Бжозовского и Стробинга-Терьена. Обе они индуцируются иерархиями предложений подходящих сигнатур по числу перемен кванторов и исчерпывают класс _апериодических языков_, играющий основную роль в верификации систем с конечным множеством состояний. Наряду с упомянутыми "логическими" иерархиями, в теории автоматов на бесконечных строках хорошо известны более грубые "топологические" иерархии, индуцируемые иерархиями дескриптивной теории множеств (Э. Бореля, Ф. Хаусдорфа, В. Вэджа). Центральную роль в этой области играет иерархия Вагнера. Она подробно изучалась В. Л. Селивановым (и другими авторами, включая Д. Перрена, О. Картона, и Ж. Дюпарка), который, в частности, установил, что она является автоматным аналогом иерархии Вэджа. В. Л. Селиванов развил соответствующую теорию для случая регулярных апериодических языков бесконечных строк, а также распространил иерархию Вагнера со случая множеств на случай к-разбиений пространства бесконечных строк. Это при к>2 приводит к гораздо более богатой и интересной структуре. В данном проекте предполагается продолжить развитие этой теории, в частности изучить соответствующие сложностные вопросы. Наряду с этим, предполагается продолжить изучение расширения иерархии Вагнера с регулярных языков бесконечных строк на языки, распознаваемые автоматами, управляемыми входом (input-driven automata), также известными как автоматы с видимым магазином (visibly pushdown automata); последняя иерархия введена А. С. Охотиным и В. Л. Селивановым (CSR 2021). Еще одна задача этого направления проекта связана с изучением возможности расширения иеархии Вагнера с языков бесконечных строк на языки ординальных строк. Это обобщение инициировано Р. Бюхи и изучалась рядом авторов, включая Чойку и Н. Бедона. Последний доказал теорему детерминизации для языков над ординалами, меньшими \omega^\omega, что дает надежду на существование естественного обобщения иерархии Вагнера на такие языки.
Понятие комбинаторной сложности бесконечных строк имеет ряд естественных обобщений. Например, в литературе изучалось понятие абелевой сложности — функции, считающей число подстрок с точностью до абелевой эквивалентности, то есть одинакового побуквенного состава (см., например, Richomme, Saari, Zamboni, "Abelian complexity of minimal subshifts", Journal of the London Mathematical Society, 2011). Примечательно, что слова Штурма, которые можно определить как непериодические строки минимальной сложности, можно также определить как непериодические строки минимальной абелевой сложности. Сравнительно новое понятие групповой сложности (Charlier, Puzynina, Zamboni, "On a group theoretic generalization of the Morse-Hedlund theorem", Proceedings of the AMS, 2017) обобщает понятия абелевой и классической комбинаторной сложности. Для того, чтобы определить групповую сложность, понадобится подгруппа симметрической группы S_n для всякого порядка n. Произвольная подгруппа S_n действует на множестве строк длины n всевозможными перестановками букв, а групповая сложность определяется как число орбит подстрок длины n относительно действия соответствующей подгруппы. Среди других обобщений понятия сложности следует отметить циклическую сложность, также являющуюся частным случаем групповой сложности (Cassaigne, Fici, Sciortino, Zamboni, "Cyclic complexity of words", J. Comb. Theory, Ser. A, 2017), k-биномиальную, k-абелеву (Karhumaki, Saarela, Zamboni, "Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence", Acta Cybern., 2017).
Одно из направлений исследований в теории сложности бесконечных строк — изучение возможных значений функций сложности бесконечных строк, а также различных классов строк. Так, известно, что порядки роста функций сложности бесконечных строк могут вести себя довольно разнообразно (см., например, Cassaigne, "Constructing Infinite Words of Intermediate Complexity", DLT 2002), однако полной классификации неизвестно. Для класса чисто морфических строк доказано, что их сложность принадлежит одному из пяти классов O(1), O(n), O(n log n), O(n log log n) и O(n^2) (Pansiot 1984), а классификация возможных значений более широкого класса морфических строк, где к неподвижной точке морфизма применяется еще один морфизм, до сих пор неизвестна (Deviatov, "On Subword Complexity of Morphic Sequences", CSR 2008). В рамках проекта планируется исследовать задачи о возможных значениях функций сложности бесконечных строк, в частности, групповой сложности.
Чтобы подступиться к большой открытой проблеме в области формальных грамматик — вопросу о разрешимости задачи об эквивалентности двух данных однозначных грамматик — предполагается продолжить изучение _GF(2)-грамматик_ — семейства грамматик, основанного на операциях из конечного поля GF(2), введённого Бакиновой и др. (Bakinova, Basharin, Batmanov, Lyubort, Okhotin, Sazhneva, "Formal languages over GF(2)", Inf. Comput., 2022). Определение этих грамматик получено заменой булевой логики в определяниях классических грамматик на операции из поля GF(2), то есть все дизъюнкции заменяются на исключающее ИЛИ. Модель GF(2)-грамматик обобщает однозначные грамматики и одновременно позволяет применять различные алгебраические методы исследования. Благодаря этому GF(2)-грамматики уже успели хорошо себя зарекомендовать и как самоценный предмет исследования, и как метод для получения результатов об однозначных грамматиках — в частности, с их помощью Макаров (Makarov, "Bounded Languages Described by GF(2)-grammars", DLT 2021) впервые доказал существенную неоднозначность языка \{a^l b^m c^n | l \neq m OR m \neq n\} – задачу, поставленную Отебером и др. (Autebert et al., 1979).
Также предполагается изучить задачу вычисления числа деревьев разбора данной строки: её параллельная сложность остаётся неизвестной. Действительно, классический алгоритм Кокка--Касами--Янгера позволяет вычислить число деревьев разбора за кубическое время, в то время как известные параллельные алгоритмы для определения принадлежности строки языку рассматривают некоторые подстроки по нескольку раз, и потому не позволяют правильно вычислить количество деревьев разбора. Научиться решать эту задачу за параллельное время (\log n)^{O(1)} было бы весьма полезно как для понимания вычислительной сложности грамматик, так и для практического их применения.
В области автоматов, управляемых входом (автоматов с видимым магазином) предполагается рассмотреть их вероятностную модель, использующую случайные числа при каждом переходе. Главный вопрос в том, можно ли преобразовать всякий такой вероятностный автомат к детерминированному? Если преобразование всегда возможно, то какова его сложность в смысле роста числа состояний? Ответ на этот вопрос добавит в теорию автоматов новую хорошо мотивированную модель.
*** Научная новизна ***
Все задачи проекта — либо известные открытые проблемы, сформулированные специалистами в своих областях и опубликованные в рецензируемых международных научных журналах, либо предложены участниками проекта и ранее не встречались в научной литературе. Это гарантирует новизну ожидаемых результатов и их соответствие мировому уровню.
Некоторые задачи проекта — это классические открытые проблемы, и гарантии полного их решения быть не может. Однако план работ и конкретных задач разработан в расчёте на то, чтобы внести вклад в исследование указанных открытых проблем, развить теорию вокруг них, и попутно решить многие другие задачи, имеющие самостоятельную ценность.
Достижимость поставленных задач обеспечена также тем, что к работе над проектом привлечена сбалансированная команда исследователей из Санкт-Петербургского университета, состоящая из трёх опытных учёных (А. С. Охотин, С. А. Пузынина, В. Л. Селиванов), двух активно работающих молодых учёных (В. М. Макаров, О. М. Мартынова) и пяти молодых перспективных исследователей. Руководитель и основные исполнители проекта имеют большой опыт научных исследований и не раз бывали приглашёнными докладчиками на международных конференциях в области формальных языков; также они имеют значительный опыт руководства студентами и успешного вовлечения их в исследовательскую деятельность, подтверждённый множеством недавних публикаций. Проведение проекта на базе факультета МКН СПбГУ обеспечит стабильный приток талантливых молодых участников в проект. Конкретные запланированные задачи соответствуют профессиональному опыту и умениям участников проекта, и с высокой долей уверенности могут быть решены предлагаемыми методами.
*** Современное состояние ***
Вопросы о числе состояний в двухсторонних автоматах и сложности их детерминизации занимают умы исследователей уже более шестидесяти лет. Среди последних работ — например, статья Капуциса и Пиггиццини (Kapoutsis, Pighizzini, "Two-Way Automata Characterizations of L/poly Versus NL", 2015) о связи сложности детерминизации 2NFA и классов вычислительной сложности, работа Капуциса о детерминизации 2NFA для строк короткой длины (Kapoutsis, "Optimal 2DFA Algorithms for One-Way Liveness on Two and Three Symbols", Adventures Between Lower Bounds and Higher Altitudes 2018), недавний результат Гийона и др. (Guillon, Pighizzini, Prigioniero, Prusa, "Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines", CoRR abs/2103.05485) о моделировании работы 2NFA на машине Тьюринга, статья Гефферта и др. (Geffert, Kapoutsis, Zakzok, "Improved complement for two-way alternating automata", Acta Informatica, 2022) о сложности дополнения для чередующихся двухсторонних автоматов (2AFA), и немало других работ. Работы по сложности конечных автоматов нередко представляются на конференциях по теоретической информатике, а также на специализированной ежегодной конференции DCFS (Descriptional Complexity of Formal Systems).
Длина кратчайшей принимаемой строки как мера сложности автоматов изучалась рядом исследователей: Эллул и др. (Ellul, Krawetz, Shallit, Wang, "Regular expressions: new results and open problems", 2005) определили длину наименьшей строки, не принимаемой односторонним недетерминированным автоматом; Чистиков и др. (Chistikov, Czerwinski, Hofman, Pilipczuk, Wehar, "Shortest paths in one-counter systems", FoSSaCS 2016) исследовали длину кратчайших строк в автоматах со счётчиками.
Древоходные автоматы активно изучаются последние двадцать лет: Боянчик и Колькомбе в своих знаменитых работах (Bojanczyk, Colcombet, "Tree-walking automata cannot be determinized", 2006; Bojanczyk, Colcombet, "Tree-walking automata do not recognize all regular languages", 2008) установили невозможность детерминизации этой модели и показали, что даже недетерминированная модель слабее древесных автоматов. Мушолл и др. (Muscholl, Samuelides, Segoufin, "Complementing deterministic tree-walking automata", 2006) доказали замкнутость детерминированных автоматов с камешками относительно дополнения, с использованием дополнительных камешков; позднее Кунц и Охотин (Kunc, Okhotin, "Reversibility of computations in graph-walking automata", Inf. Comput., 2020) показали, что то же самое можно сделать, не задействуя дополнительных камешков. Боянчик и др. (Bojanczyk, Samuelides, Schwentick, Segoufin, "Expressive power of pebble automata", 2006) доказали, что древоходные автоматы с камешками мощнее автоматов без камешков.
Сложность однозначных конечных автоматов (UFA) изучается с 1980-х. В последнее время было получено несколько ярких результатов о сложности дополнения для этой модели: Инджев и Кифер (Indzhev, Kiefer, "On complementing unambiguous automata and graphs with many cliques and cocliques", Inf. Process. Lett., 2022) улучшили ранее известную верхнюю оценку до 2^{n/2}, а Гоос и др. (Goos, Kiefer, Yuan, "Lower Bounds for Unambiguous Automata via Communication Complexity", 2022) улучшили нижнюю оценку до n^{\log n}.
Изучение автоматов на бесконечных строках было начато независимо Бюхи и Трахтенбротом в 1960-х годах и стало впоследствии центральным инструментом исследования так называемых реактивных систем, т.е. бесконечно работающих систем (таких как операционные системы, сети передачи данных, системы управления объектами инфраструктуры), обеспечивающих правильное взаимодействие системы с ее окружением. Ключевым стало обобщение автоматов на бесконечных строках до автоматов на бесконечных деревьях, развитое М. Рабином. Результаты Р. Бюхи, М. Рабина и их последователей привели не только к многочисленным применениям в информатике, но и к глубоким математическим результатам по разрешимости элементарных и монадических теорий. Важную унифицирующую роль в этой теории сыграл логический подход к теории автоматов, восходящий к классической характеризации регулярных языков с помощью определимости в монадической теории второго порядка натуральных чисел с отношением порядка (Бюхи и Элгот; Трахтенброт), и развившийся в успешные применения вариантов временной логики к задачам спецификации и верификации систем с конечным числом состояний. На основе полученного метода "проверки моделей" были разработаны программы, позволяющие автоматически верифицировать реально используемые электронные устройства.
Заметное место в современной теории автоматов на бесконечных строках занимает _иерархия Вагнера_, дающая законченную топологическую классификацию регулярных языков бесконечных строк и включающая в качестве частных случаев более ранние результаты Бюхи, Ландвебера, Штайгера и др. Впоследствии В. Л. Селиванов (Selivanov, "Fine Hierarchy of Regular omega-Languages", TAPSOFT 1995) развил новый подход к изложению этой теории, приведший и к новым результатам. Несколько позже аналогичная попытка была предпринята французскими учеными Д. Перреном, О. Картоном (Carton, Perrin, "Chains and superchains for omega-rational sets, automata and semigroups", 1997) и Ж. Дюпарком. Эти работы положили начало самостоятельному направлению теории автоматов на бесконечных объектах, которое продолжает активно развиваться. Вопросы разрешимости уровней и описания соответствующей сводимости для иерархии Вагнера были решены самим К. Вагнером. Им же совместно с В. Л. Селивановым (Selivanov, Wagner, "Complexity of topological properties of regular omega-languages", DLT 2008) были найдены эффективные решающие алгоритмы. В. Л. Селиванов (Selivanov, "Fine hierarchy of regular aperiodic omega-languages", DLT 2007) развил соответствующую теорию для случая регулярных апериодических языков бесконечных строк (что потребовало доказательства апериодического аналога теоремы Бюхи-Ландвебера о бесконечных играх), а также распространил иерархию Вагнера со случая множеств на случай к-разбиений пространства бесконечных строк (Selivanov, "Classifying omega-regular partitions", LATA 2007; Selivanov, "A fine hierarchy of omega-regular k-partitions", CiE 2011). Это при к>2 приводит к гораздо более богатой и интересной структуре.
Задача эквивалентности для однозначных грамматик ранее изучалась в частном случае: А. Л. Семёнов ("Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик", Докл. АН СССР, 1973) доказал её разрешимость в том случае, когда один из двух языков регулярен — и это остаётся единственным большим результатом по сей день. Предложенные методы, основанные на GF(2)-грамматиках и на сечениях языка — это попытка подступиться к этому классическому открытому вопросу с чистого листа.
*** Методы и подходы, общий план ***
Для решения задач проекта будут привлечены разнообразные методы, разработанные в теории автоматов, логике, алгебре и комбинаторике.
Говоря об отдельных задачах, при изучении графоходных автоматов с разбрасываемыми камешками предполагается доказать, что они не увеличивают класс распознаваемых языков — то есть что работу автомата с такими камешками можно промоделировать обычным графоходным автоматом без камешков. Для такого моделирования предполагается использовать методы обхода дерева вычислений, восходящие к известной работе Сипсера (Sipser, "Halting space-bounded computations", 1980) — подобные методы недавно использовались участниками проекта для построения обратимых автоматов (Kunc, Okhotin, "Reversibility of computations in graph-walking automata", Inform. Comput, 2020; Martynova, Okhotin, "Lower bounds for graph-walking automata", STACS 2021).
Для доказательства нетривиальности изучаемых иерархий языков на бесконечных строках планируется в основном использовать различные варианты метода игр Эренфойхта, разработанного в теории моделей и особенно полезного для конечных моделей. При доказательства нетривиальности иерархий гибридных систем будут использованы методы симуляции и бисимуляции, тесно связанные с играми Эренфойхта. При изучении топологических иерархий регулярных языков будут использованы также варианты игр Бюхи--Ландвебера. В исследовании иерархий регулярных языков для случаев автоматов над бесконечными строками будут использованы методы, разработанные В. Л. Селивановым при изучении так называемых тонких иерархий — в частности, характеризация их уровней посредством итерированных размеченных деревьев. Для построения эффективных решающих алгоритмов для уровней иерархии разбиений будут применяться известные алгоритмы на графах.
Доказательство нетривиальности уровней иерархий регулярных языков бесконечых строк будет развивать методы известных иерархий Бжозовского и Стробинга--Терьена, а также их вариантов и утончений. Для конечных строк немало подобных результатов уже известно, однако систематического изучения задачи для языков бесконечных строк и языков ординальных строк пока не проведено. В ряде случаев (например, для иерархий языков, распознаваемых магазинными автоматами, управляемыми входом) даже определение таких иерархий языков бесконечных и ординальных строк неочевидно.
Одной из задач комбинаторики слов, важной как с теоретической точки зрения, так и в приложениях, является задача восстановления строки по её подстрокам. Различные вариации этой задачи уже рассматривались в литературе. Так, известно, что строка восстанавливается по её подстрокам длины не более половины (Lothaire, 1983), а если вдобавок известны кратности строк, то известны только верхняя оценка порядка sqrt(n) (Borwein, Erdelyi, Kos, 1999) и нижняя оценка порядка log n (Dudika, Schulman, 2003). Планируется рассмотреть аналогичную задачу о восстановлении циклической строки по её разреженным подстрокам ограниченной длины.
В рамках проекта планируется изучать различные вариации понятия сложности бесконечных стрпл, а также связи поведения функций сложности с различными структурными свойствами бесконечных строк и факторных языков. Планируется исследовать спектр возможных значений функций сложности, в частности, групповой сложности.
Помимо задач, поставленных для бесконечных строк, планируется рассматривать их обобщения на пространства сдвига, то есть множества бесконечных строк, которые определяются некоторым ограничениями на множества их возможных подстрок. В частности, планируется рассматривать пространства сдвига, определяемые множествами подстрок бесконечной строки, пространства сдвига конечного типа и софические пространства сдвига. Такого рода задачи позволяют использовать одновременно подходы из комбинаторики слов и символьной динамики.
Планируется продолжать изучение алгебраических моделей и методов для грамматик в целом и GF(2)-грамматик (грамматик, использующих логические операции из поля GF(2), то есть конъюнкцию и исключающее ИЛИ).
Вероятностная разновидность автоматов, управляемых входом (автоматов с видимым магазином) не изучалась до сих пор. Предполагается доказать возможность преобразовать всякий такой автомат к детерминированному, обобщив методы, использованные Рабином (Rabin, "Probabilistic Automata", Inf. Control, 1963) в доказательстве аналогичного преобразования для конечных автоматов.
** 2023 **
Изучение кратчайших принимаемых строк для двухсторонних конечных автоматов, построение автомата с длинной кратчайшей строкой. (Мартынова, Охотин)
Изучение графоходных автоматов с камешками, которые можно класть, но нельзя поднимать. (Мартынова, Охотин)
Изучение сложности преобразования 2DFA к однозначным конечным автоматам. (Петров, Охотин)
Исследование двухсторонних перестановочных автоматов. (Радионова, Охотин)
Будет изучаться сложность распознавания уровней иерархии Вагнера к-разбиений по заданному конечному автомату Мюллера и связанные с этим вопросы. При к=2 известен полиномиальный алгоритм решения этой задачи, найденный независимо Вильке-Яо и Брейтоном-Кришнаном-Пьюри. При к>2 наличие такого алгоритма неочевидно, поскольку структура классов иерархии становится весьма сложной, хотя и остается Нетеровым часстичным порядком. Тем не менее, есть надежда получить полиномиальные оценки сложности и в общем случае, используя недавние результаты П.Е. Алаева и В.Л. Селиванова о сложности представления структур итерированных размеченных лесов и подходящие алгоритмы на графах. (Селиванов)
Планируется исследовать задачу о восстановлении циклического слова по его разреженным подсловам. Точнее, задача заключается в следующем: для всякого натурального числа n найти наименьшее число k, такое что всякое циклическое слово длины n восстанавливается по множеству его подслов длины k. Предварительные вычисления для малых длин позволяют выдвинуть гипотезу, что слово восстанавливается по его словам длины 3/4n, и эта оценка точна. В течение первого года проекта предполагается доказать гипотезу, а именно, показать, что для всякого n два любых циклических слова n имеют разные множества циклических подслов длины не более 3/4n, а также что для всякого n найдутся два слова, такие что их множества подслов длины менее 3/4n совпадают. (Пузынина, Лучинин)
Развитием методов из недавней статьи Макарова (Makarov, "Bounded Languages Described by GF(2)-grammars", DLT 2021) планируется получить полную или почти полную классификацию подмножеств a_1* a_2* ... a_n*, задаваемых GF(2)-грамматиками. (Макаров)
Предполагается получить параллельный NC^2-алгоритм подсчёта количества деревьев разбора данной строки относительно фиксированной обыкновенной (бесконтекстной) грамматики. (Михельсон, Охотин)
Предполагается исследовать преобразование вероятностного магазинного автомата, управляемого входом (автомата с видимым магазином), к детерминированному автомату. (Розе, Охотин)
** 2024 **
Изучение недетерминированных графоходных автоматов — их предполагаемой незамкнутости относительно дополнения, а также их однозначного подкласса. (Мартынова, Охотин)
Изучение сложности преобразования 2NFA к однозначным конечным автоматам. (Петров, Охотин)
Исследование сложности задач распознавания свойств для двухсторонних перестановочных автоматов. (Радионова, Охотин)
Будут изучены возможности расширения иерархии Вагнера со случая конечных автоматов на случай автоматов, управляемых входом. Первые результаты в этом направлении недавно получены А. С. Охотиным и В. Л. Селивановым, однако они относятся только к относительно простому случаю правильно вложенных строк. (Селиванов)
Предполагается рассмотреть задачу о возможных значениях групповой сложности бесконечных строк. В частности, планируется исследовать вопрос: для каких бесконечных строк подбором группы можно получить любое значение групповой сложности между абелевой сложностью и групповой? (Пузынина)
Планируется продолжить изучение упомянутых ранее связей между представимостью языков грамматиками и схемами для вычислительных задач. В частности, предполагается применить ранее упомянутый аналог схемной сложности для получения результатов о непредставимости языков обыкновенными (бесконтекстными) грамматиками. В качестве такого языка может подойти определённым образом закодированное множество всех перестановок. Полученный таким образом язык будет соответствовать сложной для монотонных схем задаче о наличии паросочетания в двудольном графе и потому не будет представим грамматикой. (Макаров)
** 2025 **
Изучение недетерминированных древоходных автоматов — предполагается, что и они будут незамкнуты относительно дополнения, однако для этого потребуется более сложное доказательство, поскольку нельзя использовать графы с циклами. Предполагается развить методы, предложенные в классических работах Боянчика и Колькомбе (2006, 2008) и продвинуться на пути решению этой задачи. (Мартынова)
Будут изучены возможности расширения иерархии Вагнера со случая конечных автоматов на бесконечных строках на случай конечных автоматов на ординальных строках (для ординалов меньших \omega^\omega). Поведение автоматов на таких строках рассматривалось рядом авторов начиная с Р. Бюхи, однако, насколько нам известно, обобщение иерархии Вагнера пока в литературе не рассматривалось. (Ореховский, Селиванов)
Обобщение рассматриваемых задач по комбинаторике слов с бесконечных строк на пространства сдвига. (Пузынина)
Планируется исследование того, как замкнутость класса языков, задаваемых GF(2)-грамматиками относительно таких операций, как GF(2)-обращение и подстановка произвольных языков вместо символов, помогает доказывать положительные и отрицательные результаты о грамматиках. (Макаров)
