Repositorio de producción científica de la Universidad de Sevilla

Complexity aspects of polarizationless membrane systems

Opened Access Complexity aspects of polarizationless membrane systems

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: 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: 2009
Publicado en: Natural Computing, 8 (4), 703-717.
Tipo de documento: Artículo
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 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.
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.
Tamaño: 1.010Mb
Formato: PDF

URI: http://hdl.handle.net/11441/68042

DOI: 10.1007/s11047-008-9100-1

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones