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:

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



Claus Rick
2000-05-10