Information Technology Reference
In-Depth Information
In order to study the dynamical behavior of a CA we introduce the notion
of De Bruijn graph.
Definition 3.
The De Bruijn graph B
(
r, A
)
associated to any A,r,f CA is
the pair A
2
r
,E, where E
=
{
(
x, y
)
| x, y ∈A
2
r
s.t. x
2
=
y
1
,... ,x
2
r
=
y
2
r−
1
}.
This graph is common to any CA, independently from the particular analyti-
cal form of the local rule
f
. But if we consider one particular CA, then the edges
of the above De Bruijn graph can be labelled by letters of the alphabet
A
using
the local rule
f
of the involved CA. Precisely, the label of each edge (
x, y
)
∈ E
is
defined as
l
(
x, y
):=
f
(
x
1
,x
2
,... ,x
2
r
,y
2
r
)
∈A
. This labelled De Bruijn graph
will be denoted by
B
f
(
r, A
). If we read a configuration
x
as a bi-infinite path
along nodes of
B
f
(
r, A
), the next time configuration
F
f
(
x
) is the resulting path
along the corresponding labels. Therefore we can say that the labelled De Bruijn
graph associated to a CA describes its one step forward global dynamics.
Furthermore, in order to represent the CA subshift,we consider the subgraph
AG
f
:=
A
2
r
,E
of its De Bruijn graph, making use of an edge validation func-
tion to suppress those edges which represent forbidden blocks of the subshift, i.e.,
E
=
{
(
x, y
)
| x, y ∈A
2
r
s.t. x
2
=
y
1
,... ,x
2
r
=
y
2
r−
1
,
(
x
1
,x
2
,... ,x
2
r
,y
2
r
)
∈
F
2
r
+1
(
f
)
}
. Trivially, bi-infinite paths along nodes on the graph
AG
f
correspond
to bi-infinite strings of the subshift
S
f
.
In the general case we can minimize the subgraph
AG
f
removing all the
unnecessary nodes. From now on we will consider only minimized graphs.
Example 1. The ECA local rule 170
. This rule is such that the set of all length
3 left-forbidden blocks is
F
3
(170) =
∅
.Thusthe
AG
170
graph coincides with the
associated “complete” De Bruijn graph in which each edge is labelled according
to the local rule
f
170
.
The set
S
170
generated by ECA rule 170 coincides with the whole phase space
{
0
,
1
}
Z
. Then the global next state function induced by the ECA local rule 170
is the
full
shift map
σ
.
Example 2. The ECA local rule 91
. This CA local rule has 000, 100, 101, 110
and 111 as left-forbidden blocks. The
AG
91
graph of rule 91 is the following:
