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.
Besozzi, D., Mauri, G., Paun, G., Zandron, C. (2003). Gemmating P systems: collapsing hierarchies. THEORETICAL COMPUTER SCIENCE, 296(2), 253-267 [10.1016/S0304-3975(02)00657-6].
Gemmating P systems: collapsing hierarchies
BESOZZI, DANIELA;MAURI, GIANCARLO;ZANDRON, CLAUDIO
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
