Presentation
Small Computationally Complete Symport/Antiport P Systems
Author/s | Csuhaj Varjú, Erzsébet
Margenstern, Maurice Vaszil, György Verlan, Sergey |
Publication Date | 2006 |
Deposit Date | 2016-03-09 |
Published in |
|
ISBN/ISSN | 8461106814 |
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 ... 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
csuhaj-small-univ.pdf | 240.7Kb | ![]() | View/ | |