On lengths of words in context-free languages
From MaRDI portal
Publication:1575557
DOI10.1016/S0304-3975(98)00266-7zbMath0944.68099MaRDI QIDQ1575557
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
decidability; context-free language; slender language; effective constructions; single and paired loops
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 the structure of the counting function of sparse context-free languages.
Uses Software
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