Abstract
A time-varying distributed H system (TVDH system) is a splicing system which has the following feature: at different moments one uses different sets of splicing rules (these sets are called components of TVDH system). The number of components is called the degree of the TVDH system. The passage from a component to another one is specified in a cycle. It was proved by the first two authors (2001) that TVDH systems of degree one generate all recursively enumerable languages. The proof was made by a sequential modelling of Turing machines. This solution is not a fully parallel one. A. Păun (1999) presented a complete parallel solution for TVDH systems of degree four by modelling type-0 formal grammars. His result was improved by the first two authors by reducing the number of components of such TVDH systems down to three (2000). In this paper we improve the last result by reducing the number of components of such TVDH systems down to two. This question remains open for one component, i.e. is it possible to construct TVDH systems of degree one which completely uses the parallel nature of molecular computations based on splicing operations (say model type-0 formal grammars)?
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Csuhaj-Varjú, E., Kari, L., Păun, G.: Test Tube distributed system based on splicing. Computer and AI. 2–3 (1996) 211–232
Ferretti, C., Mauri, G., Zandron, C.: Nine test tubes generate any RE language. Theoretical Computer Science. 231, no.2 (2000) 171–180.
Head, T.: Formal language theory and DNA: an analysis of the generative capacity of recombinant behaviors. Bulletin of Mathematical Biology 49 (1987) 737–759
Head, T., Păun, Gh., Pixton, D.: Language theory and molecular genetics. Generative mechanisms suggested by DNA recombination. Chapter 7 in vol.2 of G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, 3 volumes, Springer-Verlag, Heidelberg (1997)
Margenstern, M., Rogozhin, Yu.: A universal time-varying distributed H-system of degree 2. Biosystems 52 (1999) 73–80.
Margenstern M., Rogozhin Yu., About Time-Varying Distributed H Systems. Lecture Notes in Computer Science, Springer, vol. 2054, 2001, p.53–62. (Proceedings of DNA6, Leiden, The Netherlands, June 13–17, 2000).
Margenstern M., Rogozhin Yu.: A universal time-varying distributed H system of degree 1. Proceedings of the DNA7, Seventh International Meeting on DNA Based Computers, University of South Florida, U.S.A., June 10–13, 2001, (2002)-LNCS to appear.
Margenstern, M., Rogozhin, Yu.: Time-varying distributed H systems of degree 1 generate all recursively enumerable languages, in vol. Words, Semigroups and Transductions (M. Ito, Gh. Paun, S. Yu, eds), World Scientific, Singapore, 2001, p. 329–340.
Păun, A.: On Time-Varying H Systems. Bulletin of EATCS. 67 (1999) 157–164
Păun, G., Rozenberg, G., Salomaa, A.: Computing by splicing. Theoretical Computer Science. 168, no.2 (1996) 321–336
Păun, G.: DNA computing: distributed splicing systems. In Structures in Logic and Computer Science. A Selection of Essays in honor of A. Ehrenfeucht, Lecture Notes in Computer Science 1261 (1997) 353–370
Păun, G.: DNA Computing Based on Splicing: Universality Results. Theoretical Computer Science. 231, no.2 (2000) 275–296.
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998)
Pixton, D.: Regularity of splicing languages. Discrete Applied Mathematics 69 (1996) 101–124
Priese, L., Rogozhin, Yu., Margenstern, M.: Finite H-Systems with 3 Test Tubes are not Predictable. In Proceedings of Pacific Symposium on Biocomputing, Kapalua, Maui, January 1998 (R.B. Altman, A.K. Dunker, L. Hunter, T.E. Klein, eds), World Sci. Publ., Singapore (1998) 545–556
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Margenstern, M., Rogozhin, Y., Verlan, S. (2003). Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations. In: Hagiya, M., Ohuchi, A. (eds) DNA Computing. DNA 2002. Lecture Notes in Computer Science, vol 2568. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36440-4_29
Download citation
DOI: https://doi.org/10.1007/3-540-36440-4_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00531-5
Online ISBN: 978-3-540-36440-5
eBook Packages: Springer Book Archive