Brane calculi are a family of biologically inspired process calculi proposed in [3] for modeling the interactions of dynamically nested membranes. In [3] a basic calculus for membranes interactions – called Phago/Exo/Pino – is proposed, whose primitives are inspired by endocytosis and exocytosis. An alternative basic calculus – called Mate/Bud/Drip and inspired by membrane fusion and fission – is also outlined and shown to be encodable in Phago/Exo/Pino in [3]. In this paper we investigate and compare the expressiveness of such two calculi w.r.t. their ability to act as computational devices. We show that (a fragment of) the Phago/Exo/Pino calculus is Turing powerful, by providing an encoding of Random Access Machines. On the other hand, we show the impossibility to define a “faithful” encoding of Random Access Machines in the Mate/Bud/Drip calculus, by providing a proof of the decidability of the existence of a divergent computation in Mate/Bud/Drip.

N. Busi, R. Gorrieri (2006). On the Computational Power of Brane Calculi. Heidelberg : Springer [10.1007/11880646_2].

On the Computational Power of Brane Calculi

BUSI, NADIA;GORRIERI, ROBERTO
2006

Abstract

Brane calculi are a family of biologically inspired process calculi proposed in [3] for modeling the interactions of dynamically nested membranes. In [3] a basic calculus for membranes interactions – called Phago/Exo/Pino – is proposed, whose primitives are inspired by endocytosis and exocytosis. An alternative basic calculus – called Mate/Bud/Drip and inspired by membrane fusion and fission – is also outlined and shown to be encodable in Phago/Exo/Pino in [3]. In this paper we investigate and compare the expressiveness of such two calculi w.r.t. their ability to act as computational devices. We show that (a fragment of) the Phago/Exo/Pino calculus is Turing powerful, by providing an encoding of Random Access Machines. On the other hand, we show the impossibility to define a “faithful” encoding of Random Access Machines in the Mate/Bud/Drip calculus, by providing a proof of the decidability of the existence of a divergent computation in Mate/Bud/Drip.
2006
Transactions on Computational Systems Biology VI
16
43
N. Busi, R. Gorrieri (2006). On the Computational Power of Brane Calculi. Heidelberg : Springer [10.1007/11880646_2].
N. Busi; R. Gorrieri
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/38110
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
social impact