On enhanced time-varying distributed H systems
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 Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2002-11-01
|
| Series: | Computer Science Journal of Moldova |
| Online Access: | http://www.math.md/nrofdownloads.php?file=/files/csjm/v10-n3/v10-n3-(pp263-279).pdf |
| _version_ | 1811186470365429760 |
|---|---|
| author | Sergey Verlan |
| author_facet | Sergey Verlan |
| author_sort | Sergey Verlan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T13:45:58Z |
| format | Article |
| id | doaj.art-24d9cad39a974b93841aae344c2929ca |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-11T13:45:58Z |
| publishDate | 2002-11-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-24d9cad39a974b93841aae344c2929ca2022-12-22T04:21:01ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422002-11-01103(30)263279On enhanced time-varying distributed H systemsSergey Verlan0Laboratoire d'Informatique Theorique et Appliquee Universite de Metz, FranceAn 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.http://www.math.md/nrofdownloads.php?file=/files/csjm/v10-n3/v10-n3-(pp263-279).pdf |
| spellingShingle | Sergey Verlan On enhanced time-varying distributed H systems Computer Science Journal of Moldova |
| title | On enhanced time-varying distributed H systems |
| title_full | On enhanced time-varying distributed H systems |
| title_fullStr | On enhanced time-varying distributed H systems |
| title_full_unstemmed | On enhanced time-varying distributed H systems |
| title_short | On enhanced time-varying distributed H systems |
| title_sort | on enhanced time varying distributed h systems |
| url | http://www.math.md/nrofdownloads.php?file=/files/csjm/v10-n3/v10-n3-(pp263-279).pdf |
| work_keys_str_mv | AT sergeyverlan onenhancedtimevaryingdistributedhsystems |