Исследовательская группа

Лаборатория языковых инструментов

Параллельная сложность задачи CFL-reachability

2 декабря 2019

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

Несмотря на то, что данная задача в общем виде не может быть эффективно распараллелена, существуют подклассы контекстно-свободных грамматик и графов, для которых можно построить эффективный параллельный алгоритм. Мы рассмотрим данные подклассы и увидим, какие их свойства позволяют получить более эффективный, по сравнению с общим случаем, параллельный алгоритм. Также будет построена булева схема для решения задачи CFL-reachability.

Докладчик: Екатерина Шеметова