Affiliations: Institute of Mathematics and Computer Science Academy
of Science of iof Moldova, Str. Academiei 5, Chişinău, MD 2028,
Moldova | Research Group on Mathematical Linguistics, Rovira i
Virgili University, Pl. Imperial Tàrraco 1, 43005 Tarragona, Spain | Department of Control Science and Engineering,
Huazhong University of Science and Technology, Wuhan 430074, Hubei, People's
Republic of China
Abstract: P systems are parallel molecular computing models based on
processing multisets of objects in cell-like membrane structures. Recently,
Petr Sosík has shown that a semi-uniform family of P systems with active
membranes and 2-division is able to solve the PSPACE-complete problem
QBF-SAT in linear time; he has also conjectured that the membrane dissolving
rules of the (d) type may be omitted, but probably not the (f) type rules for
non-elementary membrane division. In this paper, we partially confirm the
conjecture proving that dissolving rules are not necessary. Moreover, the
construction is now uniform. It still remains open whether or not
non-elementary membrane division is needed.
Keywords: Membrane computing, P system, PSPACE-complete problem, QBF-SAT problem
