=Paper=
{{Paper
|id=Vol-2962/invited01
|storemode=property
|title=The Power of Parallelism in Membrane Computing
|pdfUrl=https://ceur-ws.org/Vol-2962/invited01.pdf
|volume=Vol-2962
|authors=Rudolf Freund
|dblpUrl=https://dblp.org/rec/conf/itat/Freund21
}}
==The Power of Parallelism in Membrane Computing==
https://ceur-ws.org/Vol-2962/invited01.pdf
The power of Parallelism in Membrane Computing
Rudolf Freund
Faculty of Informatics, TU Wien
Favoritenstraße 9–11, 1040 Wien, Austria
rudi@emcc.at
Abstract: Maximal parallelism has been an important fea- In the context of catalytic and purely catalytic P sys-
ture of membrane systems from the beginning, i.e., only tems, the question how many catalysts are needed for ob-
non-extendable multisets of rules are applied to the un- taining computational completeness has been one of the
derlying configuration. During the last two decades many most intriguing challenges from the beginning. Without
new variants of parallel derivation modes have been in- catalysts only regular (semi-linear) sets can be generated
vestigated, for example, non-extendable sets of rules are when using the standard maximally parallel derivation
used instead of non-extendable multisets of rules. In many mode and the standard halting mode. For catalytic P sys-
cases, computational completeness can be obtained. Re- tems with only one catalyst a lower bound was established
cently, derivation modes applying multisets of rules affect- in [32]: P systems with one catalyst can simulate partially
ing or generating the maximal number of objects or yield- blind register machines, i.e., they can generate more than
ing the maximal difference between the objects in the cur- just semi-linear sets. At least when using additional con-
rent and the derived configuration have been shown to al- trol mechanisms, even one catalyst can be sufficient to ob-
low for computational completeness even when using only tain computational completeness, see [28]: for example, in
very restricted variants of rules. P systems with label selection, only rules from one set of a
finite number of sets of rules in each computation step are
used; in time-varying P systems, the available sets of rules
1 Introduction change periodically with time. For many other variants of
P systems using specific control mechanism for the appli-
When membrane systems were introduced in [37] more cation of rules the interested reader is referred to the list of
than two decades ago, the application of non-extendable references, for example, see [1, 2, 3, 6, 7, 8, 9, 10, 12, 14,
multisets of rules was one of the basic features of this 15, 16, 17, 18, 20, 21, 22, 23, 26, 27, 28, 29, 30, 31, 34, 35].
bio-inspired model of computing. An introduction to this
In [24] it was shown that without any additional ingredi-
fascinating area is documented in two textbooks, see [38]
ents like a priority relation on the rules as used in the origi-
and [39]. For actual information see the P systems web-
nal definition computational completeness can be obtained
page [42] and the issues of the Bulletin of the International
by showing that register machines with n registers can be
Membrane Computing Society and of the Journal of Mem-
simulated by (purely) catalytic P systems with (n+3) n+2
brane Computing.
catalysts.
The basic model of membrane systems (P systems,
see [37] and [38]) can be seen as a multiset rewriting sys- In [8], the idea of using a priority relation on the rules
tem where objects evolve in parallel in all the regions of a was revived, but in a very weak form: overall in the sys-
hierarchical membrane structure, but the resulting objects tem, catalytic rules have weak priority over non-catalytic
may also pass through the membranes surrounding a mem- rules. Even without using more than this weak priority
brane region. In every derivation step a non-extendable of catalytic rules over the non-catalytic (non-cooperative)
multiset of rules is applied. The result of a computation is rules, computational completeness could be established
extracted when the system halts, i.e., when no rule is appli- for catalytic P systems with only one catalyst. Moreover,
cable any more. The multiset rewriting rules often can be starting from this result, an even stronger result has been
restricted to non-cooperative rules of the form a → v and established in [12], where computational completeness for
catalytic rules of the form ca → cv, where c is a catalyst, catalytic P systems with only one catalyst is shown when
a is a single object and v is a multiset of objects. Catalysts the derivation mode maxob jects is used, i.e., only those mul-
are special objects which allow only one object to evolve tisets of rules are taken which affect the maximal number
in its context, but in their basic variant never evolve them- of objects in the underlying configuration.
selves. P systems using only these two types of rules are In this paper, after recalling some classic results, I will
called catalytic, and if only catalytic rules are allowed we focus on the research which has been started in [12] and
speak of purely catalytic P systems. then has been continued in [11] and in [13]. I will con-
sider several variants of derivation modes based on non-
extendable multisets of rules and taking only those for
Copyright ⃝2021
c for this paper by its authors. Use permitted un-
der Creative Commons License Attribution 4.0 International (CC BY which (i) the number of affected objects is maximal, (ii)
4.0). the number of objects generated by the application of the
multiset of rules is maximal, or (iii) the difference of ob- • p : (SUB(r), q, s); p ∈ B \ {lh }, q, s ∈ B, 1 ≤ r ≤ m.
jects between the underlying configuration and the config- If the value of register r is not zero then decrease the
uration after the application of the multiset of rules is max- value of register r by one (decrement case) and jump
imal. In case of catalytic P systems, for all these variants to instruction q, otherwise jump to instruction s (zero-
one can also take such multisets of rules without request- test case).
ing them to fulfill the condition to be non-extendable.
• lh : HALT .
Stop the execution of the register machine.
2 Definitions
A configuration of a register machine is described by the
The set of natural numbers n ≥ 0 is denoted by N. For any contents of each register and by the value of the current
two natural numbers m, n, m ≤ n, [m..n] denotes the set of label, which indicates the next instruction to be executed.
natural numbers {k | m ≤ k ≤ n}. Moreover, m ⊕n +1 is M is called deterministic if the ADD-instructions all are of
defined as m + 1 for 1 ≤ m < n and n ⊕n +1 = 1. the form p : (ADD(r), q).
For an alphabet V , the free monoid generated by V un- Throughout the paper, BADD denotes the set of labels
der the operation of concatenation, i.e., the set contain- of ADD-instructions p : (ADD(r), q, s) of arbitrary regis-
ing all possible strings over V is denoted by V ∗ . The ters r, and BSUB(r) denotes the set of labels of all SUB-
empty string is denoted by λ . A multiset M with under- instructions p : (SUB(r), q, s) of a decrementable register
lying set A is a pair (A, f ) where f : A → N is a map- r. Moreover, for any p ∈ B\{lh }, Reg(p) denotes the regis-
ping. If M = (A, f ) is a multiset then its support is de- ter affected by the ADD- or SUB-instruction labeled by p;
fined as supp(M) = {x ∈ A | f (x) > 0}. A multiset is for the sake of completeness, in addition Reg(lh ) = 1 is
empty (respectively finite) if its support is the empty set taken.
(respectively a finite set). If M = (A, f ) is a finite multi-
set over A and supp(M) = {a1 , . . . , ak }, then it can also be In the accepting case, a computation starts with the in-
f (a ) f (a )
represented by the string a1 1 . . . ak k over the alphabet put of an l-vector of natural numbers in its first l registers
{a1 , . . . , ak }, and, moreover, all permutations of this string and by executing the first instruction of P (labeled with l0 );
precisely identify the same multiset M. The set of all mul- it terminates with reaching the HALT -instruction. Without
tisets over V is denoted by V ◦ . The cardinality of a set or loss of generality, we may assume all registers to be empty
multiset M is denoted by |M|. at the end of the computation.
For further notions and results in formal language the- In the generating case, a computation starts with all reg-
ory I refer to textbooks like [19] and [40]. isters being empty and by executing the first instruction of
P (labeled with l0 ); it terminates with reaching the HALT -
2.1 Register Machines instruction and the output of a k-vector of natural numbers
in its last k registers. Without loss of generality, we may
Register machines are well-known universal devices for assume all registers except the last k output registers to be
computing on (or generating or accepting) sets of vectors empty at the end of the computation.
of natural numbers. The following definitions and propo- In the computing case, a computation starts with the in-
sitions are given as in [12]. put of an l-vector of natural numbers in its first l registers
and by executing the first instruction of P (labeled with
Definition 1. A register machine is a construct l0 ); it terminates with reaching the HALT -instruction and
the output of a k-vector of natural numbers in its last k
M = (m, B, l0 , lh , P) registers. Without loss of generality, we may assume all
registers except the last k output registers to be empty at
where
the end of the computation.
• m is the number of registers, For useful results on the computational power of regis-
ter machines, we refer to [36]; for example, to prove our
• P is the set of instructions bijectively labeled by ele- main theorem, we need the following formulation of re-
ments of B, sults for register machines generating or accepting recur-
sively enumerable sets of vectors of natural numbers with
• l0 ∈ B is the initial label, and
k components or computing partial recursive relations on
• lh ∈ B is the final label. vectors of natural numbers:
The instructions of M can be of the following forms: Proposition 1. Deterministic register machines can ac-
cept any recursively enumerable set of vectors of natural
• p : (ADD(r), q, s); p ∈ B \ {lh }, q, s ∈ B, 1 ≤ r ≤ m. numbers with l components using precisely l + 2 registers.
Increase the value of register r by one, and non- Without loss of generality, we may assume that at the end
deterministically jump to instruction q or s. of an accepting computation all registers are empty.
Proposition 2. Register machines can generate any recur- The P system Π is called catalytic, if R contains only non-
sively enumerable set of vectors of natural numbers with k cooperative rules of the form a → cv and catalytic rules of
components using precisely k + 2 registers. Without loss of the form ca → cv, where c ∈ C is a catalyst, a is an object
generality, we may assume that at the end of a generating from V \ C, and v is a multiset over V \ C. The P system
computation the first two registers are empty, and, more- Π is called purely catalytic, if R contains only catalytic
over, on the output registers, i.e., the last k registers, no rules.
SUB-instruction is ever used.
The multiset in the single membrane region of Π con-
Proposition 3. Register machines can compute any par- stitutes a configuration of the P system. The initial con-
tial recursive relation on vectors of natural numbers with l figuration is given by the initial multiset w; in case of ac-
components as input and vectors of natural numbers with cepting or computing P systems the input multiset w0 is
k components as output using precisely l + 2 + k registers, assumed to be added to w, i.e., the initial configuration
where without loss of generality, we may assume that at then is ww0 .
the end of a successful computation the first l + 2 registers A transition between configurations is governed by the
are empty, and, moreover, on the output registers, i.e., the application of the evolution rules, which is done in a given
last k registers, no SUB-instruction is ever used. derivation mode. The application of a rule u → v to a mul-
In all cases it is essential that the output registers never tiset M results in subtracting from M the multiset identified
need to be decremented. by u, and then in adding the multiset identified by v.
Remark 1. For any register machine, without loss of gen-
erality we may assume that the first instruction is an ADD- 2.3 Variants of Derivation Modes
instruction on register 1: in fact, given a register ma-
chine M = (m, B, l0 , lh , P) with having a another instruc- The definitions and the corresponding notions used in this
tion as its first instruction, we can immediately construct subsection follow the definitions and notions elaborated in
an equivalent register machine M ′ which starts with an in- [33] as well as in [12] and [13].
crement immediately followed by a decrement of the first Given a P system Π = (V,C, T, w, R), the set of multi-
register: sets of rules applicable to a configuration C is denoted by
( ) Appl(Π,C); this set also equals the set Appl(Π,C, asyn)
M ′ = m, B′ , l0′ , lh , P′ , of multisets of rules applicable in the asynchronous
B′ = B ∪ {l0′ , l0′′ }, derivation mode (abbreviated asyn).
P′ = P ∪ {l0′ : (ADD(1), l0′′ , l0′′ ), l0′′ : (SUB(1), l0 , l0 ) }. Given a multiset R of rules in Appl(Π,C), we write
R
C− → C′ if C′ is the result of applying R to C. The num-
2.2 Simple P Systems ber of objects affected by applying R to C is denoted by
Aff(C, R). The number of objects generated in C′ by the
Taking into account the well-known flattening process, right-hand sides of the rules applied to C with the mul-
which means that computations in a P system with an ar- tiset of rules R is denoted by Gen(C, R). The difference
bitrary membrane structure can be simulated in a P sys- between the number of objects in C′ and C is denoted by
tem with only one membrane, e.g., see [25], in this paper ∆ob j(C, R).
we only consider simple (catalytic, purely catalytic) P sys- The set Appl(Π,C, sequ) denotes the set of multisets of
tems, i.e., with the simplest membrane structure of only rules applicable in the sequential derivation mode (abbre-
one membrane: viated sequ), where in each derivation step exactly one rule
Definition 2. A simple P system is a construct is applied.
The standard parallel derivation mode used in P systems
Π = (V,C, T, w, R) is the maximally parallel derivation mode (max for short).
In the maximally parallel derivation mode, in any compu-
where tation step of Π we choose a multiset of rules from R in
• V is the alphabet of objects; such a way that no further rule can be added to it so that
the obtained multiset would still be applicable to the exist-
• C ⊂ V is the set of catalysts; ing objects in the configuration, i.e., in simple P systems
we only take applicable multisets of rules which cannot be
• T ⊆ (V \C) is the alphabet of terminal objects;
extended by further (copies of) rules and are to be applied
• w ∈ V ◦ is the multiset of objects initially present in to the objects in the single membrane region:
the membrane region;
Appl(Π,C, max) ={R ∈ Appl(Π,C) |
• R is a finite set of evolution rules over V ; these evo-
there is no R′ ∈ Appl(Π,C)
lution rules are mutiset rewriting rules u → v with
u, v ∈ V ◦ . such that R′ ⊃ R}.
We first consider the derivation mode maxob jects max maxGENob jects a multiset of rules R applicable to the cur-
where from the multisets of rules in Appl(Π,C, max) only rent configuration C is only taken if the number of
those are taken which affect the maximal number of ob- objects generated by the application of the rules in R
jects. As with affecting the maximal number of objects, to the configuration C is maximal with respect to the
such multisets of rules are non-extendable anyway, we will number of objects generated by the application of the
also use the notation maxob jects . Formally we may write: rules in any other multiset of rules R′ to the configu-
ration C:
Appl(Π,C, maxob jects max) = {R ∈ Appl(Π,C, max) |
there is no R′ ∈ Appl(Π,C, max) Appl(Π,C, maxGENob jects ) = {R ∈ Appl(Π,C, asyn) |
′
such that Aff(C, R) < Aff(C, R )} there is no R′ ∈ Appl(Π,C, asyn)
such that Gen(C, R) < Gen(C, R′ )}.
and
Appl(Π,C, maxob jects ) = {R ∈ Appl(Π,C, asyn) | max∆ob jects a multiset of rules R applicable to the cur-
′
there is no R ∈ Appl(Π,C, asyn) rent configuration C is only taken if the difference
∆C = |C′ | − |C| between the number of objects in the
such that Aff(C, R) < Aff(C, R′ )}. configuration C′ obtained by the application of R and
As already mentioned, both definitions yield the same the number of objects in the underlying configura-
multiset of rules. tion C is maximal with respect to the differences in
the number of objects obtained by applying any other
In addition to these well-known derivation modes, in multiset of rules:
this paper we also consider several new variants of deriva-
tion modes as already introduced in [11], where instead of Appl(Π,C, max∆ob jects ) = {R ∈ Appl(Π,C, asyn) |
looking at the number of affected objects we take into ac- there is no R′ ∈ Appl(Π,C, asyn)
count the number of generated objects and the difference
such that ∆ob j(C, R) <∆ob j(C, R′ )}.
of objects between the derived configuration and the cur-
rent configuration, respectively.
We illustrate the difference between these new deriva-
maxGENob jects max a non-extendable multiset of rules R tion modes in the following examples, thereby emphasiz-
applicable to the current configuration C is only taken ing on catalytic and non-cooperative rules:
if the number of objects generated by the application
Example 1. To illlustrate the derivation modes
of the rules in R to the configuration C is maximal
maxGENob jects max as well as max∆ob jects max, con-
with respect to the number of objects generated by the
sider a simple P system with the initial configuration caa
application of the rules in any other non-extendable
and the set of rules {a → b, ca → cd}.
multiset of rules R′ to the configuration C:
In case of the derivation mode maxGENob jects max, only
Appl(Π,C, maxGENob jects max) = {R ∈ Appl(Π,C, max) | the multiset of rules {ca → cd, a → b} can be applied,
there is no R′ ∈ Appl(Π,C, max) as Gen(caa, {ca → cd})= 2 and Gen(cab, {a → b})= 1
and therefore Gen(caa, {ca → cd, a → b})= 3, whereas
such that Gen(C, R) < Gen(C, R′ )}. Gen(caa, {a → b, a → b})= 2. Hence, the only possible
derivation with the derivation mode maxGENob jects max is
max∆ob jects max a non-extendable multiset of rules R ap- {ca→cd,a→b}
plicable to the current configuration C is only taken caa −−−−−−−−→ cdb. In this special case,
if the difference ∆C = |C′ | − |C| between the num-
ber of objects in the configuration C′ obtained by the Appl(Π, caa, maxGENob jects max) =
application of R and the number of objects in the un- Appl(Π, caa, maxob jects ).
derlying configuration C is maximal with respect to
the differences in the number of objects obtained by On the other hand, with the derivation mode
applying any other non-extendable multiset of rules: max∆ob jects max both rules yield the same difference of 0,
i.e., ∆ob j(caa, {ca → cd}) = ∆ob j(caa, {a → b}) = 0,
Appl(Π,C, max∆ob jects max) = {R ∈ Appl(Π,C, max) | which yields all two non-extendable multisets of rules
there is no R′ ∈ Appl(Π,C, max) {ca → cd, a → b} and {a → b, a → b} to be applicable to
the underlying configuration caa, i.e.,
such that ∆ob j(C, R) < ∆ob j(C, R′ )}.
Appl(Π, caa, max∆ob jects max) = Appl(Π, caa, max).
Like for maxob jects max in comparison with maxob jects
we now can also consider the variants of the other maxi- Now let us take the set of rules {a → bb, ca → cd}. Ob-
mal derivation modes where we do not start with imposing serving that Gen(caa, {a → bb})= 2 and ∆ob j(caa, {a →
the restriction of being non-extendable on the applicable bb}) = 1, we obtain the following sets of applicable mul-
multisets: tisets of rules:
Appl(Π, caa, maxGENob jects max) = 3 Some Classic Results
{{a → bb, a → bb}, {a → bb, ca → cd}},
Appl(Π, caa, max∆ob jects max) = {{a → bb, a → bb}}. In this section I recall some classic results for P systems
being computationally complete:
Finally, let us take the set of rules {a → λ , ca → cd}. As
Gen(caa, {a → λ })= 0 and ∆ob j(caa, {a → λ }) = −1, we Theorem 4. Every (computation of a) register machine M
obtain the following sets of applicable multisets of rules: can be simulated by a simple P system Π. If M is deter-
Appl(Π, caa, maxGENob jects max) = ministic, then the simulation in Π is deterministic, too.
Appl(Π, caa, max∆ob jects max) = {{a → λ , ca → cd}}.
Proof. Let M = (m, B, l0 , lh , P) be an arbitrary register ma-
Example 2. Consider a simple purely catalytic P sys- chine with the first n registers being the decrementable
tem with the initial configuration c1 c2 aa and the following ones and the registers n + 1, . . . , m being the output reg-
rules: isters.
1. c1 a → c1 Then we construct an equivalent simple P system Π =
2. c2 a → c2 b (V, T, l0 , R) as follows (as we do not use catalysts, we omit
C in the definition of Π):
3. c2 a → c2 bb
V = {ar | 1 ≤ r ≤ m} ∪ B
We immediately observe the following:
∪ {p, p′ , p′′ , p̃, p̄ | p : (SUB(r), q, s) ∈ P},
1. Gen(c1 c2 aa, {c1 a → c1 })= 1,
T = {ar | n + 1 ≤ r ≤ m},
2. Gen(c1 c2 aa, {c2 a → c2 b})= 2,
R = {p → ar q, p → ar s | p : (ADD(r), q, s) ∈ P}
3. Gen(c1 c2 aa, {c2 a → c2 bb})= 3.
∪ {p → p′ p′′ , p′ → p̃, p′′ ar → p̄,
In case of the derivation mode maxGENob jects max, the p̃ p̄ → q, p̃p′′ → s |
multiset of rules {c1 a → c1 , c2 a → c2 bb} has to be ap- p : (SUB(r), q, s) ∈ P} ∪ {lh → λ }.
plied. Hence, the only possible derivation with the deriva-
{c1 a→c1 ,c2 a→c2 bb} The contents of a register r is represented by the corre-
tion mode maxGENob jects max is c1 c2 aa −−−−−−−−−−−−→ sponding number of copies of the symbol ar .
c1 c2 bb. In this special case, An ADD-instruction p : (ADD(r), q) is simulated by the
Appl(Π, c1 c2 aa, maxGENob jects max) = rules p → ar q and p → ar s.
Appl(Π, c1 c2 aa, maxob jects ). A SUB-instruction p : (SUB(r), q, s) is simulated by the
If we do not start from non-extendable multisets of following rules:
rules, we obtain the same results, i.e., in the deriva- 1. p → p′ p′′ ;
tion mode maxGENob jects , the multiset of rules {c1 a →
c1 , c2 a → c2 bb} has to be applied, and the only possi- 2. p′ → p̃, p′′ ar → p̄
ble derivation with the derivation mode maxGENob jects is (executed in parallel if register is not empty);
{c1 a→c1 ,c2 a→c2 bb}
c1 c2 aa −−−−−−−−−−−−→ c1 c2 bb.
3. p̃p′′ → s (if register was empty),
In the same way, for the difference of generated and p̃ p̄ → q (if register was not empty).
consumed objects we obtain:
The HALT-instruction lh : HALT is simulated by the
1. ∆ob j(c1 c2 aa, {c1 a → c1 })= −1,
rule lh → λ .
2. ∆ob j(c1 c2 aa, {c2 a → c2 b})= 0,
3. ∆ob j(c1 c2 aa, {c2 a → c2 bb})= 1. Theorem 5. (see [5]) Every (computation of a) register
machine M withat least two decrementable registers can
As for the derivation mode max∆ob jects max, also for the be simulated by a simple catalytic P system Π and a simple
derivation mode maxGENob jects max we obtain that the mul- purely catalytic P system Π′ .
tiset of rules {c1 a → c1 , c2 a → c2 bb} has to be applied and
that the only possible derivation with the derivation mode Proof. Let M = (m, B, l0 , lh , P) be an arbitrary register ma-
{c1 a→c1 ,c2 a→c2 bb} chine with the first n registers being the decrementable
max∆ob jects max is c1 c2 aa −−−−−−−−−−−−→ c1 c2 bb. ones and the registers n + 1, . . . , m being the output reg-
On the other hand, if we do not start from non- isters. According to Remark 1, the first instruction is as-
extendable multisets of rules, now the rule c1 a → c1 must sumed to be an ADD-instruction on register 1. Moreover,
not be applied because it would decrease the number of without loss of generality we may assume that to output
objects, i.e., in the derivation mode max∆ob jects we obtain registers no SUB-instructions are applied and that at the
that the – not non-extendable – multiset of rules {c2 a → end of a halting computation all registers which allow for
c2 bb} has to be applied, and the only possible derivation SUB-instructions are empty.
{c2 a→c2 bb}
with the derivation mode max∆ob jects is c1 c2 aa −−−−−−−→ As in the original construction given in [24], n cat-
c1 c2 abb. alysts are used, each of these catalysts being needed
for decrementing one of the registers allowing for SUB- Simulation of the SUB-instruction p : (SUB(r), q, s if
instructions; moreover, the idea of “paired catalysts” is register r is not empty register r is empty
taken over, i.e., the catalyst cr works together with the cat- cr p → cr p̄Dn,r cr p → cr p′ D′n,r
alyst cr⊕n 1 (this is the reason why we need at least two cr⊕n 1 dr⊕n 1 → cr⊕n 1 cr⊕n 1 dr⊕n 1 → cr⊕n 1
decrementable registers). The contents of a register r is cr ar → cr a′r D′n,r cr remains idle
represented by the corresponding number of copies of the cr⊕n 1 dr⊕n 1 → cr⊕n 1 cr⊕n 1 p′ → cr⊕n 1 sDn,Reg(s)
symbol ar . ′
cr ar → cr dr⊕n 1
The following abbreviations for specific multisets (writ- cr⊕n 1 p̄ → cr⊕n 1 p̃D′n,r
ten as strings) are used: cr p̃ → cr qDn,Reg(q)
cr⊕n 1 dr⊕n 1 → cr⊕n 1
Dn,r = Π j∈[1..n]\{r} d j and
D′n,r = Π j∈[1..n]\{r,r⊕n 1} d j . The trap rules x → # guarantee that all the symbols x
are used in a correct way in the rules listed above for the
The equivalent simple catalytic P system simulation of the register machine instructions. As soon
as the trap symbol # has been introduced, the derivation
Π = (V,C, T, l0 Dn,1 , R) finally will enter an infinite loop with the rule # → #. In
the case of catalytic P systems, the only non-cooperative
(observe that we start with an ADD-instruction on regis- rules are these trap rules.
ter 1) now is constructed as follows: In case the assumption about register r being not empty
is wrong, then instead of the rule cr ar → cr a′r D′n,r the trap
V = {ar | 1 ≤ r ≤ m} ∪ B ∪C ∪ D rule cr p̄ → cr # must be used. On the other hand, in case
∪ {p, p′ , p̃, p̄ | p : (SUB(r), q, s) ∈ P}, the assumption about register r being empty is wrong, then
catalyst cr will not stay idle, but will be used with the
C = {cr | 1 ≤ r ≤ n},
rule cr ar → cr a′r D′n,r instead. Yet then in the third step
D = {dr | 1 ≤ r ≤ n}, in sum 2n − 1 objects to be handled by only n catalysts
T = {ar | n + 1 ≤ r ≤ m}, will be present in the configuration, which is impossible
R = {cr dr → cr | 1 ≤ r ≤ n} ∪ {c1 lh → c1 } and therefore will lead to the introduction of the trap sym-
∪ {cr p → cr ar qDn,Reg(q) , cr p → cr ar sDn,Reg(s) bol #.
| p : (ADD(r), q, s) ∈ P} In the purely catalytic case, one additional catalyst cd+1
∪ {cr dr → cr | 1 ≤ r ≤ n} is needed for all the non-cooperative rules given above.
∪ {cr p → cr p̄Dn,r , cr p → cr p′ D′n,r , These trap rules, and only those, are associated with this
cr ar → cr a′r D′n,r , cr p̄ → cr #, catalyst cd+1 ; for example, the trap rule # → # now is re-
cr⊕n 1 p′ → cr⊕n 1 sDn,Reg(s) , placed by the rule cd+1 # → cd+1 #.
cr a′r → cr dr⊕n 1 , cr⊕n 1 p̄ → cr⊕n 1 p̃D′n,r ,
cr p̃ → cr qDn,Reg(q) The construction given in the proof above works for
| p : (SUB(r), q, s) ∈ P} both catalytic and purely catalytic P systems. An improved
∪ {x → # | x ∈ {#} ∪ {d j , a′j | 1 ≤ j ≤ n} version for catalytic P systems with respect to the number
∪{p, p′ , p̃ | p ∈ BSUB(r) , 1 ≤ r ≤ n}}. of rules needed for simulating SUB-instructions was pre-
sented at the Workshop on Membrane Computing 2015
For each catalyst cr we use a “dummy” symbol dr , which (Satellite Workshop of UCNC 2015 in Auckland), see [4].
keeps the catalyst cr busy whenever needed enforcing cr As this improved result for catalytic P systems is the best
to use the rule cr dr → cr to keep the simulation alive. known so far with respect to the number of rules needed
When one of the instructions works on a specific register r, for simulating SUB-instructions, this specific construction
then only the catalyst cr and in case of SUB-instructions is recalled in the proof of the following theorem:
also catalyst cr⊕k 1 is involved, whereas the catalysts cor-
responding to the other registers j have to be kept busy Theorem 6. For any register machine M = (m, B, l0 , lh , P),
by the corresponding rule c j d j → c j . For each SUB- with n ≤ m being the number of decrementable regis-
instruction labeled by the “program” symbol p also the ters, we can construct a simple catalytic P system Π =
variants p′ , p̃, p̄ are used. (V,C, T, w, R) simulating the computations of M such that
The HALT-instruction lh : HALT is simulated by the |R| ≤ ADD1 (P) + 2 × ADD2 (P) +
rule c1 lh → c1 (observe that Reg(lh ) = 1 is assumed). 5 × SUB(P) + 5 × m + 1,
Each ADD-instruction j : (ADD(r), k, l) is simulated by
where ADD1 (P) denotes the number of deterministic
the two rules cr p → cr ar xDk,Reg(x) , x ∈ {q, s}.
ADD-instructions in P, ADD2 (P) denotes the number of
Each SUB-instruction j : (SUB(r), k, l) is simulated in non-deterministic ADD-instructions in P, and SUB(P) de-
at most four steps as shown in the table given below: notes the number of SUB-instructions in P.
Proof. Again a register machine M = (m, B, l0 , lh , P) with Simulation of the SUB-instruction p : (SUB(r), q, s) if
n ≤ m decrementable registers is simulated by a catalytic register r is not empty register r is empty
P system Π = (V,C, T, w, R). p → p̄er Dn,r p → p′ Dn,r
For each of the n decrementable registers, we take a cat- cr ar → cr dr [cr er → cr #] cr should stay idle
alyst cr and two specific symbols dr , er , 1 ≤ r ≤ n, for sim- p̄ → p̃D′n,r p′ → sDn
ulating SUB-instructions on these registers. cr dr → cr [dr → #] [dr → #]
p̃ → qDn
V = C ∪ D ∪ E ∪ Σ ∪ {#} ∪ {p | p ∈ B} cr⊕n 1 er → cr⊕n 1
∪ {p′ , p̄, p̃ | l ∈ BSUB },
In the first step of the simulation of each instruc-
C = {cr | 1 ≤ r ≤ n},
tion (ADD-instruction, SUB-instruction, and even HALT-
D = {dr | 1 ≤ r ≤ n},
instruction) due to the introduction of Dn in the previous
E = {er | 1 ≤ r ≤ n},
step (we also start with that in the initial configuration) ev-
Σ = {ar | 1 ≤ r ≤ m},
ery catalyst cr is kept busy by the corresponding symbol
T = {ar | 1 ≤ r ≤ n},
dr , 1 ≤ r ≤ m. Hence, this also guarantees that the zero-
R = {lh → λ }
check on register r works correctly enforcing dr → # to be
∪ {p → ar qDn , q → ar sDn
applied, as in the case of a wrong choice two symbols dr
| p : (ADD(r), q, s) ∈ P}
are present.
∪ {p → p̄er Dn,r , p → p′ Dn,r ,
p̄ → p̃D′n,r , p′ → sDn , p̃ → qDn The HALT-instruction lh : HALT is simulated by the
| p : (SUB(r), q, s) ∈ P} rule lh → λ ; observe that no objects ar for 1 ≤ r ≤ n are
∪ {cr ar → cr dr , cr dr → cr , cr⊕n 1 er → cr⊕n 1 present any more when lh has appeared.
| 1 ≤ r ≤ n},
∪ {dr → #, cr er → cr # | 1 ≤ r ≤ n} Remark 2. Exactly the same construction as elaborated
∪ {# → #}. above can be used when allowing for n + 2 catalysts, with
catalyst cn+1 being used with the state symbols and cata-
The initial configuration is lyst cn+2 being used with the trap rules. If only one ad-
ditional catalyst cn+1 is allowed to be used with all the
w = c1 . . . cn d1 . . . dn p1 w0 non-cooperative rules, a slightly more complicated simu-
lation of SUB-instructions is needed, see [41], where for
where w0 stands for additional input present at the begin- catalytic P systems
ning, for example, for the given input in case of accepting
systems. |R| ≤ 2 × ADD1 (P) + 3 × ADD2 (P) +
Usually, every catalyst cr , r ∈ [1..n], is kept busy with 6 × SUB(P) + 5 × m + 1,
the symbol dr using the rule cr dr → cr , as otherwise the
symbols dr would have to be trapped by the rule dr → #, and for purely for catalytic P systems
and the trap rule # → # then enforces an infinite non-
|R| ≤ 2 × ADD1 (P) + 3 × ADD2 (P) +
halting computation. Only during the simulation of SUB-
instructions on register r the corresponding catalyst cr is 6 × SUB(P) + 6 × m + 1,
left free for decrementing or for zero-checking in the sec-
was shown.
ond step of the simulation, and in the decrement case both
cr and its “coupled” catalyst cr⊕n 1 are needed to be free Remark 3. In case of deterministic register machines, es-
for specific actions in the third step of the simulation. pecially in the accepting case, every sequence of consec-
For the simulation of instructions, we use the following utive ADD-instructions is bounded by a constant only de-
shortcuts: pending on the given register machine. Hence, in this case
the calculations for |R| in Theorem 6 and in Remark 2 can
Dn = ∏i∈[1..n] di , omit the ADD-instructions, because any fixed sequence of
Dn,r = ∏i∈[1..n]\{r} di , consecutive ADD-instructions can be included directly in
D′n,r = ∏i∈[1..n]\{r,r⊕n 1} di . the last simulation step of the preceding SUB-instruction,
see the concept of generalized register machines as used
Each ADD-instruction p : (ADD(r), q, s), for r ∈ [1..n], in [17] and also cited in [41].
is simulated by the rules p → ar qDn and p → ar sDm ; in Remark 4. The use of the trap symbol # to enforce the
parallel, the rules cr dr → cr , 1 ≤ r ≤ n, have to be carried computation never to stop is a typical element of many
out, as otherwise the symbols dr would have to be trapped proofs to be found in the literature. Only very few vari-
by the rules dr → #. ants of P systems are known so far which allow for a de-
Each SUB-instruction p : (SUB(r), q, s), is simulated as terministic simulation of the SUB-instruction and in that
shown in the table listed below (the rules in brackets [ and ] way for a deterministic simulation of a deterministic reg-
are those to be carried out in case of a wrong choice): ister machine like the unrestricted variant considered in
Theorem 4. Therefore I already now want to emphasize of the first n sections, they “know” that they are to proba-
this important feature of most of the simple P systems in- bly simulate a SUB-instruction on register r of the register
vestigated in the following sections to allow for an even machine M.
deterministic simulation.
V = {ar | n + 1 ≤ r ≤ m}
∪ {(ar , i) | 1 ≤ r ≤ n, 1 ≤ i ≤ n + 1}
4 Catalytic P Systems with One Catalyst
∪ {(p, i) | p ∈ BADD , 1 ≤ i ≤ n + 1}
In [12] it was shown that computational completeness can ∪ {(p, i) | p ∈ BSUB(r) ,
be obtained with simple P systems and only one cata- 1 ≤ i ≤ r + 1, 1 ≤ r ≤ n}
lyst when using the derivation mode maxob jects instead of ∪ {(p, i)− , (p, i)0 | p ∈ BSUB(r) ,
max. Then in [11] computational completeness was estab- r + 2 ≤ i ≤ n + 1, 1 ≤ r ≤ n − 1}
lished for simple P systems with only one catalyst using
∪ {c, e, #},
the derivation modes maxGENob jects max, max∆ob jects max,
maxGENob jects , and max∆ob jects . The results exhibited in T = {ar | n + 1 ≤ r ≤ m}.
this section are optimal with respect to the number of cat-
The alphabet V of symbols includes register symbols
alysts for catalytic P systems working in these derivation
(ar , i) for every decrementable register r of the register
modes, because such P systems when given multisets of
machine and only the register symbol ar for each of the
non-cooperative rules can only generate semi-linear sets.
k output registers r, m − k + 1 ≤ r ≤ m.
Theorem 7. For any register machine with at least two The construction includes the trap rule # → # which will
decrementable registers we can construct a catalytic P sys- always keep the system busy and prevent it from halting
tem with only one catalyst and working in the derivation and thus from producing a result as soon as the trap sym-
mode maxob jects which can simulate every step of the regis- bol # has been introduced, yet the only rule introducing
ter machine in n + 1 steps where n is the number of decre- this trap symbol is the single rule e → #.
mentable registers.
For letting the register symbols cycle with a period of
Proof. We use the trick as elaborated in Remark 1 for get- n + 1 the following rules are used:
ting a specific variant of register machines: without loss of
generality, we start with an ADD-instruction on register 1, (ar , i) → (ar , i + 1), 1 ≤ r ≤ n;
(1)
but we also change the register machine program in such (ar , n + 1) → (ar , 1).
a way that after a SUB-instruction on register n two inter-
mediate instructions are introduced, i.e., as in Remark 1, For simulating ADD-instructions we need the following
we use an ADD-instruction on register 1 immediately fol- rules:
lowed by a SUB-instruction on register 1.
We then may simulate the resulting register machine Increment p : (ADD(r), q, s):
fulfilling these additional constraints M = (m, B, l0 , lh , P)
by a corresponding catalytic P system with one membrane c(p, i) → c(p, i + 1), 1 ≤ i ≤ n. (2)
and one catalyst Π = (V, {c}, T, (l0 , 1), R). Without loss of
If r is a decrementable register:
generality, we may assume that, depending on its use as an
accepting or generating or computing device, the register c(p, n + 1) → c(q, 1)(ar , 1),
machine M, as stated in Proposition 1, Proposition 2, and (3)
c(p, n + 1) → c(s, 1)(ar , 1).
Proposition 3, fulfills the condition that on the output reg-
isters we never apply any SUB-instruction. Moreover, we If r is an output register:
take the most general case of a register machine computing
c(p, n + 1) → c(q, 1)ar ,
a partial recursive function on vectors of natural numbers (4)
c(p, n + 1) → c(s, 1)ar
with l components as input and vectors of natural numbers
with k components as output using n decrementable regis- The catalyst has to be used with the program symbol
ters, where without loss of generality, we may assume that which otherwise would stay idle when the catalyst is used
at the end of a successful computation the first n registers with a register symbol, and the multiset of rules applied
are empty, and, moreover, on the output registers, i.e., the in this way would use one object less and thus violate the
last k registers, no SUB-instruction is ever used. condition of using the maximal number of objects.
The main idea behind the construction is that all the For simulating SUB-instructions we need the following
symbols except the catalyst c and the output symbols rules:
(representing the contents of the output registers) go Decrement and zero-test p : (SUB(r), q, s):
through a cycle of length n + 1 where n is the number
of decrementable registers of the simulated register ma- c(p, i) → c(p, i + 1), 1 ≤ i < r
(5)
chine. When the symbols are traversing the r-th section (p, r) → (p, r + 1), c(ar , r) → ce.
In case that register r is empty, i.e., there is no object trap symbol # and therefore is the only reasonable contin-
(ar , r), then the catalyst will stay idle in step r as there is uation of the computation if register r is empty.
no other object with which it could react.
c(p, i)− → c(p, i + 1)− , r + 2 ≤ i ≤ n,
If r < n: c(p, n + 1)− → c(q, 1),
(7)
ce → c, e → #, (p, r + 1) → (p, r + 2)− ; c(p, i)0 → c(p, i + 1)0 , r + 2 ≤ i ≤ n,
(6)
c(p, r + 1) → c(p, r + 2)0 . c(p, n + 1)0 → c(s, 1).
The catalyst has to be used with the program symbol
If in the first step of the simulation phase the catalyst did
which otherwise would stay idle when the catalyst is used
manage to decrement the register, it produced e. Thus, in
with a register symbol, and the multiset of rules applied
the second simulation step, the catalyst has three choices:
in this way would use one object less and thus violate the
condition of using the maximal number of objects.
1. the catalyst c correctly erases e, and to the program
symbol (p, r + 1) the rule (p, r + 1) → (p, r + 2)− If r = n:
must be applied due to the derivation mode maxob-
jects; all register symbols evolve in the usual way; ce → c, e → #,
(8)
(p, n + 1) → (q, 1), c(p, n + 1) → c(s, 1).
2. the catalyst c takes the program symbol (p, r + 1) us-
ing the rule c(p, r + 1) → c(p, r + 2)0 , thus forcing
the object e to be trapped by the rule e → #, and all We observe that in this case during the first step of the
register symbols evolve in the usual way; next cycle we have to guarantee that in the zero-test case
the catalyst must be used with the program symbol, hence,
3. the catalyst c takes a register object (ar+1 , r + 1), thus we will simulate an ADD-instruction on register 1, as the
leaving the object e to be trapped by the rule e → #, introduction of the symbol e in the wrong variant of the
the program symbol (p, r + 1) evolves with the rule zero-test case must lead to introducing the trap symbol and
(p, r + 1) → (p, r + 2)− , and all other register objects not allowing e to be erased by the catalytic rule ce → c.
evolve in the usual way. The HALT-instruction lh : HALT is simulated by the
rule clh → c.
In fact, only variant 1 now fulfills the condition given
by the derivation mode maxob jects and therefore is the only As the number of decrementable registers in generating
possible continuation of the computation if register r is not register machines needed for generating any recursively
empty. enumerable set of (vectors of) natural numbers is only two,
the following result is an immediate consequence of the
On the other hand, if register r is empty, no object e is preceding theorem:
generated, and the catalyst c has only two choices:
Corollary 1. For any generating register machine with
1. the catalyst c takes the program symbol (p, r + 1) us- two decrementable registers we can construct a catalytic
ing the rule c(p, r + 1) → c(p, r + 2)0 , and all register P system with only one catalyst and working in the deriva-
symbols evolve in the usual way; tion mode maxob jects which can simulate every step of the
register machine in 3 steps, and therefore such catalytic P
2. the catalyst c takes a register object (ar+1 , r + 1) systems with only one catalyst and working in the deriva-
thereby generating e, the program symbol (p, r + 1) tion mode maxob jects can generate any recursively enumer-
evolves with the rule (p, r + 1) → (p, r + 2)− , and all able set of (vectors of) natural numbers.
other register objects evolve in the usual way; this
variant leads to the situation that e will be trapped
The following results even yield deterministic simula-
in step r + 2, as otherwise the program symbol stays
tions of SUB-instructions of a register machine and thus
idle, thus violating the condition of the derivation
can even avoid trapping.
mode maxob jects . Hence, this variant in any case can-
not lead to a halting computation due to the introduc- Theorem 8. (see [11]) For any register machine with at
tion of the trap symbol #. We mention that in case no least two decrementable registers we can construct a sim-
register object (ar+1 , r + 1) is present we have to ap- ple catalytic P system with only one catalyst, working in
ply case 1 and thus have a correct computation step. the derivation mode max∆ob jects max or in the derivation
mode maxGENob jects max, which can simulate every step of
Both variants fulfill the condition for the derivation the register machine in n steps where n is the number of
mode maxob jects , but only variant 1 is not introducing the decrementable registers.
Proof. Given an arbitrary register machine V = {ar | n + 1 ≤ r ≤ m}
M = (m, B, l0 , lh , P) we will construct a correspond- ∪ {(ar , i) | 1 ≤ r ≤ n, 1 ≤ i ≤ n}
ing catalytic P system with one membrane and one
catalyst Π = (V, {c}, T, w, R) simulating M. Without loss ∪ {(p, i) | p ∈ BADD , 1 ≤ i ≤ n}
of generality, we may assume that, depending on its use as ∪ {(p, i) | p ∈ BSUB(r) , 1 ≤ i ≤ r + 1}
an accepting or generating or computing device, the regis-
∪ {(p, i)− , (p, i)0 | p ∈ BSUB(r) , r + 2 ≤ i ≤ n}
ter machine M, as stated in Proposition 1, Proposition 2,
and Proposition 3, fulfills the condition that on the output ∪ {c, e, d}
registers we never apply any SUB-instruction. T = {ar | n + 1 ≤ r ≤ m}.
The following proof is given for the most general case The construction includes the dummy symbol d which is
of a register machine computing any partial recursive re- erased by the rule d → λ . The effect of applying these
lation on vectors of natural numbers with l components as rules due to the requirement of the chosen multisets of
input and vectors of natural numbers with k components rules to be non-extendable will be ignored in the following
as output using precisely l + 2 + k registers, where with- calculations for ∆ob j(C, R) and Gen(C, R).
out loss of generality, we may assume that at the end of a
successful computation the first l + 2 registers are empty, The symbols ar , n + 1 ≤ r ≤ m, represent the output reg-
and, moreover, on the output registers, i.e., the last k reg- isters. For the decrementable registers, we use the symbols
isters, no SUB-instruction is ever used. In fact, the proof (ar , i), 1 ≤ r ≤ n, 1 ≤ i ≤ n, which go through a loop of n
works for any number n ≥ 2 of decrementable registers, no steps. The main idea now is that the only case when such a
matter how many of them are the l input registers and the symbol can be used to decrement register r is when i = r,
working registers, respectively. i.e., in the r-th step of the simulation cycle.
The main idea behind the construction is that all the (ar , i) → (ar , i + 1), 1 ≤ r < n; (ar , n) → (ar , 1). (9)
symbols except the catalyst c and the output symbols (rep-
resenting the contents of the output registers) go through a In the same way as the register symbols ar , the program
cycle of length n where n is the number of decrementable symbols (p, i) representing the label p from B undergo the
registers of the simulated register machine. When the same cycle of length n.
symbols are traversing the r-th section of the n sections, For simulating ADD-instructions we need the following
they “know” that they are to probably simulate a SUB- rules:
instruction on register r of the register machine M.
Increment p : (ADD(r), q, s):
As in this construction the simulation of a SUB-
instruction takes two steps, the second simulation step in c(p, i) → c(p, i + 1)d, 1 ≤ i < n. (10)
the case of a SUB-instruction on register n is shifted to
the first step of the next cycle. Yet in this case we have The catalyst has to be used with the program sym-
to guarantee that after a SUB-instruction on register n the bol which otherwise would stay idle when the catalyst is
next instruction to be simulated is not a SUB-instruction on used with a register symbol, and the difference of objects
register 1. Hence, we use a similar trick as already used in ∆ob j(C, R′ ) for this other non-extendable multiset of rules
the proof of Theorem 7, i.e., we not only do not start with a R′ would be 0 whereas when using the program symbol
SUB-instruction, but we also change the register machine for the catalyst, we obtain ∆ob j(C, R)= 1 because of the
program in such a way that after a SUB-instruction on reg- additional dummy symbol d.
ister n two intermediate instructions are introduced, we use In a similar way we can argue that in the case of the
an ADD-instruction on register 1 immediately followed by derivation mode maxGENob jects max the number of gener-
a SUB-instruction on register 1, whose simulation will end ated objects is maximal when using the catalyst together
at most in step n, as we have assumed n ≥ 2. with the program symbol; in fact, if N is the total num-
ber of register symbols for decrementable registers in the
The following construction is elaborated in such a way underlying configuration C, then with applying the set of
that it works both for the derivation mode max∆ob jects max rules R described so far we get Gen(C, R)= N + 3 in con-
and the derivation mode maxGENob jects max. trast to Gen(C, R′ )= N − 1 + 3 = N + 2 where using the
catalyst with the rule c(ar , r) → ced, as described below
We now simulate the resulting register machine fulfill- for the simulation of the SUB-Instruction, results in the
ing these additional constraints M = (m, B, l0 , lh , P) by a multiset of rules R′ .
corresponding simple P system with one catalyst:
If r is a decrementable register, we end the simulation
using one of the following rules:
Π = (V, {c}, T, c(l0 , 1), R). c(p, n) → c(q, 1)(ar , 1), c(p, n) → c(s, 1)(ar , 1). (11)
If r is an output register, we end the simulation using 2. the catalyst c takes the program symbol (p, r + 1) us-
one of the following rules introducing output symbols not ing the rule c(p, r + 1) → c(p, r + 2)0 dd, and all reg-
to be changed any more: ister symbols evolve in the usual way; in total we get
∆ob j(C, R)= 2 and Gen(C, R)= N + 4;
c(p, n) → c(q, 1)ar , c(p, n) → c(s, 1)ar . (12)
3. the catalyst c takes a register object, the program
As in both cases, together with the program sym-
symbol (p, r + 1) evolves with the rule (p, r + 1) →
bol a new register symbol is generated, we again have
(p, r + 2)− , and all other register objects evolve in
∆ob j(C, R) = 1, thus guaranteeing that the catalyst must
the usual way; in total we get ∆ob j(C, R)= 1 and
take (p, n) and cannot take (an , n) instead.
Gen(C, R)= (N − 1 + 3) + 1 = N + 3.
A similar argument again holds in the case of the deriva-
tion mode maxGENob jects max as the number of generated In total, only variant 1 fulfills the condition given by the
objects is only maximal when using the catalyst together derivation mode max∆ob jects max that ∆ob j(C, R) is maxi-
with the program symbol; again we have Gen(C, R)= N + mal, and therefore is the only possible continuation of the
3 with this multiset of rules R in contrast to Gen(C, R′ )= computation if register r is not empty.
N − 1 + 3 = N + 2 when using the catalyst with the rule A similar argument holds for the derivation mode
c(ar , r) → ced results in the multiset of rules R′ . maxGenob jects max with respect to the number of generated
objects ∆ob j(C, R).
For simulating SUB-instructions we need the following
rules: On the other hand, if register r is empty, no object e is
generated, and the catalyst c has only two choices:
Decrement and zero-test p : (SUB(r), q, s):
1. the catalyst c takes the program symbol (p, r + 1) us-
c(p, i) → c(p, i + 1)d, 1 ≤ i < r. (13) ing the rule c(p, r + 1) → c(p, r + 2)0 dd, and all reg-
For 1 ≤ i < r, we again use the dummy symbol d to ister symbols evolve in the usual way; in total we get
obtain ∆C = 1 and thus also having one more object gen- ∆ob j(C, R)= 2 and Gen(C, R)= N + 4;
erated, to enforce the catalyst to take the program symbol. 2. the catalyst c takes a register object (ar+1 , r + 1)
thereby generating ed, the program symbol (p, r + 1)
(p, r) → (p, r + 1), c(ar , r) → ced. (14) evolves with the rule (p, r + 1) → (p, r + 2)− , and
In case that register r is empty, i.e., there is no object all other register objects evolve in the usual way;
(ar , r), then the catalyst will stay idle as in this step there is this variant leads to ∆ob j(C, R)= 1 and Gen(C, R)=
no other object with which it could react. In case that reg- (N − 1 + 3) + 1 = N + 3.
ister r is not empty, i.e., there is at least one object (ar , r),
then one of these objects (ar , r) must be used with the cat- In total, variant 1 is the only possible continuation of the
alyst c as the rule c(ar , r) → ced implies ∆ob j(C, R)= 1, computation if register r is empty.
whereas otherwise, if all register symbols are used with c(p, i)− → c(p, i + 1)− d, r + 2 ≤ i < n,
the rule (ar , r) → (ar , r + 1), then ∆ob j(C, R)= 0. c(p, n)− → c(q, 1)d,
In the same way we argue that with using the rule (16)
c(ar , r) → ced we get one object generated more than c(p, i)0 → c(p, i + 1)0 d, r + 2 ≤ i < n,
if we use the rule (ar , r) → (ar , r + 1) for that symbol c(p, n)0 → c(s, 1)d.
(ar , r), i.e., Gen(C, R)= N − 1 + 3 = N + 2 in contrast to Again the catalyst has to be used with the program sym-
Gen(C, R′ )= N. bol to get ∆ob j(C, R)= 1 and Gen(C, R)= N + 3, which
If r < n − 1: otherwise would stay idle when the catalyst is used with a
register symbol, and the multiset of rules applied in this
ce → cdddd, (p, r + 1) → (p, r + 2)− ,
(15) way would only yield ∆ob j(C, R)= 0 and Gen(C, R′ )=
c(p, r + 1) → c(p, r + 2)0 dd. N − 1 + 3 = N + 2.
If in the first step of the simulation phase the catalyst did If r = n − 1:
manage to decrement the register, it produced e. Thus, in
the second simulation step, the catalyst has three choices: ce → cdddd, (p, n) → (q, 1),
(17)
1. the catalyst c correctly “erases" e using the rule c(p, n) → c(s, 1)dd.
ce → cdddd, and to the program symbol (p, r + 1)
In this case, we directly go to the first step of the next
the rule (p, r + 1) → (p, r + 2)− must be applied due
cycle.
to the fact that both derivation modes max∆ob jects max
and maxGENob jects max only allow for non-extendable If r = n:
multisets of rules; all register symbols evolve in
the usual way; in total we get ∆ob j(C, R)= 3 and ce → cdddd, (p, n + 1) → (q, 2),
(18)
Gen(C, R)= N + 6; c(p, n + 1) → c(s, 2)dd.
In this case, the second step of the simulation is already 5 Purely Catalytic P Systems
the first step of the next cycle, which means that in this
case of r = n the next instruction to be simulated is an The technique used for catalytic P systems in the proof
ADD-instruction on register 1. of Theorem 8 cannot be taken over to purely catalytic
P systems, where the number of rules to be used in ev-
ery step is bounded by the number of catalysts. Hence,
To complete the proof we have to implement the final
a similar technique as already known from the proof of
HALT -instruction lh : HALT with the rule c(lh , 1) → cdd.
the classic result given in Theorem 4 is used for prov-
In this way, finally no program symbol is present any
ing Theorem 10, yet still the result to be obtained with
more in the configuration. As we have assumed all decre-
the derivation modes max∆ob jects max, maxGENob jects max,
mentable registers to be empty when the register machine
max∆ob jects , and maxGENob jects is better than that one
halts, this means the constructed simple P system will also
known for the derivation mode max, because one catalyst
halt after having erased the dummy symbols d in the next
less is needed.
step.
Theorem 10. For any register machine with n ≥ 2 decre-
We finally observe that the proof construction given mentable registers we can construct a simple purely cat-
above is even deterministic if the underlying register ma- alytic P system with only n catalysts, working in one of
chine to be simulated is deterministic. the derivation modes max∆ob jects max, maxGENob jects max,
max∆ob jects , or maxGENob jects , which can simulate any
In a similar way, the same result can even be shown for
computation of the register machine.
the derivation modes max∆ob jects and maxGENob jects , where
the condition of non-extendability for the multisets of rules Proof. Given an arbitrary register machine
to be applied is not required. M = (m, B, l0 , lh , P) with n decrementable registers
we will construct a corresponding simple purely catalytic
Theorem 9. For any register machine with at least two P system with n catalysts
decrementable registers we can construct a simple cat-
Π = (V, {ck | 1 ≤ k ≤ n}, T, w, R)
alytic P system with only one catalyst, working in the
derivation mode max∆ob jects or in the derivation mode simulating M. Without loss of generality, we may assume
maxGENob jects , which can simulate every step of the reg- that, depending on its use as an accepting or generating
ister machine in n steps where n is the number of decre- or computing device, the register machine M, as stated
mentable registers. in Proposition 1, Proposition 2, and Proposition 3, ful-
fills the condition that on the output registers we never
As the number of decrementable registers in generating apply any SUB-instruction. Moreover, according to Re-
register machines needed for generating any recursively mark 1 we may assume that the first instruction is an ADD-
enumerable set of (vectors of) natural numbers is only two, instruction on the first register. Finally, we assume the n
from the theorems above we obtain the following result: decrementable registers to be the first ones.
The following proof again is elaborated for all
Corollary 2. For any generating register machine with the derivation modes max∆ob jects max, maxGENob jects max,
two decrementable registers we can construct a simple P max∆ob jects , and maxGENob jects , with only a few subtle
system with only one catalyst and working in the deriva- technical details to be mentioned additionally.
tion mode max∆ob jects max, maxGENob jects max, max∆ob jects , The main part of the proof is to show how to simu-
or maxGENob jects which can simulate every step of the late the instructions of M in Π; in all cases we have to
register machine in 2 steps, and therefore such catalytic take care that the n catalysts are kept busy – using corre-
P systems with only one catalyst and working in the in sponding dummy objects dr – in order to guarantee that
the derivation mode max∆ob jects max, maxGENob jects max, the simulation is executed in a correct way; especially we
max∆ob jects , or maxGENob jects max can generate any recur- have to guarantee that one of the rules using the catalysts
sively enumerable set of (vectors of) natural numbers. ck , 1 ≤ k ≤ n, must be used if possible, i.e., a catalyst can
only stay idle if the underlying configuration does not con-
The even more important achievement than the rather
tain any object which can evolve together with the catalyst.
expected computational completeness established with
Again the priority between different rules for a catalyst is
(the proof of) Theorem 8 and Theorem 9 is the
guarded by the number of objects on the right-hand side
fact that with the derivation modes max∆ob jects max,
of the rules, which argument applies for all the derivation
maxGENob jects max, max∆ob jects , and maxGENob jects only
modes under consideration, as every rule in a purely cat-
one catalyst is needed to obtain computational complete-
alytic P system has exactly two objects on its left-hand
ness, which is the optimal result with respect to the num-
side.
ber of catalysts, because with non-cooperative rules, only
During the simulation of all instructions, we use the fol-
semilinear sets can be generated. Moreover, the simula-
lowing multisets:
tion of a deterministic register machine is deterministic in
the P system, too. D′n,r = ∏i∈[1..n]\{r,r⊕n 1} di , 1 ≤ r ≤ n.
As the first instruction to be simulated is an ADD- • p : (SUB (r) , q, s), with p ∈ BSUB , q, s ∈ B, 1 ≤ r ≤ n.
instruction on the first register, we start with the initial
multiset
decrement case
w = l0 l0′ D′n,1 ∏ ci .
i∈[1..n] If the value of register r (denoted by |reg(r)|) is not
zero then the number of register objects ar is de-
As usual, the number of objects ar in a configuration creased by one using the corresponding rule cr ar →
represents the number stored in register r at that moment cr âr d 2 in the first step of the simulation. In sum three
of the computation. Objects ar for r > n are never changed steps are needed for the simulation, see table below.
again, as they represent output registers.
zero-test case.
V = {ar | 1 ≤ r ≤ m} ∪ {âr | 1 ≤ r ≤ n} If the value of register r is zero, then the correspond-
∪ {p, p′ | p ∈ BADD ∪ {lh }} ing catalyst is already free for eliminating the label
object p so that already in the second step of the sim-
∪ {p, p′ , p̄, p̂ | p ∈ BSUB(r) , 1 ≤ r ≤ n}
ulation the simulation of the next instruction s can be
∪ {ck , dk | 1 ≤ k ≤ n} ∪ {d}, initiated. In sum only two steps are needed for the
T = {ar | n + 1 ≤ r ≤ m}. simulation of this case, see table below.
The following table summarizes the rules to be used
The dummy objects di , 1 ≤ i ≤ n, are used to keep the
for the simulation of the SUB-instruction on regis-
corresponding catalyst ci busy whenever it is not needed
ter r, 1 ≤ r ≤ n, i.e., we use the following rules; we
during the simulation of a SUB-instruction, which is ac-
emphasize that again the simulation is deterministic.
complished by the following rule erasing di , but instead
introducing the necessary amount of objects d to keep the
catalyst ci away from erasing a register object ar :
step |reg(r)| rule for cr and cr⊕n 1
ci di → ci d , 1 ≤ k ≤ n.
4 1 >0 cr ar → cr âr d 2
cr⊕n 1 p′ → cr⊕n 1 p̄d 10 D′n,Reg(p)
Moreover, for erasing d we use the rules =0 cr p → cr d 2
cr⊕n 1 p′ → cr⊕n 1 p̄d 10 D′n,Reg(p)
ck d → ck , 1 ≤ k ≤ n.
2 >0 cr p̄ → cr p̂d 3
In the derivation mode max∆ob jects these erasing rules can cr⊕n 1 p → cr⊕n 1 d 9 D′n,Reg(p)
only be used at the end of a computation when no other
=0 cr d → cr (∗ )
rules can be applied any more.
cr⊕n 1 p̄ → cr⊕n 1 ss′ d 6 D′n,Reg(s)
The remaining rules in the set R of catalytic rules can
be captured from the description of how the simulation of 3 >0 cr p̂ → c1 qq′ d 2 D′n,Reg(q)
the register machine instructions works as described in the cr⊕n 1 âr → cr⊕n 1 d 4
following:
• p : (ADD (r) , q, s), with p ∈ BADD , q, s ∈ B, 1 ≤ r ≤ m. The the rule cr d → cr marked with (∗ ) is only ap-
plied in the derivation modes max∆ob jects max and
An ADD-instruction can be simulated in one step by
maxGENob jects max as well as maxGENob jects , whereas
letting every catalyst make one evolution step:
in the derivation mode max∆ob jects it will not be ap-
plied as it would decrease the difference between
cReg(p) p → cReg(p) qq′ ar dD′n,Reg(q) or
generated and consumed objects.
cReg(p) p → cReg(p) ss′ ar dD′n,Reg(s) ,
cReg(p)⊕n 1 p′ → c2 d 4 . • lh : HALT .
Taking into account that we have defined Reg(lh ) = 1,
We recall that all other catalysts ci with i ∈ [1..n] \ we take:
{Reg(p), Reg(p) ⊕n 1} are forced to apply the rule
ci di → ci d 4 . The dummy objects d are used to guar- c1 lh → c1 dd
antee that the rules given above, with in sum at least
c2 lh′ → c2 dd
5 objects on their right-hand sides, have priority over
the rules cr ar → cr âr d 2 , 1 ≤ r ≤ n, with in sum only
4 objects on their right-hand sides. After the register machine has halted (with the first n
registers being empty), which is simulated by the rules
above, finally all dummy objects generated during the sim- References
ulation steps before are deleted by using the rules
[1] Alhazov, A., Aman, B., Freund, R.: P systems with anti-
ci d → ci , 1 ≤ i ≤ n. matter. In: Gheorghe, M., Rozenberg, G., Salomaa, A.,
Sosík, P., Zandron, C. (eds.) Membrane Computing – 15th
Whereas in the derivation modes max∆ob jects max and
International Conference, CMC 2014, Prague, Czech Re-
maxGENob jects max as well as maxGENob jects some of these public, August 20–22, 2014, Revised Selected Papers. Lec-
objects d can already be erased during the simulation ture Notes in Computer Science, vol. 8961, pp. 66–85.
of SUB-instructions, see above, in the derivation mode Springer (2014). https://doi.org/10.1007/978-3-319-14370-
max∆ob jects , these erasing rules are only executed at the 5_5
end of the computation. These observations complete the [2] Alhazov, A., Aman, B., Freund, R., Păun, Gh.: Mat-
proof. ter and anti-matter in membrane systems. In: Jürgensen,
H., Karhumäki, J., Okhotin, A. (eds.) Descriptional Com-
As a consequence, we obtain the following result: plexity of Formal Systems – 16th International Work-
Corollary 3. Purely catalytic P systems working in any of shop, DCFS 2014, Turku, Finland, August 5–8, 2014. Pro-
the derivation modes max∆ob jects max, maxGENob jects max, ceedings. Lecture Notes in Computer Science, vol. 8614,
pp. 65–76. Springer (2014). https://doi.org/10.1007/978-3-
max∆ob jects , or maxGENob jects are computationally com-
319-09704-6_7
plete, i.e., they can compute any partial recursive relation
[3] Alhazov, A., Freund, R.: P systems with toxic objects. In:
on natural numbers.
Gheorghe, M., Rozenberg, G., Salomaa, A., Sosík, P., Zan-
Yet besides this computational completeness result, dron, C. (eds.) Membrane Computing – 15th International
the even more relevant achievement of the result estab- Conference, CMC 2014, Prague, Czech Republic, August
lished with Theorem 10 is the fact that, when we com- 20–22, 2014, Revised Selected Papers. Lecture Notes in
pare with the results given in (the proof of) Theorem 5, Computer Science, vol. 8961, pp. 99–125. Springer (2014).
https://doi.org/10.1007/978-3-319-14370-5_7
with all these new derivation modes, i.e., max∆ob jects max,
maxGENob jects max, max∆ob jects , and maxGENob jects , only [4] Alhazov, A., Freund, R.: Small catalytic P systems. In:
Dinneen, M. (ed.) Proceedings of the Workshop on Mem-
one catalyst for each decrementable register is needed,
brane Computing 2015 (WMC2015), (Satellite Workshop
which is an improvement of needing one catalyst less than
of UCNC2015), August 2015, CDMTCS Research Report
with the derivation mode max, and moreover the simula- Series, vol. 487, pp. 1–16. Centre for Discrete Mathematics
tion is deterministic, hence, no trapping is needed. and Theoretical Computer Science, Department of Com-
puter Science, University of Auckland, Auckland, New
Zealand (2015)
6 Conclusion
[5] Alhazov, A., Freund, R.: Variants of small universal P sys-
In this overview paper I have collected several classic as tems with catalysts. Fundam. Informaticae 138(1–2), 227–
well as many new results established just recently for sim- 250 (2015). https://doi.org/10.3233/FI-2015-1209
ple P systems working in variants of the maximally paral- [6] Alhazov, A., Freund, R., Ivanov, S.: Variants of energy-
lel derivation mode allowing for computational complete- controlled P systems. In: Proceedings of NIT 2016 (2016)
ness. In case of the parallel derivation modes (i) affect- [7] Alhazov, A., Freund, R., Ivanov, S.: Variants of P sys-
ing or (ii) generating the maximal number of objects or tems with activation and blocking of rules. Nat. Comput.
18(3), 593–608 (2019). https://doi.org/10.1007/s11047-
(iii) yielding the maximal difference between the objects
019-09747-5
in the current and the derived configuration, in simple
[8] Alhazov, A., Freund, R., Ivanov, S.: Catalytic P systems
catalytic P systems only one catalyst is needed to obtain
with weak priority of catalytic rules. In: Freund, R. (ed.)
computational completeness, which is the optimal result
Proceedings ICMC 2020, September 14–18, 2020, pp. 67–
with respect to the number of catalysts, because with non- 82. TU Wien (2020)
cooperative rules only semi-linear sets can be obtained. In
[9] Alhazov, A., Freund, R., Ivanov, S.: P systems with lim-
case of simple purely catalytic P systems at least one cata- iting the number of objects in membranes. In: Freund, R.
lyst less is needed than in the classic proofs showing com- (ed.) Proceedings ICMC 2020, September 14–18, 2020, pp.
putational completeness. 83–98. TU Wien (2020)
[10] Alhazov, A., Freund, R., Ivanov, S.: P systems with limited
Acknowledgements number of objects. Journal of Membrane Computing 3, 1–
9 (2021). https://doi.org/10.1007/s41965-020-00068-6
I am very grateful to Gheorghe Păun for involving me [11] Alhazov, A., Freund, R., Ivanov, S.: Variants of simple P
from the beginning in this new area of membrane sys- systems with one catalyst being computationally complete.
tems. Moreover, many results as presented above have In: Vaszil, Gy. (ed.) Proceedings ICMC 2021 (2021)
been developed together with my other co-authors, espe- [12] Alhazov, A., Freund, R., Ivanov, S.: When cat-
cially with my colleague Marion Oswald at the TU Wien alytic P systems with one catalyst can be computation-
and the “Moldovan team” Artiom Alhazov, Sergiu Ivanov, ally complete. Journal of Membrane Computing (2021).
and Sergey Verlan. https://doi.org/10.1007/s41965-021-00079-x
[13] Alhazov, A., Freund, R., Ivanov, S., Oswald, M.: Variants Rozenberg, G., Salomaa, A. (eds.) Membrane Comput-
of simple purely catalytic P systems with two catalysts. In: ing, Lecture Notes in Computer Science, vol. 8340, pp.
Vaszil, Gy. (ed.) Proceedings ICMC 2021 (2021) 173–188. Springer (2014). https://doi.org/10.1007/978-3-
[14] Alhazov, A., Freund, R., Ivanov, S., Verlan, S.: (Tis- 642-54239-8_13
sue) P systems with vesicles of multisets. In: Csuhaj- [26] Freund, R., Oswald, M.: Partial halting in P systems.
Varjú, E., Dömösi, P., Vaszil, Gy. (eds.) Proceedings Int. J. Found. Comput. Sci. 18(6), 1215–1225 (2007).
15th International Conference on Automata and For- https://doi.org/10.1142/S0129054107005261
mal Languages, AFL 2017, Debrecen, Hungary, Septem- [27] Freund, R., Oswald, M.: Catalytic and purely catalytic
ber 4-6, 2017. EPTCS, vol. 252, pp. 11–25 (2017). P automata: control mechanisms for obtaining compu-
https://doi.org/10.4204/EPTCS.252.6 tational completeness. In: Bensch, S., Drewes, F., Fre-
[15] Alhazov, A., Freund, R., Leporati, A., Oswald, M., Zan- und, R., Otto, F. (eds.) Fifth Workshop on Non-Classical
dron, C.: (Tissue) P systems with unit rules and energy Models for Automata and Applications – NCMA 2013,
assigned to membranes. Fundam. Informaticae 74(4), 391– Umeå, Sweden, August 13 – August 14, 2013, Proceed-
408 (2006) ings. books@ocg.at, vol. 294, pp. 133–150. Österreichis-
[16] Alhazov, A., Freund, R., Oswald, M., Verlan, S.: Par- che Computer Gesellschaft (2013)
tial halting and minimal parallelism based on arbitrary [28] Freund, R., Oswald, M., Păun, Gh.: Catalytic and purely
rule partitions. Fundam. Inform. 91(1), 17–34 (2009). catalytic P systems and P automata: Control mechanisms
https://doi.org/10.3233/FI-2009-0031 for obtaining computational completeness. Fundam. In-
[17] Alhazov, A., Freund, R., Sosík, P.: Small P systems with form. 136(1–2), 59–84 (2015). https://doi.org/10.3233/FI-
catalysts or anti-matter simulating generalized register ma- 2015-1144
chines and generalized counter automata. Comput. Sci. J. [29] Freund, R., Păun, Gh.: How to obtain computational
Moldova 23(3), 304–328 (2015) completeness in P systems with one catalyst. In: Neary,
[18] Alhazov, A., Freund, R., Verlan, S.: P systems working in T., Cook, M. (eds.) Proceedings Machines, Computations
maximal variants of the set derivation mode. In: Leporati, and Universality 2013, MCU 2013, Zürich, Switzerland,
A., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Mem- September 9–11, 2013. EPTCS, vol. 128, pp. 47–61 (2013).
brane Computing – 17th International Conference, CMC https://doi.org/10.4204/EPTCS.128.13
2016, Milan, Italy, July 25-29, 2016, Revised Selected [30] Freund, R., Păun, Gh., Pérez-Jiménez, M.J.: Polarization-
Papers. Lecture Notes in Computer Science, vol. 10105, less P systems with active membranes working in the min-
pp. 83–102. Springer (2017). https://doi.org/10.1007/978- imally parallel mode. In: Akl, S.G., Calude, C.S., Din-
3-319-54072-6_6 neen, M.J., Rozenberg, G., Wareham, T. (eds.) Uncon-
[19] Dassow, J., Păun, Gh.: Regulated Rewriting in Formal Lan- ventional Computation, 6th International Conference, UC
guage Theory. Springer (1989) 2007, Kingston, Canada, August 13-17, 2007, Proceedings.
[20] Freund, R.: Energy–controlled P systems. In: Păun, Gh., Lecture Notes in Computer Science, vol. 4618, pp. 62–76.
Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Springer (2007). https://doi.org/10.1007/978-3-540-73554-
Computing, pp. 247–260. Springer (2003) 0_8
[21] Freund, R.: Purely catalytic P systems: Two catalysts can [31] Freund, R., Rogozhin, Yu., Verlan, S.: P systems with
be sufficient for computational completeness. In: Alha- minimal left and right insertion and deletion. In: Durand-
zov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Yu. (eds.) Lose, J., Jonoska, N. (eds.) Unconventional Computation
CMC14 Proceedings – The 14th International Conference and Natural Computation – 11th International Conference,
on Membrane Computing, Chis, inău, August 20–23, 2013, UCNC 2012, Orléan, France, September 3–7, 2012. Pro-
pp. 153–166. Institute of Mathematics and Computer Sci- ceedings. Lecture Notes in Computer Science, vol. 7445,
ence, Academy of Sciences of Moldova (2013) pp. 82–93. Springer (2012). https://doi.org/10.1007/978-3-
642-32894-7_9
[22] Freund, R.: P automata: New ideas and results. In: Bor-
dihn, H., Freund, R., Nagy, B., Vaszil, Gy. (eds.) Eighth [32] Freund, R., Sosík, P.: On the power of catalytic P systems
Workshop on Non-Classical Models of Automata and Ap- with one catalyst. In: Rozenberg, G., Salomaa, A., Sem-
plications, NCMA 2016, Debrecen, Hungary, August 29– pere, J.M., Zandron, C. (eds.) Membrane Computing – 16th
30, 2016. Proceedings. books@ocg.at, vol. 321, pp. 13–40. International Conference, CMC 2015, Valencia, Spain, Au-
Österreichische Computer Gesellschaft (2016) gust 17–21, 2015, Revised Selected Papers. Lecture Notes
in Computer Science, vol. 9504, pp. 137–152. Springer
[23] Freund, R.: How derivation modes and halting condi-
(2015). https://doi.org/10.1007/978-3-319-28475-0_10
tions may influence the computational power of P sys-
tems. Journal of Membrane Computing 2(1), 14–25 (2020). [33] Freund, R., Verlan, S.: A formal framework for static (tis-
https://doi.org/10.1007/s41965-019-00028-9 sue) P systems. In: Eleftherakis, G., Kefalas, P., Păun,
Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Com-
[24] Freund, R., Kari, L., Oswald, M., Sosík, P.: Computation-
puting, Lecture Notes in Computer Science, vol. 4860, pp.
ally universal P systems without priorities: two catalysts
271–284. Springer (2007). https://doi.org/10.1007/978-3-
are sufficient. Theoretical Computer Science 330(2), 251–
540-77312-2_17
266 (2005). https://doi.org/10.1016/j.tcs.2004.06.029
[34] Freund, R., Verlan, S.: (Tissue) P systems work-
[25] Freund, R., Leporati, A., Mauri, G., Porreca, A.E., Ver-
ing in the k-restricted minimally or maximally parallel
lan, S., Zandron, C.: Flattening in (tissue) P systems. In:
transition mode. Nat. Comput. 10(2), 821–833 (2011).
Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Yu.,
https://doi.org/10.1007/s11047-010-9215-z
[35] Krithivasan, K., Păun, Gh., Ramanujan, A.: On controlled
P systems. Fundam. Inform. 131(3–4), 451–464 (2014).
https://doi.org/10.3233/FI-2014-1025
[36] Minsky, M.L.: Computation. Finite and Infinite Machines.
Prentice Hall, Englewood Cliffs, NJ (1967)
[37] Păun, Gh.: Computing with membranes. Journal of
Computer and System Sciences 61(1), 108–143 (2000).
https://doi.org/10.1006/jcss.1999.1693
[38] Păun, Gh.: Membrane Computing: An Introduction.
Springer (2002). https://doi.org/10.1007/978-3-642-56196-
2
[39] Păun, Gh., Rozenberg, G., Salomaa, A. (eds.): The Ox-
ford Handbook of Membrane Computing. Oxford Univer-
sity Press (2010)
[40] Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal
Languages. Springer (1997). https://doi.org/10.1007/978-
3-642-59136-5
[41] Sosík, P., Langer, M.: Small (purely) catalytic
P systems simulating register machines. Theo-
retical Computer Science 623, 65–74 (2016).
https://doi.org/10.1016/j.tcs.2015.09.020
[42] The P Systems Website. http://ppage.psystems.eu/