The Minimal Parallelism Is Still Universal

Abstract. A current research topic in membrane computing is to find more (biologically) realistic P systems, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper by considering a minimal parallelism: if a rule from a set of rules within a membrane or a region may be used, then at least one rule from that membrane or region could be used. Restrictive as it might look, this minimal parallelism still leads to universality, at least for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. The problem remains open for other classes of P systems.