Computing a context-free grammar-generating series

The parallel complexity of computing context-free grammar generating series is investigated. It is known that this problem is in DIV, but in terms of n(sigma) rather than it, where it is the index of the desired coefficient a nd a is the grammar size. A new method is presented which is in DIV in term s of 2(20(sigma)) - n. Evidence is provided that any direct application of elimination theory to this problem leads to a space and time resource facto r that is nearly exponential in grammar size. (C) 2001 Academic Press.