Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Воскресенье, 18 октября 2009, 11:15–12:45
Где: ПОМИ РАН

Описание

Однозначные грамматики. Лемма Огдена и доказательство существенной неоднозначности бесконтекстного языка ${a^i b^j c^j \mid i=j$ или $j=k}$. Разбор однозначных булевых грамматик за время $O(n^2)$.

A. Okhotin, “Unambiguous Boolean grammars”, Information and Computation, 206:9—10 (2008), 1234—1247.