KIT | KIT-Bibliothek | Impressum
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-AAA669948

Membership for limited ET0L languages is not decidable

Fernau, Henning

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 Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Jahr 1994
Sprache Englisch
Identifikator URN: 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