𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Parikh Slender Languages and Power Series

✍ Scribed by Juha Honkala

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
266 KB
Volume
52
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We define and study Parikh slender languages and power series. A language is Parikh slender if the number of words in the language with the same Parikh vector is bounded from above. As an application we get a new method for ambiguity proofs of context-free languages and a new proof of an earlier result of Autebert, Flajolet, and Gabarro concerning prefixes of infinite words.

📜 SIMILAR VOLUMES

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

The Equivalence Problem for DF0L Languag
The Equivalence Problem for DF0L Languages and Power Series
✍ Juha Honkala 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 158 KB

We show that equivalence is decidable for D0L systems with finite axiom sets. We discuss also DF0L power series and solve their equivalence problem over computable fields.