A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem

• Autorzy: Niu Y. , Pan L. , Pérez-Jiménez M.J. , Font M. R.
• Języki publikacji: EN

Abstrakty

EN

A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NPcomplete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules.

Słowa kluczowe

EN

membrane computing; tissue P system; cell division; tripartite matching problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 109, nr 2
• Strony: 179--188
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Niu Y.

autor

Pan L.

autor

Pérez-Jiménez M.J.

autor

Font M. R.

• Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Engineering Huazhong University of Science and Technology, Wuhan 430074, China,

Bibliografia

• [1] Alhazov, A., Martın Vide, C., Pan, L. Solving a PSPACE-complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58, 2(2003), 67-77.
• [2] Alhazov, A., Pérez-Jiménez, M.J. Uniform solution of QSAT using polarizationless active membranes. Lecture Notes in Computer Science, 4664(2007), 122-133.
• [3] Díaz-Pernil, D., Gutiérrez-Naranjo,M.A., Pérez-Jiménez,M.J., Riscos-N´u˜nez, A. A linear-time tissue P system based solution for the 3-coloring problem. Electronic Notes in Theoretical Computer Science, 171(2007), 81-93.
• [4] Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-N´u˜nez, A. Solving subset sum in linear time by using tissue P systems with cell division. Proc. of IWINAC 2007, LNCS 4527, Springer, 170-179, 2007.
• [5] Díaz Pernil, D., Gutiérrez Naranjo, M.A., Pérez Jiménez, M.J., Riscos N´u˜nez, A. Solving the partition problem by using tissue-like P systems with cell division. Proc. of 6th Brainstorming Week on Membrane Computing, Report RGNC 01/08, Fenix Editoria, 124-134, 2008.
• [6] Gutiérrez-Naranjo,M.A., Pérez-Jiménez, M.J., Riscos-N´u˜nez, A., Romero-Campero, F.J. On the power of dissolution in P systems with active membranes, Lecture Notes in Computer Science, 3850(2006), 224-240.
• [7] Martín Vide, C., Pazos, J., Pǎun, Gh., Rodríguez Pat´on, A. Tissue P systems. Theoretical Computer Science, 296(2003), 295-326.
• [8] Pan, L., Martín Vide, C. Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes. Journal of Parallel and Distributed Computing, 65(2005), 1578-1584.
• [9] Papadimitriou C.H. Computational Complexity. Addison-Wesley, Reading, Massachusetts (1994).
• [10] Pǎun, Gh. Computing with membranes. Journal of Computer and System Sciences, 61, 1(2000), 108-143.
• [11] Pǎun, Gh. Membrane Computing. An Introduction. Springer-Verlag, Berlin (2002).
• [12] Pǎun, Gh., Pérez-Jiménez, M.J. Riscos-N´u˜nez, A. Tissue P systems with cell division. Int. J. of Computers, Communications and Control, 3, 3(2008), 295-303.
• [13] Pǎun, Gh., Rozenberg, G., Salomaa, A., eds. Handbook of Membrane Computing. Oxford University Press, 2009.
• [14] P systems web page http://ppage.psystems.eu/