文章基本信息

标题：On enhanced time-varying distributed H systems
本地全文：下载
作者：Verlan Serghei
期刊名称：Computer Science Journal of Moldova
印刷版ISSN：1561-4042
出版年度：2002
卷号：10
期号：3
页码：263-279
出版社：Institute of Mathematics and Computer Science
摘要：An enhanced time-varying distributed H system (ETVDH system) is a slightly different definition of the time-varying distributed H system (TVDH system) [9] and it was proposed by M. Margenstern and Yu. Rogozhin in [4] under the name of "extended time-varying distributed H system''. The main difference is that the components of the ETVDH system are H systems and therefore splicing rules may be applied more than once as it is done in TVDH systems. This leads to difficulties in investigating the behavior of such systems because they have a higher level of parallelism. It is proved that ETVDH systems of degree 2 (i.e. with 2 components) generate all recursively enumerable languages in a sequential way [7] and that ETVDH systems of degree 4 generate all recursively enumerable languages in a "parallel'' way, modelling a formal type-0 grammar [11]. In this paper we improve the last result and we present an ETVDH system of degree 3 which generates all recursively enumerable languages modelling type-0 formal grammars. The problem of the existence of ETVDH systems of degree 2 which generate all recursively enumerable languages in a "parallel'' way is left open.