P Systems with Active Membranes and Two Polarizations

Abstract

P systems with active membranes using only two electrical charges and only rules of types (a) and (c) assigned to at most two membranes are shown to be computationally complete { thus improving the previous result of this type from the point of view of the number of polarizations as well as with respect to the number of membranes. Allowing a special variant of rules of type (c) to delete symbols by sending them out, even only one membrane is needed. Moreover, we present an algorithm for deterministically deciding SAT in linear time using only two polarizations and global rules of types (a) ; (c), and (e).