Uniform Solution of QSAT using polarizationless active membranes

TitleUniform Solution of QSAT using polarizationless active membranes
Publication TypeJournal Papers
Year of Publication2007
AuthorsAlhazov, A., & Pérez-Jiménez M. J.
Journal TitleLecture Notes in Computer Science
PublisherSpringer
Place PublishedAmsterdam, The Netherlands
Volume4664
Pages122-133
Abstract

It is known that the satisfiability problem (SAT) can be solved with a semi-uniform family of deterministic polarizationless P systems with active membranes with non–elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a quantified Boolean formula (QSAT) can be solved by a uniform family of P systems of the same kind.
The first author gratefully acknowledges the support by Academy of Finland, project 203667, and by the Supreme Council for Science and Technological Development of the Academy of Sciences of Moldova, project 06.411.03.04P. The second author wishes to acknowledge the support of the project TIN2005-09345-C04-01 of the Ministerio de Educación y Ciencia of Spain, cofinanced by FEDER funds.

URLhttp://www.springerlink.com/index/567256806100784t.pdf
ISSN Number0302-9743
DOI10.1007/978-3-540-74593-8