Семинар МЛ ТИ: "Двусторонние магазинные автоматы с указателями (2-NPPDA): трудные языки и сводимости"
Приглашаем вас на семинар международной лаборатории теоретической информатики в четверг, 18 сентября.
Александр Рубцов выступит с докладом на тему «Двусторонние магазинные автоматы с указателями (2-NPPDA): трудные языки и сводимости».
Семинар пройдет с 18:10 до 19:30 онлайн.
Мы рассмотрим недавно введённую модель вычислений — двусторонние магазинные автоматы с указателями (2-NPPDA) — и её связь с классическими двусторонними магазинными автоматами (2-NPDA). Алгоритмы проверки принадлежности слова языку для детерминированной и недетерминированной версии модели имеют ту же асимптотическую сложность, что и для соответствующих версий классической модели. Мы покажем, что это не случайное совпадение: аналогично классической модели, 2-NPPDA обладают самым трудным языком, к распознаванию которого сводится любой язык из рассматриваемого класса.
Для классической модели Chistikov, Majumdar и Schepper установили связь между задачей достижимости в КС языках (CFL reachability) и проблемой распознавания с помощью fine-grained сводимостей и предложили трудный язык. Они также показали, что существование fine-grained сводимости из SAT к задаче CFL reachability, которая усилила бы условную нижнюю оценку n^{\omega}, опровергает гипотезу о недетерминированном сильном экспоненциальном времени (NSETH). Мы покажем, как эти результаты о соотношениях между задачами распознавания и достижимости соотносятся с классическими результатами Хопкрофта и Ульмана для автоматов общего вида, а также установим связь с задачей распознавания для 2-NPPDA, используя в обоих случаях ещё более тонкие сводимости — на основании детерминированных автоматных преобразователей (Finite State Transducers).
