Город: Санкт-Петербург Новосибирск Казань Язык: Русский 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.