期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2008
卷号：1
页码：108-117
DOI：10.4204/EPTCS.1.10
出版社：Open Publishing Association
摘要：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.
