Abstract
Tissue P systems are distributed parallel and non-deterministic computing models in the framework of membrane computing, which are inspired by intercellular communication and cooperation between neurons. Recently, cell separation is introduced into tissue P systems, which enables systems to generate an exponential workspace in a polynomial time. In this work, the computational power of tissue P systems with cell separation is investigated. Specifically, a uniform family of tissue P systems with cell separation is constructed for efficiently solving a well-known NP-complete problem, the partition problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Păun Gh, Rozenberg G, Salomaa A. Handbook of Membrane Computing. Oxford: Oxford University Press, 2010
The P System Web Page: http://ppage.psystems.eu
Păun Gh. Computing with membranes. J Comput Syst Sci, 2000, 61: 108–143
Martín-Vide C, Pazos J, Păun Gh, et al. Tissue P systems. Theor Comput Sci, 2003, 296: 295–326
Păun A, Păun Gh. The power of communication: P systems with symport/antiport. New Gen Comput, 2002, 20: 295–305
Alhazov A, Freund R, Oswald M. Tissue P systems with antiport rules and small numbers of symbols and cells. Lect Notes Comput Sci, 2005, 3572: 100–111
Bernardini F, Gheorghe M. Cell communication in tissue P systems and cell division in population P systems. Soft Comput, 2005, 9: 640–649
Freund R, Păun Gh, Pérez-Jiménez M J. Tissue P systems with channel states. Theor Comput Sci, 2005, 330: 101–116
Krishna S N, Lakshmanan K, Rama R. Tissue P systems with contextual and rewriting rules. Lect Notes Comput Sci, 2003, 2597: 339–351
Lakshmanan K, Rama R. On the power of tissue P systems with insertion and deletion rules. In: Preproceedings of the Fourth International Workshop on Membrane Computing (report RGML 28/03). Tarragona, Spain, 2003. 304–318
Prakash V J. On the power of tissue P systems working in the maximal-one mode. In: Preproceedings of the Fourth International Workshop on Membrane Computing (report RGML 28/03). Tarragona, Spain, 2003. 356–364
Păun Gh, Pérez-Jiménez M J, Riscos-Núñez A. Tissue P systems with cell division. Int J Comput Commun Control, 2008, III: 295–302
Díaz-Pernil D. Sistemas P de tejido: formalización y efficiencia computacional, Ph.D. Thesis, University of Seville, Seville, Spain, 2008
Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M A, et al. A linear-time tissue P system based solution for the 3-coloring problem. Electr Notes Theor Comput Sci, 2007, 171: 81–93
Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M A, et al. A uniform family of tissue P system with cell division solving 3-COL in a linear time. Theor Comput Sci, 2008, 404: 76–87
Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M A, et al. Solving subset sum in linear time by using tissue P system with cell division. Lect Notes Comput Sci, 2007, 4527: 170–179
Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M A, et al. Computational efficiency of cellular division in tissue-like membrane systems. Rom J Inf Sci Tech, 2008, 11: 229–241
Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M A, et al. A fast solution to the partition problem by using tissue-like P systems. In: Proceedings of the Third International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2008. Adelaide, SA, Australia, 2008. 43–48
Pan L, Pérez-Jiménez M A. Computational complexity of tissue-like P systems. J Complex, 2010, 26: 296–315
Păun Gh. Membrane Computing—An Introduction. Berlin: Springer-Verlag, 2002
Martín Vide C, Pazos J, Păun Gh, et al. A new class of symbolic abstract neural nets: tissue P systems. Lect Notes Comput Sci, 2002, 2387: 573–679
Pan L, Ishdorj T-O. P systems with active membranes and separation rules. J Univer Comput Sci, 2004, 10: 630–649
Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. A polynomial complexity class in P systems using membrane division. In: Proceedings of the Fifth Workshop on Descriptional Complexity of Formal Systems, DCFS 2003. Budapest, Maryland, Hungary, 2003. 284–294
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
Gutiérrez-Naranjo M A, Pérez-Jiménez M A, Romero-Campero F J. A uniform solution to SAT using membrane creation. Theor Comput Sci, 2007, 371: 54–61
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, X., Wang, S., Niu, Y. et al. Tissue P systems with cell separation: attacking the partition problem. Sci. China Inf. Sci. 54, 293–304 (2011). https://doi.org/10.1007/s11432-010-4162-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-010-4162-y