Symbolic dynamical system

Definition

Let

𝒜 = {(A_{i})}_{i = 0}^{\infty}

be a sequence of alphabets. Denote by

\bar{𝒜^{*}}

the set of all (finite and infinite) words where the

i

-th letter is from

A_{i}

. A symbolic space is a closed subspace

X \subseteq \bar{𝒜^{*}}

with metric

d (u, v) ≔ 2^{- min {i \in ℕ | u_{i} \neq v_{i}}} .

In particular,

\bar{𝒜^{ℕ}}

is a symbolic product space.

Note The isolated points of a symbolic space are precisely the finite words.

Note A symbolic product space space is equivalent to the product space of discrete spaces.

Note

The symbolic space

\bar{𝟐^{*}}

can be (injectively but non-surjectively) mapped to

𝕀 = [0, 1]

ψ (u) ≔ 3^{- | u |} + \sum_{i = 1}^{| u |} 2 u_{i - 1} 3^{- i} .

Definition

Let

X \subseteq 𝒜^{ℕ}

. A cylinder around a finite word

u \in 𝒜^{*}

[u] ≔ {x \in X | x_{⟦ 0, | u | ⦈} = u} .

Theorem

The clopen sets in a symbolic product space are precisely the finite unions of cylinders.

Definition

A full shift is the system

(A^{ℕ}, σ)

, where

A

is an alphabet and

{σ (x)}_{i} ≔ x_{i + 1}

. A subshift is a subsystem of a full shift; i.e.

(Σ, σ)

, where

Σ

is closed and

σ

-invariant.

Theorem

Let

F \subseteq A^{*}

be a set of “forbidden words”. Then

Σ_{F} ≔ {x \in A^{ℕ} | \forall u \in F, u ⋢ F}

is a subshift, where

u ⊑ v

denotes that

u

is a factor of

v

Definition

A language

L \subseteq A^{*}

is extendable if

$\forall u \in L, \forall v ⊑ u, v \in L;$
$\forall u \in L, \exists a \in A, u a \in L .$

Definition

The subshift of an extendable language

L \subseteq A^{*}

𝒮 (L) ≔ {x \in A^{ℕ} | \forall n \geq 0, x_{⟦ 0, n ⦈} \in L} .

Definition

The language of a subshift

Σ \subseteq A^{ℕ}

ℒ (Σ) ≔ {u \in A^{*} | \exists x \in Σ, u ⊑ x};

ℒ^{n} (Σ) ≔ ℒ (Σ) \cap A^{n} .

Definition

The language of a sequence

x \in A^{ℕ}

ℒ (x) ≔ {u \in A^{*} | u ⊑ x},

ℒ^{n} (x) ≔ ℒ (x) \cap A^{n} .

Theorem

L \subseteq A^{*}

is an extendable language, then

𝒮 (L)

is a subshift and

ℒ (𝒮 (L)) = L

Theorem

Σ \subseteq A^{ℕ}

is a subshift, then

ℒ (Σ)

is an extendable language and

𝒮 (ℒ (Σ)) = Σ

Theorem

x \in A^{ℕ}

is a sequence, then

ℒ (x)

is an extendable language and

𝒮 (ℒ (Σ)) = \bar{𝒪 (x)}

Definition

A subshift

Σ \in A^{ℕ}

is a subshift of finite type (SFT) if there exists a finite set

F

of “forbidden words” such that

Σ = Σ_{F}

. An SFT has order

p \geq 2

F

can be chosen such that

F \subseteq A^{p}

. If

p = 2

Σ

is a Markov subshift.

Theorem Parry

A subshift

Σ \subseteq A^{ℕ}

is an SFT iff

(Σ, σ)

is open.

Theorem

Any SFT is conjugate to a Markov SFT.

ℒ^{p - 1} (Σ)

Definition

A transition graph is an oriented graph

(A, E)

such that

\forall a \in A, \exists b \in A, (a, b) \in E

Definition

The graph of a Markov subshift

Σ

is defined by

(a, b) \in E ⟺ a b \in ℒ^{2} (Σ)

ℒ^{1} (Σ) = A

Definition

The subshift of a transition graph

(A, E)

Σ_{E} ≔ {u \in A^{ℕ} | \forall i \geq 0, (u_{i}, u_{i + 1}) \in E} .

Bibliography