|
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. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics on Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ...
In engineering and mathematics, a dynamical system is a deterministic process in which a functions value changes over time according to a rule that is defined in terms of the functions current value. ...
In mathematics, symbolic dynamics is the practice of modelling a dynamical system by a space consisting of infinite sequences of abstract symbols, each sequence corresponding to a state of the system, and a shift operator corresponding to the dynamics. ...
In mathematics, a measure-preserving transformation T on a probability space is said to be ergodic if the only measurable sets invariant under T have measure 0 or 1. ...
Fig. ...
Definition Let be a finite set of symbols, and let A be a adjacency matrix with entries in {0,1}. The pair (V,A) then form a directed graph, with V the set of vertices, and A defining the set of edges E. 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. In mathematics and computer science, the adjacency matrix for a finite graph on n vertices is an n × n matrix in which entry aij is the number of edges from vi to vj in . ...
This article just presents the basic definitions. ...
In mathematics, and in particular functional analysis, the shift operators are examples of linear operators, important for their simplicity and natural occurrence. ...
This is a page about mathematics. ...
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: This is a page about mathematics. ...
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. In mathematics, and in particular functional analysis, the shift operators are examples of linear operators, important for their simplicity and natural occurrence. ...
- (T(x))j = xj + 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 finte 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. In mathematics, the Bernoulli scheme is a generalization of the Bernoulli process to more than two possible outcomes. ...
In mathematics, a measure is a function that assigns a number, e. ...
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). Some subshifts can be characterized by a transition matrix, as above; such subshifts are then called subshifts of finite type. Often, this distintion 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. In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice. ...
The Ising model, named after the physicist Ernst Ising, is a model in statistical mechanics. ...
In statistical mechanics, the partition function Z is an important quantity that encodes the statistical properties of a system in thermodynamic equilibrium. ...
Hamiltonian mechanics is a re-formulation of classical mechanics that was invented in 1833 by William Rowan Hamilton. ...
Topology The subshift of finite type has a natural topology, derived from the product topology on , where Topology (Greek topos, place and logos, study) is a branch of mathematics concerned with the study of topological spaces. ...
In topology, the cartesian product of topological spaces is turned into a topological space in the following way. ...
The basis of the topology of the shift of finite type are the cylinder sets 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. In topology, a clopen set (or closed-open set) in a topological space is a set which is both open and closed. ...
In mathematics the term countable set is used to describe the size of a set, e. ...
In the mathematical field of topology a homeomorphism or topological isomorphism (from the Greek words homeos = identical and morphe = shape) is a special isomorphism between topological spaces which respects topological properties. ...
In topology and related areas of mathematics a continuous function is a morphism between topological spaces; that is, a mapping which preserves the topological structure. ...
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. The p-adic number systems were first described by Kurt Hensel in 1897. ...
Compact as a general noun can refer to: Look up Compact on Wiktionary, the free dictionary a diplomatic contract or covenant among parties, sometimes known as a pact, treaty, or an interstate compact; a British term for a newspaper format; In mathematics, it can refer to various concepts: Mostly commonly...
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined. ...
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. In mathematics, a measure is a function that assigns a number, e. ...
In mathematics, a measure-preserving dynamical system is an object of study in the abstract formulation of ergodic theory. ...
In mathematics, a (discrete-time) Markov chain, named after Andrei Markov, is a discrete-time stochastic process with the Markov property. ...
A Markov chain is a pair (P,π) consisting of the transition matrix, an matrix P = (pij) for which all and
for all i. The stationary probability vector π = (πi) has all and has - .
A Markov chain, as defined above, is said to be compatible with the shift of finite type if pij = 0 whenever Aij = 0. The Markov measure of a cylinder set may then be defined by The Kolmogorov-Sinai entropy with relation to the Markov measure is
See also In 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. ...
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.)
|
Feeds |
Contact