www.elsevier.com/locate/tcs A guide to membrane computing

Membrane systems are models of computation which are inspired by some basic features of biological membranes. In a membrane system multisets of objects are placed in the compartments de.ned by the membrane structure, and the objects evolve by means of “reaction rules ” also associated with the compartments, and applied in a maximally parallel, nondeterministic manner. The objects can pass through membranes, the membranes can change their permeability, they can dissolve, and they can divide. These features are used in de.ning transitions between con.g-urations of the system, and sequences of transitions are used to de.ne computations. In the case of symbol-objects, we compute a set of numbers, and in the case of string-objects we compute a set of strings, hence a language. Many di4erent classes of such computing devices (now called P systems) have already been investigated. Most of them are computationally universal, i.e., equal in power to Turing machines. Systems with an enhanced parallelism are able to trade space for time and solve in this way (at least in principle), by making use of an exponential space, intractable problems in a feasible time. The present paper presents the basic ideas of computing with membranes and some funda