In  P systems with gemmation of mobile membranes were examined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was proved that extended gemmating P systems with only pre-dynamical rules are still computationally complete: In this case nine membranes are needed to obtain this computational power. In this paper we improve the above results concerning the size bound of extended gemmating P systems, namely we prove that these systems with at most five membranes (with meta-priority relations and without communication rules) form a class of universal computing devices, while in the case of extended systems with only pre-dynamical rules six membranes are enough to determine any recursively enumerable language.
|Titolo:||On the power and size of extended gemmating P systems|
BESOZZI, DANIELA (Primo)
|Parole Chiave:||Geffert normal form; Gemmation; Membrane computing; Recursively enumerable Language|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2005|
|Digital Object Identifier (DOI):||10.1007/s00500-004-0394-3|
|Appare nelle tipologie:||01 - Articolo su periodico|