In [3] 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.
On the power and size of extended gemmating P systems / D. Besozzi, E. Csuhaj-Varju, G. Mauri, C. Zandron. - In: SOFT COMPUTING. - ISSN 1432-7643. - 9:9(2005), pp. 650-656.
On the power and size of extended gemmating P systems
D. BesozziPrimo
;
2005
Abstract
In [3] 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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.