Information Technology Reference
In-Depth Information
Formally, we say that the configuration
C
is obtained in
one communication
step
from configuration
C
, written as
C
C
,iff
C
(
x
)=(
C
(
x
)
ϕ
β
(
{x,y}
)
(
C
(
x
)
,
\
(
N
(
{
x, y
}
))))
{x,y}∈E
G
ϕ
β
(
{x,y}
)
(
C
(
y
)
,
∪
(
N
(
{
x, y
}
)))
{x,y}∈E
G
for all
x
X
G
.
Note that a copy of a string remains in the sending node
x
only
if it not able to pass the filter of any edge connected to
x
.
Let
Γ
be an ANEPFC, the computation of
Γ
on the input string
w
∈
V
∗
∈
is a sequence of configurations
C
(
w
)
0
,C
(
w
)
1
,C
(
w
)
2
,...
,where
C
(
w
)
0
is the initial
configuration of
Γ
defined by
C
(
w
)
0
and
C
(
w
)
0
(
x
I
)=
{
w
}
(
x
)=
∅
for all
x
∈
X
G
,
=
x
I
,
C
(
w
)
2
i
C
(
w
)
2
i
+1
and
C
(
w
)
C
(
w
)
x
=
⇒
2
i
+1
2
i
+2
, for all
i
≥
0. By the previous
definitions, each configuration
C
(
w
)
i
is uniquely determined by the configuration
C
(
w
)
i−
1
. A computation as above is said to be an
accepting computation
if there
exists a configuration in which the set of strings existing in the output node
x
O
is non-empty. The
language accepted
by
Γ
is
L
(
Γ
)=
V
∗
|
{
w
∈
the computation of
Γ
on
w
is an accepting one
}
.
We denote by
L
(
AN EP F C
) the class of languages accepted by ANEPFCs.
3 Accepting Evolutionary P Systems
We now informally describe the P system we are going to investigate. An
Ac-
cepting evolutionary
P
system
(AEPS for short) of degree
m
is a construct
Π
=(
V, U, μ,
(
R
1
,ρ
1
)
,
···
,
(
R
m
,ρ
m
)),
where:
-
V
is the input alphabet,
U
V
is the working alphabet,
-
μ
is a membrane structure consisting of
m
membranes,
-
R
i
,1
⊇
m
is a finite set of
evolutionary and/or dissolving rules
over
U
associated with the
i
th region and
ρ
i
is a partial order relation over
R
i
specifying
the
priority
among the rules. An evolutionary rule is a 4-tuple (
a, b, α, β
)(or
a
≤
i
≤
b
α
→
)where
a, b
∈
U
∪{
λ
}
,
α
∈{
here,out,in
}
and
β
∈{∗
,l,r
}
. A dissolving
b
α
rule is 5-tuple (
a, b, α, β, δ
)(or
a
→
δ
), where
a, b, α, β
have the same meaning
as for evolutionary rules and
δ
∈
U
is the dissolving symbol.
b
α
in an arbitrary region of the system works
as follows: if there exists a string
w
in that region, such that
w
=
u
1
au
2
,then
w
is transformed into
u
1
bu
2
(observe that
β
establishes the way of applying
the evolutionary rule). Parameter
α
establishes where to send the new strings,
namely they are sent to the outer region, to all immediate inner regions (a copy
of each string is sent to all these regions), or remain in the same region, provided
that
β
is
out
,
in
,or
here
. If a string is to be sent to an inner region that does
not exist, then it remains where it is.
The application of a rule
a
→
Search WWH ::
Custom Search