CFG análise utilizando espaço

Existem vários algoritmos que podem analisar uma gramática livre de contexto em . Usando a multiplicação de matrizes, pode-se até assintoticamente mais rápido que isso.$O(n^3)$

No entanto, todos os algoritmos para analisar CFGs arbitrários que eu conheço têm um uso de espaço no pior dos casos de (embora, reconhecidamente, eu não tenha idéia do uso de espaço desse algoritmo de multiplicação de matrizes). Eu queria saber se existem algoritmos que melhoram esse uso do espaço (desconsiderando o tempo limite).$\Omega(n^2)$

A pergunta surgiu em minha mente depois de vincular mentalmente ao espaço vinculado a todos os algoritmos de análise de CFG que eu conhecia. Provavelmente não tem interesse prático, mas apenas algo que eu gostaria de saber.Ω ( n 2$CSG = NDSPACE(n) \subseteq DSPACE(n^2)$$\Omega(n^2)$

A primeira metade desta resposta nada mais é do que uma reformulação eficiente ( a ) da resposta de David em termos teóricos da complexidade.log 2 ( n $\log^4(n)$$\log^2(n)$

Linguagens livres de contexto vivem na classe de complexidadeEssa classe é caracterizada de maneira equivalente por circuitos semibordados de profundidade de toras . Estes são circuitos de tamanho polinomial, nos quais as portas OR possuem fan-in ilimitado e as portas AND possuem fan-in (por exemplo, 2). Ao aumentar a profundidade por um fator de log, podemos substituir todos os gateways OR de ventilação ilimitados por ORs de ventilação limitados. Isso colocou o problema emNão é difícil ver como pode ser avaliado por um , digamos, uma pesquisa em profundidade que mantém a sequência esquerda / direita de crianças nos portões explorados até agora. O resultado remonta ao artigo de Lewis-Hartmanis. E enquanto isso melhora o espaço limitado de David, isso pode levar$LOGCFL.$N C 2 D S P A C E ( log 2 ( n ) ) n log $NC^2.$$NC^2$$DSPACE(\log^2(n))$$n^{\log n}$Tempo. Nós não sabemos melhor.

A maneira tradicional de entender a troca de espaço no tempo é usar jogos de seixos. Existem alguns artigos sobre CYK; uma tentativa mais recente está na primeira parte desta apresentação . Aqui é mostrado que (a) o espaço linear pode ser alcançado no tempo exponencial e (b) se o tempo for restrito a , então o CYK usaria pelo menos espaço.n $O(n^2)$$n^2$

Certamente um problema muito interessante, digno de uma olhada.

Qualquer linguagem livre de contexto pode ser descrita por uma gramática na Forma Normal de Chomsky e depois reconhecida por um algoritmo não determinístico que usa bits de memória: basta adivinhar a produção de nível superior ( bits) e o ponto de interrupção na cadeia de entrada entre os dois substrings correspondentes aos dois lados da produção ( bits), recursa no lado menor e continua não recursivamente no lado maior.O ( 1 ) O ( log n $O(\log^2 n)$$O(1)$$O(\log n)$

Pelo teorema de Savitch, segue-se que o problema pode ser resolvido deterministicamente com bits de memória. O algoritmo resultante dessa técnica provavelmente seria bastante ineficiente.$O(\log^4 n)$

As CFLs determinísticas podem ser analisadas no espaço e no tempo polinomial (ou seja, em ). Este é um resultado antigo do Cook . É um problema em aberto se CFLs não determinísticas também estão em SC (mas isso não diz nada sobre a existência de, digamos, algoritmos de espaço linear).S C$O(\log^2 n)$$\mathrm{SC}^2$