On the Power of P Systems with DNA-Worm-Objects

• Autorzy: Maté J.L. , Rodriguez-Patón A. , Silva A.
• Języki publikacji: EN

Abstrakty

EN

We introduce a variant of P systems with string-objects - called worm-objects - inspired in the DNA computing area. These systems work with multisets of string-objects processed by splitting, mutation, replication and recombination. This model is simpler (we eliminate the replication operation) and more realistic (the recombination operation is changed by the simpler one of suffix-prefix or head-tail concatenation developed in the DNA computing framework) than the previous one. The result of a computation is the set of strings sent out of the system. We work with multisets of strings but we generate languages instead of sets of numbers. We prove that, without priority among rules or other control mechanisms, (1) these P systems with at most three membranes can generate all recursively enumerable languages, (2) with non-decreasing length mutation and splitting rules, three membranes are enough to generate the family of context-sensitive languages, and (3) with these restricted types of splitting and mutation rules, four membranes can generate the family of recursively enumerable languages.

Słowa kluczowe

EN

membrane computing; P systems; recursively enumerable languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 49, nr 1-3
• Strony: 229--239
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Maté J.L.

autor

Rodriguez-Patón A.

autor

Silva A.

• Facultad de Informatica, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte 28660 Madrid, Spain,

Bibliografia

• [1] Barreiro, J. M., Rodrigo, J., Rodrfguez-Patón, A.: Evolutionary biomolecular computing, Romanian J. of Information Science and Technology, 4(1), 1998, 287-382.
• [2] Castellanos, J., Paun, Gh., Rodrfguez-Patón, A.: Computing with membranes: P systems with worm-objects, IEEE 7th. Intern. Conf. on String Processing and Information Retrieval, SPIRE’2000, La Corufia, September 2000,64-74.
• [3] Dassow, J., Martin-Vide, C., PSun, Gh., Rodrfguez-Patón, A.: Conditional concatenation, Fundamenta Informaticae, 44(4), 2000,353-372.
• [4] 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.
• [5] Krishna, S. N., Rama, R.: A variant of P systems with active membranes: Solving NP-complete problems, Romanian J. of Information Science and Technology, 4(2), 1999,357-367.
• [6] Martfn-Vide, C., Paun, Gh.: Computing with membranes: One morę collapsing hierarchy, Bulletin of the EATCS, 72, October 2000, 183-187.
• [7] Martfn-Vide, C., PSun, Gh.: String objects in P systems, Proc, of Workshop on Algebraic Systems, Formal Languages and Computations, Kyoto, 2000,161-169.
• [8] Paun, Gh.: Computing with membranes. An introduction, Bulletin of the EATCS, 67, February 1999,139-152.
• [9] Paun, Gh.: Computing with membranes, Journal of Computer and System Sciences, 61(1), 2000,108-143.
• [10] Paun, Gh.: Computing with membranes - A variant: P systems with polarized membranes, Intern. J. of Foundations of Computer Science, 11(1), 2000,167-182.
• [11] PSun, Gh.: P systems with active membranes: attacking NP complete problems, J. Automata, Languages and Combinatorics, 1(6), 2001,75-90.
• [12] P&un, Gh., Rozenberg, G., Salomaa, A.: DNA Computing. New Computing Paradigms, Springer-Verlag, Heidelberg, 1998.
• [13] PSun, Gh., Yokomori, T.: Membranę computing based on splicing, In E. Winfree and D. Gif-ford, editors, DNA Based Computers V, MIT, Junc 1999, 213-227.
• [14] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, 3 volumes, Springer-Verlag, Berlin, 1997.
• [15] Sipper, M.: Studying artificial life using a simple, generał cellular model, Artificial Life Jour¬nal, 1(2), 1995, 1-35.