P system
From Wikipedia, the free encyclopedia
- For the computer p-System, see UCSD p-System.
A P system is a computing model that abstracts from the way in which chemicals in a living cell interact and cross membranes.
Contents |
[edit] Introduction
Gheorghe Pӑun first conceived the model in 1998. His last name is the origin of the letter P in 'P systems'.
[edit] Terminology
Chemicals are modelled by symbols, or alternatively by strings of symbols. The region defined by a membrane can contain other symbols or strings (collectively referred to as objects) or other membranes, so that a P system has exactly one outer membrane (sometimes called the skin membrane) and a hierarchical relationship governing all its membranes. If objects are symbols, their multiplicity within a region matters; however multisets are also used in some string models. Regions have associated rules that define how objects are produced, consumed, passed to other regions and otherwise interact with one another. The non-deterministic maximally parallel application of rules throughout the system is a transition between system states, and a sequence of transitions is called a computation. Particular goals can be defined to signify a halting state, at which point the result of the computation can be e.g. the objects contained in a particular region or the objects sent out of the skin membrane.
[edit] Graphical representation
Because of their hierarchical nature, P systems are often depicted graphically with drawings that resemble Venn_diagrams. Such drawings are perhaps best described using an example.
In this example P system with symbols, the four membranes are labelled with consecutive integers. Membrane 1 (the skin membrane), contains membranes two and three as well as a rule. The particular rule moves any symbol c it encounters into region 2. This is possible because region 2 is directly accessible (adjacent) to region 1. Region 2 contains a rule that destroys (replaces with nothing) c symbols. Region 3 initially contains five c symbols. The first rule takes two c symbols and erases them as before, so that after 2 transitions only one symbol will remain. Region 4 is essentially a counter. After three transitions the a symbol is sent out of the membrane into region 3. The second rule of region 3 will consume the a symbol and the one remaining c symbol and send a c symbol out to region. By now it should be obvious that the symbol will eventually be destroyed in region 2, and thus the computation is not very useful.
Graphical representations may have other elements according to the variation of the model that is being studied. For example a rule may produce the special symbol δ, in which case the membrane that contains it is dissolved and all its contents move up in the region hierarchy.
[edit] Variant models
Many variant models have been studied. Researchers are primarily interested in such things as
- proving computational universality for systems with a small number of membranes
- solving NP-complete problems such as the SAT and the TSP using P systems by trading space and time complexities
and less often
- using models to explain natural processes in living cells (See also systems biology)
- devising models that may be implemented on hardware
[edit] See also
[edit] External links
- P Systems – website for P systems research.
