Complexity aspects of polarizationless membrane systems

Mon, 11/23/2009 - 11:21 — mmartinez

Title	Complexity aspects of polarizationless membrane systems
Publication Type	Journal Papers
Year of Publication	2009
Authors	Leporati, A., Ferretti C., Mauri G., Pérez-Jiménez M. J., & Zandron C.
Journal Title	Natural Computing
Publisher	Springer Verlag
Place Published	Amsterdam, Netherlands
Volume	8
Pages	703-717
Date Published	12/2009
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.
URL	http://www.springerlink.com/content/a8q346311328p807/
Issue	4
ISSN Number	1567-7818
DOI	10.1007/s11047-008-9100-1