A characterization of poly-slender context-free languages

DOI10.1051/ita:2000100zbMath0966.68097OpenAlexW2025440801MaRDI QIDQ4494483

Lucian Ilie, Arto Salomaa, Grzegorz Rozenberg

Publication date: 6 February 2001

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222052

zbMATH Keywords

context-free languagepoly-slender languageDyck loop

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (14)

Periodic and Sturmian languages ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ 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 ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ On universally easy classes for NP-complete problems. ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ On bounded linear codes and the commutative equivalence ⋮ On the commutative equivalence of bounded context-free and regular languages: the code case ⋮ 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 the separability of sparse context-free languages and of bounded rational relations ⋮ The Parikh counting functions of sparse context-free languages are quasi-polynomials ⋮ A sharpening of the Parikh mapping

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Language-theoretic problems arising from Richelieu cryptosystems
• Decision problems concerning thinness and slenderness of formal languages
• Numeration systems, linear recurrences, and regular sets
• On a conjecture about slender context-free languages
• Slender 0L languages
• Length considerations in context-free languages
• On lengths of words in context-free languages
• Thin and slender languages
• On Parikh slender languages and power series
• Semi-discrete context-free languages^†
• H-bounded and semi-discrete languages
• Bounded Algol-Like Languages

This page was built for publication: A characterization of poly-slender context-free languages