Article
Tissue P systems with evolutional communication rules with two objects in the left-hand side
Author/s | Orellana Martín, David
Valencia Cabrera, Luis Song, Bosheng Pan, Linqiang Pérez Jiménez, Mario de Jesús |
Department | Universidad de Sevilla. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Publication Date | 2022-10-19 |
Deposit Date | 2023-04-11 |
Published in |
|
Abstract | In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is ... In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important task to tackle the P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumed efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the SAT problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the righthand side of the rules have at most two objects; that is, with recognizer P systems from TSECð2; 2Þ. This result improves a previous one, when 3 objects could be used in the left-hand side of the evolutional communication rules |
Funding agencies | Junta de Andalucía |
Project ID. | P20_00486 |
Citation | Orellana Martín, D., Valencia Cabrera, L., Song, B., Pan, L. y Pérez Jiménez, M.d.J. (2022). Tissue P systems with evolutional communication rules with two objects in the left-hand side. Natural Computing, 22, 119-132. https://doi.org/10.1007/s11047-022-09924-z. |
Files | Size | Format | View | Description |
---|---|---|---|---|
s11047-022-09924-z.pdf | 404.5Kb | [PDF] | View/ | |