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

Small Computationally Complete Symport/Antiport P Systems


Advanced Search
Opened Access Small Computationally Complete Symport/Antiport P Systems
Show item statistics
Export to
Author: Csuhaj Varjú, Erzsébet
Margenstern, Maurice
Vaszil, György
Verlan, Sergey
Date: 2006
Published in: Proceedings of the Fourth Brainstorming Week on Membrane Computing, Vol.I, 267-281. Sevilla, E.T.S. de Ingeniería Informática, 30 de Enero-3 de Febrero, 2006
ISBN/ISSN: 8461106814
Document type: Presentation
Abstract: It is known that P systems with symport/antiport rules simulate the register machines, i.e., they are computationally complete. Hence, due to the existence of universal register machines, there exist computationally complete subclasses of symport/antiport P systems with a number of rules limited by a constant. However, there was no estimation of this number in the literature. In this article, we first give a simple estimation of this constant, and then we show that the number can be reduced by grouping together several instructions of the simulated variant of the register machines. Finally, a universal P system with symport/antiport having only 44 rules is obtained.
Size: 240.7Kb
Format: PDF


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

This item appears in the following Collection(s)