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
Cites

Show item statistics
Icon
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

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

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)