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

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

Поиск путей с контекстно-свободными огрничениями через умножение матриц

September 25

В докладе будет рассмотрена задача поиска путей с контекстно-свободными ограничениями в графах, а также представлен алгоритм для ей решения, использующий умножение матриц. В данной задаче на вход принимается помеченный ориентированный граф с символами из некоторого алфавита на ребрах и некоторая грамматика над тем же алфавитом. Требуется найти пути в графе, метки на ребрах которых образуют цепочки, принадлежащие языку, заданному входной грамматикой. Алгоритм, решающий данную задачу для КС грамматик и использующий матричное умножение, основан на алгоритме Валианта. На практике представленный алгоритм имеет преимущество перед аналогами за счет возможности эффективного использования GPGPU и параллельного вычисления.

Материалы к докладу: https://github.com/YaccConstructor/articles/blob/master/InProgress/EDBT/graphparsing.pdf

Докладчик: Рустам Азимов