Subshift of Finite Type - Definition

Definition

Let be a finite set of symbols (alphabet). Let X denote the set VZ of all bi-infinite sequences of elements of V with T the shift operator. We endow V with the discrete topology and X with the product topology. A symbolic flow or subshift is a closed shift-invariant subset Y of (X,T), and the associated language LY is the set of finite subsequences of Y.

Now let A be a adjacency matrix with entries in {0,1}. Using these elements we construct a directed graph G=(V,E) with V the set of vertices, the set of edges E defined with A: so x→y is in E iff Ax,y=1. Let Y be the set of all infinite admissible sequences of edges, where by admissible it is meant that the sequence is a walk of the graph. Let T be the shift operator on such sequences; it plays the role of the time-evolution operator of the dynamical system. A subshift of finite type is then defined as a pair (X, T) obtained in this way. If the sequence extends to infinity in only one direction, it is called a one-sided subshift of finite type, and if it is bilateral, it is called a two-sided subshift of finite type.

Formally, one may define the sequence of edges as

\Sigma_{A}^{+} = \left\{ (x_0,x_1,\ldots): x_j \in V, A_{x_{j}x_{j+1}}=1, j\in\mathbb{N} \right\}.

This is the space of all sequences of symbols such that the symbol p can be followed by the symbol q only if the (p,q)th entry of the matrix A is 1. The space of all bi-infinite sequences is defined analogously:

\Sigma_{A} = \left\{ (\ldots, x_{-1},x_0,x_1,\ldots): x_j \in V, A_{x_{j}x_{j+1}}=1, j\in\mathbb{Z} \right\}.

The shift operator T maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e.

Clearly this map is only invertible in the case of the two-sided shift.

A subshift of finite type is called transitive if G is strongly connected: there is a sequence of edges from any one vertex to any other vertex. It is precisely transitive subshifts of finite type which correspond to dynamical systems with orbits that are dense.

An important special case is the full n-shift: it has a graph with an edge that connects every vertex to every other vertex; that is, all of the entries of the adjacency matrix are 1. The full n-shift corresponds to the Bernoulli scheme without the measure.

Read more about this topic:  Subshift Of Finite Type

Famous quotes containing the word definition:

    “No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
    —Florence Nightingale (1820–1910)

    “Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.”
    —Willard Van Orman Quine (b. 1908)

    “It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
    —Jane Adams (20th century)