Прошел семинар лаборатории "Задача регулярной реализуемости в рамках теории формальных языков и автоматов"

Прошел семинар лаборатории теоретической информатики 19 марта 2026 года.

Докладчик: Александр Рубцов, сотрудник лаборатории теоретической информатики

Задача регулярной реализуемости состоит в проверке непустоты пересечения регулярного языка, заданного на входе, и фиксированного формального языка — фильтра, выступающего параметром задачи. Эта задача возникает на стыке нескольких разделов теоретической информатики, включая теорию вычислений, теорию формальных языков и автоматов, а также теорию булевых функций.

В докладе основное внимание будет уделено связи задачи регулярной реализуемости с теорией автоматов. Одно из её ключевых приложений заключается в установлении связи между автоматами с дополнительными структурами данных и структурными классами формальных языков — так называемыми главными рациональными конусами, к которым, в частности, относятся контекстно-свободные языки.

Помимо этой структурной связи, задача регулярной реализуемости позволяет по-новому взглянуть на классические алгоритмические проблемы теории формальных языков — задачи проверки пустоты языка и принадлежности слова языку — в контексте теории вычислительной сложности. В то время как классическая теория формальных языков в основном сосредоточена на вопросах разрешимости этих задач, задача регулярной реализуемости естественным образом приводит к их изучению с точки зрения сложности вычислений.

Наконец, мы обсудим, каким образом задача регулярной реализуемости обобщает известную задачу достижимости для контекстно-свободных языков. Для этой задачи сравнительно недавно были получены новые результаты [Chistikov, Majumdar, Schepper, POPL 2022], в том числе связанные с тонкими (fine-grained) сводимостями.