| Что: | Лекция |
| Когда: | Суббота, 17 октября 2009, 19:05–20:35 |
| Где: | ПОМИ РАН |
Узкое место алгоритма Кокка—Касами—Янгера. Разбор через умножение матриц. Метод Штрассена умножения матриц за время \(O(n^{\log_2 7})\).
L. G. Valiant, “General context-free recognition in less than cubic time”, Journal of Computer and System Sciences, 10:2 (1975), 308--314; A. Okhotin, “Fast parsing for Boolean grammars: a generalization of Valiant's algorithm”, TUCS TR 953, принято на DLT 2010.
