Lower bounds for context-free grammars

DOI10.1016/j.ipl.2011.06.006zbMath1260.68204OpenAlexW2055190789MaRDI QIDQ1944159

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 grammarslower boundsformal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

On the sizes of DPDAs, PDAs, LBAs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Regular expression length via arithmetic formula complexity ⋮ Largest common prefix of a regular tree language

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of normal form grammars
• Generating all permutations by context-free grammars in Chomsky normal form
• Generating all permutations by context-free grammars in Greibach normal form
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• The Smallest Grammar Problem

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