|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040205,
author = {Fernau, Henning and Stephan, Frank},
title = {Characterizations of Recursively Enumerable Languages
by Programmed Grammars with Unconditional Transfer},
journal = jalc,
year = 1999,
volume = 4,
number = 2,
pages = {117--142},
keywords = {programmed grammars, unconditional transfer,
leftmost derivation, non-effective construction},
abstract = {We prove that every recursively enumerable language can
be generated by a programmed grammar with context-free core
rules using unconditional transfer with leftmost derivation
of type~3 or type~2. Interestingly, we have to give a
non-constructive proof of the first mentioned universality
result based on {\sc Higman}'s lemma, since finding a
transformation from a Turing machine to a programmed grammar
with unconditional transfer and leftmost derivation of
type~3 turns out to be equivalent to solving the halting
problem for Turing machines. As a corollary, we show that
every recursively enumerable tally language can be generated
by a programmed grammar with context-free core rules using
unconditional transfer or by some $k$-limited ET0L system,
where~$k$ is an arbitrary positive integer.}
}