International Journal of Computers, Communications & Control
Vol. I (2006), No. 1, pp. 25-32

One More Universality Result for P Systems with Objects on Membranes

Gheorghe Păun

Abstract: We continue here the attempt to bridge brane calculi with membrane computing,
following the investigation started in [2]. Specifically, we consider P systems with objects
placed on membranes, and processed by membrane operations. The operations used in this
paper are membrane creation (cre), and membrane dissolution (dis), defined in a way which
reminds the operations pino, exo from a brane calculus from [1]. For P systems based on these
operations we prove the universality, for one of the two possible variants of the operations;
for the other variant the problem remains open.
Keywords: Membrane computing, Brane calculi, Matrix grammar, Universality

1 Introduction

This paper is a direct continuation of [2], where a first step was made to bridge membrane computing [4],
[5], [6] and brane calculi [1]. The main point of this effort is to define P systems which work with multisets
of objects placed on the membranes rather than inside the compartments defined by membranes, and to process
these multisets by means of operations with membranes rather than by multiset rewriting rules acting only on
objects. The operations pino, exo, mate, drip were formalized in [2] as membrane computing rules, and used
in defining P systems based on them. The universality of mate, drip operations was proved in [2] (for systems
using simultaneously at any step of a computation at most eleven membranes). We give here an universality result
for other two operations, membrane creation (cre), and membrane dissolution (dis), which have the same syntax
as pino, exo operations, but a different interpretation in what concerns the contents of the handled membranes –
details can be found in Section 3 below. Actually, as it was the case in [2] with pino, exo, we have two variants of
each of the operations cre, dis. For one of these variants, we prove the Turing completeness, while the case of the
other variant remains open (we believe that a similar result holds true).

2 Prerequisites

All notions of formal language theory we use are elementary and standard, and can be found in any basic
monograph of formal language theory. For the sake of completeness, we introduce below only the notion of matrix
grammars with appearance checking – after specifying that by RE we denote the family of recursively enumerable
languages, and by PsRE the family of Parikh images of languages from RE (the Parikh mapping associated with
an alphabet V is denoted by ΨV ).

A matrix grammars with appearance checking [3] is a construct G = (N, T, S, M, F), where N, T are disjoint
alphabets (of non-terminals and terminals, respectively), S ∈ N (axiom), M is a finite set of matrices, that is
sequences of the form (A1 → x1, . . . , An → xn), n ≥ 1, of context-free rules over N ∪T , and F is a set of occurrences
of rules in the matrices of M.

For w, z ∈ (N ∪ T )∗ we write w =⇒ z if there is a matrix (A1 → x1, . . . , An → xn) in M and the strings wi ∈
(N ∪T )∗, 1 ≤ i ≤ n + 1, such that w = w1, z = wn+1, and, for all 1 ≤ i ≤ n, either (1) wi = w′iAiw′′i , wi+1 = w′ixiw′′i ,
for some w′i, w

′′
i ∈ (N ∪ T )∗, or (2) wi = wi+1, Ai does not appear in wi, and the rule Ai → xi appears in F . (If

applicable, the rules from F should be applied, but if they cannot be applied, then we may skip them. That is why
the rules from F are said to be applied in the appearance checking mode.) If F = /0, then the grammar is said to be
without appearance checking.

The language generated by G is defined by L(G) = {w ∈ T ∗ | S =⇒∗ w}, where =⇒∗ is the reflexive and
transitive closure of the relation =⇒.

The family of languages of this form is denoted by MATac; it is known that MATac = RE.
We say that a matrix grammar with appearance checking G = (N, T, S, M, F) is in the Z-binary normal form if

