New Choice for Small Universal Devices: Symport/Antiport P Systems

Sergey Verlan
Yurii Rogozhin

Symport/antiport P systems provide a very simple machinery inspired by corresponding operations in the living cell. It turns out that systems of small descriptional complexity are needed to achieve the universality by these systems. This makes them a good candidate for small universal devices replacing register machines for different simulations, especially when a simulating parallel machinery is involved. This article contains survey of these systems and presents different trade-offs between parameters.

In Turlough Neary, Damien Woods, Tony Seda and Niall Murphy: Proceedings International Workshop on The Complexity of Simple Programs (CSP 2008), Cork, Ireland, 6-7th December 2008, Electronic Proceedings in Theoretical Computer Science 1, pp. 235–242.
Published: 25th June 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.1.23 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org