Ponencia
Size and Power of Extended Gemmating P Pystems
Autor/es | Besozzi, Daniela
Csuhaj Varjú, Erzsébet Mauri, Giancarlo Zandron, Claudio |
Fecha de publicación | 2004 |
Fecha de depósito | 2016-02-11 |
Publicado en |
|
ISBN/ISSN | 84-688-6101-4 |
Resumen | In P systems with gemmation of mobile membranes were ex-
amined. It was shown that (extended) systems with eight membranes are as
powerful as the Turing machines. Moreover, it was also proved that extended
gemmating P ... In P systems with gemmation of mobile membranes were ex- amined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was also 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 ¯ve membranes (with meta-priority relations and without (in=out) 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
GEMMAT.pdf | 130.4Kb | [PDF] | Ver/ | |