Repositorio de producción científica de la Universidad de Sevilla

The Role of the Environment in Tissue P Systems with Cell Division

Opened Access The Role of the Environment in Tissue P Systems with Cell Division
Estadísticas
Icon
Exportar a
Autor: Pérez Jiménez, Mario de Jesús
Riscos Núñez, Agustín
Rius Font, Miquel
Romero Campero, Francisco José
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2012
Publicado en: Proceedings of the Tenth Brainstorming Week on Membrane Computing, (2)89-104. Sevilla, E.T.S. de Ingeniería Informática, 30 de Enero-3 de Febrero, 2012,
ISBN/ISSN: 978-84-940056-6-4
Tipo de documento: Ponencia
Resumen: Classical tissue P systems with cell division have a special alphabet whose elements appear at the initial configuration of the system in an arbitrary large number of copies. These objects are shared in a distinguished place of the system, called the environment. Besides, the ability of these computing devices to have infinite copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems. This paper deals with computational aspects of tissue P systems with cell division where there is not an environment having the property mentioned above. Specifically, we establish the relationships between the polynomial complexity class associated with tissue P systems with cell division and with or without environment. As a consequence, we prove that it is not necessary to have infinite copies of some objects at the initial configuration in order to solve NP–complete problems in an efficient way.
Tamaño: 134.1Kb
Formato: PDF

URI: http://hdl.handle.net/11441/34091

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones