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

Complexity aspects of polarizationless membrane systems


Advanced Search
Opened Access Complexity aspects of polarizationless membrane systems

Show item statistics
Export to
Author: Leporati, Alberto
Ferretti, Claudio
Mauri, Giancarlo
Pérez Jiménez, Mario de Jesús
Zandron, Claudio
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2009
Published in: Natural Computing, 8 (4), 703-717.
Document type: Article
Abstract: 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.
Cite: 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.
Size: 1.010Mb
Format: PDF


DOI: 10.1007/s11047-008-9100-1

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)