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
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
