Information Technology Reference
In-Depth Information
2. Strong transitive ECA subshifts are characterized by an
AG
f
subgraph of
the De Bruijn graphs which has a unique strongly connected component with
equal number of nodes and edges.
This kind of subshift is constituted by a finite number of mutually periodic
configurations and the cardinality of the subshift is equal to the cycle order
of the graph.
3. Mixing (but not strong transitive) ECA subshifts have infinite cardinality.
Theorem 3.
The following two statements are equivalent for ECA:
i) it is topological mixing, but not strongly transitive.
ii) it is D-chaotic.
By this theorem, infinite topological mixing subshifts are the only transitive
subshifts which are sensitive to initial conditions.
3 Transitivity on DTDS
Aswehaveseen,transitivityisthekeytostudythechaoticbehaviorofasubshift.
This fact holds also in the case of maps on a interval of real numbers; moreover
in the CA case transitivity implies sensitivity. We have renamed transitivity
as positive transitivity (see the introduction). We remark that if a DTDS is
positively transitive, then for any pair
A, B
of nonempty open subset of
X
both
the following conditions must hold:
∃n
1
∈
N :
g
n
1
(
A
)
∩ B
=
∅
PT1)
∃n
2
∈
N :
g
n
2
(
B
)
∩ A
=
∅
PT2)
Example 4. A non positively transitive DTDS.
Let
N
,g
s
be the DTDS where the phase space N is equipped with the trivial
metric
d
tr
: N
×
N
→
R
+
,
d
tr
(
x, y
)=1if
x
=
y
and
d
tr
(
x, y
) = 0 otherwise, and
g
s
: N
→
N is the successor function defined as follows:
∀x ∈
N
g
s
(
x
)=
x
+1.If
A
=
{
3
}
and
B
=
{
5
}
, there exists
n
1
= 2, s.t.
g
n
s
(
A
)
∩ B
=
∅
but there is no
integer
n
2
∈
N s.t.
g
n
s
(
B
)
∩ A
=
∅
.
In [2] one can find the following notion of transitivity renamed by us as
negatively
transitive
.
Definition 6.
A DTDS is said to be
negatively transitive
iff for any pair A, B
of nonempty open subsets of the phase space X, there exists an integer n ∈
N
such that g
−n
(
A
)
∩ B
=
∅.
It easy to show that the positive transitivity is equivalent to the negative one.
The existence of a dense orbit is not su
@
cient to guarantee the positive
transitivity of a DTDS as shown in the following examples.
