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.
