Artículo
The role of the direction in tissue P systems with cell separation
Autor/es | Macías Ramos, Luis Felipe
Martínez del Amor, Miguel Ángel Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín Valencia Cabrera, Luis |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2014 |
Fecha de depósito | 2023-02-21 |
Publicado en |
|
Resumen | Tissue P systems with cell separation where the communication among cells is performed by means of symport and antiport rules are able to efficiently solve computationally hard problems in a feasible time by a space-time ... Tissue P systems with cell separation where the communication among cells is performed by means of symport and antiport rules are able to efficiently solve computationally hard problems in a feasible time by a space-time trade off. Symport and antiport rules formally capture the cases where a number of chemical substances pass through a membrane at the same time, with the help of each other, either in the same direction (symport) or in opposite directions (antiport). The present paper investigates the role of the direction in communication rules from a computational complexity point of view. More precisely, the efficiency of tissue P systems with cell separation is analyzed in the case when their communication rules are all of the same type: either symport rules or antiport rules. The main result is that in the framework of tissue P systems with cell separation, passing from using only symport rules to using only antiport rules amounts to passing from non-efficiency to efficiency, assuming that P ≠ NP. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España Junta de Andalucía |
Identificador del proyecto | TIN2012-37434
P08 – TIC 04200 |
Cita | Macías Ramos, L.F., Martínez del Amor, M.Á., Pérez Jiménez, M.d.J., Riscos Núñez, A. y Valencia Cabrera, L. (2014). The role of the direction in tissue P systems with cell separation. Journal of Automata, Languages and Combinatorics, 19 (1-4), 185-199. https://doi.org/10.25596/jalc-2014-185. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
2014_JALC_TheRoleOfTheDirection.pdf | 170.3Kb | [PDF] | Ver/ | |