Синтаксический анализ CFG с использованием пространства

Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.$O(n^3)$

Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в худшем случае (хотя, по общему признанию, я понятия не имею, каково использование пространства этого алгоритма умножения матриц). Мне было интересно, есть ли какие-либо алгоритмы, которые улучшают это использование пространства (так, не обращая внимания на временные рамки).$\Omega(n^2)$

Вопрос возник у меня в голове после того, как мы мысленно связали с пространством Ω ( n 2 ), ограниченным всеми алгоритмами синтаксического анализа CFG Я знал. Это, вероятно, не представляет практического интереса, а просто то, что мне было бы интересно узнать.$CSG = NDSPACE(n) \subseteq DSPACE(n^2)$$\Omega(n^2)$

Первая половина этого ответа - не более чем эффективная ( - log 2 ( n ) ) перефразировка ответа Дэвида в терминах теории сложности.$\log^4(n)$$\log^2(n)$

Контекст свободных языков живут в классе сложности Этот класс эквивалентно характеризуется полунезависимой схемой глубины каротажа . Это схемы полиномиального размера, в которых вентили ИЛИ имеют неограниченную веерность, а вентили И имеют ограниченную веерность (скажем, 2). Увеличивая глубину на логарифмический коэффициент, мы можем заменить каждый неограниченный вентиль OR с ограниченным вентилем OR. Это ставит проблему в N C 2 . Нетрудно увидеть, как N $LOGCFL.$$NC^2.$ можно оценить с помощью D S P A C E ( log 2$NC^2$ скажем, поиск в глубину, который поддерживает последовательность левых / правых детей у изученных до сих пор ворот. Результат восходит к статье Льюиса-Хартманиса. И хотя это улучшает ограничение пространства Дэвида, это может занять n log n времени. Мы не знаем лучше.$DSPACE(\log^2(n))$$n^{\log n}$

Традиционный способ понять компромисс между временем и пространством - это использовать игры с галькой. Там было несколько работ на CYK; более поздняя попытка находится в первой части этой презентации . Здесь показано, что (а) линейное пространство может быть достигнуто за экспоненциальное время и (б) если время ограничено , то CYK будет использовать по крайней мере n 2 пространства.$O(n^2)$$n^2$

Конечно, очень интересная проблема, достойная внимания.

Любой контекстно-свободный язык может быть описан грамматикой в ​​нормальной форме Хомского, а затем распознан недетерминированным алгоритмом, который использует битов памяти: достаточно угадать производственный ( O ( 1 ) биты) верхнего уровня и точка останова во входной строке между двумя подстроками, совпадающими с двумя сторонами производства ( O ( $O(\log^2 n)$$O(1)$$O(\log n)$

$O(\log^4 n)$

$O(\log^2 n)$$\mathrm{SC}^2$