A uniform solution to the independent set problem through tissue <bold>P</bold> systems with cell separation

doi:10.1007/s11704-012-1054-x

Front Comput Sci

2012, Vol. 6

Issue (4) : 477-488 https://doi.org/10.1007/s11704-012-1054-x

RESEARCH ARTICLE

A uniform solution to the independent set problem through tissue P systems with cell separation

Xingyi ZHANG¹, Xiangxiang ZENG², Bin LUO¹, Zheng ZHANG³(

)

1. Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Computer Science and Technology, Anhui University, Hefei 230039, China; 2. Department of Computer Science, Xiamen University, Xiamen 361005, China; 3. Key Laboratory of Image Processing and Intelligent Control, Department of Control Science and Engineering, Huazhong University of Science and Technology,Wuhan 430074, China

Download: PDF(328 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Membrane computing is an emergent branch of natural computing, which is inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. Tissue P systems are a class of the most investigated computing models in the framework of membrane computing, especially in the aspect of efficiency. To generate an exponential resource in a polynomial time, cell separation is incorporated into such systems, thus obtaining so called tissue P systems with cell separation. In this work, we exploit the computational efficiency of this model and construct a uniform family of such tissue P systems for solving the independent set problem, a well-known NP-complete problem, by which an efficient solution can be obtained in polynomial time.

Keywords membrane computing tissue P system cell separation independent set problem

Corresponding Author(s): ZHANG Zheng,Email:leaf@mail.hust.edu.cn

Issue Date: 01 August 2012

Cite this article:

Xingyi ZHANG,Xiangxiang ZENG,Bin LUO, et al. A uniform solution to the independent set problem through tissue P systems with cell separation[J]. Front Comput Sci, 2012, 6(4): 477-488.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-012-1054-x
https://academic.hep.com.cn/fcs/EN/Y2012/V6/I4/477

1	Pǎun G. Computing with membranes. Journal of Computer and System Sciences , 2000, 61(1): 108-143 doi: 10.1006/jcss.1999.1693
2	Pan L, Pǎaun G. Spiking neural P systems with antispikes. International Journal of Computers, Communications & Control , 2009, IV(3): 273-282
3	Pan L, Pǎun G. Spiking neural P systems: an improved normal form. Theoretical Computer Science , 2010, 411(6): 906-918 doi: 10.1016/j.tcs.2009.11.010
4	Wang J, Hoogeboom H J, Pan L, Pǎun G, Pérez-Jiménez M J. Spiking neural P systems with weights. Neural Computation , 2010, 22(10): 2615-2646 doi: 10.1162/NECO_a_00022
5	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 , 2005, 65(12): 1578-1584 doi: 10.1016/j.jpdc.2005.05.018
6	Pan L, Martín-Vide C. Further remark on P systems with active membranes and two polarizations. Journal of Parallel and Distributed Computing , 2006, 66(6): 867-872 doi: 10.1016/j.jpdc.2006.01.003
7	Alhazov A, Martín-Vide C, Pan L. Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae , 2003, 58(2): 67-77
8	Pǎun G, Rozenberg G, Salomaa A. Handbook of Membrane Computing. Oxford: Oxford University Press, 2010
9	Martín-Vide C, Pazos J, Pǎun G, Rodríguez-Patón A. A new class of symbolic abstract neural nets: tissue P systems. In: Proceedings of the 8th Annual International Conference on Computing and Combinatorics . 2002, 290-299
10	Martín-Vide C, Pazos J, Pǎun G, Rodríguez-Patón A. Tissue P systems. Theoretical Computer Science , 2003, 296(2): 295-326 doi: 10.1016/S0304-3975(02)00659-X
11	Zhang G, Gheorghe M, Wu C. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae , 2008, 87(1): 93-116
12	Zhang G, Liu C, Rong H. Analyzing radar emitter signals with membrane algorithms. Mathematical and Computer Modelling , 2010, 52(11-12): 1997-2010 doi: 10.1016/j.mcm.2010.06.002
13	Nishida T Y. Membrane algorithms. In: Proceedings of the 6th International Workshop on Membrane Computing . 2005, 55-66
14	Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Romero-Campero F J. A linear solution for QSAT with membrane creation. In: Proceedings of the 6th International Workshop on Membrane Computing . 2005, 241-252
15	Pan L, Ishdorj T-O. P systems with active membranes and separation rules. Journal of Universal Computer Science , 2004, 10(5): 630-649
16	Pǎaun G. P systems with active membranes: attacking NP-complete problems. Journal of Automata, Languages and Combinatorics , 2001, 6(1): 75-90
17	Pǎaun G, Pérez-Jiménez M J, Riscos-Nú?ez A. Tissue P system with cell division. International Journal of Computers, Communications & Control , 2008, III(3): 295-303
18	Pan L, Pérez-Jiménez M J. Computational Complexity of Tissue-like P Systems. Journal of Complexity , 2010, 26(3): 296-315 doi: 10.1016/j.jco.2010.03.001
19	Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos- Nú?ez A. A linear-time tissue P system based solution for the 3- coloring problem. Electronic Notes in Theoretical Computer Science , 2007, 171(2): 81-93 doi: 10.1016/j.entcs.2007.05.009
20	Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos- Nú?ez A. Solving subset sum in linear time by using tissue P system with cell division. In: Proceedings of the 2nd International Work- Conference on the Interplay between Natural and Artificial Computation . 2007, 170-179
21	Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos-Nú?ez A. Computational efficiency of cellular division in tissue-like membrane systems. Romanian Journal of Information Science and Technology , 2008, 11(3): 229-241
22	Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos-Nú?ez A. A linear time solution to the partition problem in a cellular tissue-like model. Journal of Computational and Theoretical Nanoscience , 2010, 7(5): 884-889 doi: 10.1166/jctn.2010.1435
23	Zhang X,Wang S, Niu Y, Pan L. Tissue P systems with cell separation: attacking the partition problem. Science China Information Sciences , 2011, 54(2): 293-304 doi: 10.1007/s11432-010-4162-y
24	Lu C, Zhang X. Solving vertex cover problem in tissue P systems with cell separation. International Journal of Computers, Communications & Control , 2010, 5(4): 540-550
25	Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos-Nú?ez A. Solving the independent set problem by using tissue-like P systems with cell division. In: Proceedings of the 3rd International Work-Conference on the Interplay between Natural and Artificial Computation . 2009, 213-222
26	Pérez-Jiménez M J, Romero-Jiménez á, Sancho-Caparrini F. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics , 2006, 11(4): 423-434
27	Pérez-Jiménez M J, Romero-Jiménez á, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Natural Computing , 2003, 2(3): 265-285 doi: 10.1023/A:1025449224520
28	Garey M R, Johnson D S. Computers and Intractability A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company, 1979

[1]	Tao SONG, Xiaolong SHI, Jinbang XU. Reversible spiking neural P systems[J]. Front Comput Sci, 2013, 7(3): 350-358.
[2]	Gheorghe Pãun. A quick overview of membrane computing with some details about spiking neural P systems[J]. Front. Comput. Sci., 2007, 1(1): 37-49.

Viewed

Full text

Abstract

Cited

Shared

Discussed