KIT | KIT-Bibliothek | Impressum | Datenschutz

Membership for limited ET0L languages is not decidable

Fernau, Henning


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.

Open Access Logo

Volltext §
DOI: 10.5445/IR/66994
Cover der Publikation
Zugehörige Institution(en) am KIT 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.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page