Capítulo de Libro
On the Power of Dissolution in P Systems with Active Membranes
Autor/es | Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín Romero Campero, Francisco José |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2006 |
Fecha de depósito | 2017-01-31 |
Publicado en |
|
ISBN/ISSN | 978-3-540-30948-2 0302-9743 |
Resumen | In this paper we study membrane dissolution rules in the
framework of P systems with active membranes but without using electrical
charges. More precisely, we prove that the polynomial computational
complexity class ... In this paper we study membrane dissolution rules in the framework of P systems with active membranes but without using electrical charges. More precisely, we prove that the polynomial computational complexity class associated with the class of recognizer P systems with active membranes, without polarizations and without dissolution coincides with the standard complexity class P. Furthermore, we demonstrate that if we consider dissolution rules, then the resulting complexity class contains the class NP. |
Agencias financiadoras | Ministerio de Ciencia y Tecnología (MCYT). España |
Identificador del proyecto | TIC2002-04220-C03-01 |
Cita | Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J.,...,Romero Campero, F.J. (2006). On the Power of Dissolution in P Systems with Active Membranes. En Membrane Computing 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers. Lecture Notes in Computer Science Volume 3850 (pp. 224-240). Berlin: Springer. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
chp%3A10.1007%2F11603047_16.pdf | 626.7Kb | [PDF] | Ver/ | |