P system

For the computer p-System, see UCSD p-System.

A P system is a computational model in the field of computer science that performs calculations using a biologically-inspired process. They are based upon the structure of biological cells, abstracting from the way in which chemicals interact and cross cell membranes. The concept was first introduced in a 1998 report[1] by the computer scientist Gheorghe Păun, whose last name is the origin of the letter P in 'P Systems'. Variations on the P system model led to the formation of a branch of research known as 'membrane computing.'

Although inspired by biology, the primary research interest in P systems is concerned with their use as a computational model, rather than for biological modeling,[2] although this is also being investigated.[3][4]

Informal description

A P system is defined as a series of membranes containing chemicals (in finite quantities), catalysts and rules which determine possible ways in which chemicals may react with one another to form products. Rules may also cause chemicals to pass through membranes or even cause membranes to dissolve.

Just as in a biological cell, where a chemical reaction may only take place upon the chance event that the required chemical molecules collide and interact (possibly also with a catalyst), the rules in a P system are applied at random. This causes the computation to proceed in a non-deterministic manner, often resulting in multiple solutions being encountered if the computation is repeated.

A P system continues until it reaches a state where no further reactions are possible. At this point the result of the computation is all those chemicals that have been passed outside of the outermost membrane, or otherwise those passed into a designated 'result' membrane.[4]

Components of a P system

Although many varieties of P system exist, most share the same basic components. Each element has a specific role to play, and each has a founding in the biological cell architecture upon which P systems are based.

The environment

The environment is the surroundings of the P system. In the initial state of a P system it contains only the container-membrane, and while the environment can never hold rules, it may have objects passed into it during the computation. The objects found within the environment at the end of the computation constitute all or part of its “result.”

Membranes

Membranes are the main “structures” within a P system. A membrane is a discrete unit which can contain a set of objects (symbols/catalysts), a set of rules, and a set of other membranes contained within. The outermost membrane, held within the environment, is often referred to as the 'container membrane' or 'skin membrane'. As implied to by their namesake, membranes are permeable and symbols resulting from a rule may cross them. A membrane (but not the container membrane) may also “dissolve”, in which case its content, except for rules (which are lost), migrate into the membrane in which it was contained.[2]

Some P system variants allow for a membrane to divide, possess a charge or have varying permeability by changing membrane thickness.[2]

Symbols

Symbols represent chemicals which may react with other chemicals to form some product. In a P system each type of symbol is typically represented by a different letter. The symbol content of a membrane is therefore represented by a string of letters. Because the multiplicity of symbols in a region matters, multisets are commonly used to represent the symbol content of a region.

Special case symbols exist, for example a lower case delta (δ) is often used to initiate the dissolving of a membrane, and this will only ever be found in the output of a rule: upon being encountered it invokes a reaction, and is used in the process.

Catalysts

Catalysts are similar to their namesakes in chemistry. They are represented and used in the same way as symbols, but are never consumed during a “reaction,” they are simply a requirement for it to occur.

Rules

Rules represent a possible chemical reaction within a membrane, causing it to evolve to a new state. A rule has a required set of input objects (symbols or catalysts) which must be present in order for it to be applied. If the required objects are present, it consumes them and produces a set of output objects. A rule may also be specified to have a priority over other rules, in which case less dominant rules will only be applied when it is not possible to apply a more dominant rule (i.e. the required inputs are not present).

There are three (in the basic P system model) distinct ways in a rule may handle its output objects. Usually the output objects are passed into the current membrane (the same membrane in which the rule and the inputs reside), known as a here rule. However there are two modifiers which can be specified upon output objects when rules are defined, in and out. The in modifier causes the object to be passed to one of the current membrane’s children (travelling inwards relative to the structure of the P system), chosen at random during the computation. The out modifier causes the object to be passed out of the current membrane and into either its parent membrane or to a sibling membrane, specified during specification of the P system.

Computation process

A computation works from an initial starting state towards an end state through a number of discrete steps. Each step involves iterating through all membranes in the P system and the application of rules, which occurs in both a maximally parallel and non-deterministic manner.[4]

Working through step-by-step, a computation halts when no further evolution can take place (i.e. when no rules are able to be applied). At this point whatever objects have been passed to the environment, or into a designated 'result' membrane, are counted as the result of the computation.[4]

Rule application

At each step of a computation an object may only be used once, as they are consumed by rules when applied. The method of applying a rule within a membrane is as follows:

  1. Assign symbols from a membrane’s content to the rule’s inputs
  2. If all inputs are satisfied, remove all assigned symbols from membrane
  3. Create output symbols and hold until all rule assignment, for all membranes, has taken place.
  4. Add output symbols to targeted membranes.
  5. Dissolve membranes as necessary

Outputs are not passed immediately into membranes because this would contravene the maximally parallel nature of rule application, instead they are distributed after all possible rules have been applied.

Non-deterministic application

The order of rule application is chosen at random. Rule application order can have a significant effect on which rules may be applied at any given time, and the outcome of a step of execution.

