An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

• Autorzy: Pérez-Jiménez M. J. , Sosík P.

Identyfikatory

DOI

10.3233/FI-2015-1197

• Języki publikacji: EN

Abstrakty

EN

A membrane system (P system) is a distributed computingmodel inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non–efficiency to efficiency, assuming that P 6= NP.

Słowa kluczowe

EN

membrane computing; tissue P system; cell separation; computational complexity; SAT problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 45--60
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Pérez-Jiménez M. J.

• Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, 41012 Sevilla, Spain

autor

Sosík P.

• Research Institute of the IT4Innovations Centre of Excellence Faculty of Philosophy and Science Silesian University in Opava, 74601 Opava, Czech Republic

Bibliografia

• [1] Alhazov, A., Freund, R. and Oswald, M. Tissue P Systems with Antiport Rules ans Small Numbers of Symbols and Cells. Lecture Notes in Computer Science 3572, (2005), 100–111.
• [2] Bernardini, F. and Gheorghe, M. Cell Communication in Tissue P Systems and Cell Division in Population P Systems. Soft Computing 9, 9, (2005), 640–649.
• [3] Christinal, H.A., Díaz-Pernil, D., Gutiérrez-Naranjo, M.A. and Pérez-Jiménez, M.J. Tissue-like P systems without environment. In M.A. Martínez-del-Amor, Gh. Păun, I. Pérez-Hurtado, A. Riscos-Núñez (eds.) Proceedings of the Eight Brainstorming Week on Membrane Computing, Sevilla, Spain, February 1-5, 2010, Fénix Editora, Report RGNC 01/2010, pp. 53–64.
• [4] D. Díaz, M.A. Gutiérrez, M.J. Pérez-Jiménez, A. Riscos. Solving the Independent Set problem by using tissue-like P systems with cell division. Methods and Models in Artificial and Natural Computation. A Homage to Professor Mira’s Scientific Legacy. Lecture Notes in Computer Science, 5601 (2009), 213-222.
• [5] Freund, R., Păun, Gh. and Pérez-Jiménez, M.J. Tissue P Systems with channel states. Theoretical Computer Science 330, (2005), 101–116.
• [6] Garey, M.R. and Johnson, D.S. Computers and Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, (1979).
• [7] Ito, M., Martín Vide, C. and Păun, Gh. A characterization of Parikh sets of ET0L laguages in terms of P systems. In M. Ito, Gh. Păun, S. Yu (eds.) Words, Semigroups and Transducers, World Scientific, Singapore, 2001, 239-254.
• [8] Krishna, S.N., Lakshmanan K. and Rama, R. Tissue P Systems with Contextual and Rewriting Rules. Lecture Notes in Computer Science 2597, (2003), 339–351.
• [9] Martín Vide, C. Pazos, J. Păun, Gh. and Rodríguez Patón, A. A New Class of Symbolic Abstract Neural Nets: Tissue P Systems. Lecture Notes in Computer Science 2387, (2002), 290–299.
• [10] Martín Vide, C. Pazos, J., Păun, Gh. and Rodríguez Patón, A. Tissue P systems. Theoretical Computer Science, 296, (2003), 295–326.
• [11] Pan, L. and Ishdorj, T.-O. P systems with active membranes and separation rules. Journal of Universal Computer Science, 10, 5, (2004), 630–649.
• [12] Pan, L. and Pérez-Jiménez, M.J. Computational complexity of tissue–like P systems. Journal of Complexity, 26, 3 (2010), 296–315.
• [13] Pan, L., Pérez-Jiménez, M.J., Riscos A. and Rius, M. New frontiers of the efficiency in tissue P systems. L. Pan, Gh. Păun, T. Song (eds.) Pre-proceedings of Asian Conference on Membrane Computing, Huazhong University of Science and Technology,Wuhan, China, October 5-18, 2012, pp. 61-73.
• [14] Păun, A. and Păun, Gh. The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3, (2002), 295–305.
• [15] Păun, Gh. Computing with membranes. Journal of Computer and System Sciences, 61, 1, (2000), 108–143. Also in Turku Center for Computer Science–TUCS, Report 208, November 1998.
• [16] Păun, Gh. Attacking NP-complete problems. In UnconventionalModels of Computation, UMC’2K (I. Antoniou, C. Calude, M. J. Dinneen, eds.), Springer-Verlag, 2000, pp. 94-115.
• [17] Păun, Gh., Pérez-Jiménez, M.J. and Riscos-Núñez, A. Tissue P System with cell division. International Journal of Computers, Communications and Control, 3, 3, (2008), 295–303.
• [18] Păun, Gh., Rozenberg, G. and Salomaa, A. (Eds.) The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, (2010).
• [19] Pérez-Jiménez,M.J., Romero-Jiménez, A. and Sancho-Caparrini, F. Complexity classes in models of cellular computing with membranes. Natural Computing, 2, 3 (2003), 265–285.
• [20] Pérez-Jiménez, M.J., Romero-Jiménez, A. and Sancho-Caparrini, F. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics, 11, 4, (2006), 423-434.
• [21] The P Systems Webpage, http://ppage.psystems.eu/