Home

From The P Systems Webpage



Introduction to Membrane Computing



Computing with membranes (P systems) is a branch of Molecular Computing initiated by Gh. Paun by the paper Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108-143 (first circulated ad TUCS Research Report No 208, November 1998, http://www.tucs.fi ). In February 2003, the Institute for Scientific Information, ISI, has mentioned this paper as fast breaking in the area of computer science (see http://esi-topics.com, February 2003).

A P system is a computing model which abstracts from the way the alive cells process chemical compounds in their compartmental structure. In short, in the regions defined by a membrane structure we have objects which evolve according to given rules. The objects can be described by symbols or by strings of symbols (in the former case their multiplicity matters, that is, we work with multisets of objects placed in the regions of the membrane structure; in the second case we can work with languages of strings or, again, with multisets of strings). By using the rules in a nondeterministic, maximally parallel manner, one gets transitions between the system configurations. A sequence of transitions is a computation. With a halting computation we can associate a result, in the form of the objects present in a given membrane in the halting configuration, or expelled from the system during the computation.

Various ways of controlling the transfer of objects from a region to another one and of applying the rules, as well as possibilities to dissolve, divide, create, or move membranes were considered. Also, tissue P systems, neural P systems, and population P systems were investigated.

Many of these variants lead to computationally universal systems, while several variants with an enhanced parallelism are able to "solve" NP-complete problems in polynomial (often, linear) time - of course, by making use of an exponential space. A series of applications, in biology, linguistics, computer science, management, etc., were reported.



About this website



This site contains information about the latest developments in this field News here, coming or past conferences - on or related to membrane computing Conferences here, a membrane computing bibliography Bibliography here, the proceedings of the conferences or workshops and brainstorming meetings, as well as some papers and PhD theses Download here, addresses of most of the contributors Addresses here, prizes awarded Prizes here, pictures taken throughout the years Pictures here, membrane computing in education Education here and software tools for various membrane systems Tools here.