Artículo
Membrane creation and symport/antiport rules solving QSAT
Autor/es | Orellana Martín, David
Valencia Cabrera, Luis Pérez Jiménez, Mario de Jesús |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2022-09-12 |
Fecha de depósito | 2023-04-05 |
Publicado en |
|
Resumen | In Membrane Computing, diferent variants of devices can be found by changing both syntactical and semantic ingredients. These devices are usually called membrane systems or P systems, and they recall the structure and ... In Membrane Computing, diferent variants of devices can be found by changing both syntactical and semantic ingredients. These devices are usually called membrane systems or P systems, and they recall the structure and behavior of living cells in the nature. In this sense, rules are introduced as a way for objects to interact with membranes, giving P systems the ability to solve computational problems. Some of these rules, as division, separation and creation rules are inspired by the membrane division through the mitosis process or new membranes are created through gemmation. These rules seem to be crucial in the path to solve computationally hard problems. In this work, creation rules are used in classical P systems with symport/ antiport rules, where objects travel through membranes without changing to achieve enough computational power to efciently solve PSPACE-complete problems. More precisely, a solution to the QSAT problem is given by means of a uniform family of these systems. This paper was originally submitted to the International Conference on Membrane Computing 2021. |
Cita | Orellana Martín, D., Valencia Cabrera, L. y Pérez Jiménez, M.d.J. (2022). Membrane creation and symport/antiport rules solving QSAT. Journal of Membrane Computing, 4, 261-267. https://doi.org/10.1007/s41965-022-00104-7. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
s41965-022-00104-7.pdf | 878.6Kb | [PDF] | Ver/ | |