Next: A boolean function requiring
Up: Abstracts
Previous: On the average case
For all
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
.
Claus Rick
2000-05-10