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

DOI10.1016/0304-3975(82)90122-0MaRDI QIDQ759487zbMATH OpenOpenAlexFDO

Authors Norbert Blum

Publication date 1983

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(82)90122-0

zbMATH Keywords

context-free languagesize reduction

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

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}).\)

Recommendations

• Lower bounds for context-free grammars
• On the context-free production complexity of finite languages
• Greibach normal form transformation revisited.
• Polynomial size test sets for context-free languages
• Derivational complexity of context-free grammars

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• On Graphs that do not Contain a Thomsen Graph
• On the power of chain rules in context free grammars

Cited in

(3)

• Lower bounds for context-free grammars
• scientific article; zbMATH DE number 58320 (Why is no real title available?)
• Greibach normal form transformation, revisited

This page was built for publication: More on the power of chain rules in context-free grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q759487)