Lower bounds for context-free grammars
From MaRDI portal
Publication:1944159
DOI10.1016/j.ipl.2011.06.006zbMath1260.68204MaRDI QIDQ1944159
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
68Q45: Formal languages and automata
Related Items
Unnamed Item, Unnamed Item, Regular expression length via arithmetic formula complexity, Largest common prefix of a regular tree language, On the sizes of DPDAs, PDAs, LBAs, On the complexity of the smallest grammar problem over fixed alphabets
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