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

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)

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