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 |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.772000789642334
0 references
0.7509542107582092
0 references
0.7488687634468079
0 references
0.7479202747344971
0 references
0.7479202747344971
0 references
