Analiza CFG przy użyciu spacji

18

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(n3)

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).Ω(n2)

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)reS.P.ZAdomi(n2))Ω(n2))

Alex ten Brink
źródło
5
Nie wiem o wszystkich innych algorytmach parsowania, ale te oparte na mnożeniu macierzy zajmują miejsca; patrz: cstheory.stackexchange.com/questions/1313/...Θ(n2)
Ryan Williams,

Odpowiedzi:

14

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.log4(n)log2(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.NC2.NC2 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(log2(n))nlogn

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(n2)n2

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

V Vinay
źródło
To była całkiem interesująca prezentacja, dzięki za link.
Alex ten Brink
13

O(log2n)O(1)O(logn)

O(log4n)

David Eppstein
źródło
3
Właśnie natknąłem się na podobny wynik Lewisa i in. tutaj: ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5397245 . Pozostaje jednak pytanie, czy możemy zrobić coś lepszego niż przestrzeń kwadratowa, używając tylko czasu wielomianowego.
Alex ten Brink
8

O(log2n)SC2

Emil Jeřábek wspiera Monikę
źródło