On the Computational Power of the Mate/Bud/Drip Brane Calculus: Interleaving vs. Maximal Parallelism

Brane calculi are a family of biologically inspired process calculi proposed in [3] for modeling the interactions of dynamically nested membranes. In [3] two basic calculi are proposed. Mate/Bud/Drip (MBD) is one of such basic calculi, and its primitives are inspired by membrane fusion and fission.

In this paper we investigate the expressiveness of MBD w.r.t. its ability to act as a computational device. In particular, we compare the expressiveness of two different semantics for MBD: the standard interleaving semantics – where a single interaction is executed at each computational step – and the maximal parallelism semantics – according to which a computational step is composed of a maximal set of independent interactions.

For the interleaving semantics, we show a nondeterministic encoding of Register Machines in MBD, that preserves the existence of a terminating computation, but that could introduce additional divergent (i.e., infinite) computations.

For the maximal parallelism semantics, we provide a deterministic encoding of Register Machines, which preserves both the existence of a terminating computation and the existence of a divergent computation.

The impossibilty of providing a deterministic encoding under the interleaving semantics is a consequence of the decidability of the existence of a divergent computation proved in [1].