Information Technology Reference
In-Depth Information
3
Introduction to NEPs
Networks of evolutionary processors (NEPs) [1] are a new computing mechanism
directly inspired in the behaviour of cell populations. Each cell contains its own
genetic information (represented by a set of strings of symbols) that is changed by
some
evolutive
transformations implemented as elemental operations on strings.
Cells are interconnected and can exchange information (strings) with other cells.
A NEP can be defined as a graph whose nodes are processors which perform
very simple operations on strings and send the resulting strings to other nodes.
Every node has filters that block some strings from being sent and/or received.
NEPs: Definitions and Key Features.
Following [1] we introduce the basic
definition of NEPs.
Definition 1.
A Network of Evolutionary Processors of size
n
is a construct:
Γ
=(
V, N
1
,N
2
, ..., N
n
,G
)
,
where:
-
V
is an alphabet.
-
For each 1
n
,
N
i
=(
M
i
,A
i
,PI
i
,PO
i
) is the i-th evolutionary node
processor of the network. The parameters of every processor are:
•
≤
i
≤
M
i
is a finite set of evolution rules of just one of the following forms:
i.
a
→
b
,where
a, b
∈
V
(substitution rules),
ii.
a
→
ε
,where
a
∈
V
(deletion rules),
iii.
ε
→
a
,where
a
∈
V
(insertion rules).
•
A
i
is a finite set of strings over
V
.Theset
A
i
is the set of initial strings
in the
i
-th node.
•
PI
i
and
PO
i
are subsets of
V
∗
respectively representing the input and
the output filters. These filters are defined by the membership condition,
namely a string
w
∈
V
∗
can pass the input filter (the output filter) if
w ∈ PI
i
(
w
∈
PO
i
). In this paper we will use two kind of filters:
∗
Those defined as two components (
P, F
)of
P
ermitting and
F
orbidding
contexts (a word
w
passes the filter if (
α
(
w
)
⊆
P
)
∧
(
F
∩
α
(
w
)=
∅
),
where
α
represents the set of symbols of a given string).
∗
Those defined as regular expressions
r
(a word
w
passes the filter if
w
L
(
r
), where
L
(
r
) stands for the language defined by the regular
expression
r
).
∈
-
G
=(
,E
) is an undirected graph called the underlying
graph of the network. The edges of
G
, that is the elements of
E
,aregivenin
the form of sets of two nodes. The complete graph with
n
vertices is denoted
by
K
n
.
{
N
1
,N
2
,...,N
n
}
V
∗
for
A configuration of a NEP is an
n
-tuple
C
=(
L
1
,L
2
,...,L
n
), with
L
i
⊆
all 1
n
. It represents the sets of strings which are present in any node at
a given moment.
≤
i
≤
Search WWH ::
Custom Search