DNA Computing
Lecture Notes in Computer Science, 2004, Volume 2943/2004, 1978-1979, DOI: 10.1007/978-3-540-24628-2_6

Time-Varying Distributed H Systems with Parallel Computations: The Problem Is Solved

Maurice Margenstern, Yurii Rogozhin and Sergey Verlan

View Related Documents

Abstract

In this article we show that time-varying distributed H systems (TVDH systems) with one component are able to model any type-0 grammar. Thus we completely answered to the question of constructing TVDH systems of smallest degree which generate any RE language using the parallel nature of molecular computations based on splicing operations. Another interesting point is that the proof is based on a simulation of a TVDH system of degree two and not of type-0 grammars as it is usually done in similar proofs.
Work supported by French Ministry of Education, NATO project PST.CLG.976912 and project IST-2001-32008 MolCoNet
This revised version was published in November 2004 and replaces the previous preliminary version.

Fulltext Preview

Image of the first page of the fulltext document