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

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

Языки с ограниченной размерностью и рациональный индекс

28 марта

На семинаре мы рассмотрим две интересные концепции из формальных языков (и не только): размерность дерева разбора (или число Штралера) и рациональный индекс языка \rho_L(n), который определяется как максимальная длина кратчайшей строки в пересечении языков L и R для любого регулярного языка R, распознаваемого автоматом с n состояниями. Также мы узнаем как "хорошие" значения этих свойств языка влияют на сложность парсинга, CFL-reachability и многих других задач. Мы покажем, что рациональный индекс языков с ограниченной размерностью деревьев разбора является "хорошим", а именно представляет собой полиномиальную функцию от n.

Докладчица: Екатерина Шеметова (JetBrains Research, СПбАУ, СПбГУ)

Google Meet: https://meet.google.com/myu-dhmz-gvu