N = N1 ∪ N2 ∪{S, Z, #}, with these three sets mutually disjoint, and the matrices in M are in one of the following
forms:

1. (S → X A), with X ∈ N1, A ∈ N2,
2. (X → Y, A → w), with X ,Y ∈ N1, A ∈ N2, w ∈ (N2 ∪T )∗,|w| ≤ 2,

Copyright c© 2006 by CCC Publications



26 Gheorghe Păun

3. (X → Y, A → #), with X ∈ N1,Y ∈ N1 ∪{Z}, A ∈ N2,

4. (Z → λ ).

Moreover, there is only one matrix of type 1, F consists exactly of all rules A → # appearing in matrices of type 3,
and, if a sentential form generated by G contains the symbol Z, then it is of the form Zw, for some w ∈ (T ∪{#})∗
(that is, the appearance of Z makes sure that, except for Z, all symbols are either terminal or the trap-symbol #).
The matrix of type 4 is used only once, in the last step of a derivation.

For each language L ∈ RE there is a matrix grammar with appearance checking G in the Z-binary normal form
such that L = L(G).

As usual, we represent multisets over an alphabet V by strings over V , with the obvious observation that all
permutations of a string represent the same multiset.

3 P Systems Using the Cre/Dis Operations

We start by recalling from [2] the formalization of the operations pino, exo in terms of membrane computing.
A membrane is represented, as usual, by a pair of square brackets, [ ], but we associate here with membranes

multisets of object (corresponding to the proteins embedded in the real membranes). A membrane having asso-
ciated a multiset u (represented by a string) is written in the form [ ] u; we also use to say that the membrane is
marked with the multiset u.

The following four operations were defined in [2]:

pinoi : [ ] uav → [ [ ] ux] v, (1)
exoi : [ [ ] ua] v → [ ] uxv, (2)

pinoe : [ ] uav → [ [ ] v] ux, (3)
exoe : [ [ ] u] av → [ ] uxv. (4)

in all cases with a ∈ V , u, x ∈ V ∗, v ∈ V +, with ux ∈ V + for pino rules, where V is a given alphabet of objects.
In each case, multisets of proteins are transferred from input membranes to output membranes as indicated

in the rules, with protein a evolved into the multisets x (which can be empty). The subscripts i and e stand for
“internal" and “external", respectively, pointing to the “main" membrane of the operation in each case.

It is important to note that the multisets u, v and the protein a marking the left hand membranes of these rules
correspond to the multisets u, v, x from the right hand side of the rules; specifically, the multiset uxv resulting when
applying the rule is precisely split into ux and v, with these two multisets assigned to the two new membranes.

The rules are applied as follows. Assume that we have a membrane [ ] zuav, for a ∈ V, u, v, z ∈ V ∗. By a pinoi
rule as in (1), we obtain any one of the pairs of membranes [ [ ] z1ux ] z2v such that z = z1z2, z1, z2 ∈ V

∗, and by a
pinoe rule as in (3), we obtain any one of the pairs of membranes [ [ ] z1v ] z2ux such that z = z1z2, z1, z2 ∈ V

∗.
In the case of the two exo operations, the result is uniquely determined. From a pair of membranes [ [ ] z1ua] z2v,

by an exoi rule as in (2) we obtain the membrane [ ] z1z2uxv, and from [ [ ] z1u] z2av, by an exoe rule as in (4) we
obtain the same membrane [ ] z1z2uxv.

The contents of membranes involved in these operations is transferred from the input membranes to the out-
put membranes in the same way as in brane calculi (P,Q represent here the possible contents of the respective
membranes):

pinoi : [ P ] uav → [ [ ] ux P ] v,
exoi : [ [ P ] ua Q ] v → P [ Q ] uxv,

pinoe : [ P ] uav → [ [ ] v P ] ux,
exoe : [ [ P ] u Q ] av → P [ Q ] uxv.

Here we change the interpretation of these rules, as suggested below (because the new semantics do not cor-
respond to the operations pino, exo, we change the name of operations to cre, dis, for “membrane creation" and



One More Universality Result for P Systems with Objects on Membranes 27

“membrane dissolution"):

crei : [ P ] uav → [ [ P ] ux ] v,
disi : [ [ P ] ua Q ] v → [ P Q ] uxv,
cree : [ P ] uav → [ [ P ] v ] ux,
dise : [ [ P ] u Q ] av → [ P Q ] uxv.

That is, when a membrane is created inside an existing membrane, the new membrane contains all previously
existing membranes, and while dissolving a membrane, its contents remains inside the membrane where it was
placed before the operation. The interpretation of the latter operation is rather similar to the usual dissolution
operation in membrane computing, while the membrane creation is understood as doubling the existing membrane,
with a distribution of the multiset marking the initial membrane to the two new membranes.

Using rules as defined above, we can define a P system as

Π = (A, µ, u1, . . . , um, R),

where:

1. A is an alphabet (finite, non-empty) of objects;

2. µ is a membrane structure with m ≥ 2 membranes;

3. u1, . . . , um are multisets of objects (represented by strings over A) bound to the m membranes of µ at the
beginning of the computation; the skin membrane is marked with u1 = λ ;

4. R is a finite set of cre, dis rules, of the forms specified above, with the objects from the set A.

For a rule of any type, with u, a, v as above, |uav| is called the weight of the rule.
In what follows, the skin membrane plays no role in the computation, no rule can be applied to it. Also, we

stress the fact that there is no object in the compartments of µ ; a membrane can contain other membranes inside,
but in-between membranes there is nothing.

When using any rule of any type, we say that the membranes from its left hand side are involved in the rule;
they all are “consumed", and the membranes from the right hand side of the rule are produced instead. Similarly,
the object a specified in the left hand side of rules is “consumed", and it is replaced by the multiset x.

The evolution of the system is defined in the standard way used in membrane computing, with the rules applied
in the non-deterministic maximally parallel manner, with each membrane involved in at most one rule. Thus,
the parallelism is maximal at the level of membranes – each membrane which can evolve has to do it – but each
multiset of objects evolves in a sequential manner, as only one rule can act on any multiset in a transition step.
More precise details can be found in [2]. A computation which starts from the initial configuration is successful
if (i) it halts, that is, it reaches a configuration where no rule can be applied, and (ii) in the halting configuration
there are only two membranes, the skin (marked with λ ) and an inner one. The result of a successful computation
is the vector of multiplicities of objects which mark the inner membrane in the halting configuration. The set of all
vectors computed in this way by Π is denoted by Ps(Π).

The family of all sets of vectors Ps(Π) computed by P systems Π using at any moment during a computation
at most m membranes, and crei, disi rules of weight at most p, q, respectively, is denoted by PsOPm(crep, disq).
When one of the parameters m, p, q is not bounded we replace it with ∗.

We end this section by pointing out some relations which follow directly from the definitions (and from Turing-
Church thesis).

Lemma 1. (i) PsOPm(crep, disq) ⊆ PsOPm′(crep′, disq′), for all m ≤ m′, p ≤ p′, q ≤ q′.
(ii) PsOP∗(cre∗, dis∗) ⊆ PsRE.

We also recall the main result from [2]: PsOP11(mate5, drip5) = PsRE (the notation is self-explanatory).



28 Gheorghe Păun

4 Universality for the Cre/Dis Operations

In the case of cre, dis operations as defined above, we cannot generate vectors of norm 0 or 1: in each rule
[ ] uav → [ [ ] ux] v, [ [ ] ua] v → [ ] uxv (necessary in the last step of any computation in order to get only one internal
membrane) we have imposed to have |uxv| ≥ 2. That is why the universality below is obtained modulo vectors of
the form (0, . . . , 0) and (0, . . . , 0, 1, 0, . . . , 0). We denote by Ps′RE and Ps′OPm(crep, disq) the sets of vectors from
PsRE and PsOPm(crep, disq) having the sum of elements greater than or equal to 2.

Theorem 2. Ps′RE = Ps′OPm(crep, disq) for all m ≥ 7, p ≥ 4, and q ≥ 4.
Proof. Let us consider a language L ∈ RE = MATac, L ⊆ V 2V ∗, for an alphabet V with n symbols. We write this
language in the form

L =
⋃

a,b∈V
{ab}∂ lab(L).

Let Gab = (Nab,V, Sab, Mab, Fab) be a matrix grammar with appearance checking such that L(Gab) = ∂ lab(L), for
a, b ∈ V . We consider these grammars Gab in the Z-normal form, with the notations from Section 2 (hence Nab =
Nab,1 ∪Nab,2 ∪{Sab, Zab, #}), and we construct the matrix grammar G = (N,V, S, M, F) with

N = N1 ∪N2 ∪{Zab | a, b ∈ V}∪{S, #},
N1 =

⋃

a,b∈V
Nab,1,

N2 =
⋃

a,b∈V
Nab,2,

M = {(S → X A) | for (Sab → X A) ∈ Mab, a, b ∈ V}
∪ {(X → Y, A → w) | for (X → Y, A → w) ∈ Mab, a, b ∈ V}
∪ {(Zab → ab) | for (Z → λ ) ∈ Mab, a, b ∈ V}.

Obviously, L(G) = L.
We assume that all two-rules matrices from M are injectively labeled, in the form ml : (X → Y, A → x), l ∈ Lab,

for a set of labels Lab.
Starting from the grammar G we now construct a P system

Π = (A, [ [ ] ], λ , S1S2, R),

with the alphabet

A = {Y,Y ′,Y ′′,Y ′′′,Y iv,Y v,Y vi,Y vii,Y viii,Y ix,Y x | Y ∈ N1}
∪ {α, α′, α′′ | α ∈ N2 ∪V}
∪ {Ā | A ∈ N2}
∪ {Zab, Z′ab, Z′′ab, Z′′′ab | a, b ∈ V}
∪ {E, H, H′, S1, S2, S3, c1, . . . , c11, c0, c′0, c′′0 , c′3, c′′3 , d1, d2, d′1, d′2, f ′, f ′′, #},

and the rules from the set R as constructed below.
Any computation starts from the configuration [ [ ] S1S2 ] λ , by using the following rules:

Step 1 : [ ] S1S2 → [ [ ] X ] S2 ,
Step 2 : [ [ ] X ] S2 → [ ] X c0d1S2 ,
Step 3 : [ ] X S2c0d1 → [ [ ] X S3 ] c0d1 ,
Step 4 : [ ] S3X → [ [ ] EĀ ] X , [ ] c0d1 → [ [ ] c′0 ] d1 ,
Step 5 : [ [ ] EĀ ] X → [ ] EĀX , [ [ ] c′0 ] d1 → [ ] c′′0 d1 ,
Step 6 : [ ] X ĀE → [ [ ] X A ] E , [ ] c′′0 d1 → [ [ ] c1 ] d1 ,

for each matrix (Sab → X A) ∈ Mab, for a, b ∈ V .



One More Universality Result for P Systems with Objects on Membranes 29

The rules are used as indicated in the table above, with two rules simultaneously applied in steps 4, 5, 6. The
only possible branching is in step 3, when instead of the rule [ ] X S2c0d1 → [ [ ] X S3 ] c0d1 , we can also use the rule
[ ] c0d1 → [ [ ] c′0 ] d1 . In this way we obtain the membranes [ [ ] c′0 ] d1 , with X S2 distributed among them. Because
S3 will be never introduced, we continue only with rules which process membranes marked with ci and d1, namely,
the rules from the third column of Table 1; in this way, the computation will never stop, both because we can return
again and again to a pair of membranes of the form [ [ ] c1 ] d1 , and because pairs of membranes marked with c

′
3

will appear and introduce trap objects/membranes – see also below.
The evolution of the membrane structure is indicated in Figure 1.

Initial [ [ ] S1S2 ] λ
Step 1 [ [ [ ] X ] S2 ] λ
Step 2 [ [ ] X c0d1S2 ] λ
Step 3 [ [ [ ] X S3 ] c0d1 ] λ
Step 4 [ [ [ [ [ ] EĀ ] X ] c′0

] d1 ] λ
Step 5 [ [ [ ] EĀX ] c′′0 d1

] λ
Step 6 [ [ [ [ [ ] X A ] E ] c1 ] d1 ] λ

Figure 1: The evolution of membranes at the beginning of computations.

Thus, we end with a configuration of the form [ [ [ [ [ ] X A ] E ] c1 ] d1 ] λ .
The rules for simulating the two-rules matrices from M are indicated in Table 1; by w′ we denote here the string

obtained from w by priming one symbol; if w = λ , then w′ = f ′, hence α′ = f ′, α′′ = f ′′ and, in row 6, α = λ .

Step ml : (X → Y, A → w) ml : (X → Y, B → #)
1 [ [ ] X ] E → [ ] Xl E [ [ ] X ] E → [ ] Xl E [ [ ] c1 ] d1 → [ ] c2c3d1
2 [ ] AEXl → [ [ ] w′ ] EXl [ ] Xl BE → [ [ ] Xl ## ] E [ ] c3c2d1 → [ [ ] c′3 ] c2d1
3 [ [ ] EXl ] c′3

→ [ ] EY ′c′3 [ [ ] Xl E ] c′3 → [ ]Y vi HEc′3 [ ] c2d1 → [ [ ] c4 ] d1
4 [ ] c′3Y ′E

→ [ [ ] c′3Y ′′ ] E [ ]Y vic′3EH → [ [ ] c′3Y vii ] EH [ [ ] c4 ] d1 → [ ] c5d1
5 [ [ ] α′ ] c′3Y ′′

→ [ ] α′′c′3Y ′′ [ ]Y vii c′3 → [ [ ]Y viii ] c′3 [ ] c5d1 → [ [ ] c6 ] d1
[ ] HE → [ [ ] H′ ] E

6 [ [ ] α′′c′3Y ′′
] E → [ ] α c′3Y ′′E [ [ ] c′3 ] H′ → [ ] c′′3 H′ [ [ ] c6 ] d1 → [ ] c7d1

7 [ ] c′3Y ′′E
→ [ [ ] c′3Y ′′′ ] E [ [ ]Y viii ] c′′3 H′ → [ ]Y ix c′′3 H′ [ ] c7d1 → [ [ ] c8 ] d1

8 [ [ ] c′3Y ′′′
] E → [ ]Y ′′′E [ [ ]Y ix c′′3 H′] E → [ ]Y ix H′E [ [ ] c8 ] d1 → [ ] c9d1

9 [ ]Y ′′′E → [ [ ]Y iv ] E [ ]Y ix H′E → [ ]Y x ] E [ ] c9d1 → [ [ ] c10 ] d1
10 [ [ ]Y iv ] E → [ ]Y vE [ [ ]Y x ] E → [ ]Y x E [ [ ] c10 ] d1 → [ ] c11d1
11 [ ]Y vE → [ [ ]Y ] E [ ]Y x E → [ [ ]Y ] E [ ] c11d1 → [ [ ] c1 ] d1

Table 1: Rules for simulating two-rules matrices.

We also consider the rules

[ ] Xl E → [ [ ] ## ] E , for each matrix ml : (X → Y, A → w),
[ [ ] H′ ] E → [ ] ##E ,
[ ] ## → [ [ ] # ] #,
[ [ ] # ] # → [ ] ##.

The simulation of matrices in G is performed by modifying the marking of the central membranes, those
emerging from the initial membranes with markings X A and E, with these operations being assisted by the two
membranes with markings c1 and d1 and their successors, which are external to the central membranes where
the sentential form of G is produced. Always during the computation, the membranes remain embedded one in
another, in a linear manner, never having two membranes on the same level (here stands the essential difference
between the interpretation of the cre, dis operations and the interpretation of the pino, exo operations from [1], [2]).



30 Gheorghe Păun

The evolution of the membranes and of their relevant markings can be followed in Figure 2. If in the second
step the rule [ ] AEXl → [ [ ] w′ ] EXl is not applicable (hence the matrix ml cannot be applied), then the rule [ ] Xl E →
[ [ ] ## ] E will be applied, introducing the trap-object #, and the computation will never halt.

Starting [ [ [ [ [ ] X ] E ] c1 ] d1 ] λ
Step 1 [ [ [ ] Xl EA ] c2c3d1 ] λ
Step 2 [ [ [ [ [ ] w′ ] EXl ] c′3

] c2d1 ] λ
Step 3 [ [ [ [ [ ] α′ ] EY ′c′3

] c4 ] d1 ] λ
Step 4 [ [ [ [ [ ] α′ ] c′3Y ′′

] E ] c5d1 ] λ
Step 5 [ [ [ [ [ ] α′′c′3Y ′′

] E ] c6 ] d1 ] λ
Step 6 [ [ [ ] α c′3Y ′′E

] c7d1 ] λ
Step 7 [ [ [ [ [ ] c′3Y ′′′

] E ] c8 ] d1 ] λ
Step 8 [ [ [ ]Y ′′′E ] c9d1 ] λ
Step 9 [ [ [ [ [ ]Y iv ] E ] c10 ] d1 ] λ

Step 10 [ [ [ ]Y vE ] c11d1 ] λ
Step 11 [ [ [ [ [ ]Y ] E ] c1 ] d1 ] λ

Figure 2: The evolution of membranes when simulating ml : (X → Y, A → w).

The evolution of membranes in the case of the simulation of a matrix ml : (X → Y, B → #) can be followed in
Figure 3. This time, if B is present, in step 2 we have to use the rule [ ] Xl BE → [ [ ] Xi## ] E , and the computation
will never halt. If no copy of B is present, then the central membrane does not evolve, waiting for the membrane
marked with c′3 to be produced; this membrane can be used in the next step for evolving the central membrane.

Starting [ [ [ [ [ ] X ] E ] c1 ] d1 ] λ
Step 1 [ [ [ ] Xl E ] c2c3d1 ] λ
Step 2 [ [ [ [ ] Xl E ] c′3

] c2d1 ] λ
Step 3 [ [ [ [ ]Y viHEc′3

] c4 ] d1 ] λ
Step 4 [ [ [ [ ] c′3Y vii

] EH ] c5d1 ] λ
Step 5 [ [ [ [ [ [ [ ]Y viii ] c′3

] H′ ] E ] c6 ] d1 ] λ
Step 6 [ [ [ [ [ ]Y viii ] c′′3 H′

] E ] c7d1 ] λ
Step 7 [ [ [ [ [ ]Y ix c′′3 H′

] E ] c8 ] d1 ] λ
Step 8 [ [ [ ]Y ix H′E ] c9d1 ] λ
Step 9 [ [ [ [ [ ]Y x ] E ] c10 ] d1 ] λ

Step 10 [ [ [ ]Y x E ] c11d1 ] λ
Step 11 [ [ [ [ [ ]Y ] E ] c1 ] d1 ] λ

Figure 3: The evolution of membranes when simulating ml : (X → Y, B → #).

Another step when we can apply a rule different from that indicated in Table 1 is step 4, when we can also use
the rule [ ] HE → [ [ ] H′ ] E . In this way, we pass to the configuration of membranes [ [ [ [ ] H′w1 ] Ew2 ] c5d1 ] λ ,
where w1w2 = Y vic′3. No rule can be applied to the two inner membranes other than [ [ ] H′ ] E → [ ] ##E , and again
the computation will never stop.

Therefore, the simulation of matrices in G should be done as above, and in this way we return to a configuration
as that we have started with, with four membranes marked with X , E, c1, d1, respectively (the central membranes
also having on them the symbols of the current sentential form of G which is simulated in Π).

Note that the rules used for simulating a matrix ml : (X → Y, A → w) cannot be mixed with the rules used for
simulating a matrix ml′ : (X

′ → Y ′, A′ → #), because of the injective labeling of matrices from M and because of
the priming of symbols from N1.

The process can be iterated, hence at some moment we introduce the symbol Zab identified by the symbols
from N1 used. The respective configuration is of the form: [ [ [ [ [ ] Zab ] E ] c1 ] d1 ] λ . The central membrane will



One More Universality Result for P Systems with Objects on Membranes 31

“swallow" all other membranes, also removing all auxiliary objects. To this aim, we use the following rules:

Step 1 [ [ ] Zab ] E → [ ] Z′abE ,
Step 2 [ [ ] Z′abE

] c2c3 → [ ] Z′abbc2c3 ,
Step 3 [ ] Z′abc2c3d1

→ [ [ ] Z′ab ] c3d1 ,
Step 4 [ [ ] Z′ab

] c3d1 → [ ] Z′′abc3d1 ,
Step 5 [ ] Z′′abc3d1

→ [ [ ] Z′′ab ] d1 ,
Step 6 [ [ ] Z′′ab

] d1 → [ ] Z′′′abd1 ,
Step 7 [ ] Z′′′abd1b

→ [ [ ] Z′′′ab ] b,
Step 8 [ [ ] Z′′′ab

] b → [ ] ab,
for all a, b ∈ V . Furthermore, we consider the rules

[ ] Z′abE
→ [ [ ] ## ] E ,

[ [ ] c′3
] c′3
→ [ ] ##c′3 ,

[ ] #a → [ [ ] ## ] a, for all a ∈ V.
The first of these rules is used in step 2 if the rule [ [ ] Z′abE

] c2c3 → [ ] Z′abbc2c3 is not used – the objects c2c3d1
might be used at that time by the rule [ ] c3c2d1 → [ [ ] c′3 ] c2d1 from Table 1. Similarly, if this last rule is used in
step 3 instead of the rule [ ] Z′abc2c3d1

→ [ [ ] Z′ab ] c3d1 , then a membrane marked with c
′
3 is introduced, which will

never be removed. In particular, after 11 steps, we introduce another membrane marked with c′3, and then the rule
[ [ ] c′3

] c′3
→ [ ] ##c′3 is used, preventing the termination of the computation. In conclusion, the evolution of the

membranes in the final stage of the computation is as indicated in Figure 4.

Starting [ [ [ [ [ ] Zab ] E ] c1 ] d1 ] λ
Step 1 [ [ [ ] Z′abE

] c2c3d1 ] λ
Step 2 [ [ ] Z′abbc2c3d1

] λ
Step 3 [ [ [ ] Z′ab

] c3d1 ] λ
Step 4 [ [ ] Z′′abc3d1

] λ
Step 5 [ [ [ ] Z′′ab

] d1 ] λ
Step 6 [ [ ] Z′′′abd1

] λ
Step 7 [ [ [ ] Z′′′ab

] b ] λ
Step 8 [ [ ] ab ] λ

Figure 4: The evolution of membranes in the end of computations.

The equality ΨV (L(G)) = Ps(Π) follows from the previous explanations.
With the observation that the maximal number of membranes present in the system is seven, in step 5 from

Figure 3 (during the simulation of matrices with a rule to be used in the appearance checking mode), and that the
rules have the weight as specified in the theorem, we conclude the proof.

5 Final Remarks

The case of using the operations cree, dise remains as a task for the reader, and the same with other operations
from brane calculus – see also [2] for related problems. Improvements of the result in Theorem 2 are also plausible
in what concerns the degree of context-sensitivity of the rules (and maybe also in what concerns the number of
membranes). The same problems can be formulated for the result from [2].

As a general research topic, it remains to systematically investigate P systems with multisets of objects placed
on membranes (maybe also in the compartments), processed by membrane handling operations like in brane calculi
(maybe also by local multiset rewriting rules).



32 Gheorghe Păun

References

[1] L. Cardelli, Brane calculi. Interactions of biological membranes, Proc. Computational Methods in Systems
Biology, 2004, Springer-Verlag, Berlin, to appear.

[2] L. Cardelli, Gh. Păun, An universality result for a (mem)brane calculus based on mate/drip operations, Intern.
J. Foundations of Computer Sci., 17, 1 (2006), 49–68.

[3] J. Dassow, Gh. Păun, Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.

[4] Gh. Păun, Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143 (and
Turku Center for Computer Science–TUCS Report 208, November 1998, www.tucs.fi).

[5] Gh. Păun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002.

[6] The membrane computing web page: http://psystems.disco.unimib.it.

Institute of Mathematics of the Romanian Academy
PO Box 1-764, 014700 Bucureşti, Romania

and
Research Group on Natural Computing

Department of Computer Science and Artificial Intelligence
University of Sevilla

Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
E-mail: george.paun@imar.ro, gpaun@us.es

Editor’s note about the author:
Gheorghe PĂUN (born on December 6, 1950) graduated the Faculty of
Mathematics of the Bucharest University in 1974 and got his PhD at the
same faculty in 1977. He has won many scholarships, in Germany, Fin-
land, The Netherlands, Spain, etc. Presently he is a senior researcher at
the Institute of Mathematics of the Romanian Academy, Bucharest, and
a Ramon y Cajal research professor at Sevilla University, Spain. Since
1997 he is a Corresponding Member of the Romanian Academy, and
since 2006 a member of Academia Europaea. His main research fields
are formal language theory (regulated rewriting, contextual grammars,
grammar systems), automata theory, combinatorics on words, compu-
tational linguistics, DNA computing, membrane computing (this last
area was initiated by him in 1998). He has (co)authored and (co)edited
more than fifty books in these areas, and he has (co)authored more than
400 research papers. In the last two decades he has visited many uni-
versities from Europe, USA, Canada, Japan, also participating to many
international conferences, several times as an invited speaker. He is a
member of the editorial board of numerous computer science journals
and professional associations.