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

decidability; context-free language; slender language; effective constructions; single and paired loops

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

Related Items

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

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