Length considerations in context-free languages

DOI10.1016/S0304-3975(96)00308-8zbMath0911.68097MaRDI QIDQ1391135

Danny Raz

Publication date: 22 July 1998

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

zbMATH Keywords

context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (16)

Slender 0L languages ⋮ On differentiation functions, structure functions, and related languages of context-free grammars ⋮ Language-theoretic complexity of disjunctive sequences ⋮ Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages1 1Work supported by the Grants-in Aid for Scientific Research No. 1 0440034, Japan Society for the Promotion of Sciences and the Dirección General de Enseñanza Superior e Investigación Cientifica, SB 97-00110508 ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ The monoids of the patience sorting algorithm ⋮ A decision method for Parikh slenderness of context-free languages ⋮ Slender Siromoney matrix languages ⋮ FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME ⋮ On the structure of the counting function of sparse context-free languages. ⋮ On Parikh slender context-free languages ⋮ Contexts on trajectories ⋮ The Parikh counting functions of sparse context-free languages are quasi-polynomials ⋮ On lengths of words in context-free languages ⋮ A characterization of poly-slender context-free languages ⋮ Min of Mat is not necessarily Mat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Language-theoretic problems arising from Richelieu cryptosystems
• Closure properties of slender languages
• On a conjecture about slender context-free languages
• Thin and slender languages

This page was built for publication: Length considerations in context-free languages