Теория формальных языков – это классическая область теоретической информатики, изучающая такие объекты, как символьные строки, конечные автоматы и формальные грамматики. Изначально эти модели вдохновлены задачами обработки информации – они формализуют представление информации, модели вычисления ограниченной мощности, определения характерных для синтаксиса языков вложенных конструкций. Изучение этих объектов со временем оформилось в самостоятельный раздел математики, задействующий методы логики, алгебры, комбинаторики и теории вероятностей, а также развивающий свои собственные математические методы.
В современных исследованиях в области формальных языков речь очень часто идёт о разнообразных видах _сложности_. Среди прочего, рассматриваются меры сложности языков по числу состояний в распознающих их автоматах, комбинаторная сложность строк по количеству различных подстрок, вычислительная сложность задач распознавания свойств тех или иных моделей – все подобные аспекты сложности имеют значение для практического применения этих объектов. Изучаются оценки сложности различных объектов, рост размера описания при переходе от одной модели к другой, взаимоотношения между различными мерами сложности.
Проект направлен на изучение различных аспектов сложности в формальных языках, и объединяет специалистов в разных видах сложности.
Одна из основных тем проекта – вопросы сложности в классических семействах конечных автоматов: двухсторонних конечных автоматах (2DFA, 2NFA), древоходных автоматах и графоходных автоматах. Двухсторонние автоматы широко известны; знаменитая задача о числе состояний, необходимом для детерминизации 2NFA, поставленная Сакодой и Сипсером (1978), остаётся нерешённой, а её тесная связь с задачей L vs. NL из теории сложности вычислений делает её особенно важной. Древоходные автоматы – это обобщение двухсторонних: они ходят уже не по строке, а по дереву, и ими моделируется обход иерархических структур в алгоритмах. Наконец, графоходные автоматы ходят по графам произвольного вида – это модель робота в лабиринте, а также более общая модель в теории автоматов. В проекте будет изучен ряд неизвестных вопросов о сложности таких автоматов.
Другое направление проекта относится к автоматам на бесконечных строкаx — моделям вычислительных устройств, работающих вечно и взаимодействующих со внешней средой – так называемых _реактивных систем_. Эти модели важны в теории и технологии разработки систем с конечным числом состояний. Теория реактивных систем основана на логических и топологических классификациях соответствующих языков. Логические классификации используются как языки спецификаций поведения систем, а топологические классификации описывают особенности их поведения на бесконечных строках. Одна из задач проекта – исследование взаимосвязей между логическими и топологическими классификациями.
Ещё одна разновидность сложности в теории формальных языков – это комбинаторная сложность конечных и бесконечных строк, изучаемая в _комбинаторике слов_. Комбинаторика слов связана со многими областями математики, такими как комбинаторная теория групп, символьные динамические системы и теория чисел, и имеет приложения не только в информатике, но и в других науках — например, в кристаллографии и биохимии.
Следующая часть проекта посвящена сложности различных классов формальных грамматик. В проекте предлагается исследовать семейство _GF(2)-грамматик_ с помощью алгебраических методов, и попробовать так подступиться к классической задаче эквивалентности для однозначных грамматик.
Наконец, последняя часть проекта посвящена сложности вероятностных моделей в теории формальных языков. Вероятностные автоматы – это модель алгоритмов, использующих случайные числа. В данном проекте предполагается впервые исследовать вероятностные магазинные автоматы, управляемые входом (input-driven pushdown automata).
