16–17 июня в МЦА прошли открытые лекции профессора факультета математики и компьютерных наук СПбГУ Александра Сергеевича Охотина.
В лекциях был сделан подробный обзор основных результатов о магазинных автоматах, управляемых входом (input-driven pushdown automata, IDPDA). Модель IDPDA позволяет проводить тонкий анализ вложенных конструкций, при этом во многих приложениях IDPDA можно применять с той же лёгкостью, что и обычные конечные автоматы.
В рамках лекций обсуждался алгоритм детерминизации для недетерминированных IDPDA. Были выведены точные оценки сложности задачи пустоты для IDPDA: эта задача является P-полной для детерминированных автоматов и EXP-полной в недетерминированном случае. Также показаны оценки на число состояний, требуемое этими автоматами для представления основных операций над языками.
Лекции А. С. Охотина организованы сотрудниками МЦА Виктором Селивановым и Николаем Баженовым. Николай Баженов рассказывает:
При поддержке МЦА ведутся исследования по субрекурсивной сложности алгебраических структур: в частности, исследуются полиномиально вычислимые структуры и структуры, представимые посредством конечных автоматов. А. С. Охотин является ведущим специалистом по теории автоматов и формальных грамматик. В его лекциях дан обзор важных результатов по алгоритмической сложности различных проблем для IDPDA. Со своей стороны, хочу особо отметить замечательную структурированность прочитанных лекций: несмотря на общую сложность представленного материала, изложение построено доступно для студентов, освоивших базовый курс теории алгоритмов.
