Abstract
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].
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Busi, N., Gorrieri, R.: On the computational power of brane calculi. In: Proc. Third Workshop on Computational Methods in Systems Biology (CMSB 2005), Edinburgh, Scotland (2005)
Busi, N., Zavattaro, G.: Deciding reachability in mobile ambients. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol. 3444, pp. 248–262. Springer, Heidelberg (2005)
Cardelli, L.: Brane calculi – Interactions of biological membranes. In: Danos, V., Schachter, V. (eds.) CMSB 2004. LNCS (LNBI), vol. 3082, pp. 257–278. Springer, Heidelberg (2005)
Cardelli, L., Gordon, A.D.: Mobile ambients. Theoretical Computer Science 240(1), 177–213 (2000)
Cardelli, L., Păun, G.: An universality result for a (mem)brane calculus based on mate/drip operations. International Journal of Foundations of Computer Science (to appear)
Freund, R.: Asynchronous P Systems and P Systems Working in the Sequential Mode. In: Mauri, G., Păun, G., Jesús Pérez-Jímenez, M., Rozenberg, G., Salomaa, A. (eds.) WMC 2004. LNCS, vol. 3365, pp. 36–62. Springer, Heidelberg (2005)
Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Păun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000)
Păun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)
Regev, A., Panina, E.M., Silverman, W., Cardelli, L., Shapiro, E.: BioAmbients: An abstraction for biological compartments. Theoretical Computer Science 325(1), 141–167 (2004)
Reisig, W.: Petri Nets: An Introduction. Springer, Berlin (1985)
Shepherdson, J.C., Sturgis, J.E.: Computability of recursive functions. Journal of the ACM 10, 217–255 (1963)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Busi, N. (2006). On the Computational Power of the Mate/Bud/Drip Brane Calculus: Interleaving vs. Maximal Parallelism. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2005. Lecture Notes in Computer Science, vol 3850. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11603047_10
Download citation
DOI: https://doi.org/10.1007/11603047_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30948-2
Online ISBN: 978-3-540-32340-2
eBook Packages: Computer ScienceComputer Science (R0)