Computational Efficiency of Minimal Cooperation and Distribution in Polarizationless P Systems with Active Membranes

• Autorzy: Valencia-Cabrera L. , Orellana-Martín D. , Martínez-del-Amor M. A. , Riscos-Núñez A. , Pérez-Jiménez M. J.

Identyfikatory

DOI

10.3233/FI-2017-1535

• Języki publikacji: EN

Abstrakty

EN

Polarizationless P systems with active membranes are non-cooperative systems, that is, the left-hand side of their rules have a single object. Usually, these systems make use of division rules as a mechanism to produce an exponential workspace in linear time. Division rules are inspired by cell division, a process of nuclear division that occurs when a parent cell divides to produce two identical daughter cells. On the other hand, separation rules are inspired by the membrane fission process, a mechanism by which a biological membrane is split into two new ones in such a manner that the contents of the initial membrane is distributed between the new membranes. In this paper, separation rules are used instead of division rules. The computational efficiency of these models is studied and the role of the (minimal) cooperation in object evolution rules is explored from a computational complexity point of view.

Słowa kluczowe

EN

active membranes; complexity classes; membrane computing; membrane fission; SAT problem; separation rules

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 1/2
• Strony: 147--172
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Valencia-Cabrera L.

• Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Orellana-Martín D.

• Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Martínez-del-Amor M. A.

• Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Riscos-Núñez A.

• Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

autor

Pérez-Jiménez M. J.

• Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Bibliografia

• [1] Alhazov A, Ishdorj TO. Membrane operations in P systems with active membranes. In Gh. Păun, A. Riscos-Núñez, A. Romero-Jiménez, F. Sancho-Caparrini (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, 2-7 February 2004, Research Group on Natural Computing, TR 01/2004, University of Seville, 37–44. URL http://hdl.handle.net/11441/34550.
• [2] Cormen TH, Leiserson CE, Rivest RL. An Introduction to Algorithms. The MIT Press, Cambridge, Massachussets, 1994.
• [3] Gutiérrez-Escudero R, Pérez-Jiménez MJ, Rius-Font M. Characterizing tractability by tissue-like P systems. Lecture Notes in Computer Science, 2010;5957:289–300. doi:10.1007/978-3-642-11467-0.
• [4] Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A, Romero-Campero FJ. On the power of dissolution in P systems with active membranes. Lecture Notes in Computer Science, 2006;3850:224–240. doi:10.1007/11603047_16.
• [5] Pan L, Ishdorj TO. P systems with active membranes and separation rules. Journal of Universal Computer Science, 2004;10(5): 630–649. doi:10.3217/jucs-010-05-0630.
• [6] Pan L, Pérez-Jiménez MJ. Computational complexity of tissue–like P systems. Journal of Complexity, 2010;26(3):296–315. URL https://doi.org/10.1016/j.jco.2010.03.001
• [7] Păun Gh. Computing with membranes, Journal of Computer and Systems Science, 2000;61(1):108–143. URL https://doi.org/10.1006/jcss.1999.1693.
• [8] Păun Gh. Further twenty six open problems in membrane computing, Third Brainstorming Week on Membrane Computing (M.A. Gutiérrez et al. eds.), Fénix Editora, Sevilla, 2005, pp. 249–262.
• [9] Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Natural Computing, 2003;2(3):265–285. doi:10.1023/A:1025449224520.
• [10] Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez-Jiménez MJ. Minimal cooperation in polarizationless P systems with active membranes. Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, Sevilla, Spain, February 1-5, 2016, pp. 327–356. URL http://hdl.handle.net/11441/50713.
• [11] Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez-Jiménez MJ. Polarizationless P systems with active membranes: Computational complexity aspects. Journal of Automata, Languages and Combinatorics, 2016;21(1-2):101–117. ISSN-1430-189X.