Artículo
Efficient simulation of tissue-like P systems by transition cell-like P systems
Autor/es | 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 de publicación | 2009 |
Fecha de depósito | 2017-12-28 |
Publicado en |
|
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 ... 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 tissue-like P systems. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | TIN2006-13425
TIC-581 |
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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
s11047-008-9102-z.pdf | 359.5Kb | [PDF] | Ver/ | |
Este registro aparece en las siguientes colecciones
Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Items relacionados
Enseñando items relacionados por título, autor, creador y materia.
-
Ponencia
Metabolism in eco-holonic manufacturing systems based on the living systems theory
Ávila-Gutiérrez, María Jesús; Martín-Gómez, Alejandro Manuel; Aguayo-González, Francisco (IOP Publishing, 2021-10)The industrial metabolism has been conceived on the basis of analogies about the set of biochemical reactions (anabolism ...
-
Tesis Doctoral
Application of Multibody System Techniques to Human Locomotor System
Ojeda Granja, Joaquín (2012) -
Tesis Doctoral
P systems, a computational modelling framework for systems biology
Romero Campero, Francisco José (2008-02-06)LOS PROGRAMAS INFORMÁTICOS QUE MODELIZAN CÉLULAS FACILITARÁN EL TRABAJO DE LOS BIÓLOGOS Se basa en hacer modelos de células, ...