Information Technology Reference
In-Depth Information
Ta b l e 2 . 1 0
The bracket representation of the membrane system of Fig. 2.46
[
0
2
a
+
b
+
c
+[
1
a
+
c
+[
4
]
4
]
1
+[
5
]
5
+[
6
2
a
+
2
b
+
2
c
+[
2
]
2
+[
3
]
3
]
6
]
0
[
0
a
+
b
→
[
0
c
[
0
c
→
[
5
d
[
1
a
→
[
4
b
[
6
a
→
[
3
b
[
6
b
→
[
2
c
Usually, membrane systems are represented by means of Venn diagrams with
symbols and rules inside them. Many different notations can be used, very often
with a natural interpretation. However, when a multiset
m
inside a membrane of
index
i
is denoted by
[
m
]
i
, then we mean that
m
is all the content of
[]
i
, while we
write
[]
i
.
This notation is also called
boundary notation
and was introduced [65] in order
to cope with more general membrane rules. In fact, in Paun's original formulation,
rules are inside membranes and everything outside the membrane where a rule is lo-
cated remains unknown to the rule. But, in many cases a wider visibility is required.
The essential point of boundary representation is the idea of rules with a greater
level of localization knowledge about the objects which they apply to. An important
case of this situation is present in
anti-port rules
which postulate to consider objects
inside and outside membranes.
The example of Fig. 2.47 is not standard in membrane computing, but it is very
intuitive because it constitutes a membrane representation of a classical abacus for
performing sums.
Multiset rewriting with maximal parallel strategy means that at any step a set
of rules is chosen in a maximal way, because they can be simultaneously applied,
and no other rule can be applied together with them (and rules have to consume as
many objects as they can). This rewriting strategy provides universal computation
even in the case of only one membrane. The proof of this statement is given by
means of a membrane representation of register machines, in a formulation due
to Minsky (which are proved to be computationally universal). They use only two
types of instructions. Any instruction has a number as label (indicated on the left),
and applies when this label is equal to the content of the
program counter
(a special
register). Instruction
i
:
inc
k
j
increments the content of the register
R
k
and sets to
j
the value of the program counter. The instruction
i
:
condec
k
j
[
i
m
for indicating that
m
is a sub-multiset of the content of
h
decrements the
content of the register
R
k
, by putting
j
as the value of the program counter, if the
content of
R
k
is different from zero, while it does not alter any register, and sets to
h
the value of the program counter, if the content of
R
k
is zero.
Let us represent the register
R
k
containing the value
m
with the multiset of
m
copies of symbol
r
k
, and let us represent by the presence of symbol
P
i
the fact
,
