=Paper=
{{Paper
|id=None
|storemode=property
|title=Natural Computing Modelling of the Polynomial Space Turing Machines
|pdfUrl=https://ceur-ws.org/Vol-1356/paper_63.pdf
|volume=Vol-1356
|dblpUrl=https://dblp.org/rec/conf/icteri/AmanC15
}}
==Natural Computing Modelling of the Polynomial Space Turing Machines==
https://ceur-ws.org/Vol-1356/paper_63.pdf
Natural Computing Modelling of the
Polynomial Space Turing Machines
Bogdan Aman and Gabriel Ciobanu
Romanian Academy, Institute of Computer Science
Blvd. Carol I no.11, 700506 Iaşi, Romania
baman@iit.tuiasi.ro, gabriel@info.uaic.ro
Abstract. In this paper we consider a bio-inspired description of the
polynomial space Turing machines. For this purpose we use membrane
computing, a formalism inspired by the way living cells are working.
We define and use logarithmic space systems with active membranes,
employing a binary representation in order to encode the positions on
the Turing machine tape.
Keywords. Natural computing, membrane computing, Turing machines.
Key Terms. MathematicalModel, Research.
1 Introduction
Membrane computing is a branch of the natural computing inspired by the archi-
tecture and behaviour of living cells. Various classes of membrane systems (also
called P systems) have been defined in [12], together with their connections to
other computational models. Membrane systems are characterized by three fea-
tures: (i) a membrane structure consisting of a hierarchy of membranes (which
are either disjoint or nested), with an unique top membrane called the skin; (ii)
multisets of objects associated with membranes; (iii) rules for processing the
objects and membranes. When membrane systems are seen as computing de-
vices, two main research directions are usually considered: computational power
in comparison with the classical notion of Turing computability (e.g., [2]), and
efficiency in algorithmically solving NP-complete problems in polynomial time
(e.g., [3]). Such efficient algorithms are obtained by trading space for time, with
the space grown exponentially in a linear time by means of bio-inspired op-
erations (e.g., membrane division). Thus, membrane systems define classes of
computing devices which are both powerful and efficient.
Related to the investigations of these research directions, there have been
studied several applications of these systems; among them, modelling of vari-
ous biological phenomena and the complexity and emergent properties of such
systems presented in [7]. In [4] it is presented the detailed functioning of the
sodium-potassium pump, while in [1] it is described and analyzed the immune
system in the formal framework of P systems.
In this paper we consider P systems with active membranes [11], and show
that they provide an interesting simulation of polynomial space Turing machines
by using only logarithmic space and a polynomial number of read-only input
objects.
2 Preliminaries
We consider P systems with active membranes extended with an input alphabet,
and such that the input objects cannot be created during the evolution [14]. The
original definition also includes dissolution and division rules, rules that are not
needed here. The version used in this paper is similar to evolution-communication
P systems used in [6] with additional read-only input objects and polarities.
Definition 1. A P system with active membranes and input objects is a tuple
Π = (Γ, ∆, Λ, µ; w1 , . . . , wd , R), where:
• d ≥ 1 is the initial degree;
• Γ is a finite non-empty alphabet of objects;
• ∆ is an input alphabet of objects such that ∆ ∩ Γ = ∅;
• Λ is a finite set of labels for membranes;
• µ is a membrane structure (i.e., a rooted unordered tree, usually represented
by nested brackets) in which each membrane is labelled by an element of Λ in
a one-to-one way, and possesses an attribute called electrical charge, which
can be either neutral (0), positive (+) or negative (-);
• w1 , . . . , wd are strings over Γ , describing the initial multisets of objects placed
in a number of d membranes of µ; notice that wi is assigned to membrane i;
• R is a finite set of rules over Γ ∪ ∆:
1. [a → w]α h object evolution rules
An object a ∈ Γ is rewritten into the multiset w, if a is placed inside
a membrane labelled by h with charge α. An object a can be deleted by
considering w the empty multiset ∅. Notice that these rules allow only to
rewritten objects from Γ , but not from ∆.
β
2. a[ ]α h → [b]h send-in communication rules
An object a is sent into a membrane labelled by h and with charge α,
becoming b; also, the charge of h is changed to β. If b ∈ ∆, then a = b
must hold.
β
3. [a]α h → b[ ]h send-out communication rules
An object a, placed into a membrane labelled by h and having charge α,
is sent out of membrane h and becomes b; simultaneously, the charge of
h is changed to β. If b ∈ ∆, then a = b must hold.
Each configuration Ci of a P system with active membranes and input objects is
described by the current membrane structure, including the electrical charges,
together with the multisets of objects located in the corresponding membranes.
The initial configuration of such a system is denoted by C0 . An evolution step
from the current configuration Ci to a new configuration Ci+1 , denoted by Ci ⇒
Ci+1 , is done according to the principles:
• Each object and membrane is involved in at most one communication rule
per step.
• Each membrane could be involved in several object evolution rules that can
be applied in parallel inside it.
• The application of rules is maximally parallel: the only objects and mem-
branes that do not evolve are those associated with no rule, or only to rules
that are not applicable due to the electrical charges.
• When several conflicting rules could be applied at the same time, a nonde-
terministic choice is performed; this implies that multiple configurations can
be reached as the result of an evolution step.
• In each computation step, all the chosen rules are applied simultaneously.
• Any object sent out from the skin membrane cannot re-enter it.
A halting evolution of such a system Π is a finite sequence of configurations
→
−
C = (C0 , . . . , Ck ), such that C0 ⇒ C1 ⇒ . . . ⇒ Ck , and no rules can be applied
→
−
any more in Ck . A non-halting evolution C = (Ci | i ∈ N) consists of an infinite
evolution C0 ⇒ C1 ⇒ . . ., where the applicable rules are never exhausted.
Example 1. Addition is trivial; we consider n objects a and m objects b placed
in a membrane 0 with charge +. The rule [b → a]+ says that an object b is
transformed in one object a. Such a rule is applied in parallel as many times
as possible. Consequently, all objects b are erased. The remaining number of
objects a represents the addition n + m. More examples can be found in [5].
In order to solve decision problems (i.e., decide languages over an alphabet
Σ), we use families of recognizer P systems Π = {Πx | x ∈ Σ ∗ } that respect
the following conditions: (1) all evolutions halt; (2) two additional objects yes
(successful evolution) and no (unsuccessful evolution) are used; (3) one of the
objects yes and no appears in the halting configuration [13]. Each input x is
associated with a P system Πx that decides the membership of x in the language
L ⊆ Σ ∗ by accepting or rejecting it. The mapping x ⊢ Πx must be efficiently
computable for each input length [10].
In this paper we use a logarithmic space uniformity condition [14].
Definition 2. A family of P systems Π = {Πx | x ∈ Σ ∗ } is said to be (L, L)-
uniform if the mapping x ⊢ Πx can be computed by two deterministic logarithmic
space Turing machines F (for “family”) and E (for “encoding”) as follows:
• F computes the mapping 1n ⊢ Πn , where Πn represents the membrane struc-
ture with some initial multisets and a specific input membrane, while n is
the length of the input x.
• E computes the mapping x ⊢ wx , where wx is a multiset encoding the specific
input x.
• Finally, Πx is Πn with wx added to the multiset placed inside its input mem-
brane.
In the following definition of space complexity adapted from [14], the input
objects do not contribute to the size of the configuration of a P system. In this
way, only the actual working space of the P system is measured, and P systems
working in sublinear space may be analyzed.
Definition 3. Given a configuration C, the space size |C| is defined as the sum
of the number of membranes in µ and the number of objects in Γ it contains.
→
− →
−
If C is a halting evolution of Π, then | C | = max{|C0 |, . . . , |Ck |} or, in the case
−
→ − →
of a non-halting evolution C , | C | = sup{|Ci | | i ∈ N}. The space required by Π
→ −
− →
itself is then |Π| = sup{| C | | C is an evolution of Π}.
Notice that |Π| = ∞ if Π has an evolution requiring infinite space or an infinite
number of halting evolutions that can occur such that for each k ∈ N there exists
at least one evolution requiring most than k steps..
3 A Membrane Structure for Simulation
Let M be a single-tape deterministic Turing machine working in polynomial
space s(n). Let Q be the set of states of M , including the initial state s; we denote
by Σ ′ = Σ ∪ {⊔} the tape alphabet which includes the blank symbol ⊔ 6∈ Σ.
A computation step is performed by using δ : Q × Σ ′ → Q × Σ ′ × {−1, 0, 1},
a (partial) transition function of M which we assume to be undefined on (q, σ)
if and only if q is a final state. We describe a uniform family of P systems
Π = {Πx | x ∈ Σ ∗ } simulating M in logarithmic space.
Let x ∈ Σ n be an input string, and let m = ⌈log s(n)⌉ be the minimum num-
ber of bits needed in order to write the tape cell indices 0, . . . , s(n)-1 in binary
notation. The P system Πn associated with the input length n and computed
as F (1n ) has a membrane structure consisting of |Σ ′ | · (m + 1) + 2 membranes.
The membrane structure contains:
– a skin membrane h;
– an inner membrane c (the input membrane) used to identify the symbol
needed to compute the δ function;
– for each symbol σ ∈ Σ ′ of M , the following set of membranes, linearly nested
inside c and listed inward:
• a membrane σ for each symbol σ of the tape alphabet Σ ′ of M ;
• for each j ∈ {0, . . . , (m − 1)}, a membrane labelled by j.
This labelling is used in order to simplify the notations. To respect the one-to-
one labelling from Definition 1, the membrane j can be labelled jσ . Thus in all
rules using membranes j, the σ symbol is implicitly considered. Furthermore,
the object z0 is located inside the skin membrane h.
The encoding of x, computed as E(x), consists of a set of objects describ-
ing the tape of M in its initial configuration on input x. These objects are the
symbols of x subscripted by their position bin(0), . . . , bin(n − 1) (where bin(i) is
the binary representation of i on m positions) in x, together with the s(n) − n
blank objects subscripted by their position bin(n), . . . , bin(s(n) − 1). The binary
representation, together with the polarities of the membranes, is essential when
the membrane system has to identify the symbol needed to simulate the δ func-
tion (e.g., rule (13)). The multiset E(x) is placed inside the input membrane c.
Figure 1 depicts an example.
0
0
0 0 0
0 0 0
0 0 0
1 1 1
0 0 0
a b ⊔
a00 b01 b10 ⊔11 z0
c
h
′
Fig. 1. Initial configuration of the P system Π3 with tape alphabet Σ = {a, b, ⊔},
working in space s(n) = n + 1 = 4 on the input abb.
During the first evolution steps of Πx , each input object σi is moved from
the input membrane c to the innermost membrane (m − 1) of the corresponding
membrane σ by means of the following communication rules:
σi [ ]0σ → [σi ]0σ for σ ∈ Σ ′ , bin(0) ≤ i < bin(s(n)) (1)
σi [ ]0j → [σi ]0j for σ ∈ Σ ′ , bin(0) ≤ i < bin(s(n)), 0 ≤ j < m (2)
Since only one communication rule per membrane can be applied during
each evolution step of Πx , all s(n) input objects pass through m membranes,
in order to reach the innermost membranes (m − 1), in at most l = s(n) + m
evolution steps. In the meantime, the subscript of object z0 is incremented up
to max{0, l − 3} before object zl−3 exits and enters membrane c changing the
membrane charge from 0 to +:
[zt → zt+1 ]0c for 0 ≤ t < l − 3 (3)
[zl−3 ]0c → zl−3 [ ]0c (4)
zl−3 [ ]0c → [zl−3 ]+
c (5)
The object zl−3 is rewritten to a multiset of objects containing an object z ′ (used
in rule (9)) and |Σ ′ | objects z+ (used in rules (7)
[zl−3 → z ′ z+ · · · z+ ]+
| {z } c (6)
|Σ ′ | copies
The objects z+ are used to change the charges from 0 to + for all membranes
σ ∈ Σ ′ using parallel communication rules, and then are deleted:
z+ [ ]0σ → [#]+
σ for σ ∈ Σ ′ (7)
[# → ∅]+
σ for σ ∈ Σ ′ (8)
In the meantime, the object z ′ is rewritten into z ′′ (in parallel with rule (7)),
and then, in parallel with rule (8), into s00 (where s is the initial state of M ):
[z ′ → z ′′ ]+
c (9)
[z ′′ → s00 ]+
c (10)
The configuration reached by Πx encodes the initial configuration of M :
0
+
+ + +
0 0 0
0 0 0
a00 b01 ⊔11
b10
1 1 1
0 0 0
a b ⊔
s00
c
h
Fig. 2. Configuration of Πx (from Figure 1) encoding the initial configuration of M on
input x = abb and using s(|x|) = 4 tape cells.
An arbitrary configuration of M on input x is encoded by a configuration
of Πx as it is described in Figure 3:
• membrane c contains the state-object qi , where q is the current state of M
and i ∈ {bin(0), . . . , bin(s(n) − 1)} is the current position of the tape head;
• membranes (m − 1) contain all input objects;
• all other membranes are empty;
• all membranes are neutrally charged, except those labelled by σ ∈ Σ ′ and
by c which all are positively charged.
We employ this encoding because the input objects must be all located in the
input membrane in the initial configuration of Πx (hence they must encode both
symbol and position on the tape), and they can never be rewritten.
0
+
+ + +
0 0 0
0 0 0
a00 b10 ⊔11
b01
1 1 1
q1 0 0 0
a b ⊔
q01
a a b c
0 1 2 3 h
Fig. 3. A configuration of M (from Figure 1) and the corresponding configuration of
Πx simulating it. The presence of b01 inside membrane 1 of a indicates that tape cell
1 of M contains the symbol a.
4 Simulating Polynomial Space Turing Machines
Starting from a configuration of the single-tape deterministic Turing machine
M , the simulation of a computation step of M by the membrane system Πx is
directed by the state-object qi . As stated above, qi encodes the current state
of M and the position of the head on the tape (in binary format). To simulate
the transition function δ of the Turing machine M in state q, it is necessary to
identify the actual symbol occurring at tape position i. In order to identify this
σi object from one of the (m − 1) membranes, the object qi is rewritten into |Σ ′ |
copies of qi′ , one for each membrane σ ∈ Σ ′ :
[qi → qi′ · · · qi′ ]+ q ∈ Q, bin(0) ≤ i < bin(s(n))
| {z } c (11)
|Σ ′ | copies
The objects qi′ first enter the symbol-membranes in parallel, without changing
the charges:
qi′ [ ]+ ′ +
σ → [qi ]σ for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)) (12)
The object qi′ traverses the membranes 0, . . . , (m − 1) while changing their
charges such that they represent the bits of i from the least to the most significant
one, where a positive charge is interpreted as 1 and a negative charge as 0.
− +
For instance, the charges of [[[ ]−
2 ]1 ]0 encode the binary number 001 (that is,
decimal 1). By the j-th bit of a binary number is understood the bit from the
j-th position when the number is read from right to left (e.g, the 0-th bit of the
binary number 001 is 1). The changes of charges are accomplished by the rules:
qi′ [ ]0j → [qi′ ]α
j for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)), 0 ≤ j < m, (13)
where α is − if the j-th bit of i is 0, and α is + if the j-th bit of i is 1.
The membranes j, where 0 ≤ j < m, behave now as “filters” for the input
objects σk occurring in membrane (m − 1): these objects are sent out from each
membrane j if and only if the j-th bit of k corresponds to the charge of j.
[σk ]α α
j → [ ]j σk for σ ∈ Σ ′ , bin(0) ≤ k < bin(s(n)), 0 < j < m, (14)
where α is − if the j-th bit of k is 0, and α is + if j-th bit of k is 1.
If an object σk reaches membrane 0, it is sent outside if the 0-th bit of k
corresponds to the charge of membrane 0. In order to signal that it is the symbol
occurring at location i of the tape, the charge of the corresponding membrane 0
is changed (either from + to − or from − to +). By applying the rules (15) to
(17), exactly one object σk , with k = i, will exit through membrane c:
[σk ]+ −
0 → [ ]0 σk for σ ∈ Σ ′ , bin(0) ≤ k < bin(s(n)),
(15)
[σk ]0 → [ ]+
−
0 σk for σ ∈ Σ ′ , bin(0) ≤ k < bin(s(n)),
where α is − if the j-th bit of k is 0, and α is + if the j-th bit of k is 1;
[σk ]+
τ → σk [ ]τ
−
for σ, τ ∈ Σ ′ , bin(0) ≤ k < bin(s(n)). (16)
After an σi exits from membrane c it gets blocked inside membrane h, by the
new charge of membrane c, until it is allowed to move to its new location accord-
ing to function δ of the Turing machine M . Thus, if another object τj reached
membrane σ due to the new charge of membrane 0 established by rule (15), τj is
contained in membrane σ until reintroduced in a membrane (m-1) using rule (2).
[σk ]+
c → σk [ ]c
−
for σ ∈ Σ ′ , bin(0) ≤ k < bin(s(n)) (17)
Since there are s(n) input objects, and each of them must traverse at most
(m + 1) membranes, the object σi reaches the skin membrane h after at most
l + 1 steps, where l is as defined in Section 3 before rule (3). While the input
objects are “filtered out”, the state-object qi′ “waits” for l steps using the rules:
′′ α
[qi′ → qi,1 ]m−1 for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)), α ∈ {−, +} (18)
′′
[qi,t → qi,t+1
′′
]α
m−1 for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)),
(19)
α ∈ {−, +}, 1 ≤ t ≤ l
′′
[qi,l+1 → qi′′ ]α for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)), α ∈ {−, +}
m−1
(20)
′′
In order to reach membrane c, the objects qi are sent out through membranes
j (0 < j ≤ m − 1) using rule (21), through membrane 0 by rules (22) and (24),
and through membranes σ ∈ Σ ′ by rule (23). While passing through all these
membranes, the charges are changed to neutral. This allows the input objects to
move back to the innermost membrane (m − 1) by using rules of type (2).
[qi′′ ]α 0 ′′
j → [ ]j qi for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n))
(21)
0 < j ≤ m − 1, α ∈ {−, +}
When qi′′ reaches the membranes 0, only one has the charge different from the
0-th bit of i, thus allowing qi′′ to identify the symbol in tape location i of M :
[qi′′ ]α 0 ′′′
0 → [ ]0 qi for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)), (22)
where α is − if the 0-th bit of i is 1, and α is + if the 0-th bit of i is 0.
0
σ → [ ]σ qi,σ,1
[qi′′′ ]− for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)) (23)
The other copies of qi′′ are sent out as objects # through membrane 0, and then
deleted by rules of type (8):
[qi′′ ]α 0
0 → [ ]0 # for σ ∈ Σ , q ∈ Q, bin(0) ≤ i < bin(s(n)),
′
(24)
where α is − if the 0-th bit of i is 0, and α is + if the 0-th bit of i is 1.
The state-object qi,σ,1 waits in membrane c for l steps, l representing an
upper bound of the number of steps needed for all the input objects to reach the
innermost membranes:
[qi,σ,t → qi,σ,t+1 ]−
c for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)), 1 ≤ t < l (25)
qi,σ,l [ ]0σ → [qi,σ,l ]+
σ for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)) (26)
+ +
[qi,σ,l ]σ → qi,σ [ ]σ for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n))
′
(27)
′
The state-object qi,σ now contains all the information needed to compute the
transition function δ of the Turing machine M . Suppose δ(q, σ) = (r, v, d) for
some d ∈ {−1, 0, +1}. Then qi,σ
′
sets the charge of membrane v to − and waits
for m + 1 steps, thus allowing σi to move to membrane (m − 1) of v by using
the rules (31), (32) and (2):
′
qi,σ [ ]+ ′ +
v → [qi,σ ]v for σ, v ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)) (28)
′
[qi,σ ]+
v → qi,σ,1 [ ]v
′ −
for σ ∈ Σ , q ∈ Q, bin(0) ≤ i < bin(s(n))
′
(29)
0
c → qi,σ,1 [ ]c for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n))
′
[qi,σ,1 ]− ′
(30)
σi [ ]0c → [σi ]0c for σ ∈ Σ ′ , bin(0) ≤ i < bin(s(n)) (31)
σi [ ]v → [σi ]v for σ, v ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n))
− −
(32)
′
[qi,σ,t → qi,σ,t+1
′
]0h for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n))
(33)
1≤t≤m
′
The object qi,σ,m+1 is used to change the charges of membranes c and v to +,
thus preparing the system for the next step of the simulation:
′
qi,σ,m+1 [ ]0c → [qi,σ,m+1
′
]+
c for σ ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)) (34)
v → [qi,σ,m+1 ]v for σ, v ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n)) (35)
′
qi,σ,m+1 [ ]− ′ −
+
v → qi,σ [ ]v for σ, v ∈ Σ ′ , q ∈ Q, bin(0) ≤ i < bin(s(n))
′
[qi,σ,m+1 ]− ′′
(36)
′′
Finally, the state-object qi,σ is rewritten to reflect the change of state and head
position, thus producing a configuration of Πx corresponding to the new config-
uration of M , as described in Section 3:
′′
[qi,σ → ri+d ]+
c for bin(0) ≤ i < bin(s(n)) (37)
The P system Πx is now ready to simulate the next step of M . If q ∈ Q is a final
state of M , we assume that δ(q, σ) is undefined for all σ ∈ Σ ′ ; thus we introduce
the following rules which halt the P system with the same result (acceptance or
rejection) as M :
[qi ]+ +
c → [ ]c yes for bin(0) ≤ i < bin(s(n)), if q is an accepting state (38)
[yes]0h → [ ]0h yes for bin(0) ≤ i < bin(s(n)), if q is an accepting state (39)
[qi ]+ +
c → [ ]c no for bin(0) ≤ i < bin(s(n)), if q is a rejecting state (40)
[no]0h → [ ]0h no for bin(0) ≤ i < bin(s(n)), if q is a rejecting state (41)
The simulation directly leads to the following result.
Theorem 1. Let M be a single-tape deterministic Turing machine working in
polynomial space s(n) and time t(n). Then there exists an (L, L)-uniform family
Π of P systems Πx with active membranes using object evolution and commu-
nication rules that simulates M in space O(log n) and time O(t(n)s(n)).
Proof. For each x ∈ Σ n , the P system Πx can be built from 1n and x in logarith-
mic space as it is described in Definition 2; thus, the family Π is (L, L)-uniform.
Each P system Πx uses only a logarithmic number of membranes and a constant
number of objects per configuration; thus, Πx works in space O(log n). Simu-
lating one of the t(n) steps of M requires O(s(n)) time, an upper bound to the
subscripts of objects used to introduce delays during the simulation; thus, the
total time is O(t(n)s(n)).
5 Conclusion
In this paper we provided a simulation of the polynomial space Turing ma-
chines by using logarithmic space P systems with active membranes and binary
representations for the positions on the tape. A similar approach is presented
in [9]. There are important differences in terms of technical details and effi-
cient representation; in comparison to [9], we improve the simulation by re-
ducing the number of membranes (by |Σ ′ | − 1) and the number of rules (by
|Σ ′ |·|Q|·s(n)·(5−|Σ ′ |)+|Σ ′ |·|Σ ′ |s(n)·(2·m+1)+|Q|·s(n)−|Σ ′ |·s(n)·(m+3)). In
particular, for the running example, the number of rules is reduced by 14·|Q|+84.
A different approach is presented in [8] where it is claimed that a constant space
is sufficient. However, in order to obtain the constant space space, input objects
(from ∆) are allowed to create other objects (from Γ ) leading to a different and
more powerful formalism than the one used by us in this paper, and making
such an approach not so interesting because of these unrealistic (powerful) input
objects.
References
1. B. Aman, G.Ciobanu. Describing the Immune System Using Enhanced Mobile
Membranes. Electronic Notes in Theoretical Computer Science 194, 5–18 (2008).
2. B. Aman, G.Ciobanu. Turing Completeness Using Three Mobile Membranes. Lec-
ture Notes in Computer Science 5715, 42–55 (2009).
3. B. Aman, G. Ciobanu. Mobility in Process Calculi and Natural Computing. Natural
Computing Series, Springer (2011).
4. D. Besozzi, G. Ciobanu. A P System Description of the Sodium-Potassium Pump.
Lecture Notes in Computer Science 3365, 210–223 (2004).
5. C. Bonchiş, G. Ciobanu, C. Izbaşa. Encodings and Arithmetic Operations in Mem-
brane Computing. Lecture Notes in Computer Science Volume 3959, 621–630
(2006).
6. M. Cavaliere. Evolution-Communication P Systems. Lecture Notes in Computer
Science 2597, 134–145 (2003).
7. G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez (Eds.). Applications of Membrane
Computing. Springer (2006).
8. A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron. Constant-Space
P Systems with Active Membranes. Fundamenta Informaticae 134(1–2), 111–128
(2014).
9. A. Leporati, G. Mauri, A.E. Porreca, C. Zandron. A Gap in the Space Hierar-
chy of P Systems With Active Membranes. Journal of Automata, Languages and
Combinatorics 19 (1-4), 173–184 (2014).
10. N. Murphy, D. Woods. The Computational Power of Membrane Systems Under
Tight Uniformity Conditions. Natural Computing 10, 613-632 (2011).
11. Gh. Păun. P Systems With Active Membranes: Attacking NP-complete Problems.
Journal of Automata, Languages and Combinatorics 6, 75-90 (2001).
12. Gh. Păun, G. Rozenberg, A. Salomaa (Eds.). The Oxford Handbook of Membrane
Computing, Oxford University Press (2010).
13. M.J. Pérez-Jiménez, A. Riscos-Núñez, A. Romero-Jiménez, D. Woods. Complexity-
Membrane Division, Membrane Creation. In [12], 302–336.
14. A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, Sublinear-Space P Systems with
Active Membranes. Lecture Notes in Computer Science 7762, 342–357 (2013).