The P Systems Web Page
HIGHLIGHTED NEWS :
January 15, 2008
Paper by Gheorghe Paun concerning Open Problems for the
Sixth Brainstorming Week on Membrane Computing (BWMC6)
Click here to download the paper
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.
A current bibliography of P systems can be found here, as well as news from this area, a list of addresses of persons who have (co)authored papers about P systems, some open problems , and several recent papers .
Links to web addresses related to this subject are also available.
If you have any comment, question or feedback, please contact the webmaster
Website created on October 2000
Last updated: January 2006