Subshift of finite type
Encyclopedia
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 space
s are the subshifts of finite type.
be a finite set of 
symbols (alphabet), and 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. Let X 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 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
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:
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 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
.
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 model
s (n-letter generalizations of Ising model
s), 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 product topology, defined below); 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
.
on
, where
The basis for the topology of the shift of finite type are the cylinder set
s
The cylinder sets are clopen set
s. 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 space
s.
, 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
matrix 
for which all 
and
for all i. The stationary probability vector
has all 
and has
.
A Markov chain, as defined above, is said to be compatible with the shift of finite type if
whenever 
. The Markov measure of a cylinder set may then be defined by
The Kolmogorov-Sinai entropy with relation to the Markov measure is
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics
Symbolic dynamics
In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics given by the shift operator...
and ergodic theory
Ergodic theory
Ergodic theory is a branch of mathematics that studies dynamical systems with an invariant measure and related problems. Its initial development was motivated by problems of statistical physics....
. They also describe the set of all possible sequences executed by a finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
. The most widely studied shift space
Shift space
In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words representing the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms....
s are the subshifts of finite type.
Definition
Let be a finite set of symbols (alphabet), and let A be a adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
with entries in {0,1}. Using these elements we construct a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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 the sequence is a walk of the graph. Let T be the shift operator
Shift operator
In mathematics, and in particular functional analysis, the shift operator or translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag 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
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:
The shift operator
Shift operator
In mathematics, and in particular functional analysis, the shift operator or translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag 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 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
Bernoulli scheme
In mathematics, the Bernoulli scheme or Bernoulli shift is a generalization of the Bernoulli process to more than two possible outcomes. Bernoulli schemes are important in the study of dynamical systems, as most such systems exhibit a repellor that is the product of the Cantor set and a smooth...
without the measure
Measure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...
.
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 model
Potts model
In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. By studying the Potts model, one may gain insight into the behaviour of ferromagnets and certain other phenomena of solid state physics...
s (n-letter generalizations of Ising model
Ising model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
s), 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 product topology, defined below); the partition function
Partition function (statistical mechanics)
Partition functions describe the statistical properties of a system in thermodynamic equilibrium. It is a function of temperature and other parameters, such as the volume enclosing a gas...
and Hamiltonian
Hamiltonian mechanics
Hamiltonian mechanics is a reformulation of classical mechanics that was introduced in 1833 by Irish mathematician William Rowan Hamilton.It arose from Lagrangian mechanics, a previous reformulation of classical mechanics introduced by Joseph Louis Lagrange in 1788, but can be formulated without...
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
Quantum finite automata
In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be defined, including measure-once and measure-many automata...
.
Topology
The subshift of finite type has a natural topology, derived from the product topologyProduct topology
In topology and related areas of mathematics, a product space is the cartesian product of a family of topological spaces equipped with a natural topology called the product topology...
on
, whereThe basis for the topology of the shift of finite type are the cylinder set
Cylinder set
In mathematics, a cylinder set is the natural open set of a product topology. Cylinder sets are particularly useful in providing the base of the natural topology of the product of a countable number of copies of a set...
s
The cylinder sets are clopen set
Clopen set
In topology, a clopen set in a topological space is a set which is both open and closed. That this is possible for a set is not as counter-intuitive as it might seem if the terms open and closed were thought of as antonyms; in fact they are not...
s. Every open set in the subshift of finite type is a countable union of cylinder sets. In particular, the shift T is a homeomorphism
Homeomorphism
In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...
; 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 compactCompact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
metric space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s.
Measure
A subshift of finite type may be endowed with any one of several different measuresMeasure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...
, thus leading to a measure-preserving dynamical system
Measure-preserving dynamical system
In mathematics, a measure-preserving dynamical system is an object of study in the abstract formulation of dynamical systems, and ergodic theory in particular.-Definition:...
. A common object of study is the Markov measure, which is an extension of a Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
to the topology of the shift.
A Markov chain is a pair (P,π) consisting of the transition matrix, an
matrix for which all andfor all i. The stationary probability vector
has all and has.A Markov chain, as defined above, is said to be compatible with the shift of finite type if
whenever . The Markov measure of a cylinder set may then be defined byThe Kolmogorov-Sinai entropy with relation to the Markov measure is
See also
- Transfer operatorTransfer operatorIn mathematics, the transfer operator encodes information about an iterated map and is frequently used to study the behavior of dynamical systems, statistical mechanics, quantum chaos and fractals...
- De Bruijn graphDe Bruijn graphIn graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence...
- Quantum finite automataQuantum finite automataIn quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be defined, including measure-once and measure-many automata...