On the degree of parallelism in membrane systems

Abstract

In the literature, several designs of P systems might be found for performing the same task. The use of different techniques or even different P system models makes it very difficult to compare these designs. In this paper, we introduce a new criterion for such a comparison: the degree of parallelism of a P system. With this aim, we define the labelled dependency graph associated with a P system, and we use this new concept for proving some results concerning the maximum number of applications of rules in a single step through the computation of a P system.