Исследовательская группа
Лаборатория языковых инструментов
Алгоритм Риттера: синтаксический анализ через поиск кратчайшего пути
May 7
BM(n) -- это время пермножения двух булевых матриц размера n x n. Риттер показал, что задача распознования может быть сведена к поиску кратчайшего пути в специальном графе с весами из ассоциотивного полукольца фиксированного размера.
Будет разобран алгоритм Риттера и приведён пример его работы.
Литература к докладу:
Wojciech Rytter. Context-free recognition via shortest paths computation: a version of Valiant's algorithm (https://www.sciencedirect.com/science/article/pii/030439759400265K)
Докладчик: Екатерина Шеметова