𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On characterizations of recursively enumerable languages

✍ Scribed by Michel Latteux; Paavo Turakainen

Publisher
Springer-Verlag
Year
1990
Tongue
English
Weight
402 KB
Volume
28
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

Recursively enumerable languages and van
Recursively enumerable languages and van Wijngaarden grammars
✍ Jan Van Leeuwen πŸ“‚ Article πŸ“… 1977 πŸ› Elsevier Science βš– 580 KB

We show that each re language can be generated by a minimal deterministic linear contextfree based strict normal VW-grammar. We also prove that each re language can be generated by a strict normal VW-grammar with at most one metanotion denoting a non-regular contextfree language.