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:

    “... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
    —Adrienne Rich (b. 1929)

    “I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)