Computing with membranes

We introduce a new computability model, of a distributed pal allel type, ba sed on the notion of a membrane structure. Such a structure consists of sev eral cell-like membranes, recurrently placed inside a unique "skin" membran e. A plane representation is a Venn diagram without intersected sets and wi th a unique superset. In the regions delimited by the membranes there are p laced objects. These objects are assumed to evolve: each object can be tran sformed in other objects, can pass through a membrane, or can dissolve the membrane in which it is placed. A priority relation between evolution rules can be considered. The evolution is done in parallel for all objects able to evolve. In this way, we obtain a computing device (we call it a P system ): start with a certain number of objects in a certain membrane and let the system evolve; if it will halt (no object can further evolve), then the co mputation is finished, with the result given as the number of objects in a specified membrane. If the development of the system goes forever, then the computation fails to have an output. We prove that the P systems with the possibility of objects to cooperate characterize the recursively enumerable sets of natural numbers; moreover, systems with only two membranes suffice . In fact, we do not need cooperating rules, but we only use catalysts, spe cified objects which are present in the rules but are not modified by the r ule application, One catalyst suffices. A variant is also considered, with the objects being strings over a given alphabet. The evolution rules are no w based on string transformations. We investigate the case when either the rewriting operation from Chomsky grammars (with respect to context-free pro ductions) or the splicing operation from H systems investigated in the DNA computing is used, In both cases, characterizations of recursively enumerab le languages are obtained by very simple P systems: with three membranes in the rewriting case and four in the splicing case. Several open problems an d directions for further research an formulated. (C) 2000 Academic Press.