| 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
|