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

Описание

Разбор бесконтекстных языков булевой схемой: алгоритм Брента—Гольдшлягера—Риттера, строящий схему высоты \(O(\log^2 n)\) с \(O(n^6)\) элементами. Реализация алгоритма на машине Тьюринга с использованием \(O(\log^2 n)\) бит памяти. Понятие P-полного языка, P-полнота задачи о значении схемы. Булева грамматика для P-полного языка.

R. P. Brent, L. M. Goldschlager, “A parallel algorithm for context-free parsing&#148, Australian Computer Science Communications, 6:7 (1984), 7.1—7.10; W. Rytter, &#147On the recognition of context-free languages&#148, FCT 1985, LNCS 208, 315—322; R. E. Ladner, &#147The circuit value problem is log space complete for P&#148, SIGACT News, 7:1 (1975), 18—20; A. Okhotin, “A simple P-complete problem and its representations by language equations&#148, MCU 2007, 267—278.