Что: | Лекция |
Когда: | Воскресенье, 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.