Remarks on Propagating Partition-Limited ETOL Systems
Дата
Авторы
Fernau,Henning
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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].
Ключевые слова
Formal languages , parallel rewriting systems , k-limited systems