In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words that represent the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms. The most widely studied shift spaces are the subshifts of finite type and the sofic shifts.
In the classical framework a shift space is any subset of , where is a finite set, which is closed for the Tychonov topology and invariant by translations. More generally one can define a shift space as the closed and translation-invariant subsets of , where is any non-empty set and is any monoid.
Let be a monoid, and given , denote the operation of with by the product . Let denote the identity of . Consider a non-empty set (an alphabet) with the discrete topology, and define as the set of all patterns over indexed by . For and a subset , we denote the restriction of to the indices of as .
On , we consider the prodiscrete topology, which makes a Hausdorff and totally disconnected topological space. In the case of being finite, it follows that is compact. However, if is not finite, then is not even locally compact.
This topology will be metrizable if and only if is countable, and, in any case, the base of this topology consists of a collection of open/closed sets (called cylinders), defined as follows: given a finite set of indices , and for each , let . The cylinder given by and is the set
When , we denote the cylinder fixing the symbol at the entry indexed by simply as .
In other words, a cylinder is the set of all set of all infinite patterns of which contain the finite pattern .
Given , the g-shift map on is denoted by and defined as
A shift space over the alphabet is a set that is closed under the topology of and invariant under translations, i.e., for all . We consider in the shift space the induced topology from , which has as basic open sets the cylinders .
For each , define , and .