Name
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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(02)00657-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
open problem,Computer Science,Theoretical Computer Science,mobile membrane,membranes collapse,P system,Gemmating P system,Membrane computing,recursively enumerable language,Matrix grammar,Universality,extended system,Italian Conf,Lecture Notes,Recursively enumerable languages | Journal | 296 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 4 |
PageRank | References | Authors |
0.61 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniela Besozzi | 1 | 391 | 39.10 |
| Giancarlo Mauri | 2 | 2106 | 297.38 |
| Gheorghe Paun | 3 | 2840 | 369.48 |
| C. Zandron | 4 | 4 | 0.61 |