Title P Systems with Gemmation of Mobile Membranes
Authors Daniela Besozzi, Universita' degli studi dell'Insubria
Claudio Zandron, Universita' di Milano - Bicocca
Giancarlo Mauri, Universita' di Milano - Bicocca
Nicoletta Sabadini, Universita' degli studi dell'Insubria
Main Fields 4. computational complexity
8. formal languages
12. parallel and distributed computation
Other Main Fields
Abstract + Keywords 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 define 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.

Keyworkds: Molecular Computing, NP-Complete problems, Recursively
Enumerable Languages