On lengths of words in context-free languages

DOI10.1016/S0304-3975(98)00266-7zbMath0944.68099MaRDI QIDQ1575557

Lucian Ilie

Publication date: 21 August 2000

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

zbMATH Keywords

decidabilitycontext-free languageslender languageeffective constructionssingle and paired loops

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (8)

On differentiation functions, structure functions, and related languages of context-free grammars ⋮ On counting functions and slenderness of languages ⋮ Slender Siromoney matrix languages ⋮ On the structure of the counting function of sparse context-free languages. ⋮ Decimations of languages and state complexity ⋮ On strongly context-free languages ⋮ A characterization of poly-slender context-free languages ⋮ Min of Mat is not necessarily Mat

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decision method for Parikh slenderness of context-free languages
• Language-theoretic problems arising from Richelieu cryptosystems
• Decision problems concerning thinness and slenderness of formal languages
• Closure properties of slender languages
• Numeration systems, linear recurrences, and regular sets
• On a conjecture about slender context-free languages
• Slender 0L languages
• Language-theoretic complexity of disjunctive sequences
• Length considerations in context-free languages
• A note on decidability questions on presentations of word semigroups
• Thin and slender languages
• On Parikh slender languages and power series
• On slender context-free languages
• Characterizing regular languages with polynomial densities
• Bounded Algol-Like Languages

This page was built for publication: On lengths of words in context-free languages