Context-free complexity of finite languages

DOI10.1016/0304-3975(83)90024-5zbMATH Open0536.68065OpenAlexW2023738367MaRDI QIDQ792097FDOQ792097

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

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

zbMATH Keywords

finite languagesinfinite languagenumber of productionssublinear complexity

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Concise description of finite languages
• A note on a problem in the theory of grammatical complexity

Cited In (23)

• Title not available (Why is that?)
• On the cover complexity of finite languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Context-Free Languages of Countable Words
• The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages
• Title not available (Why is that?)
• On subword complexity functions
• Title not available (Why is that?)
• Generating all permutations by context-free grammars in Chomsky normal form
• Generating all permutations by context-free grammars in Greibach normal form
• Compressibility of Finite Languages by Grammars
• Title not available (Why is that?)
• Cover complexity of finite languages
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• On the context-free production complexity of finite languages
• Title not available (Why is that?)
• A lower-bound for the number of productions required for a certain class of languages
• Estimating the Size of Context-Free Tiling Languages
• On the compressibility of finite languages and formal proofs
• Context-free languages over infinite alphabets
• Context free closed families of 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)