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

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

2009-06-17

arxiv.org/abs/0906.3119v1

EPTCS 1, 2009, pp. 108-117

Computer Science

Computational Complexity

Scientific paper

10.4204/EPTCS.1.10

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.

Affiliated with

Also associated with

No associations

Rating

Computational Power of P Systems with Small Size Insertion and Deletion Rules does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computational Power of P Systems with Small Size Insertion and Deletion Rules, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Power of P Systems with Small Size Insertion and Deletion Rules will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-222887