We continue the analysis of P systems with gemmation of mobile membranes. We solve an open problem from Besozzi et al. (Proc. Italian Conf. on Theoretical Computer Science 2001, Lecture Notes in Computer Science, Vol. 2202, Springer, Berlin, 2001, pp. 136–153), showing that the hierarchy on the number of membranes collapses: systems with eight membranes characterize the recursively enumerable languages (seven membranes are enough in the case of extended systems). We also prove that P systems, which use only gemmation, but neither classical rewriting rules nor in/out communications, can generate the same family of languages. In this case, the hierarchy on the number of membranes collapses to level nine.

Gemmating P systems: collapsing hierarchies / D. Besozzi, G. Mauri, G . Paun , C. Zandron. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 296:2(2003), pp. 253-267.

Gemmating P systems: collapsing hierarchies

D. Besozzi
Primo
;
2003

Abstract

We continue the analysis of P systems with gemmation of mobile membranes. We solve an open problem from Besozzi et al. (Proc. Italian Conf. on Theoretical Computer Science 2001, Lecture Notes in Computer Science, Vol. 2202, Springer, Berlin, 2001, pp. 136–153), showing that the hierarchy on the number of membranes collapses: systems with eight membranes characterize the recursively enumerable languages (seven membranes are enough in the case of extended systems). We also prove that P systems, which use only gemmation, but neither classical rewriting rules nor in/out communications, can generate the same family of languages. In this case, the hierarchy on the number of membranes collapses to level nine.
Matrix grammar; Membrane computing; Recursively enumerable languages; Universality
Settore INF/01 - Informatica
2003
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/10027
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact