Context-free complexity of finite languages

DOI10.1016/0304-3975(83)90024-5zbMath0536.68065OpenAlexW2023738367MaRDI QIDQ792097

W. Bucher, Hermann Maurer, Karel II Culik

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90024-5

zbMATH Keywords

finite languagesinfinite languagenumber of productionssublinear complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Generating all permutations by context-free grammars in Chomsky normal form ⋮ Generating all permutations by context-free grammars in Greibach normal form ⋮ On the context-free production complexity of finite languages ⋮ On the compressibility of finite languages and formal proofs ⋮ GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM ⋮ On the cover complexity of finite languages ⋮ A lower-bound for the number of productions required for a certain class of languages

Cites Work

• Unnamed Item
• Concise description of finite languages
• A note on a problem in the theory of grammatical complexity