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

Efficient simulation of tissue-like P systems by transition cell-like P systems

Opened Access Efficient simulation of tissue-like P systems by transition cell-like P systems

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Díaz Pernil, Daniel
Pérez Jiménez, Mario de Jesús
Romero Jiménez, Álvaro
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2009
Publicado en: Natural Computing, 8 (4), 797-806.
Tipo de documento: Artículo
Resumen: In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally hard problems (unless P = NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution, communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/ antiport rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of basic cell-like P systems to this kind of tiss...
[Ver más]
Cita: Díaz Pernil, D., Pérez Jiménez, M.d.J. y Romero Jiménez, Á. (2009). Efficient simulation of tissue-like P systems by transition cell-like P systems. Natural Computing, 8 (4), 797-806.
Tamaño: 359.5Kb
Formato: PDF

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

DOI: 10.1007/s11047-008-9102-z

Ver versión del editor

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