Оптимизация матричного алгоритма достижимости с контекстно свободными ограничениями

Доклад посвящён задаче достижимости с ограничениями в виде контекстно-свободных языков и тому, как был многократно ускорен решающий её матричный алгоритм Рустама Азимова. Формулируется задача, рассматриваются примеры её применения для статического анализа кода. Разбирается матричный алгоритм Рустама Азимова и ряд оптимизаций этого алгоритма. Обсуждается, как к этим оптимизациям можно прийти и насколько они улучшают производительность в теории и на практике. Представляются результаты экспериментального сравнения с другими решателями контекстно-свободной достижимости, подтверждающие эффективность предложенного решения по времени работы и использованию оперативной памяти.