Analiza CFG przy użyciu spacji

Istnieje wiele algorytmów, które mogą analizować gramatykę bezkontekstową w czasie . Używając mnożenia macierzy, można nawet iść asymptotycznie szybciej.$O(n^3)$

Jednak wszystkie algorytmy do analizy dowolnych CFG, które znam, mają najgorsze wykorzystanie przestrzeni (chociaż, co prawda, nie mam pojęcia, jakie jest użycie przestrzeni przez ten algorytm mnożenia macierzy). Zastanawiałem się, czy istnieją jakieś algorytmy, które poprawiłyby wykorzystanie tego miejsca (więc pomijając ograniczenie czasowe).$\Omega(n^2)$

Pytanie pojawiło się w moim umyśle po mentalnym połączeniu ze spacją związaną ze wszystkimi znanymi algorytmami parsowania CFG. Prawdopodobnie nie ma to praktycznego znaczenia, a jedynie coś, o czym chciałbym wiedzieć.$CSG = NDSPACE(n) \subseteq DSPACE(n^2)$$\Omega(n^2)$

Pierwsza połowa tej odpowiedzi to nic innego jak skuteczne ( do log 2 ( n ) ) przeformułowanie odpowiedzi Davida w kategoriach złożoności teoretycznej.$\log^4(n)$$\log^2(n)$

Język bezkontekstowy żyć w klasie złożoność Klasa ta jest równoważnie charakteryzowana przez półzwiązane obwody o głębokości logarytmicznej . Są to obwody wielomianowe, w których bramki OR mają nieograniczony wachlarz, a bramki AND mają ograniczony wachlarz (powiedzmy 2). Zwiększając głębokość o współczynnik logarytmiczny, możemy zastąpić każdą nieograniczoną bramę wachlarza wachlarza ograniczonymi OR wachlarzem wachlarza. To postawiło problem w N C 2 . Nietrudno dostrzec, jak N C 2 można ocenić za pomocą D S P A C E ( log 2$LOGCFL.$$NC^2.$$NC^2$ powiedzmy najpierw głębokie poszukiwanie, które utrzymuje lewą / prawą sekwencję dzieci przy zbadanych do tej pory bramach. Wynik wraca do pracy Lewisa-Hartmanisa. I chociaż poprawia to ograniczenie przestrzeni Davida, może to zająć n log n czasu. Nie wiemy nic lepszego.$DSPACE(\log^2(n))$$n^{\log n}$

Tradycyjnym sposobem na zrozumienie kompromisu czasoprzestrzennego jest użycie gry kamykowej. Było kilka artykułów na temat CYK; ostatnia próba jest w pierwszej części tej prezentacji . Tutaj pokazano, że (a) przestrzeń liniowa może być osiągnięta w czasie wykładniczym i (b) jeśli czas jest ograniczony do , wówczas CYK użyłby co najmniej n 2 przestrzeni.$O(n^2)$$n^2$

Z pewnością bardzo interesujący problem wart uwagi.

$O(\log^2 n)$$O(1)$$O(\log n)$

$O(\log^4 n)$

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