About Splicing P Systems with One Membrane

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

Abstrakty

EN

In this article we consider splicing P systems with one membrane. We show that the original definition of splicing P systems is not complete and we propose several variants in order to complete it. We show that the choice of the variant is important and that the computational power of splicing P systems with one membrane directly depends on it.

Słowa kluczowe

EN

membrane computing; splicing systems; formal languages; universal computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 65, nr 3
• Strony: 279--290
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Verlan S.

• Laboratoire d'Informatique Theorique et Appliquée Université de Metz, Ile du Saulcy, 57045, Metz, France

autor

Margenstern M.

• Laboratoire d'Informatique Theorique et Appliquée Université de Metz, Ile du Saulcy, 57045, Metz, France

Bibliografia

• [1] Frisco, P.: On Two Variants of Splicing Super-Cell Systems, Romanian Journal of Information Science and Technology, 4(1-2), 2001, 89–100.
• [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 [11], 295–360.
• [4] Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 2nd edition, Addison-Wesley, Reading, Mass., 2001.
• [5] 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.
• [6] Păun, A., Păun,M.: On the Membrane Computing Based on Splicing, in: Where Do Mathematics, Computer Science, Linguistic and Biology Meet (C.Martin-Vide, V.Mitrana, Eds.), Kluwer Academic, Dortrecht, 2000, 409–422.
• [7] Păun, G.: Computing with Membranes, Journal of Computer and System Sciences, 1(61), 2000, 108–143, Also TUCS Report No. 208, 1998.
• [8] Păun, G.: Membrane Computing. An Introduction, Springer Verlag, Berlin, Heidelberg, New York, 2002.
• [9] Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms, Springer Verlag, Berlin, Heidelberg, New York, 1998.
• [10] Păun, G., Yokomori, T.: Membrane Computing Based on Splicing, in: DNA Based Computers V (E.Winfree, D. K. Gifford, Eds.), vol. 54 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1999, 217–232.
• [11] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, 3 volumes, Springer Verlag, Berlin, Heidelberg,New York, 1997.
• [12] Verlan, S.: Head Systems and Applications to Bio-Informatics, Ph.D. Thesis, University of Metz, 2004.
• [13] Verlan, S., Zizza, R.: 1-splicing vs. 2-splicing: Separating Results, in: Proceedings of WORDS’03, 4th International Conference on Combinatorics on Words, September 10-13, 2003, Turku, Finland (T. Harju, J. Karhumäki, Eds.), TUCS General Publication No. 27, 2003, 320–331.
• [14] Zandron, C.: The P Systems Web Page, http:www.psystems.disco.unimib.it/