On Parikh slender context-free languages

DOI10.1016/S0304-3975(00)00393-5MaRDI QIDQ5941095zbMATH OpenFDO

Authors Juha Honkala

Publication date 20 August 2001

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

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00393-5

zbMATH Keywords

bounded languagescontext-free languagesParikh slender languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

In a recent paper we defined and studied Parikh slender languages and showed that they can be used in simplifying ambiguity proofs of context-free languages. In this paper Parikh slender context-free languages are characterized. The characterization has diverse applications.

Recommendations

• On Parikh slender languages and power series
• A decision method for Parikh slenderness of context-free languages
• Chomsky-Schützenberger type characterizations of poly-slender and Parikh slender context-free languages
• On slender context-free languages
• scientific article; zbMATH DE number 1156871

Cites work

• A decision method for Parikh slenderness of context-free languages
• Analytic models and ambiguity of context-free languages
• Bounded Algol-Like Languages
• Closure properties of slender languages
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 58306 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 1995145 (Why is no real title available?)
• scientific article; zbMATH DE number 1543062 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Language-theoretic problems arising from Richelieu cryptosystems
• Length considerations in context-free languages
• Numeration systems, linear recurrences, and regular sets
• On a conjecture about slender context-free languages
• On Parikh slender languages and power series
• Prefixes of infinite words and ambiguous context-free languages
• Slender 0L languages
• Thin and slender languages

Cited in

(12)

• The Parikh counting functions of sparse context-free languages are quasi-polynomials
• On Parikh slender languages and power series
• On bounded linear codes and the commutative equivalence
• On the structure of the counting function of sparse context-free languages.
• A Chomsky-Schützenberger-Stanley type characterization of the class of slender context-free languages
• scientific article; zbMATH DE number 1059896 (Why is no real title available?)
• scientific article; zbMATH DE number 1543062 (Why is no real title available?)
• On the commutative equivalence of bounded context-free and regular languages: the code case
• Chomsky-Schützenberger type characterizations of poly-slender and Parikh slender context-free languages
• ON GENERALIZED SLENDERNESS OF CONTEXT-FREE LANGUAGES
• On the Commutative Equivalence of Algebraic Formal Series and Languages
• A decision method for Parikh slenderness of context-free languages

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: On Parikh slender context-free languages

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