Gemmating P systems: collapsing hierarchies

TitleGemmating P systems: collapsing hierarchies
Publication TypeJournal Papers
Year of Publication2003
AuthorsBesozzi, D., Mauri G., Paun G., & Zandron C.
Journal TitleTheoretical Computer Science
Place PublishedAmsterdam (The Netherlands)

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.

Keywordsmatrix grammar, Membrane computing, recursively enumerable languages, Universality
ISSN Number0304-3975