Tissue P Systems with Cell Division

Authors

  • Gheorghe Păun 1Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania 2 Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Technical Higher School of Computer Science Engineering University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
  • Mario J. Perez-Jimenez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Technical Higher School of Computer Science Engineering University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
  • Agustí­n Riscos-Nunez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Technical Higher School of Computer Science Engineering University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Keywords:

Tissue-like P systems, cell division rule, SAT problem, NP-complete problem

Abstract

In tissue P systems several cells (elementary membranes) communicate through symport/antiport rules, thus carrying out a computation. We add to such systems the basic feature of (cell—like) P systems with active membranes — the possibility to divide cells. As expected (as it is the case for P systems with active membranes), in this way we get the possibility to solve computationally hard problems in polynomial time; we illustrate this possibility with SAT problem.

References

D. Díaz-Pernil: Sistemas celulares de tejidos: Formalización y eficiencia computacional, PhD Thesis, University of Sevilla, 2008.

D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Nú-ez: Solving subset sum in linear time by using tissue P systems with cell division. In J. Mira, J.R. Alvarez, eds. Bio- Inspired Modeling of Cognitive Tasks, Second International Work-Conference on the Interplay between Natural and Artificial Computation, IWINAC 2007, La Manga del Mar Menor, Spain, June 2007,Part I, LNCS 4527, Springer, 2007, 170-179. http://dx.doi.org/10.1007/978-3-540-73053-8_17

D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Nú-ez: Solving the partition problem by using tissue-like P systems with cell division. In D. Díaz, C. Graciani, M.A. Gutiérrez, Gh. P˘aun, I. Pérez-Hurtado, A. Riscos, eds., Proceedings of the Sixth Brainstorming Week on Membrane Computing, Report RGNC 01/08, Fénix Editora, 2008, 123-134.

D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Nú-ez: A linear-time tissue P system based solution for the 3-coloring problem, Electronic Notes in Theoretical Computer Science, 171 (2007), 81-93. http://dx.doi.org/10.1016/j.entcs.2007.05.009

D. Díaz-Pernil, M.J. Pérez-Jiménez, A. Riscos-Nú-ez, A. Romero-Jiménez: Computational efficiency of cellular division in tissue-like membrane systems, submitted, 2008.

P. Frisco, H.J. Hoogeboom: Simulating counter automata by P systems with symport/antiport. In Gh. Paun, G. Rozenberg, A. Salomaa, C. Zandron, eds., Membrane Computing. International Workshop WMC 2002, Curtea de Arge¸s, Romania, Revised Papers, LNCS 2597, Springer, 2003, 288-301.

M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, F.J. Romero-Campero: A linear time solution for QSAT with membrane creation. In R. Freund, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds., Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers, LNCS 3850, Springer, 2006, 241-252.

Gh. P˘aun: Computing with Membranes: An Introduction, Springer, Berlin, 2002.

M.J. Pérez-Jiménez: An approach to computational complexity in membrane computing. In G. Mauri, Gh. P˘aun, M.J. Pérez-Jiménez, G. Rozenberg, A. Salomaa, eds., Membrane Computing, 5th International Workshop, WMC5, Revised Selected and Invited Papers, LNCS 3365, Springer, 2005, 85-109. http://dx.doi.org/10.1007/978-3-540-31837-8_5

M. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, Teoría de la Complejidad en Modelos de Computatión Celular con Membranas, Editorial Kronos, Sevilla, 2002.

P. Sosik, A. Rodríguez-Patón: Membrane computing and complexity theory: A characterization of PSPACE, International Journal of Foundations of Computer Science, 73, 1 (2007), 137-152. http://dx.doi.org/10.1016/j.jcss.2006.10.001

Published

2008-09-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.