CFG-Analyse mit

Es gibt eine Vielzahl von Algorithmen, die eine kontextfreie Grammatik in analysieren können.. Mit der Matrixmultiplikation kann man sogar asymptotisch schneller gehen.$O(n^3)$

Alle Algorithmen zum Parsen beliebiger CFGs, die ich kenne, haben jedoch eine schlechteste Raumnutzung von (obwohl ich zugegebenermaßen keine Ahnung habe, wie viel Raum dieser Matrixmultiplikationsalgorithmus verwendet). Ich habe mich gefragt, ob es Algorithmen gibt, die diese Speicherplatznutzung verbessern (also die Zeitgrenze außer Acht lassen).$\Omega(n^2)$

Die Frage tauchte in meinem Kopf auf, nachdem ich mental mit dem Ω ( n 2 ) -Raum verknüpft hatte, der für alle CFG-Parsing-Algorithmen gilt Ich wusste. Es ist wahrscheinlich nicht von praktischem Interesse, sondern nur etwas, das mich interessieren würde.$CSG = NDSPACE(n) \subseteq DSPACE(n^2)$$\Omega(n^2)$

Die erste Hälfte dieser Antwort ist nichts anderes als eine effiziente ( bis log 2 ( n ) ) Umformulierung von Davids Antwort in komplexitätstheoretischen Begriffen.$\log^4(n)$$\log^2(n)$

Kontextfreie Sprachen leben in der Komplexitätsklasse Diese Klasse ist äquivalent gekennzeichnet durch logarithmisch tiefe, halbbegrenzte Schaltungen. Hierbei handelt es sich um polynomgroße Schaltungen, bei denen ODER-Gatter einen unbegrenzten Fan-In und UND-Gatter einen begrenzten Fan-In aufweisen (z. B. 2). Durch Erhöhen der Tiefe um einen logarithmischen Faktor können wir jedes unbegrenzte Fan-In-ODER-Gatter durch begrenzte Fan-In-ODER-Gatter ersetzen. Dies brachte das Problem in N C 2 . Es ist nicht schwer zu erkennen, wie N C 2 mit einem D S P A C E ( log 2$LOGCFL.$$NC^2.$$NC^2$ etwa eine Tiefensuche, die die bisher untersuchte Links- / Rechtsreihenfolge der Kinder an den Toren beibehält. Das Ergebnis geht auf das Lewis-Hartmanis-Papier zurück. Und während dies Davids Platzbedarf verbessert, kann dies n log n Zeit in Anspruch nehmen. Wir wissen es nicht besser.$DSPACE(\log^2(n))$$n^{\log n}$

Der traditionelle Weg, um den Zeit-Raum-Kompromiss zu verstehen, ist die Verwendung von Kieselspielen. Es gab einige Artikel über CYK; Ein neuerer Versuch befindet sich im ersten Teil dieser Präsentation . Hier wird gezeigt, dass (a) ein linearer Raum zur Exponentialzeit erreicht werden kann und (b) wenn die Zeit auf , dann würde CYK mindestens n 2 Raum verwenden.$O(n^2)$$n^2$

Mit Sicherheit ein sehr interessantes Problem, das einen Blick wert ist.

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

$O(\log^4 n)$

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