Analyse CFG en utilisant l' espace

Il existe une multitude d'algorithmes qui peuvent analyser une grammaire sans contexte en temps . En utilisant la multiplication matricielle, on peut même aller plus vite asymptotiquement que cela.$O(n^3)$

Cependant, tous les algorithmes d'analyse syntaxique des CFG arbitraires que je connais ont une utilisation de l'espace dans le pire des cas de (bien que, certes, je n'ai aucune idée de l'utilisation de l'espace de cet algorithme de multiplication matricielle). Je me demandais s'il existe des algorithmes qui améliorent cette utilisation de l'espace (sans tenir compte de la limite de temps).$\Omega(n^2)$

La question esprit après avoir mentalement avec l' espace lié à tous les algorithmes d'analyse CFG que je connaissais. Ce n'est probablement d'aucun intérêt pratique, mais simplement quelque chose que j'aimerais savoir.$CSG = NDSPACE(n) \subseteq DSPACE(n^2)$$\Omega(n^2)$

La première moitié de cette réponse n'est rien d'autre qu'une reformulation efficace ( à log 2 ( n ) ) de la réponse de David en termes théoriques de complexité.$\log^4(n)$$\log^2(n)$

Langues libres de contexte vivent dans la classe de complexité Cette classe est caractérisée de manière équivalente par des circuits semi-illimités de profondeur logarithmique . Il s'agit de circuits de taille polynomiale dans lesquels les portes OU ont une entrée fanée illimitée et les portes ET ont une entrée fanée bornée (disons 2). En augmentant la profondeur par un facteur logarithmique, nous pouvons remplacer chaque porte OU de fan-in illimitée par des OR de fan-in bornés. Cela a posé le problème dans N C 2 . Il n'est pas difficile de voir comment N C 2 peut être évalué par un D S P A C E ( log 2$LOGCFL.$$NC^2.$$NC^2$ par exemple une première recherche en profondeur qui maintient la séquence gauche / droite des enfants aux portes explorées jusqu'à présent. Le résultat remonte à l'article de Lewis-Hartmanis. Et bien que cela améliore l'espace lié à David, cela peut prendre n log n temps. Nous ne savons pas mieux.$DSPACE(\log^2(n))$$n^{\log n}$

La manière traditionnelle de comprendre le compromis espace-temps est d'utiliser des jeux de galets. Il y a eu quelques articles sur CYK; une tentative plus récente figure dans la première partie de cette présentation . Ici, il est montré que (a) l'espace linéaire peut être atteint à un temps exponentiel et (b) si le temps est limité à , alors CYK utiliserait au moins n 2 espace.$O(n^2)$$n^2$

Certainement un problème très intéressant qui mérite le détour.

Tout langage sans contexte peut être décrit par une grammaire sous forme normale de Chomsky, puis reconnu par un algorithme non déterministe qui utilise bits de mémoire: il suffit de deviner la production de niveau supérieur ( O ( 1 ) bits) et le point d'arrêt dans la chaîne d'entrée entre les deux sous-chaînes correspondant aux deux côtés de la production ( bits O ( log n ) ), récursif sur le petit côté, puis continue de manière non récursive sur le grand côté.$O(\log^2 n)$$O(1)$$O(\log n)$

Par le théorème de Savitch, il s'ensuit que le problème peut être résolu de façon déterministe avec bits de mémoire. Cependant, l'algorithme résultant de cette technique serait probablement assez inefficace.$O(\log^4 n)$

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