𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture about slender context-free languages

✍ Scribed by Lucian Ilie

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
450 KB
Volume
132
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Remarks about Commutative Context-Free L
Remarks about Commutative Context-Free Languages
✍ Juha Kortelainen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 205 KB

We prove that the complement of a commutative language L is context-free if the Parikh-map of L is a proper linear set. Some sharpenings to results considering the Fliess conjecture on commutative contextfree languages are given. A conjecture concerning commutative star languages is disproved by a c

A decision method for Parikh slenderness
A decision method for Parikh slenderness of context-free languages
✍ Juha Honkala 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 218 KB

In a recent paper we introduced Parikh slender languages as a generalization of slender languages defined and studied by AndraSiu, Dassow, Pgun and Salomaa. Results concerning Pa&h slender languages can be applied in ambiguity proofs of context-free languages. In this paper an algorithm is presented

Chomsky-Schützenberger Type Characteriza
Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages
✍ Masami Ito; Carlos Martín-Vide; Victor Mitrana 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 272 KB

In this paper we propose a Chomsky-Schützenberger type characterization ofpoly-slender context-free languages, as the homomorphical image of an intersection of a Dyck language and a ´¾ • ½ µ -poly-slender regular language. A stronger result is provided, namely the homomorphism and the Dyck language