Задача регулярной реализуемости в рамках теории формальных языков и автоматов (Александр Рубцов)

Семинар международной лаборатории теоретической информатики ФКН. Задача регулярной реализуемости состоит в проверке непустоты пересечения регулярного языка, заданного на входе, и фиксированного формального языка — фильтра, выступающего параметром задачи. Эта задача возникает на стыке нескольких разделов теоретической информатики, включая теорию вычислений, теорию формальных языков и автоматов, а также теорию булевых функций. В докладе основное внимание уделено связи задачи регулярной реализуемости с теорией автоматов. Одно из её ключевых приложений заключается в установлении связи между автоматами с дополнительными структурами данных и структурными классами формальных языков — так называемыми главными рациональными конусами, к которым, в частности, относятся контекстно-свободные языки. Помимо этой структурной связи, задача регулярной реализуемости позволяет по-новому взглянуть на классические алгоритмические проблемы теории формальных языков — задачи проверки пустоты языка и принадлежности слова языку — в контексте теории вычислительной сложности. В то время как классическая теория формальных языков в основном сосредоточена на вопросах разрешимости этих задач, задача регулярной реализуемости естественным образом приводит к их изучению с точки зрения сложности вычислений. Также обсуждается, каким образом задача регулярной реализуемости обобщает известную задачу достижимости для контекстно-свободных языков. Для этой задачи сравнительно недавно были получены новые результаты, в том числе связанные с тонкими (fine-grained) сводимостями. Выступает Александр Рубцов, сотрудник международной лаборатории теоретической информатики ФКН НИУ ВШЭ. 19 марта 2026 Международная лаборатория теоретической информатики: https://cs.hse.ru/big-data/tcs-lab/ ФКН: https://cs.hse.ru Подписывайтесь на нас: