# Catalytic P systems

Petr Sosik (2010), Scholarpedia, 5(1):9336. | doi:10.4249/scholarpedia.9336 | revision #137058 [link to/cite this article] |

**Catalytic P systems** (CP systems, for short) represent a branch of membrane computing, i.e., abstract computing models based mostly on operations with multisets. They are freely inspired by the structure of (eukaryotic) cells and by the regulatory role of their membranes delimiting various compartments. CP systems primarily characterize the computational potential of certain abstract operations inspired by those in living cells and thus can help to understand information processes in the nature. They could also possibly serve for cellular modeling and synthetic biology purposes (including biocomputers). The most comprehensive recent monograph is The Oxford Handbook of Membrane Computing, for up-to-date information please visit the P Systems Webpage.

## Contents |

## Description and function

A CP system is formed by a hierarchical *membrane structure* with uniquely labeled membranes. The
whole structure is embedded in a single *skin membrane*, see
the figure bellow. Each membrane contains a multiset of primitive abstract
*objects*. The objects are members of a finite alphabet \(O\)
which is divided into two parts: the set of *catalysts* \(C,\)
and the set \(O\setminus C\) of *non-catalytic* objects. Each
membrane has assigned an initial multiset of objects and a fixed set
of *evolution rules* of two possible types: (1) \(ca \rightarrow cv\)
(*catalytic rules*), (2) \(a \rightarrow v\) (*non-cooperative rules*), where \(c\) is a catalyst, \(a\) is a non-catalyst, and \(v\) is
a (possibly empty) multiset of non-catalysts. The rule transforms the
object \(a\) into the multiset of objects \(v\) in one step. In the case
of catalytic rules also the catalyst \(c\) participates in the rule application but it passes intact. A CP system
is called *purely catalytic* if it contains only catalytic
rules.

Furthermore, each object resulting from an application of a rule
(i.e., an element of the multiset \(v\)) can be transported through a
membrane. It has assigned a target
*here*, *out* or *in*\(_j\) denoting its target
membrane after the rule application (\(j\) is a label of an inner
membrane). The target *here* is usually omitted.

The whole system evolves in discrete computational steps. Each
object can evolve due to at most one rule at a given step. The rules
are usually applied in the *maximally parallel mode* (click here for other modes): at each
computational step and in each membrane, the selected multiset of
applicable rules must be maximal, i.e., unused objects do not
allow for an application of another rule. For example, let a
membrane contain non-catalysts \(a,b\) and a catalyst \(c.\) Let there
be rules \(ca \rightarrow cu,\) \(cb \rightarrow cv\) and \(a \rightarrow w.\) Then the selected
multiset of rules can contain either (i) only the rule \(ca \rightarrow cu\)
or (ii) both rules \(cb \rightarrow cv\) and \(a \rightarrow w.\)

The computation continues until no rule can be applied in any of the membranes and the system halts (or it can compute ad infinitum).

## Generation of number sets and languages

Consider a CP system starting its computation from an *initial configuration* where each membrane contains a pre-defined initial multiset of objects. After a sequence of parallel steps, the system eventually
halts. The final number of objects present in a specific
*output membrane* is the *result* of the computation.
Sometimes we take instead the *Parikh vector* of the
multiset of objects present in the output membrane (i.e., a numerical vector whose components equal the multiplicity of individual objects in the multiset). Hence, the
result is a non-negative integer or a vector of integers.
As a CP system is generally non-deterministic, it can perform
various computations with different results. The collection of all
these results forms a set of numbers (or vectors) *generated*
by the system.

Consider the CP system depicted on the right-hand side, working with alphabet \(O=\{a,b,c,d,e\}\ ,\) where \(c\) is a catalyst and the remaining objects are non-catalysts. Objects \(a,b,c\) are initially present in membrane 1. At most one of the two catalytic rules can be used at each computational step. Hence, due to the maximal parallelism, the rule \(a\rightarrow\lambda\) or \(b\rightarrow\lambda\) (or both) must be also used in the first step. (Note that \(\lambda\) represents the empty multiset.) Then an arbitrary number of steps using the same catalytic rule can follow until a \(\lambda\)-rule is used second time and the system halts. Each application of a catalytic rule transports the multiset \(\{d,e\}\) (or \(\{d,e,e\}\ ,\) respectively) into membrane 2. Let membrane 2 be the output membrane. The system generates the set \(\{2n\, |\, n\ge 0\}\cup \{3n\, |\, n\ge 0\}.\) If Parikh vectors were considered instead, the generated set would be \(\{(0,0,0,n,n)\, |\, n\ge 0\}\cup \{(0,0,0,n,2n)\, |\, n\ge 0\}.\)

CP systems with a single membrane and only two catalysts wield the power of a universal computer, i.e., they can generate all the computably enumerable sets of (vectors of) natural numbers (Freund et al., 2005). Three catalysts are needed in the case of purely catalytic systems. These CP systems can also compute any Turing-computable function over (vectors of) natural numbers. The CP systems with a single catalyst are not completely investigated yet but in several cases which have been studied yet, only regular sets can be generated (Ibarra et al., 2004).

If non-catalytic objects are interpreted as symbols of the
alphabet \(O\setminus C\ ,\) CP systems can also be used to
*generate formal languages*. At each step, a multiset of symbols can
be sent out through the skin membrane. We take all possible strings
obtained by permutations of elements of this multiset as the result
of this particular step. By concatenating the results of all steps
of a halting computation, we obtain a set of strings generated
during this computation. Similarly as above, the union of results of
all possible halting computations of a CP system gives the set of strings
(i.e., a formal language) it generates. CP systems with
the parameters specified in the previous paragraph can generate all
recursively enumerable languages.

## Accepting catalytic P systems

A CP system can also act as an accepting device (or automaton):
an input (a non-negative integer or a vector
of integers) can be represented as the Parikh vector of a multiset of
designated objects. This multiset is inserted into a specific input membrane at
the beginning of computation. The input is *accepted* by a given CP system if
there exists a halting computation with this input. Freund et al. (2005) showed that any
computably enumerable set of natural numbers can be accepted by a CP system
with a single membrane and two catalysts (or three catalysts for purely
catalytic systems). CP systems can also accept all the computably enumerable
sets of vectors of natural numbers. The minimal number of catalysts needed in
this case equals the dimension of the input vector plus a constant.

The situation is different when we consider *deterministic* CP
systems (DCP systems), i.e., having exactly one computation for any
given input. The computational power of DCP systems has to be
investigated yet but it is known that any DCP system can accept only
a semilinear set of (vectors of) natural numbers and its
halting problem is decidable in polynomial time
(Ibarra and Yen, 2006).

To regain the universal computing power (i.e., that of the Turing machine), two extensions of DCP systems have been considered. Paun (2000) introduces priorities among rules, i.e., a strict partial order. If two or more rules compete for object(s), the rule with the highest priority is chosen. DCP systems with priorities among rules can accept all computably enumerable sets. Further variants of priorities (strongly prioritized or statically prioritized DCP systems) have been also considered by Ibarra and Yen (2006).

An interesting extension is the concept of \(k\)-*determinism* introduced in
(Oswald, 2003): a \(k\)-deterministic CP system behaves deterministically
provided that it can, at each step, scan all the branches of its computational
tree \(k\) steps ahead. It was shown that 4-deterministic CP systems can accept
all computably enumerable set of (vectors of) natural numbers.

## Further variants

**Bistable catalysts**

A bistable catalyst has two forms and switches reversibly from one to another. Its rules are of the form \(ca \rightarrow c'v\) and \(c'b \rightarrow cu,\) where \(c,c'\) are two forms of a catalyst, \(a, b\) are non-catalysts and \(u, v\) are multisets of non-catalysts. Bistable catalysts are more powerful than the basic ones: one bistable catalysts grants to a CP system the power of universal computer (Alhazov, 2006).

**Mobile catalysts**

This variant of CP systems allows catalysts to migrate between membranes in the same manner as non-catalysts. Also this variant is more powerful than standard catalysts – one catalyst is enough to obtain the universal computing power provided that we use at least three membranes (Krishna and Paun, 2004).

**Sequential and asynchronous mode**

Various derivation modes, as well as variants of halting, were systematically described first by Freund and Verlan (2007). In the sequential mode, at each computational step only one randomly chosen rule is applied out of all applicable rules in the whole system. In the asynchronous mode, a randomly chosen multiset of applicable rules is used. CP systems can only generate semilinear sets in both these modes (Freund et al., 2009), pointing out the importance of synchronization. The P system described in the example above would generate the set of all natural numbers except 1 if it worked in the sequential or asynchronous (or minimally parallel) mode.

**Minimally parallel mode**

Similarly as in the asynchronous mode, a randomly chosen multiset of applicable rules is used in each step. However, for each membrane and each step the following condition must hold: if there are applicable rules in the membrane, then at least one of them must be used. These CP systems are computationally universal with least two membranes and an unlimited number of bistable catalysts (Freund et al., 2009). It is not known whether an analogous result can be achieved with standard catalysts. Further refined variants have been also studied, as the \(k\)-restricted minimal parallelism (Freund and Verlan, 2008) where the set of all rules \(R\) is partitioned into disjoint subsets and at most \(k\) rules is used from each subset.

**Variants of halting**

Consider again a partitioning of \(R\) into disjoint subsets. The *partial halting* condition states that during each derivation step, exactly one rule
from each subset must be applied, otherwise the system halts. Interestingly
enough, in the asynchronous and minimally parallel modes with partial halting,
CP systems can generate only Parikh images of matrix languages. Other
conditions of halting have been considered, as the appearance of certain
objects in a certain membrane or a repeated cycle of configurations.
Eventually, one can ignore halting at all and consider the set of all contents
of the output membrane at all steps as the result of computation. More details of these and further variants can be found in (Freund et al., 2009).

## References

- Alhazov, A (2006). Number of protons/bi-stable catalysts and membranes in P systems. Time-freeness. Membrane Computing, 6th Intern. Workshop WMC 2005, LNCS 3850, Freund et al. editors. Springer, Berlin. 79-95.

- Freund, R; Ibarra, O H; Paun, A; Sosík, P and Yen, H-C (2009). Catalytic P systems. The Oxford Handbook of Membrane Computing, Paun et al. editors. Oxford University Press, Oxford. Chapter 4.

- Freund, R; Kari, L; Oswald, M and Sosík, P (2005). Computationally universal P systems without priorities: two catalysts are sufficient.
*Theoretical Computer Science*330: 251–266. doi:10.1016/j.tcs.2004.06.029.

- Freund, R and Verlan, S (2007). A formal framework for P systems. Pre-proc. Membrane Computing, Intern. Workshop WMC8, Eleftherakis et al. editors. SEERC, Thessaloniki. 317-330.

- Freund, R and Verlan, S (2008). (Tissue) P systems working in the k-restricted minimally parallel derivation mode. Proceedings of the International Workshop on Computing with Biomolecules, Csuhaj-Varjú et al. editors. Osterreichische Computer Gesellschaft, Vienna. 43–52.

- Krishna(2004). Results on catalytic and evolution-communication P systems.
*New Generation Computing*22: 377-394. doi:10.1007/bf03037288.

- Ibarra, O; Dang, Z and Egecioglu, O (2004). Catalytic P systems, semilinear sets, and vector addition systems.
*Theoretical Computer Science*312: 379–399. doi:10.1016/j.tcs.2003.10.028.

- Ibarra(2006). Deterministic catalytic systems are not universal.
*Theoretical Computer Science*363: 149–161. doi:10.1016/j.tcs.2006.07.029.

- Oswald, M (2003). P Automata. PhD thesis. Faculty of Computer Science, Vienna University of Technology.

- Paun, G (2000). Computing with Membranes
*Journal of Computer and System Sciences*61(1): 108–143. doi:10.1006/jcss.1999.1693.

**Internal references**

- Gheorghe Paun (2010) Membrane Computing. Scholarpedia, 5(1):9259.

- Paul M.B. Vitanyi (2009) Turing machine. Scholarpedia, 4(3):6240.

## Further reading

- Calude, C and Paun, G (2000). Computing with Cells and Atoms. CRC Press, London. ISBN 0-748-40899-1.

- Frisco, P (2009). Computing with Cells. Advances in Membrane Computing. Oxford University Press, Oxford. ISBN 0-199-54286-4.

- Paun, G (2002). Membrane Computing. An Introduction. Springer-Verlag, Berlin. ISBN 3-540-43601-4.

- Paun, G; Rozenberg, G and Salomaa, A (2009). The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford. ISBN 0-199-55667-9.