Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Суббота, 17 октября 2009, 19:05–20:35
Где: ПОМИ РАН

Описание

Узкое место алгоритма Кокка—Касами—Янгера. Разбор через умножение матриц. Метод Штрассена умножения матриц за время \(O(n^{\log_2 7})\).

L. G. Valiant, &#147General context-free recognition in less than cubic time&#148, Journal of Computer and System Sciences, 10:2 (1975), 308--314; A. Okhotin, &#147Fast parsing for Boolean grammars: a generalization of Valiant's algorithm&#148, TUCS TR 953, принято на DLT 2010.