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

Семинар по алгоритму Риттера: синтаксический анализ через поиск кратчайшего пути

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)

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

07.05.2018, 17:15.

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