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 σ rather than n, where n is the index of the desired coefficient and σ is the grammar size. A new method is presented which is in DIV in terms of 22 O(σ) ·n. Evidence is provided that any direct application of elimination theory to this problem leads to a space and time resource factor that is nearly exponential in grammar size.

Authors

• Bruce Litow

Keywords

No keywords are indexed for this paper.