Семинар лаборатории теоретической информатики: "Автоматы с дополнительными структурами данных". Докладчик: А. Рубцов

24 апреля на семинаре лаборатории теоретической информатики состоится доклад Александра Рубцова "Автоматы с дополнительными структурами данных"

Автоматы с магазинной памятью являются одним из основных практических приложений теории автоматов (для компиляции). Они являются частным случаем автоматов с дополнительной структурой данных (ДСД). В 60-х годах были начаты исследования общего случая (J. E. Hopcroft, J. D. Ulman, S. Ginsburg). Эти исследования касались в основном вопросов разрешимости базовых задач: проверки принадлежности слова языку, распознаваемому автоматом с ДСД и проверки языка, распознаваемого ДСД на пустоту. Были получены результаты, связывающие разрешимость этих задач как для односторонних, так и для двусторонних автоматов с ДСД.

Мы обобщаем часть известных результатов, перейдя от вопросов разрешимости к вычислительной сложности. Мы уточняем определение автоматов с ДСД известных как Balloon Automata, и это уточнение гарантирует хорошие структурные свойства для языков, распознаваемых автоматами с ДСД. Также это уточнение приводит к новому и простому методу доказательства нижних оценок на проблему пустоты: для трудности в классе C достаточно доказать, что автомат с ДСД распознаёт язык соответствующий классу сложности C (в роли C могут выступать, например, NP и PSPACE). Эта техника была успешно применена для автоматов со словарём (Set Automata) открытых в 2014 г. М. Кутрибом, А. Мальхером и М. Вендландтом (конференции DLT и DCFS). Основной результат исследования —  сложность проблемы пустоты для автоматов с ДСД совпадает со сложностью языков, распознаваемых машиной Тьюринга на логарифмической памяти с ДСД.

Семинар пройдет с 18:10 до 19:30 в аудитории 503 ФКН.
Заказ пропуска: dchernyshova@hse.ru