RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.10, n.3 (30), 2002/

On enhanced time-varying distributed H systems

Authors: Verlan Serghei

Abstract

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.

Sergey Verlan
Laboratoire d'Informatique Theorique et Appliquee
Universite de Metz, France,
E-mail:



Fulltext

Adobe PDF document – 0.20 Mb