Repositorio de producción científica de la Universidad de Sevilla

Size and Power of Extended Gemmating P Pystems


Advanced Search
Opened Access Size and Power of Extended Gemmating P Pystems
Show item statistics
Export to
Author: Besozzi, Daniela
Csuhaj Varjú, Erzsébet
Mauri, Giancarlo
Zandron, Claudio
Date: 2004
Published in: Proceedings of the Second Brainstorming Week on Membrane Computing, 92-101. Sevilla, E.T.S. de Ingeniería Informática, 2-7 de Febrero, 2004
ISBN/ISSN: 84-688-6101-4
Document type: Presentation
Abstract: 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.
Size: 130.4Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)