Information Technology Reference
In-Depth Information
There is no bi-infinite path along nodes of
AG
91
.This means that the set
S
91
generated by ECA rule 91 is empty. All the nodes of the graph
AG
91
are unnec-
essary. Thus the minimization leads to completely eliminate the
AG
91
graph.
Example 3. The ECA local rule 74
. This rule is such that the set of all length
3 left-forbidden blocks is
F
3
(74) =
{
101
,
110
,
111
}
. The
AG
74
graph of rule 74
is the following:
The bi-infinite paths along nodes of
AG
74
graph give rise to bi-infinite strings in
which each 1 is followed and preceded at least by two 0's. We can minimize the
AG
74
graph removing node 11 and the edge (01
,
11).
Now we can express dynamical CA properties over
S
f
by properties of its
associated subgraph
AG
f
. In particular, the following results hold concerning
the existence and the cardinality of a subshift generated by a CA.
