We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the power and size of extended gemmating P systems.
- Authors
Daniela Besozzi; Erzsbet Csuhaj-Varj; Giancarlo Mauri; Claudio Zandron
- Abstract
Abstract In [3] P systems with gemmation of mobile membranes were examined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was 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 five membranes (with meta-priority relations and without 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.
- Subjects
MACHINE theory; TURING machines; ALGORITHMS; MATHEMATICAL logic
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2005, Vol 9, Issue 9, p650
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-004-0394-3