P systems with symport-antiport
| Pierluigi Frisco (2011), Scholarpedia, 6(10):11704. | doi:10.4249/scholarpedia.11704 | revision #121467 [link to/cite this article] |
P systems with symport/antiport are one of the most studied models in membrane computing. Their simple and elegant way to operate has caught the interest of several researchers and many papers have been written on this model or inspired by the operations used by it.
In this article we describe the biological processes that inspired this abstract model of computation and we briefly summarise the known results. Due to the nature of Scholarpedia, what presented here is rather informal. Formal definitions and proofs can be found in the provided bibliography. The current state-of-the-art is a result of a few series of original results and improvements by A. Alhazov, I. Ardelean, F. Bernardini, M. Cavaliere, E. Csuhaj-Varju, R. Freund, P Frisco, M. Gheorghe, H.J. Hoogeboom, O.H. Ibarra, M. Ionescu, L. Kari, S.N. Krishna, M. Margenstern, C. Martin-Vide, M. Oswald, A. Paun, Gh. Paun, J. Pazos, A. Rodriguez-Paton, M.J. Perez-Jimenez, V. Rogojin, Yu. Rogozhin, G. Rozenberg, Gy. Vaszil, S. Verlan, S. Woodworth and others.
Contents |
Biological motivations
The abstract model of computation described in this article has been inspired by the protein-mediated transport present in living cells. In these cells one of the functions of the plasma membrane is to maintain the internal composition of the cell. This membrane forms a barrier that blocks the free exchange of most biological molecules between the cytoplasm and the environment.
Facilitated diffusion is performed by specific transport proteins, channel and carrier proteins, mediating the selective passage of molecules across the membrane.
Carrier proteins bind specific molecules to be transported and undergo conformational changes that allow the molecules to pass across the membrane. This transport is performed by (see Figure 1 ):
uniporters transport a single type of molecule;
symporters can transport two molecules in the same direction;
antiporters can transport two molecules in opposite directions.
Informal definitions
Theoretical devices in membrane computing, P systems with symport/antiport consist of a set of nested membranes defining compartments. The nesting present in P systems with symport/antiport is hierarchical and it defines a cell-tree: a compartment can be contained in at most one compartment and it can contain several compartments. Within each compartments there may be objects evolving and moving to neighbouring membranes following rules specified for the particular system.
Recent overviews Frisco P. (2009) and Păun Gh. et. al.(2010) are a good source for motivation and for a tutorial on the various categories of P systems.
In P systems with symport/antiport, as introduced in Păun A., Păun Gh. (2002), computation is restricted to the synchronous movement of objects from one compartment into another. This means that the system contains unstructured objects that are not rewritten or changed in any other way. A configuration of the system is given by a finite multiset for each of the compartments; each compartment contains a finite number of objects, whereas the objects initially present in the environment are assumed to have infinite (unbounded) supply. Rules associated to the compartments and inspired by the protein mediated transport described in the previous section, are of one of the following forms, where \(x\) and \(y\) are strings of objects (representing multisets in the obvious way)\[(x, in)\ ,\] multiset \(x\) moves into the compartment from the compartment (membrane or environment) surrounding it;
\((x, out)\ ,\) multiset \(x\) moves out from the compartment to the compartment surrounding it;
\((x, in; y, out)\ ,\) multiset \(x\) moves into the membrane from the compartment surrounding it, while at the same time multiset \(y\) moves into the other direction.
The first two forms \((x, in)\) and \((x, out)\) are called symport rules, the latter form \((x, in; y, out)\) is called antiport.
The weight of a rule is given by \(|x|\) for symport, and \(max\{|x|, |y|\}\) for antiport.
The degree of a system is the number of compartments it has while the weight of a system is a pair of numbers given by the maximum weights for the symport and antiport present in the system. If a system does not have any symport, then the maximum weight for symports is 0; similarly for antiports. If the symports in a system can have an unbounded weight (that is, they can move an unbounded number of objects), then the maximum weight for symports is denoted by *; similarly for antiports.
Computational steps consist of the application of a multiset of these rules, under the requirement (usual in membrane computing) of maximal parallelism: such a multiset cannot be carried out if there is the possibility of performing a step that involves a strictly larger multiset of rules.
A computation is successful if it starts in the initial configuration (specified as a multiset of objects for each membrane, and an infinite supply of objects in the environment) and if it ends in a halting configuration, i.e., a configuration where no rule is applicable. The result of a successful computation is the number of objects present in a designated membrane, the output membrane. By convention this membrane is elementary, i.e., it does not contain any membranes.
Example
Let us consider the P system with symport/antiport depicted in Figure 2.
This system consists of three compartments (plus the environment) each surrounded by a membrane numbered 1, 2 or 3..
The innermost compartment (number 3) does not contain any object and it contains only the rule \((AA, in)\ .\) This rule tells that pairs of \(A\)'s can pass from compartment 2 (external to compartment 3) to compartment 3.
Compartment 2 includes compartment 3, it contains only one occurrence of object \(C\) and it contains two rules\[(AA, in)\ ,\] telling that pairs of \(A\)'s can pass from compartment 1 (external to compartment 2) to compartment 2, and \((B, in; C, out)\) telling that the \(C\) present in compartment 2 can be exchanged for the \(B\) in compartment 1.
Compartment 1 includes compartment 2, it contains only one occurrences of object \(B\) and it contains two rules\[(B, out)\ ,\] telling that the object \(B\) can be moved to the environment, and \((AB, in)\) telling that pairs of \(A\) and \(B\) can pass from the environment to compartment 1.
The environment contains an unbounded number of \(A\)'s.
We remind the reader that the system works under the requirement of maximal parallelism: all applicable rules are applied (please, refer to Păun et. al.(2010) for a more precise definition of this operational mode).
What can this system do? At any moment when the \(B\) is present in compartment 1 the rule \((C, out; B, in)\) can be applied. In the following we will assume that this rule is not applied for a few transitions.
If the rule \((C, out; B, in)\) is not applied, then in the system in Figure 2, the rule \((B, out)\) can be applied. Every time \((B, out)\) is applied, then the application of \((AB, in)\) follows (remember that the environment contains an unbounded number of \(A\)'s, so the \(B\) can always go back to compartment 1 bring an \(A\) along).
After \((AB, in)\) is applied the first time, then compartment 1 contains one \(A\) and one \(B\ .\) The rule \((B, out)\) can be applied again (notice that the \(A\) in compartment 1 cannot be subject to any rule - rule \((AA, in)\) in compartment 2 asks for pairs of \(A\)'s, not single \(A\)'s) and this is followed again by the application of \((AB, in)\ .\)
Now compartment 1 contains two \(A\)'s and one \(B\ .\) The rule \((AA, in)\) in compartment 2 can now be applied and it is indeed applied moving the two \(A\)'s to compartment 2. At the same time rule \((B, out)\) can be applied again.
What do we have now? The \(B\) is in the environment, compartment 1 does not have any object, compartment 2 has one \(C\) and two \(A\)'s, compartment 3 does not have any object. The applied rules are\[(AA, in)\] in compartment 3 and \((AB, in)\) in compartment 1.
When this happens, then two \(A\)'s are in compartment 3, compartment 2 contains only the \(C\ ,\) compartment 1 contains one \(A\) and one \(B\ .\) Let us assume that the rule \((B, out)\) is again applied an it is then followed by the application of \((AB, in)\ .\)
Again compartment 1 has two \(A\)'s and one \(B\ .\) Let us assume that now the applied rules are both rules in compartment 2. This means that the \(C\) passes to compartment 1, while the \(B\) and the two \(A\)'s in compartment 1 pass to compartment 2.
The only rule that can be applied is \((AA, in)\) in compartment 3. When this happens the system halts with four \(A\)'s in compartment 3, one \(B\) in compartment 2, one \(C\) in compartment 1 and (of course) an infinite amount of \(A\)'s in the environment.
Here we just described one possible sequence of applied rules (computation) for the system in Figure 2, but in general, what does this system do? It should not be too difficult to understand that when this system halts (that is, when no rule can be applied), then:
compartment 3 contains an even number of \(A\)'s (zero included),
compartment 2 contains only one \(B\ ,\)
compartment 1 can contain either only one \(C\) or one \(C\) and one \(A\) (this last case takes place when an 'odd' \(A\)'s is moved to compartment 1 and then the rule \((C. out; B, in)\) is applied).
In the previous section we said that the result of a computation is the number of objects present in a designed membrane called output membrane and that this output membrane has to be elementary. As the only elementary membrane in the system in Figure 2 is membrane 3, and as in this system the compartment defined by this membrane can only collect an even number of \(A\)'s, then we can say that this system computes (generates) even numbers.
The P system with symport/antiport has degree 3 (because it has 3 compartments), the weight of this system is (2, 1), this is because the maximum weight for its symports is 2 and the maximum weight for its antiports is 1.
Short summary of known results
Researchers in P systems with symport/antiport were interested to answer, besides others, the following questions:
What is the class of numbers that can be generated by these systems?
How this classes of numbers change is one imposes restrictions on the systems? (as we will see, 'restrictions' can be to use only symports, or only antiports, or symports with a specific weight, or to allow only one symbol in the system, etc.)
This kind of research is part of formal language theory, a branch of theoretical computer science. Even if we will keep the current presentation informal, readers who are not familiar with formal language theory are advised to read Rozenberg and Salomaa (1996) if they want to make more sense of what follows.
We denote with\[N\]FIN the class of finite sets of numbers;
\(N\)REG the class of regular sets of numbers;
\(N\)RE the class of recursively enumerable sets of numbers.
Minimal degree and weight
This section summarises the known answers to the following question: Given a family of numbers \(X\ ,\) what is minimal number of compartments and what is the minimal weight a P system with symport/antiport needs to have in order to generate \(X\ ?\)
In the following table the column "min. number of objects" indicates the number of objects that are present in the output compartment for any computation. Readers interested in these details can refer to the given references on P systems.
| degree | max. weight symport | max. weight antiport | min. number of objects | class of numbers |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | \(\subseteq N\)FIN |
| 1 | 2 | 0 | 0 | \(\subseteq N\)FIN |
| 1 | 1 | 2 | 0 | \(= N\)RE |
| 1 | 0 | 2 | 1 | \(= N\)RE |
| 1 | 3 | 0 | 7 | \(= N\)RE |
| 2 | 1 | 1 | 1 | \(= N\)RE |
| 2 | 2 | 0 | 1 | \(= N\)RE |
Small number of symbols
This section summarises the known answers to the following question: Given a family of numbers \(X\ ,\) what is minimal number of compartments and what is the minimal weight a P system with symport/antiport using only a limited number of object needs to have in order to generate \(X\ ?\)
It is important to notice the restriction to the number of object, this restriction was not present in the results summarised in the previous section.
In the following table the column "min. number of object" is absent as this number is 0 for each entry. Readers interested in these details can refer to the given references on P systems (with the exception of the result in the last row which can only be found in Frisco P. (2010).)
| number of objects | degree | max. weight symport | max. weight antiport | class of numbers |
|---|---|---|---|---|
| 1 | 1 | * | * | \(= N\)FIN |
| 1 | 2 | * | * | \(\supseteq N\)REG |
| 2 | 1 | * | * | \(\supseteq N\)REG |
| 1 | 4 | * | * | \(\supseteq N\)REG |
| 5 | 1 | * | * | \(= N\)RE |
| 4 | 2 | * | * | \(= N\)RE |
| 3 | 3 | * | * | \(= N\)RE |
| 2 | 4 | * | * | \(= N\)RE |
| 1 | 7 | * | * | \(= N\)RE |
Different variants
Many models (variants) of P systems with symport/antiport exists. Researchers slightly changed the origins definition of these systems and then they investigated how the changes in the definition effected the computational power of the resulting model.
Here we summarise the main variants of these interesting systems. More comprehensive descriptions can be found in Frisco P. (2009) and Păun Gh. et. al.(2010).
Following the traces
The output of the system is not given by the number of objects present in the output compartment when the system ends its computation, but it is given by the trace of a distinguished object called 'traveler.
In this variant the output of a system is a string given by the sequence of labels associated to the compartments visited by the traveler. So, for instance, in such a system the traveler visits first compartment 1, then compartment 2, then compartment 1 again and then the systems halts, then the output of the system is "121".
Accepting systems
In this variant the systems do not generate sets of numbers, they accepts sets of numbers. The output compartment does no longer exist but there is an input compartment which initially contains a certain set of objects.
If starting with a specific sets of objects \(X\)the P system halts, then it is said that that P system accepts \(X\ .\)
Symport/antiport of rules
Imagine a P system with symport/antiport in which the rules can move. This means that there are two kinds of rules: rules of type A operating on objects and being multiset rewriting rules (that is, something of the kind \(\alpha \rightarrow \beta\ ,\) where \(\alpha\) and \(\beta\) are multisets of objects) and rules of type B operating on rules of type A and being either symports or antiports.
This means that the objects present in the system do not move from one compartment to another (as in P systems with symport/antiport), but that are transformed into other objects. The rule of type A can move from one compartment to another.
Tissue P systems
In this section we consider membrane systems with symport/antiport having a cell-graph as underlying structure. To fully understand the motivations behind the research presented in the following we have to recall a few aspects in the history of membrane computing.
This field of research originated by observations of the functioning of single cells, for this reason the first models had a cell-tree as underlying structure. The study of cell-graphs as underlying structures arrived later in the field. The models of membrane systems considering cell-graphs were either inspired by biological processes or they simply originated by mathematical abstractions.
Tissue P systems are among the models having a cell-graph as underlying structure inspired by biological reality. Under this name a broad range of models have been studied, some of these inspired by neural interaction others, as the ones presented in the following, inspired by cell-cell communication.
Biological motivations
Cells can be connected to each other to form tissues. Our skin, guts and muscles are examples of tissues.
Gap junctions allow small chemicals to pass directly from the cytoplasm of one cell to the one of another (see Figure 3)). This passage is performed by transmembrane proteins, called channel-forming proteins, present on the plasma membrane. When two of these proteins present on the plasma membrane of two cells are aligned, then a channel is established.
Informal definitions
Tissue P systems were introduced in Martin-Vide C. et. al. (2003) and, they can be considered as a generalisation of P systems with symport/antiport. Also here objects are simply moved from one compartment to another by the symport and antiport rules associated to the connections (edges) between cells. So, if one considers Figure 3, one can imagine that each gap junction has either a symport or an antiport associated with it.
The definitions of degree', weight, computation and acceptance are similar to the ones given for P systems with symport/antiport. The only difference is that the output compartment is not required to be elementary.
Short summary of known results
The questions addressed by researches in tissue P systems have been:
Given a family of numbers \(X\ ,\) what is minimal number of compartments and what is the minimal weight a P system with symport/antiport needs to have in order to generate \(X\ ?\)
and
Given a family of numbers \(X\ ,\) what is minimal number of compartments and what is the minimal weight a P system with symport/antiport using only a limited number of object needs to have in order to generate \(X\ ?\)
It is important to notice the restriction to the number of object in this second question.
The results summarised in the first five rows of the next table follow directly from results in P systems with symport/antiport. The results summarised in the remaining rows are original to tissue P systems.
Readers interested in the details of the results in the next table can refer to the given references on P systems.
| number of objects | degree | max. weight symport | max. weight antiport | class of numbers |
|---|---|---|---|---|
| 1 | 1 | 1 | \(\subseteq N\)FIN | |
| 1 | 2 | 0 | \(\subseteq N\)FIN | |
| 1 | 1 | * | * | \(= N\)FIN |
| 1 | 2 | * | * | \(\supseteq N\)REG |
| 1 | 4 | * | * | \(\supseteq N\)REG |
| 1 | 7 | * | * | \(= N\)RE |
| 2 | 3 | * | * | \(= N\)RE |
| 4 | 2 | * | * | \(= N\)RE |
| 2 | 1 | * | * | \(= N\)REG |
| 2 | 1 | 1 | \(= N\)RE | |
| 2 | 2 | 0 | \(= N\)RE |
References
- Frisco, P. (2010). P systems and unique-sum sets. CMC11 LNCS 6501: 208-225.
- Martin-Vide, C.; Păun, Gh.; Pazos, J. and Rodriguez-Paton, A. (2003). Tissue P systems. Theoretical Computer Science 296: 295-326.
- Păun(2002). The power of communication: P systems with symport/antiport. New Generation Computing 20(3): 295-306.
- Frisco, P. (2009). Computing with Cells. Advances in Membrane Computing. Oxford University Press, Oxford.
- Păun, Gh.; Rozenberg, G. and Salomaa, A. (2010). The Oxford Handbook of Membrane Computing. (Chapter 5) Oxford University Press, Oxford.
- Rozenberg, G. and Salomaa, A (1996). Handbook of Formal Languages. Springer-Verlag, Heidelberg.
Surveys and Related Papers
The most up-to-date source of information for P systems (membrane computing) is the P systems webpage.
