Options
On power of P Systems using sequential and parallel rewriting
Date Issued
01-12-2001
Author(s)
Krishna, Shankara Narayanan
Rama, Raghavan
Abstract
A new class of distributed computing models inspired from biology, that of P Systems, was recently introduced by Gh. Pǎ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 REC ⊆ RP3(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. © 2001 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint.
Volume
76