Record Details

Upper and lower bounds for the computational power of P systems with mobile membranes

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Upper and lower bounds for the computational power of P systems with mobile membranes
 
Creator KRISHNA, SN
 
Description We continue the study of P systems with mobile membranes introduced in [7], which 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 (RE) 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 shown in [5] 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, thereby trying to find out the border line between universality and non-universality. We show that 3 membranes axe sufficient for computational universality, whereas two membranes are not, if lambda -free rules are used.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T20:29:13Z
2011-12-15T09:10:58Z
2011-10-23T20:29:13Z
2011-12-15T09:10:58Z
2006
 
Type Article; Proceedings Paper
 
Identifier LOGICAL APPROACHES TO COMPTATIONAL BARRIERS, PROCEEDINGS,3988,526-535
3-540-35466-2
0302-9743
http://dx.doi.org/10.1007/11780342_53
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15227
http://hdl.handle.net/100/1772
 
Source 2nd Conference on Computability in Europe (CiE 2006),Swansea, WALES,JUN 30-JUL 05, 2006
 
Language English