Time-Varying Distributed H Systems: An Overview

• Autorzy: Margenstern M. , Verlan S. , Rogozhin Y.
• Języki publikacji: EN

Abstrakty

EN

Time-varying distributed H systems are a well known model of molecular computing. In this article we present an overview of this model, its history, related results, and open problems.

Słowa kluczowe

EN

biomolecular computing; splicing; formal grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 291--306
• Opis fizyczny: Bibliogr. 30 poz.

Twórcy

autor

Margenstern M.

• LITA, Université de Metz, France

autor

Verlan S.

• LITA, Université de Metz, France

autor

Rogozhin Y.

• Institute of Mathematics and Computer Science, Academy of Sciences of Moldova

Bibliografia

• [1] Cocke, J., Minsky,M.: Universality of tag systems with P=2, Journal of the ACM, 11(1), 1964, 15–20.
• [2] Head, T.: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, Bulletin of Mathematical Biology, 49(6), 1987, 737–759.
• [3] Head, T., Păun, G., Pixton, D.: Language theory and molecular genetics. Generative mechanisms suggested by DNA recombination, in: Handbook of Formal Languages, 3 volumes, vol. 2, Springer Verlag, Berlin, Heidelberg, New York, 1997, 295–360.
• [4] Marcus, S.: Language at the crossroad of computation and biology, Computing with Bio-Molecules. Theory and Experiments (G. Păun, Ed.), Springer Verlag, Berlin, 1998.
• [5] Marcus, S.: Membranes versus DNA, Fundamenta Informaticae, 49(1–3), 2002, 223–227.
• [6] Margenstern, M., Rogozhin, Y.: Generating All Recursively Enumerable Languages with a Time-Varying Distributed H System of Degree 2, Technical report, Institut Universitaire de Technologie de Metz, 1999, Publications du G.I.F.M.
• [7] Margenstern, M., Rogozhin, Y.: A universal time-varying distributed H-system of degree 2, Proceedings of the 4th DIMACS meeting on DNA based computers (L. Kari, H. Rubin, D. H. Wood, Eds.), 52, (1–3), Elsevier, 1999, 73–80.
• [8] Margenstern, M., Rogozhin, Y.: A universal time-varying distributed H system of degree 2, BioSystems, 52, 1999, 73–80.
• [9] Margenstern, M., Rogozhin, Y.: About time-varying distributed H systems, DNA Computing: 6th International Workshop on DNA-Based Computers, DNA 2000, Leiden, The Netherlands, June 13-17, 2000, Revised Papers (A. Condon, G. Rozenberg, Eds.), vol. 2054 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2000, 53–62.
• [10] Margenstern, M., Rogozhin, Y.: Time-varying distributed H systems of degree 2 generate all recursively enumerable languages, in: Where Do Mathematics, Computer Science and Biology Meet (C. Martin-Vide, V. Mitrana, Eds.), Kluwer Academic, Dortrecht, 2000, 399–407.
• [11] Margenstern, M., Rogozhin, Y.: Extended time-varying distributed H systems - universality result, Proceedings of The 5th World Multi-Conference on Systemics, Cybernetics and Informatics, Industrial Systems, SCI 2001, Orlando, Florida USA, July 22-25, 2001, IX, 2001.
• [12] Margenstern, M., Rogozhin, Y.: Time-varying distributed H systems of degree 1 generate all recursively enumerable languages, in: Words, Semigroups, and Transductions (M. Ito, G. Păun, S. Yu, Eds.), World Scientific, Singapore, 2001.
• [13] Margenstern,M., Rogozhin, Y.: A universal time-varying distributed H system of degree 1, DNA Computing: 7th International Workshop on DNA-Based Computers, DNA7, Tampa, FL, USA, June 10-13, 2001. Revised Papers (N. Jonoska, N. C. Seeman, Eds.), vol. 2340 of Lecture Notes in Computer Science, Springer-Verlag, 2002, 371–380.
• [14] Margenstern, M., Rogozhin, Y., Verlan, S.: Time-varying distributed H systems of degree 2 can carry out parallel computations, DNA Computing: 8th InternationalWorkshop on DNA-Based Computers, DNA8, Sapporo, Japan, June 10-13, 2002. Revised Papers (M. Hagiya, A. Ohuchi, Eds.), vol. 2568 of Lecture Notes in Computer Science, Hokkaido University, Springer-Verlag, Berlin, 2002, 326–336.
• [15] Margenstern, M., Rogozhin, Y., Verlan, S.: Time-varying distributed H systems with parallel computations: the problem is solved, in: DNA Computing: 9th International Workshop on DNA Based Computers, DNA9, Madison, WI, USA, June 1-3, 2003. Revised Papers (J. Chen, J. Reif, Eds.), vol. 2943 of Lecture Notes in Computer Science, Springer, 2004, 48–53.
• [16] Minsky,M.: Computations: Finite and Infinite Machines, Prentice Hall, Englewood Cliffts, NJ, 1967.
• [17] Păun, A.: On time-varying H systems, Bulletin of EATCS, 67, 1999, 157–164.
• [18] Păun, G.: Regular extended H systems are computationally universal, JALC, 1(1), 1996, 27–36.
• [19] Păun, G.: DNA computing: distributed splicing systems, Structures in Logic and Computer Science. A Selection of Essays in Honor of A. Ehrenfeucht (J. Mycielsky, G. Rozenberg, A. Salomaa, Eds.), vol. 1261 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1997, 351–370.
• [20] Păun, G.: DNA computing based on splicing: universality results, Proceedings of the Second Internetional Colloquium on Universal Machines and Computations, Metz, France (M. Margenstern, Ed.), vol. I, IUT de Metz, 1998, 67–91.
• [21] Păun, G.: DNA computing based on splicing: universality results, Theoretical Computer Science, 231(2), 2000, 275–296, Journal version of [20].
• [22] Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms, Springer-Verlag, Berlin, 1998.
• [23] Rogozhin, Y.: Small universal Turing machines, Theoretical Computer Science, 168(2), 1996, 215–240.
• [24] TVDHsim: Time-Varying Distributed H Systems Simulator http://lita.sciences.univ-metz.fr/`verlan/.
• [25] Verlan, S.: Calculs Moléculaires: les Systémes Distribués à Changement de Phase,Master Thesis, Université de Metz, 2001.
• [26] Verlan, S.: On enhanced time-varying distributed H systems, Computer Science Journal of Moldova, 10(3), 2002, 263–279.
• [27] Verlan, S.: A frontier result on enhanced time-varying distributed H systems with parallel computations, Preproceedings of DCFS’03, Descriptional Complexity of Formal Systems, Budapest, Hungary, July 12-14, 2003, 2003, 221–232.
• [28] Verlan, S.: Communicating distributed H systems with alternating filters, in: Aspects of Molecular Computing. Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (N. Jonoska, G. Paun, G. Rozenberg, Eds.), vol. 2950 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2004, 367–384.
• [29] Verlan, S.: Head Systems and Applications to Bio-Informatics, Ph.D. Thesis, University of Metz, 2004.
• [30] Zandron, C.: The P Systems Web Page, http://psystems.disco.unimib.it/.