|Title||P Systems with Gemmation of Mobile Membranes|
|Authors||Daniela Besozzi, Universita' degli
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