Logical Approaches to Computational Barriers
Print this page
Regular Talk:
Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes
| THIS TALK HAS BEEN CANCELLED!!! | |
| Speaker: | Krishna. S |
| Author(s): | Krishna. S |
Abstract
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
|