Ponencia
Small Computationally Complete Symport/Antiport P Systems
Autor/es | Csuhaj Varjú, Erzsébet
Margenstern, Maurice Vaszil, György Verlan, Sergey |
Fecha de publicación | 2006 |
Fecha de depósito | 2016-03-09 |
Publicado en |
|
ISBN/ISSN | 8461106814 |
Resumen | 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 ... 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
csuhaj-small-univ.pdf | 240.7Kb | [PDF] | Ver/ | |