SUBSHIFT OF FINITE TYPE

(Redirected from Shift of finite type)
In mathematics, 'subshifts of finite type' are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type.

Contents

Definition

Terminology

Generalizations

Topology

Metric

Measure

See also

References

Definition

Let $V$ be a finite set of $n$ symbols (alphabet), and let ''A'' be a $n\; imes\; n$ 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''. Let ''X'' be the set of all infinite 'admissible' sequences of edges, where by ''admissible'' it is meant that that the sequence is a walk of the graph. Let ''T'' be the shift operator on this sequence; it plays the role of the time-evolution operator of the dynamical system. The 'subshift of finite type' is then defined as the pair (''X'', ''T''). 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, jinmathbb{N}
ight}.
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, jinmathbb{Z}
ight}.
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.
:$(T(x))\_\{j\}=x\_\{j+1\}.$
Clearly this map is only invertible in the case of the two-sided shift.
A subshift of finite type is called 'transitive' if 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.

Terminology

By convention, the term 'shift' is understood to refer to the full ''n''-shift. A 'subshift' is then any subspace of the full shift that is shift-invariant (that is, a subspace that is invariant under the action of the shift operator), non-empty, and closed for the product topology defined below. Some subshifts can be characterized by a transition matrix, as above; such subshifts are then called subshifts of finite type. Often, this distinction is relaxed, and subshifts of finite type are called simply 'shifts of finite type'. Subshifts of finite type are also sometimes called 'topological Markov shifts'.

Generalizations

A 'sofic system' is a subshift of finite type where different edges of the transition graph may correspond to the same symbol.
A 'renewal system' is defined to be the set of all infinite concatenations of a finite set of finite words.
Subshifts of finite type are identical to free (non-interacting) one-dimensional Potts models (''n''-letter generalizations of Ising models), with certain nearest-neighbor configurations excluded. Interacting Ising models are defined as subshifts together with a continuous function of the configuration space (continuous with respect to the topology defined in this article); the partition function and Hamiltonian are explicitly expressible in terms of this function.
Subshifts may be quantized in a certain way, leading to the idea of the quantum finite automata.

Topology

The subshift of finite type has a natural topology, derived from the product topology on $V^mathbb\{Z\}$, where
:$V^mathbb\{Z\}=\; Pi\_\{n\; in\; mathbb\{Z\}\}\; V\; =\; \{\; x=(ldots,x\_\{-1\},x\_0,x\_1,ldots)\; :$
x_k in V ; orall k in mathbb{Z} }
The basis of the topology of the shift of finite type are the cylinder sets
:$C\_t[a\_0,\; ldots,\; a\_s]=\; \{x\; in\; V^mathbb\{Z\}\; :$
x_t = a_0, ldots ,x_{t+s} = a_s }
The cylinder sets are clopen sets. Every open set in the subshift of finite type is a countable union of cylinder sets. In particular, the shift ''T'' is a homeomorphism; that is, it is continuous with respect to this topology.

Metric

A variety of different metrics can be defined on a shift space. One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common; this is the p-adic metric. In fact, both the one- and two-sided shift spaces are compact metric spaces.

Measure

A subshift of finite type may be endowed with any one of several different measures, thus leading to a measure-preserving dynamical system. A common object of study is the 'Markov measure', which is an extension of a Markov chain to the topology of the shift.
A Markov chain is a pair (''P'',π) consisting of the 'transition matrix', an $n\; imes\; n$ matrix $P=(p\_\{ij\})$ for which all $p\_\{ij\}\; ge\; 0$ and
:$sum\_\{j=1\}^np\_\{ij\}=1$
for all ''i''. The 'stationary probability vector' $pi=(pi\_i)$ has all $pi\_\{ij\}\; ge\; 0$ and has
:$sum\_\{i=1\}^n\; pi\_i\; p\_\{ij\}=\; pi\_j$.
A Markov chain, as defined above, is said to be 'compatible' with the shift of finite type if $p\_\{ij\}\; =\; 0$ whenever $A\_\{ij\}\; =\; 0$. The 'Markov measure' of a cylinder set may then be defined by
:$mu(C\_t[a\_0,ldots,a\_s])\; =\; pi\_\{a\_0\}\; p\_\{a\_0,a\_1\}\; cdots\; p\_\{a\_\{s-1\},\; a\_s\}$
The Kolmogorov-Sinai entropy with relation to the Markov measure is
:$s\_mu\; =\; -sum\_\{i=1\}^n\; pi\_i\; sum\_\{j=1\}^n\; p\_\{ij\}\; log\; p\_\{ij\}$

See also

★ Transfer operator

★ De Bruijn graph

★ Quantum finite automata

References

★ Natasha Jonoska, ''Subshifts of Finite Type, Sofic Systems and Graphs'', (2000).

★ Douglas Lind and Brian Marcus, ''An Introduction to Symbolic Dynamics and Coding''

★ Michael S. Keane, ''Ergodic theory and subshifts of finite type'', (1991), appearing as Chapter 2 in ''Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces'', Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). ISBN 0-19-853390-X ''(Provides a short expository introduction, with exercises, and extensive references.)''

★ David Damanik, ''Strictly Ergodic Subshifts and Associated Operators'', (2005)