JUCS - Journal of Universal Computer Science 2(11): 745-755, doi: 10.3217/jucs-002-11-0745
Remarks on Propagating Partition-Limited ETOL Systems
expand article infoHenning Fernau‡
‡ Wilhelm-Schickard-Institut für Informatik; Universität Tübingen, Germany, Tübingen, Germany

Corresponding author: Henning Fernau ( fernau@informatik.uni-tuebingen.de )

© Henning Fernau.
This article is freely available under the J.UCS Open Content License.
Citation: Fernau H (1996) Remarks on Propagating Partition-Limited ETOL Systems. JUCS - Journal of Universal Computer Science 2(11): 745-755. https://doi.org/10.3217/jucs-002-11-0745
Open Access
Abstract
In this paper, we sharpen the results of Gaeartner on the universality of partition-limited ET0L systems by showing that such deterministic systems characterize the recursively enumerable sets, and, furthermore, the propagating deterministic partition-limited ET0L systems characterize the programmed languages with appearance checking disallowing erasing productions. The main results of this paper have been announced in [10].
Keywords
Formal languages, parallel rewriting systems, k-limited systems