JetBrains Research — наука, меняющая мир

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

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

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


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

02.11.2019, 17:15.

Место: ауд. 3248, мат-мех. факультет СПбГУ, Старый Петергоф, Университетский пр-т, д. 2