Análisis de CFG usando el espacio

Hay una multitud de algoritmos que pueden analizar una gramática libre de contexto en tiempo . Usando la multiplicación de matrices, incluso se puede ir asintóticamente más rápido que eso.$O(n^3)$

Sin embargo, todos los algoritmos para analizar CFG arbitrarios que conozco tienen un uso de espacio en el peor de los casos de (aunque, ciertamente, no tengo idea de cuál es el uso de espacio de ese algoritmo de multiplicación de matriz). Me preguntaba si hay algún algoritmo que mejore este uso del espacio (sin tener en cuenta el límite de tiempo).$\Omega(n^2)$

La pregunta apareció en mi mente después de vincular mentalmente con el espacio vinculado en todos los algoritmos de análisis de CFG que conocía. Probablemente no tenga ningún interés práctico, sino simplemente algo que me interesaría saber.Ω ( n 2$CSG = NDSPACE(n) \subseteq DSPACE(n^2)$$\Omega(n^2)$

La primera mitad de esta respuesta no es más que una reformulación eficiente ( $\log^4(n)$ a $\log^2(n)$ ) de la respuesta de David en términos teóricos de complejidad.

Los lenguajes libres de contexto viven en la clase de complejidad $LOGCFL.$Esta clase se caracteriza de manera equivalente por circuitos semifuncionales de profundidad logarítmica . Estos son circuitos de tamaño polinómico en los que las compuertas OR tienen entrada de ventilador sin límites y las compuertas AND tienen entrada de ventilador limitada (digamos 2). Al aumentar la profundidad por un factor de registro, podemos reemplazar todas las compuertas OR de entrada de ventilador ilimitadas con ORs de entrada de ventilador delimitadas. Esto puso el problema en $NC^2.$No es difícil ver cómo $NC^2$ puede ser evaluado por un $DSPACE(\log^2(n))$ mediante una primera búsqueda en profundidad que mantiene la secuencia izquierda / derecha de los niños en las puertas exploradas hasta ahora. El resultado se remonta al artículo de Lewis-Hartmanis. Y si bien esto mejora el límite de espacio de David, esto puede tomar $n^{\log n}$hora. No sabemos nada mejor.

La forma tradicional de entender el intercambio espacio-tiempo es usar juegos de guijarros. Ha habido algunos trabajos sobre CYK; Un intento más reciente se encuentra en la primera parte de esta presentación . Aquí se muestra que (a) se puede lograr un espacio lineal en el tiempo exponencial y (b) si el tiempo está restringido a , entonces CYK usaría al menos espacio.n $O(n^2)$$n^2$

Sin duda un problema muy interesante digno de una mirada.

Cualquier lenguaje libre de contexto puede describirse mediante una gramática en forma normal de Chomsky, y luego reconocerse mediante un algoritmo no determinista que utiliza bits de memoria: solo adivine los bits de producción de nivel superior ( ) y el punto de interrupción en la cadena de entrada entre las dos subcadenas emparejadas por los dos lados de la producción ( bits ), se repite en el lado más pequeño y luego continúa de forma no recursiva en el lado más grande.O ( 1 ) O ( log n $O(\log^2 n)$$O(1)$$O(\log n)$

Según el teorema de Savitch, se deduce que el problema se puede resolver de manera determinista con bits de memoria. Sin embargo, el algoritmo resultante de esta técnica probablemente sería bastante ineficiente.$O(\log^4 n)$

Los CFL deterministas se pueden analizar en el espacio y el tiempo polinomial (es decir, en ). Este es un viejo resultado de Cook . Es un problema abierto si las CFL no deterministas también están en SC (pero esto no dice nada sobre la existencia de, digamos, algoritmos de espacio lineal).S C$O(\log^2 n)$$\mathrm{SC}^2$