P system

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'.

Each element has a specific role to play, and each has a founding in the biological cell architecture upon which P systems are based.

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 are the main “structures” within a P system.

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) that must be present in order for it to be applied.

There are three (in the basic P system model) distinct ways in which a rule may handle its output objects.

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.

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.

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.

[6] As a model for computation, P systems offer the attractive possibility of solving NP-complete problems in less-than exponential time.

As there is no current method of directly implementing a P system in its own right, their functionality is instead emulated[8] and therefore solving NP-complete problems in linear time remains theoretical.

Because of their hierarchical nature, P systems are often depicted graphically with drawings that resemble Venn diagrams or David Harel's Higraph (see Statechart).

Membrane 2 contains four here rules, with two in a priority relationship: cc → c will always be applied in preference to c → δ.

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.