Artículo
Complexity aspects of polarizationless membrane systems
Autor/es | Leporati, Alberto
Ferretti, Claudio Mauri, Giancarlo Pérez Jiménez, Mario de Jesús ![]() ![]() ![]() ![]() ![]() ![]() ![]() Zandron, Claudio |
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 | We investigate polarizationless P systems with active membranes working in
maximally parallel manner, which do not make use of evolution or communication rules, in
order to find which features are sufficient to efficiently ... We investigate polarizationless P systems with active membranes working in maximally parallel manner, which do not make use of evolution or communication rules, in order to find which features are sufficient to efficiently solve computationally hard problems. We show that such systems are able to solve the PSPACE-complete problem QUANTIFIED 3-SAT, provided that non-elementary membrane division is controlled by the presence of a (possibly non-elementary) membrane. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | TIN2006-13425
![]() TIC-581 ![]() |
Cita | Leporati, A., Ferretti, C., Mauri, G., Pérez Jiménez, M.d.J. y Zandron, C. (2009). Complexity aspects of polarizationless membrane systems. Natural Computing, 8 (4), 703-717. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
s11047-008-9100-1.pdf | 1.010Mb | ![]() | Ver/ | |