𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subclasses of Linear Context—Free Languages and Homomorphic Characterizations of Languages

✍ Scribed by Satoshi Okawa; Sadaki Hirose

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
618 KB
Volume
22
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The inclusion problem for some subclasse
The inclusion problem for some subclasses of context-free languages
✍ Peter R.J. Asveld; Anton Nijholt 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 131 KB

By a reduction to Post's Correspondence Problem we provide a direct proof of the known fact that the inclusion problem for unambiguous context-free grammars is undecidable. The argument or some straightforward modiÿcation also applies to some other subclasses of context-free languages such as linear

Growth-sensitivity of context-free langu
Growth-sensitivity of context-free languages
✍ Tullio Ceccherini-Silberstein; Wolfgang Woess 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 265 KB

A language L over a ÿnite alphabet is called growth-sensitive if forbidding any set of subwords F yields a sub-language L F whose exponential growth rate is smaller than that of L. It is shown that every (essentially) ergodic non-linear context-free language of convergent type is growth-sensitive. "

Homomorphic characterizations of recursi
Homomorphic characterizations of recursively enumerable languages with very small language classes
✍ Satoshi Okawa; Sadaki Hirose 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 137 KB

In this paper, we attempt to characterize the class of recursively enumerable languages with much smaller language classes than that of linear languages. Language classes, (i; j) LL and (i; j)ML, of (i; j) linear languages and (i; j) minimal linear languages are deÿned by posing restrictions on the