Shift Of Finite Type
   HOME

TheInfoList



OR:

In mathematics, subshifts of finite type are used to model
dynamical systems In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in ...
, and in particular are the objects of study in
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 ( ...
and ergodic theory. They also describe the set of all possible sequences executed by a
finite state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
. The most widely studied shift spaces are the subshifts of finite type.


Definition

Let V be a finite set of n symbols (alphabet). Let ''X'' denote the set V^\mathbb of all bi-infinite sequences of elements of ''V'' together with the
shift operator In mathematics, and in particular functional analysis, the shift operator also known as translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator. Shift ...
''T''. We endow ''V'' with the
discrete topology In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest t ...
and ''X'' with the
product 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. This topology differs from another, perhaps more natural-seem ...
. A symbolic flow or subshift is a closed ''T''-invariant subset ''Y'' of ''X'' Xie (1996) p.21 and the associated language ''L''''Y'' is the set of finite subsequences of ''Y''.Xie (1996) p.22 Now let A be an n\times n
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...
with entries in . Using these elements we construct a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...
''G''=(''V'',''E'') with ''V'' the set of vertices and ''E'' the set of edges containing the directed edge x \rightarrow y in ''E'' if and only if A_=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, and the sequence can be either one-sided or two-sided infinite. Let ''T'' be the left 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 (''Y'', ''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 sequences of edges as :\Sigma_^ = \left\. 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_ = \left\. The
shift operator In mathematics, and in particular functional analysis, the shift operator also known as translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator. Shift ...
''T'' maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e. :\displaystyle(T(x))_=x_. 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.


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, subshifts of finite type are called simply shifts of finite type. Subshifts of finite type are also sometimes called topological Markov shifts.


Examples

Many chaotic
dynamical system In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water i ...
s are isomorphic to subshifts of finite type; examples include systems with transverse homoclinic connections,
diffeomorphism In mathematics, a diffeomorphism is an isomorphism of smooth manifolds. It is an invertible function that maps one differentiable manifold to another such that both the function and its inverse are differentiable. Definition Given tw ...
s of closed manifolds with a positive metric entropy, the Prouhet–Thue–Morse system, the Chacon system (this is the first system shown to be weakly mixing but not strongly mixing), Sturmian systems and Toeplitz systems. Matthew Nicol and Karl Petersen, (2009)
Ergodic Theory: Basic Examples and Constructions
, ''Encyclopedia of Complexity and Systems Science'', Springer https://doi.org/10.1007/978-0-387-30440-3_177


Generalizations

A sofic system is an image of a subshift of finite type where different edges of the transition graph may be mapped to the same symbol. It may be regarded as the set of labellings of paths through an
automaton An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
: a subshift of finite type then corresponds to an automaton which is deterministic.Pytheas Fogg (2002) p.205 Such systems correspond to regular languages. Context-free systems are defined analogously, and are generated by
phrase structure grammar The term phrase structure grammar was originally introduced by Noam Chomsky as the term for grammar studied previously by Emil Post and Axel Thue ( Post canonical systems). Some authors, however, reserve the term for more restricted grammars in ...
s. A renewal system is defined to be the set of all infinite concatenations of some fixed finite collection of finite words. Subshifts of finite type are identical to free (non-interacting) one-dimensional
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 phen ...
s (''n''-letter generalizations of
Ising model The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
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.


Topology

A subshift has a natural topology, derived from the
product 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. This topology differs from another, perhaps more natural-seem ...
on V^\mathbb, where :V^\mathbb= \Pi_ V = \ and ''V'' is given the
discrete topology In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest t ...
. A basis for the topology of V^\mathbb, which induces the topology of the subshift, is the family of cylinder sets :C_t _0, \ldots, a_s \ The cylinder sets are
clopen set In topology, a clopen set (a portmanteau of closed-open set) in a topological space is a set which is both open and closed. That this is possible may seem counter-intuitive, as the common meanings of and are antonyms, but their mathematical d ...
s in V^\mathbb. Every open set in V^\mathbb is a
countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
union of cylinder sets. Every open set in the subshift is the intersection of an open set of V^\mathbb with the subshift. With respect to this topology, the shift ''T'' is a
homeomorphism In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomor ...
; that is, with respect to this topology, it is continuous with continuous inverse. The space V^\mathbb is homeomorphic to a
Cantor set In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883. T ...
.


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 space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...
s.


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 A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
to the topology of the shift. A Markov chain is a pair (''P'',π) consisting of the transition matrix, an n \times n matrix P=(p_) for which all p_ \ge 0 and :\sum_^np_=1 for all ''i''. The stationary probability vector \pi=(\pi_i) has all \pi_ \ge 0,\sum \pi_i = 1 and has :\sum_^n \pi_i p_= \pi_j. A Markov chain, as defined above, is said to be compatible with the shift of finite type if p_ = 0 whenever A_ = 0. The Markov measure of a cylinder set may then be defined by :\mu(C_t _0,\ldots,a_s = \pi_ p_ \cdots p_ The Kolmogorov–Sinai entropy with relation to the Markov measure is :s_\mu = -\sum_^n \pi_i \sum_^n p_ \log p_


Zeta function

The
Artin–Mazur zeta function In mathematics, the Artin–Mazur zeta function, named after Michael Artin and Barry Mazur, is a function that is used for studying the iterated functions that occur in dynamical systems and fractals. It is defined from a given function f as th ...
is defined as the formal power series :\zeta(z)=\exp (\sum_^\infty \left, \textrm (T^n)\ \frac ), where Fix(''T''''n'') is the set of fixed points of the ''n''-fold shift. It has a product formula :\zeta(z) = \prod_\gamma (1-z^)^ \ where γ runs over the closed orbits.Brin & Stuck (2002) p.60 For subshifts of finite type, the zeta function is a
rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be ...
of ''z'':Brin & Stuck (2002) p.61 :\zeta(z) = (\det(I-zA))^ \ .


See also

* Transfer operator * De Bruijn graph * Quantum finite automata *
Axiom A In mathematics, Smale's axiom A defines a class of dynamical systems which have been extensively studied and whose dynamics is relatively well understood. A prominent example is the Smale horseshoe map. The term "axiom A" originates with Stephen Sm ...


Notes


References

* * David Damanik,
Strictly Ergodic Subshifts and Associated Operators
', (2005) * *
Natasha Jonoska Natasha (russian: Наташа) is a name of Slavic origin. The Slavic name is the diminutive form of Natalia. Notable people * Natasha, the subject of '' Natasha's Story'', a 1994 nonfiction book * Natasha Aguilar (1970–2016), Costa Rican sw ...
,
Subshifts of Finite Type, Sofic Systems and Graphs
', (2000). * 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). ''(Provides a short expository introduction, with exercises, and extensive references.)'' * * *


Further reading

* {{DEFAULTSORT:Subshift Of Finite Type Ergodic theory Automata (computation) Markov processes Combinatorics on words Symbolic dynamics