Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
229--239
Opis fizyczny
bibliogr. 15 poz.
Twórcy
autor
autor
autor
- Facultad de Informatica, Universidad Politécnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte 28660 Madrid, Spain, arpaton@fi.upm.es
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0003-0112