More on the power of chain rules in context-free grammars (Q759487)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: More on the power of chain rules in context-free grammars |
scientific article; zbMATH DE number 3881892
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | More on the power of chain rules in context-free grammars |
scientific article; zbMATH DE number 3881892 |
Statements
More on the power of chain rules in context-free grammars (English)
0 references
1983
0 references
For all \(\epsilon >0\) we prove for every sufficiently large n: there exists a context-free language \(CL_ n\) with the following properties: (a) \(CL_ n\) has a cfg of size O(n). (b) Each chain rule free cfg for \(CL_ n\) has size \(\Omega (\epsilon^ 3n^{3/2-\epsilon}).\)
0 references
size reduction
0 references
context-free language
0 references
