A characterization of poly-slender context-free languages

DOI10.1051/ITA:2000100MaRDI QIDQ4494483zbMATH OpenOpenAlexFDO

Authors Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa

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, https://semanticscholar.org/paper/227802033a0515f49f699b6cd5742fee9336958c

zbMATH Keywords

context-free languagepoly-slender languageDyck loop

Mathematics Subject Classification ID

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

Recommendations

• ON GENERALIZED SLENDERNESS OF CONTEXT-FREE LANGUAGES
• Chomsky-Schützenberger type characterizations of poly-slender and Parikh slender context-free languages
• scientific article; zbMATH DE number 2186402
• scientific article; zbMATH DE number 1870552
• A Chomsky-Schützenberger-Stanley type characterization of the class of slender context-free languages

Cites work

• scientific article; zbMATH DE number 3880130 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1995145 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• scientific article; zbMATH DE number 3415406 (Why is no real title available?)
• Bounded Algol-Like Languages
• Decision problems concerning thinness and slenderness of formal languages
• H-bounded and semi-discrete languages
• Language-theoretic problems arising from Richelieu cryptosystems
• Length considerations in context-free languages
• Numeration systems, linear recurrences, and regular sets
• On Parikh slender languages and power series
• On a conjecture about slender context-free languages
• On lengths of words in context-free languages
• Semi-discrete context-free languages^†
• Slender 0L languages
• Thin and slender languages

Cited in

(20)

• scientific article; zbMATH DE number 1870552 (Why is no real title available?)
• On the Commutative Equivalence of Algebraic Formal Series and Languages
• On universally easy classes for NP-complete problems.
• On bounded linear codes and the commutative equivalence
• scientific article; zbMATH DE number 1059896 (Why is no real title available?)
• Recognition of poly-slender context-free languages by trellis automata
• Slender Siromoney matrix languages
• Chomsky-Schützenberger type characterizations of poly-slender and Parikh slender context-free languages
• Dead ends and rationality of complete growth series
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• ON GENERALIZED SLENDERNESS OF CONTEXT-FREE LANGUAGES
• On the structure of the counting function of sparse context-free languages.
• scientific article; zbMATH DE number 2186402 (Why is no real title available?)
• Periodic and Sturmian languages
• The Parikh counting functions of sparse context-free languages are quasi-polynomials
• A sharpening of the Parikh mapping
• A Chomsky-Schützenberger-Stanley type characterization of the class of slender context-free languages
• On the separability of sparse context-free languages and of bounded rational relations
• On the commutative equivalence of bounded context-free and regular languages: the code case
• Finding the growth rate of a regular or context-free language in polynomial time

Describes a project that uses

Uses Software

• ALGOL 60

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4494483)