𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the degree of scattered context-sensitivity

✍ Scribed by Henning Fernau; Alexander Meduna

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
76 KB
Volume
290
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with no more than two context-sensitive productions.

πŸ“œ SIMILAR VOLUMES

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.