P systems are computational models inspired by some biological features of the structure and the functioning of real cells. In this paper we introduce a new kind of communication between membranes, based upon the natural budding of vesicles in a cell. We de-ne the operations of gemmation and fusion of mobile membranes, and we use membrane structures and rules over strings of biological inspiration only. We prove that P systems of this type can generate all recursively enumerable languages and, moreover, the Hamiltonian Path Problem can be solved in a quadratic time. Some open problems are also formulated

Besozzi, D., Zandron, C., Mauri, G., Sabatini, N. (2001). P systems with Gemmation of Mobile Membranes. In Proc. Italian Conference of Theoretical Computer Science (pp.136-153). Berlin : Springer-Verlag [10.1007/3-540-45446-2_9].

P systems with Gemmation of Mobile Membranes

BESOZZI, DANIELA;ZANDRON, CLAUDIO;MAURI, GIANCARLO;
2001

Abstract

P systems are computational models inspired by some biological features of the structure and the functioning of real cells. In this paper we introduce a new kind of communication between membranes, based upon the natural budding of vesicles in a cell. We de-ne the operations of gemmation and fusion of mobile membranes, and we use membrane structures and rules over strings of biological inspiration only. We prove that P systems of this type can generate all recursively enumerable languages and, moreover, the Hamiltonian Path Problem can be solved in a quadratic time. Some open problems are also formulated
No
slide + paper
Scientifica
P systems, gemmation, mobile, membranes
English
Italian Conference on Theoretical Computer Science, ICTCS - 4-6 october
978-3-540-42672-1
Besozzi, D., Zandron, C., Mauri, G., Sabatini, N. (2001). P systems with Gemmation of Mobile Membranes. In Proc. Italian Conference of Theoretical Computer Science (pp.136-153). Berlin : Springer-Verlag [10.1007/3-540-45446-2_9].
Besozzi, D; Zandron, C; Mauri, G; Sabatini, N
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: http://hdl.handle.net/10281/12255
Citazioni
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
Social impact