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 \Lambda of, where A 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 A is any non-empty set and \mathbb{G} is any monoid.

Definition

Let \mathbb{G} be a monoid, and given, denote the operation of g with h by the product gh. Let denote the identity of \mathbb{G}. Consider a non-empty set A (an alphabet) with the discrete topology, and define as the set of all patterns over A indexed by \mathbb{G}. For and a subset, we denote the restriction of \mathbf{x} to the indices of N as. On, we consider the prodiscrete topology, which makes a Hausdorff and totally disconnected topological space. In the case of A being finite, it follows that is compact. However, if A is not finite, then is not even locally compact. This topology will be metrizable if and only if \mathbb{G} 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 i\in D, let a_i\in A. The cylinder given by D and is the set When D={g}, we denote the cylinder fixing the symbol b at the entry indexed by g simply as [b]_g. 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 A is a set that is closed under the topology of and invariant under translations, i.e., for all. We consider in the shift space \Lambda the induced topology from, which has as basic open sets the cylinders. For each k\in\N^*, define, and. An equivalent way to define a shift space is to take a set of forbidden patterns and define a shift space as the set Intuitively, a shift space X_F is the set of all infinite patterns that do not contain any forbidden finite pattern of F.

Language of shift space

Given a shift space and a finite set of indices, let , where \epsilon stands for the empty word, and for let be the set of all finite configurations of A^N that appear in some sequence of \Lambda, i.e., Note that, since \Lambda is a shift space, if is a translation of, i.e., M=gN for some , then if and only if there exists such that w_j=v_i if j=gi. In other words, and contain the same configurations modulo translation. We will call the set the language of \Lambda. In the general context stated here, the language of a shift space has not the same mean of that in Formal Language Theory, but in the classical framework which considers the alphabet A being finite, and \mathbb{G} being \mathbb{N} or \mathbb{Z} with the usual addition, the language of a shift space is a formal language.

Classical framework

The classical framework for shift spaces consists of considering the alphabet A as finite, and \mathbb{G} as the set of non-negative integers (\mathbb{N}) with the usual addition, or the set of all integers (\mathbb{Z}) with the usual addition. In both cases, the identity element corresponds to the number 0. Furthermore, when, since all can be generated from the number 1, it is sufficient to consider a unique shift map given by for all n. On the other hand, for the case of , since all \mathbb{Z} can be generated from the numbers {-1, 1}, it is sufficient to consider two shift maps given for all n by and by. Furthermore, whenever \mathbb{G} is \mathbb{N} or \mathbb{Z} with the usual addition (independently of the cardinality of A), due to its algebraic structure, it is sufficient consider only cylinders in the form Moreover, the language of a shift space will be given by where and \epsilon stands for the empty word, and In the same way, for the particular case of, it follows that to define a shift space \Lambda=X_F we do not need to specify the index of \mathbb{G} on which the forbidden words of F are defined, that is, we can just consider and then However, if, if we define a shift space \Lambda=X_F as above, without to specify the index of where the words are forbidden, then we will just capture shift spaces which are invariant through the shift map, that is, such that. In fact, to define a shift space such that it will be necessary to specify from which index on the words of F are forbidden. In particular, in the classical framework of A being finite, and \mathbb{G} being \mathbb{N}) or \mathbb{Z} with the usual addition, it follows that M_F is finite if and only if F is finite, which leads to classical definition of a shift of finite type as those shift spaces such that \Lambda=X_F for some finite F.

Some types of shift spaces

Among several types of shift spaces, the most widely studied are the shifts of finite type and the sofic shifts. In the case when the alphabet A is finite, a shift space \Lambda is a shift of finite type if we can take a finite set of forbidden patterns F such that \Lambda=X_F, and \Lambda is a sofic shift if it is the image of a shift of finite type under sliding block code (that is, a map \Phi that is continuous and invariant for all g-shift maps ). If A is finite and \mathbb{G} is \mathbb{N} or \mathbb{Z} with the usual addition, then the shift \Lambda is a sofic shift if and only if W(\Lambda) is a regular language. The name "sofic" was coined by, based on the Hebrew word סופי meaning "finite", to refer to the fact that this is a generalization of a finiteness property. When A is infinite, it is possible to define shifts of finite type as shift spaces \Lambda for those one can take a set F of forbidden words such that is finite and \Lambda=X_F. In this context of infinite alphabet, a sofic shift will be defined as the image of a shift of finite type under a particular class of sliding block codes. Both, the finiteness of M_F and the additional conditions the sliding block codes, are trivially satisfied whenever A is finite.

Topological dynamical systems on shift spaces

Shift spaces are the topological spaces on which symbolic dynamical systems are usually defined. Given a shift space and a g-shift map it follows that the pair is a topological dynamical system. Two shift spaces and are said to be topologically conjugate (or simply conjugate) if for each g-shift map it follows that the topological dynamical systems and are topologically conjugate, that is, if there exists a continuous map such that. Such maps are known as generalized sliding block codes or just as sliding block codes whenever \Phi is uniformly continuous. Although any continuous map \Phi from to itself will define a topological dynamical system, in symbolic dynamics it is usual to consider only continuous maps which commute with all g-shift maps, i. e., maps which are generalized sliding block codes. The dynamical system is known as a **'generalized **cellular automaton****' (or just as a cellular automaton whenever \Phi is uniformly continuous).

Examples

The first trivial example of shift space (of finite type) is the full shift A^\mathbb N. Let A={a,b}. The set of all infinite words over A containing at most one b is a sofic subshift, not of finite type. The set of all infinite words over A whose b form blocks of prime length is not sofic (this can be shown by using the pumping lemma). The space of infinite strings in two letters, is called the Bernoulli process. It is isomorphic to the Cantor set. The bi-infinite space of strings in two letters, is commonly known as the Baker's map, or rather is homomorphic to the Baker's map.

Footnotes