Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 2 / Issue 11

available in:   PDF (181 kB) PS (48 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-002-11-0745


Remarks on Propagating Partition-Limited ETOL Systems

Henning Fernau (Wilhelm-Schickard-Institut für Informatik; Universität Tübingen, Germany, Germany)

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, k-limited systems, parallel rewriting systems

Categories: F.4.2, F.4.3