Context-free complexity of finite languages

DOI10.1016/0304-3975(83)90024-5MaRDI QIDQ792097zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On the context-free production complexity of finite languages
• Publication:4937901
• On the character of words of sublinear complexity
• On subword complexity functions
• Cover complexity of finite languages

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• A note on a problem in the theory of grammatical complexity
• Concise description of finite languages

Cited in

(23)

• A lower-bound for the number of productions required for a certain class of languages
• Estimating the Size of Context-Free Tiling Languages
• Compressibility of Finite Languages by Grammars
• Generating all permutations by context-free grammars in Chomsky normal form
• On the cover complexity of finite languages
• Cover complexity of finite languages
• Context-free languages over infinite alphabets
• scientific article; zbMATH DE number 3960994 (Why is no real title available?)
• Generating all permutations by context-free grammars in Greibach normal form
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)
• scientific article; zbMATH DE number 5201364 (Why is no real title available?)
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• On the context-free production complexity of finite languages
• scientific article; zbMATH DE number 4011962 (Why is no real title available?)
• scientific article; zbMATH DE number 1404277 (Why is no real title available?)
• Context-Free Languages of Countable Words
• Context free closed families of languages
• scientific article; zbMATH DE number 5309909 (Why is no real title available?)
• scientific article; zbMATH DE number 2150276 (Why is no real title available?)
• scientific article; zbMATH DE number 4035186 (Why is no real title available?)
• On subword complexity functions
• On the compressibility of finite languages and formal proofs
• The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages

This page was built for publication: Context-free complexity of finite languages

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