On Various Notions of Parallelism in P Systems
Resource
International Journal of Foundations of Computer Science 16 (4): 683-705
Journal
International Journal of Foundations of Computer Science
Journal Volume
16
Journal Issue
4
Pages
683-705
Date Issued
2005-08
Author(s)
Abstract
We consider the following definition (different from the standard definition in the literature) of "maximal parallelism" in the application of evolution rules in a P system G: Let R = {r1,...r k} be the set of (distinct) rules in the system. G operates in maximally parallel mode if at each step of the computation, a maximal subset of R is applied, and at most one instance of any rule is used at every step (thus at most k rules are applicable at any step). We refer to this system as a maximally parallel system. We look at the computing power of P systems under three semantics of parallelism. For a positive integer n ≤ k, define: n-Max-Parallel: At each step, nondeterministically select a maximal subset of at most n rules in R to apply (this implies that no larger subset is applicable). ≤ n-Parallel: At each step, nondeterministically select any subset of at most n rules in R to apply. n-Parallel: At each step, nondeterministically select any subset of exactly n rules in R to apply. In all three cases, if any rule in the subset selected is not applicable, then the whole subset is not applicable. When n = 1, the three semantics reduce to the Sequential mode. We focus on two popular models of P systems: multi-membrane catalytic systems and communicating P systems. We show that for these systems, n-Max-Parallel mode is strictly more powerful than any of the following three modes: Sequential, ≤ n-Parallel, or n-Parallel. For example, it follows from the result in [9] that a maximally parallel communicating P system is universal for n = 2. However, under the three limited modes of parallelism, the system is equivalent to a vector addition system, which is known to only define a recursive set. These generalize and refine the results for the case of 1-membrane systems recently reported in [3]. Some of the present results are rather surprising. For example, we show that a Sequential 1-membrane communicating P system can only generate a semilinear set, whereas with k membranes, it is equivalent to a vector addition system for any k ≥ 2 (thus the hierarchy collapses at 2 membranes - a rare collapsing result for nonuniversal P systems). We also give another proof (using vector addition systems) of the known result [8] that a 1-membrane catalytic system with only 3 catalysts and (non-prioritized) catalytic rules operating under 3-Max-Parallel mode can simulate any 2-counter machine M. Unlike in [8], our catalytic system needs only a fixed number of noncatalysts, independent of M. A simple cooperative system (SCO) is a P system where the only rules allowed are of the form a → ν or of the form aa → ν, where a is a symbol and u is a (possibly null) string of symbols not containing o. We show that a 9-Max-Parallel 1-membrane SCO is universal. © World Scientific Publishing Company.
Type
conference paper