Lower bounds for context-free grammars

DOI10.1016/J.IPL.2011.06.006MaRDI QIDQ1944159zbMATH OpenOpenAlexFDO

Authors Yuval Filmus

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.06.006

zbMATH Keywords

context-free grammarsformal languageslower bounds

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Polynomial size test sets for context-free languages
• scientific article; zbMATH DE number 2032367
• On minimal grammar problems for finite languages
• Generating all permutations by context-free grammars in Greibach normal form
• More on the power of chain rules in context-free grammars

Cites work

• Complexity of normal form grammars
• Generating all circular shifts by context-free grammars in Chomsky normal form
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• Generating all permutations by context-free grammars in Chomsky normal form
• Generating all permutations by context-free grammars in Greibach normal form
• Regular expressions: new results and open problems
• The Smallest Grammar Problem

Cited in

(12)

• A lower bound for the nondeterministic space complexity of context-free recognition
• On the complexity of the smallest grammar problem over fixed alphabets
• Some results on small context-free grammars generating primitive words
• On the sizes of DPDAs, PDAs, LBAs
• scientific article; zbMATH DE number 2032367 (Why is no real title available?)
• scientific article; zbMATH DE number 1400022 (Why is no real title available?)
• scientific article; zbMATH DE number 7559421 (Why is no real title available?)
• Optimal regular expressions for permutations
• Regular expression length via arithmetic formula complexity
• Largest common prefix of a regular tree language
• A formal language perspective on factorized representations
• More on the power of chain rules in context-free grammars

This page was built for publication: Lower bounds for context-free grammars

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