On power of p systems using sequential and parallel rewriting

Abstract

A new class of distributed computing models inspired from biology, that of P Systems, was recently introduced by Gh. P[acaron]un. Several variants of P Systems were already shown to be computationally universal, equal in power to Turing Machines. We investigate in this paper the power of computability of P Systems based on rewriting, with cooperation, priorities and external output. It is established that rewriting P Systems with priorities and two membranes is computationally universal, thereby making an improvement in the existing result that RE⊆RP ₃(Pri). We give a new model in P Systems stressing the importance of parallelism. The power of computability of such models is investigated by comparing them with classic mechanisms in L-Systems: TOL, EOL and ETOL Systems

Keywords:

• Cooperation and Priorities
• Computationally Universal
• External Output
• Membranes of Variable Thickness
• Rewriting P Systems