EVA STAR Trefferanzeige

Volltext Volltext.pdf1.pdf (137 KB)
URN (für Zitat) http://nbn-resolving.org/urn:nbn:de:swb:90-AAA669948
Titel Membership for limited ET0L languages is not decidable.
Autor Fernau, Henning
Institution Fakultät für Informatik (INFORMATIK)
Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Dokumenttyp Buch
Jahr 1994
Erscheinungsvermerk Karlsruhe 1994. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1994,34.)
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.