CFG parsing using $o(n^2)$ space

Question

There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.

However, all algorithms for parsing arbitrary CFGs I know have a worst-case space usage of $\Omega(n^2)$ (although, admittedly, I have no idea what the space usage of that matrix multiplication algorithm is). I was wondering whether there are any algorithms that improve upon this space usage (so disregarding the time bound).

The question popped up into my mind after mentally linking $CSG = NDSPACE(n) \subseteq DSPACE(n^2)$ with the $\Omega(n^2)$ space bound on all the CFG parsing algorithms I knew. It's probably of no practical interest, but merely something I'd be interested in knowing.

Answer 1

The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms.

Context free languages live in the complexity class $LOGCFL.$ This class is equivalently characterized by log depth semi-unbounded circuits. These are polynomial sized circuits wherein OR gates have unbounded fan-in and AND gates have bounded fan-in (say 2). By increasing depth by a log factor, we can replace every unbounded fan-in OR gate with bounded fan-in ORs. This put the problem in $NC^2.$ It is not difficult to see how $NC^2$ can be evaluated by a $DSPACE(\log^2(n))$ by say a depth first search that maintains the left/right sequence of children at the gates explored thus far. The result goes back to the Lewis-Hartmanis paper. And while this improves David's space bound, this can take $n^{\log n}$ time. We do not know any better.

The traditional way to understand time space tradeoff is to use pebble games. There have been a few papers on CYK; a more recent attempt is in the first part of this presentation. Here it is shown that (a) linear space can be achieved at exponential time and (b) if time is restricted to $O(n^2)$, then CYK would use at least $n^2$ space.

Certainly a very interesting problem worthy of a look.

Answer 2

Any context free language can be described by a grammar in Chomsky Normal Form, and then recognized by a nondeterministic algorithm that uses $O(\log^2 n)$ bits of memory: just guess the top-level production ($O(1)$ bits) and the breakpoint in the input string between the two substrings matched by the two sides of the production ($O(\log n)$ bits), recurse on the smaller side, and then continue non-recursively on the larger side.

By Savitch's theorem, it follows that the problem can be solved deterministically with $O(\log^4 n)$ bits of memory. The algorithm resulting from this technique would likely be quite inefficient, however.

Answer 3

Deterministic CFL’s can be parsed in space $O(\log^2 n)$ and polynomial time (i.e., in $\mathrm{SC}^2$). This is an old result of Cook. It is an open problem whether nondeterministic CFL’s are also in SC (but this does not say anything about the existence of, say, linear space algorithms).