next up previous
Next: A boolean function requiring Up: Abstracts Previous: On the average case

More on the power of chain rules in context-free grammars

For all $\epsilon > 0$ we prove for every sufficiently large n: There exists a context-free language CLn with the following properties:

CLn has a cfg of size O(n).
Each chain rule free cfg for CLn has size $\Omega(\epsilon^3 n^{3/2-\epsilon})$.

Claus Rick