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. Besozzi
Primo
;
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.
Geffert normal form; Gemmation; Membrane computing; Recursively enumerable Language
Settore INF/01 - Informatica
2005
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/8057
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact