Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes

Speaker: Krishna. S
Author(s): Krishna. S


We continue the study of P systems with mobile membranes introduced recently. This is a variant of P systems with active membranes, but having none of the features like polarizations, label change and division of non-elementary membranes. This variant was shown to be computationally universal using only the simple operations of endocytosis and exocytosis; moreover, if elementary membrane division is allowed, it is capable of solving NP-complete problems. It was proved (refer CiE'05 proceedings) that 4 membranes are sufficient for universality while using only endo/exo operations. In this paper, we study the computational power of these systems more systematically: we examine not only the power due to the number of membranes, but also with respect to the kind of rules used. We show that 3 membranes are sufficient for computational universality, whereas two membranes are not, if lambda-free rules are used.

websites: Arnold Beckmann 2006-06-09 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by