𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An hierarchy between context-free and context-sensitive languages

✍ Scribed by Takumi Kasai

Publisher
Elsevier Science
Year
1970
Tongue
English
Weight
718 KB
Volume
4
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

Infinite subfamilies ~l, ~ .... , -oq'~o, .W,~ of the family consisting of contextsensitive languages, are introduced such that .2'~ ~z~ ..-C ~| ~o,where 9 LP a is the family of e-free context-free languages, Ld,o is the family of context-sensitive languages, and each L/', is an Abstract Family of Languages, i.e., closed under +, -, U, inverse-homomorphism, r-free homomorphism, and intersection with regular sets. Each language of .W, is defined by a grammar, called a state grammar, that may be thought of as a context-free grammar with states.

πŸ“œ SIMILAR VOLUMES

Borel hierarchy and omega context free l
Borel hierarchy and omega context free languages
✍ Olivier Finkel πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 214 KB

We give in this paper additional answers to questions of Lescow and Thomas (A decade of

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. "

On β€œinherently context-sensitive” langua
On β€œinherently context-sensitive” languages β€” An application of complexity cores
✍ Volker Diekert; Ronald V. Book πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 222 KB

The concept of an "'inherently context-sensitive language" is introduced. It is shown that every context-sensitive language that is not in the Boolean closure of the context-free languages has a subset that is inherently context-sensitive.