Cooperation in Transport of Chemical Substances : A Complexity Approach within Membrane Computing

• 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-1572

• Języki publikacji: EN

Abstrakty

EN

Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P. P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP-complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted.

Słowa kluczowe

EN

membrane computing; polarizationless P systems with active membranes; cooperative rules; P versus NP problem; SAT problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 373--385
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Valencia-Cabrera L.

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

autor

Orellana-Martín D.

• Research Group on Natural Computing, 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.

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

autor

Riscos-Núñez A.

• Research Group on Natural Computing, 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.

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

Bibliografia

• [1] Alhazov A, Pan L. Polarizationless P systems with active membranes. Grammars, 2004;7:141–159.
• [2] Alhazov A, Pan L , Pǎun Gh. Trading polarizations for labels in P systems with active membranes. Acta Informaticae, 2004;41(2-3):111–144. doi:10.1007/s00236-004-0153-z.
• [3] Cormen TH, Leiserson CE, Rivest RI. An Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 1994.
• [4] Garey MR, Johnson DS. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. ISBN:0716710447.
• [5] 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. In R. Freund, Gh. Pǎun, Gr. Rozenberg, A. Salomaa (eds.). Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers, 3850 Lecture Notes in Computer Science. 2006 pp. 224–240. doi:10.1007/11603047_16.
• [6] Pǎun Gh. P systems with active membranes: Attacking NP–complete problems, Journal of Automata, no 6 Languages and Combinatorics, 2001 pp. 75–90. A preliminary version in Centre for Discrete Mathematics and Theoretical Computer Science Research Reports Series, CDMTCS-102, May 1999. URL https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm.
• [7] M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini. Complexity classes in models of cellular computing with membranes. Natural Computing, 2003;2(3):265–285. doi:10.1023/A:1025449224520.
• [8] Sosík P, Rodríguez-Patón A. Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences, 2007;73(1):137–152. URL https://doi.org/10.1016/j.jcss.2006.10.001.
• [9] Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, 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):107–123.
• [10] Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Riscos-Núñez A, Pérez-Jiménez MJ. Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation. Theoretical Computer Science, in press, 2017. URL https://doi.org/10.1016/j.tcs.2017.04.015.
• [11] Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Riscos-Núñez A, Pérez-Jiménez MJ. Restricted polarizationless P systems with active membranes: minimal cooperation only outwards. In Proceedings of the Fifteenth Brainstorming Week on Membrane Computing, 2017 (manuscript).
• [12] 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. In C. Graciani, Gh. Pǎun, D. Orellana-Martín, A. Riscos-Núñez, L. Valencia-Cabrera (eds.) Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, 1-5 February, 2016, Sevilla, Spain, Fénix Editora, 2016 pp. 327-356. URL http://www.gcn.us.es/14bwmc proceedings.
• [13] Zandron C, Ferretti C, Mauri G. Solving NP-complete problems using P systems. In I. Antoniou, C.S. Calude, M.J. Dinneen (eds.) Unconventional Models of Computation, UMC’2K, Springer, London, 2000, pp. 153–164.