Complexity aspects of polarizationless membrane systems

TitleComplexity aspects of polarizationless membrane systems
Publication TypeJournal Papers
Year of Publication2009
AuthorsLeporati, A., Ferretti C., Mauri G., Pérez-Jiménez M. J., & Zandron C.
Journal TitleNatural Computing
PublisherSpringer Verlag
Place PublishedAmsterdam, Netherlands
Volume8
Pages703-717
Date Published12/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.

URLhttp://www.springerlink.com/content/a8q346311328p807/
Issue4
ISSN Number1567-7818
DOI10.1007/s11047-008-9100-1