Computational Power of P Systems with Small Size Insertion and Deletion Rules

Alexander Krassovitskiy
Yurii Rogozhin
Sergey Verlan

Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages. However, if additional computational distribution mechanisms like P systems are added, then the computational completeness is achieved in some cases. In this article we take two insertion-deletion systems that are not computationally complete, consider them in the framework of P systems and show that the computational power is strictly increased by proving that any recursively enumerable language can be generated. At the end some open problems are presented.

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. 108–117.
Published: 25th June 2009.

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

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