Consider a membrane containing only a single "a" symbol, and the two rules a → ab and a → aδ. As both rules rely on an “a” symbol being present, of which there is only one, the first step of computation will allow either the first or second rule to be applied, but not both. The two possible results of this step are very different:

  1. The membrane carries over to the next step of the computation with both an "a" symbol and a "b" symbol present, and again one of the two rules is randomly assigned to the "a" symbol.
  2. The membrane dissolves and a single "a" symbol is passed out to the containing membrane.

Maximally parallel application

This is a property of rule application whereby all possible rule assignments must take place during every step of the computation. In essence this means that the rule a → aa has the effect of doubling the number of "a" symbols in its containing membrane each step, because the rule is applied to every occurrence of an "a" symbol present.

As a computational model

Most P systems variants are computationally universal.[4] This extends even to include variants that do not use rule priorities, usually a fundamental aspect of P systems.[5]

As a model for computation, P systems offer the attractive possibility of solving NP-complete problems in less-than exponential time.[4] Some P system variants are known to be capable of solving the SAT (boolean satisfiability) problem in linear time[6] and, owing to all NP-complete problems being equivalent, this capability then applies to all such problems. As there is no current method of directly implementing a P system in its own right, their functionality is instead emulated[7] and therefore solving NP-complete problems in linear time remains theoretical. However, it has also been proven that any deterministic P system may be simulated on a Turing Machine in polynomial time.[2]

Example computation

The image shown depicts the initial state of a P system with three membranes. Because of their hierarchical nature, P systems are often depicted graphically with drawings that resemble Venn diagrams or David Harel's Higraph (see Statechart).

The outermost membrane, 1, is the container membrane for this P system and contains a single out rule. Membrane 2 contains four here rules, with two in a priority relationship: cc → c will always be applied in preference to c → δ. The delta symbol represents the special “dissolve” symbol. The innermost membrane, 3, contains a set of symbols (“ac”) and three rules, of type here. In this initial state no rules outside of membrane 3 are applicable: there are no symbols outside of that membrane. However, during evolution of the system, as objects are passed between membranes, the rules in other membranes will become active.

Computation

Because of the non-deterministic nature of P systems, there are many different paths of computation a single P system is capable of, leading to different results. The following is one possible path of computation for the P system depicted.

Step 1

From the initial configuration only membrane 3 has any object content: "ac"

Step 2

Membrane 3 now contains: "abcc"

Notice the maximally parallel behaviour of rule application leading to the same rule being applied twice during one step.

Notice also that the application of the second rule (a → bδ) as opposed to the first (a → ab) is non-deterministic and can be presumed random. The system could just as well have continued applying the first rule (and at the same time doubling the c particles) indefinitely.

Membrane 3 now dissolves, as the dissolve symbol (δ) has been encountered and all object content from this membrane passes into membrane 2.

Step 3

Membrane 2 now contains: “bbcccc”

Step 4

Membrane 2 now contains: "ddcc"

Step 5

Membrane 2 now contains: “dedec”

Notice that the priority over c → δ has been lifted now the required inputs for cc→ c no longer exist. Membrane 2 now dissolves, and all object content passes to membrane 1.

Step 6

Membrane 1 now contains: “deedee”

Computation halts

Membrane 1 now contains: "dd" and, due to the out rule e → eout, the environment contains: "eeee." At this point the computation halts as no further assignments of objects to rules is possible. The result of the computation is four "e" symbols.

The only non-deterministic choices occurred during steps 1 and 2, when choosing where to assign the solitary "a" symbol. Consider the case where "a" is assigned to a → bδ during step 1: upon membrane 3 dissolving only a single "b" and two "c" objects would exist, leading to the creation of only a single "e" object to eventually be passed out as the computation’s result.

See also

References

  1. ↑ Păun, Gheorghe (1998). Computing with Membranes. TUCS Report 208. Turku Centre for Computer Science. ISBN 978-952-12-0303-9. Retrieved 16 December 2012.
  2. ↑ 2.0 2.1 2.2 2.3 Păun, Gheorghe; Grzegorz Rozenberg (2002). "A guide to membrane computing". Theoretical Computer Science 287 (1): 73–100. doi:10.1016/S0304-3975(02)00136-6. ISSN 0304-3975.
  3. ↑ Ardelean, Ioan; Matteo Cavaliere (June 2003). "Modelling biological processes by using a probabilistic p system software". Natural Computing 2 (2): 173–197. doi:10.1023/A:1024943605864. ISSN 1567-7818.
  4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 Păun, Gheorghe (2006). "Introduction to Membrane Computing". Applications of Membrane Computing. Springer Berlin Heidelberg. pp. 1–42. ISBN 978-3-540-29937-0.
  5. ↑ Freund, Rudolf; Marion Oswald and Petr Sosík (2005). "Computationally universal P systems without priorities: two catalysts are sufficient". Theoretical Computer Science 330 (2): 251–266. doi:10.1016/j.tcs.2004.06.029. ISSN 0304-3975.
  6. ↑ Păun, Gheorghe (2001). "P systems with active membranes: attacking NP-complete problems". Automata, Languages and Combinatorics 6 (1): 75–90. Retrieved 2008-02-03.
  7. ↑ Zandron, Claudio; Claudio Ferretti and Giancarlo Mauri (2000). "Solving NP-Complete Problems Using P Systems with Active Membranes". Unconventional Models of Computation. pp. 289–301. ISBN 1-85233-415-0.

External links