Membership for limited ET0L languages is not decidable
Abstract:
In this paper, we show how to encode arbitrary enumerable set of
numbers given by register machines within limited EPT0L systems
and programmed grammars with unconditional transfer.This result
has various consequences, e.g.the existence of nonrecursive sets
generable by 1lET0L systems or by programmed grammars with
unconditional transfer. Moreover, ordered grammars are strictly
less powerful than 1lET0L systems.
| Zugehörige Institution(en) am KIT | Fakultät für Informatik – Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.) |
| Publikationstyp | Buch |
| Publikationsjahr | 1994 |
| Sprache | Englisch |
| Identifikator | urn:nbn:de:swb:90-AAA669948 KITopen-ID: 66994 |
| Erscheinungsvermerk | Karlsruhe 1994. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1994,34.) |