Shift space

Let ${\displaystyle \mathbb {G} }$ be a monoid, and given ${\displaystyle g,h\in \mathbb {G} }$, denote the operation of ${\displaystyle g}$ with ${\displaystyle h}$ by the product ${\displaystyle gh}$. Let ${\displaystyle \mathbf {1} _{\mathbb {G} }}$ denote the identity of ${\displaystyle \mathbb {G} }$. Consider a non-empty set ${\displaystyle A}$ (an alphabet) with the discrete topology, and define ${\displaystyle A^{\mathbb {G} }}$ as the set of all patterns over ${\displaystyle A}$ indexed by ${\displaystyle \mathbb {G} }$. For ${\displaystyle \mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }}$ and a subset ${\displaystyle N\subset \mathbb {G} }$, we denote the restriction of ${\displaystyle \mathbf {x} }$ to the indices of ${\displaystyle N}$ as ${\displaystyle \mathbf {x} _{N}:=(x_{i})_{i\in N}}$.

On ${\displaystyle A^{\mathbb {G} }}$, we consider the prodiscrete topology, which makes ${\displaystyle A^{\mathbb {G} }}$ a Hausdorff and totally disconnected topological space. In the case of ${\displaystyle A}$ being finite, it follows that ${\displaystyle A^{\mathbb {G} }}$ is compact. However, if ${\displaystyle A}$ is not finite, then ${\displaystyle A^{\mathbb {G} }}$ is not even locally compact.

This topology will be metrizable if and only if ${\displaystyle \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 ${\displaystyle D\subset \mathbb {G} }$, and for each ${\displaystyle i\in D}$, let ${\displaystyle a_{i}\in A}$. The cylinder given by ${\displaystyle D}$ and ${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$ is the set

${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.}$

When ${\displaystyle D=\{g\}}$, we denote the cylinder fixing the symbol ${\displaystyle b}$ at the entry indexed by ${\displaystyle g}$ simply as ${\displaystyle [b]_{g}}$.

In other words, a cylinder ${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}}$ is the set of all set of all infinite patterns of ${\displaystyle A^{\mathbb {G} }}$ which contain the finite pattern ${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$.

Given ${\displaystyle g\in \mathbb {G} }$, the g-shift map on ${\displaystyle A^{\mathbb {G} }}$ is denoted by ${\displaystyle \sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }}$ and defined as

${\displaystyle \sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }}$.

A shift space over the alphabet ${\displaystyle A}$ is a set ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ that is closed under the topology of ${\displaystyle A^{\mathbb {G} }}$ and invariant under translations, i.e., ${\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda }$ for all ${\displaystyle g\in \mathbb {G} }$.[note 1] We consider in the shift space ${\displaystyle \Lambda }$ the induced topology from ${\displaystyle A^{\mathbb {G} }}$, which has as basic open sets the cylinders ${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda }$.

For each ${\displaystyle k\in \mathbb {N} ^{*}}$, define ${\displaystyle {\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}}$, and ${\displaystyle {\mathcal {N}}_{A^{\mathbb {G} }}^{f}:=\bigcup _{k\in \mathbb {N} }{\mathcal {N}}_{k}=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }A^{N}}$. An equivalent way to define a shift space is to take a set of forbidden patterns ${\displaystyle F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}}$ and define a shift space as the set

${\displaystyle X_{F}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ \forall N\subset \mathbb {G} ,\forall g\in \mathbb {G} ,\ \left(\sigma ^{g}(\mathbf {x} )\right)_{N}=\mathbf {x} _{gN}\notin F\}.}$

Intuitively, a shift space ${\displaystyle X_{F}}$ is the set of all infinite patterns that do not contain any forbidden finite pattern of ${\displaystyle F}$.

Given a shift space ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ and a finite set of indices ${\displaystyle N\subset \mathbb {G} }$, let ${\displaystyle W_{\emptyset }(\Lambda ):=\{\epsilon \}}$, where ${\displaystyle \epsilon }$ stands for the empty word, and for ${\displaystyle N\neq \emptyset }$ let ${\displaystyle W_{N}(\Lambda )\subset A^{N}}$ be the set of all finite configurations of ${\displaystyle A^{N}}$ that appear in some sequence of ${\displaystyle \Lambda }$, i.e.,

${\displaystyle W_{N}(\Lambda ):=\{(w_{i})_{i\in N}\in A^{N}:\ \exists \ \mathbf {x} \in \Lambda {\text{ s.t. }}x_{i}=w_{i}\ \forall i\in N\}.}$

Note that, since ${\displaystyle \Lambda }$ is a shift space, if ${\displaystyle M\subset \mathbb {G} }$ is a translation of ${\displaystyle N\subset \mathbb {G} }$, i.e., ${\displaystyle M=gN}$ for some ${\displaystyle g\in \mathbb {G} }$, then ${\displaystyle (w_{j})_{j\in M}\in W_{M}(\Lambda )}$ if and only if there exists ${\displaystyle (v_{i})_{i\in N}\in W_{N}(\Lambda )}$ such that ${\displaystyle w_{j}=v_{i}}$ if ${\displaystyle j=gi}$. In other words, ${\displaystyle W_{M}(\Lambda )}$ and ${\displaystyle W_{N}(\Lambda )}$ contain the same configurations modulo translation. We will call the set

${\displaystyle W(\Lambda ):=\bigcup _{N\subset \mathbb {G}  \atop \#N<\infty }W_{N}(\Lambda )}$

the language of ${\displaystyle \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 ${\displaystyle A}$ being finite, and ${\displaystyle \mathbb {G} }$ being ${\displaystyle \mathbb {N} }$ or ${\displaystyle \mathbb {Z} }$ with the usual addition, the language of a shift space is a formal language.

The classical framework for shift spaces consists of considering the alphabet ${\displaystyle A}$ as finite, and ${\displaystyle \mathbb {G} }$ as the set of non-negative integers (${\displaystyle \mathbb {N} }$) with the usual addition, or the set of all integers (${\displaystyle \mathbb {Z} }$) with the usual addition. In both cases, the identity element ${\displaystyle \mathbf {1} _{\mathbb {G} }}$ corresponds to the number 0. Furthermore, when ${\displaystyle \mathbb {G} =\mathbb {N} }$, since all ${\displaystyle \mathbb {N} \setminus \{0\}}$ can be generated from the number 1, it is sufficient to consider a unique shift map given by ${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$ for all ${\displaystyle n}$. On the other hand, for the case of ${\displaystyle \mathbb {G} =\mathbb {Z} }$, since all ${\displaystyle \mathbb {Z} }$ can be generated from the numbers {-1, 1}, it is sufficient to consider two shift maps given for all ${\displaystyle n}$ by ${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$ and by ${\displaystyle \sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}}$.

Furthermore, whenever ${\displaystyle \mathbb {G} }$ is ${\displaystyle \mathbb {N} }$ or ${\displaystyle \mathbb {Z} }$ with the usual addition (independently of the cardinality of ${\displaystyle A}$), due to its algebraic structure, it is sufficient consider only cylinders in the form

${\displaystyle [a_{0}a_{1}...a_{n}]:=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.}$

Moreover, the language of a shift space ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ will be given by

${\displaystyle W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),}$

where ${\displaystyle W_{0}:=\{\epsilon \}}$ and ${\displaystyle \epsilon }$ stands for the empty word, and

${\displaystyle W_{n}(\Lambda ):=\{((a_{i})_{i=0,..n}\in A^{n}:\ \exists \mathbf {x} \in \Lambda \ s.t.\ x_{i}=a_{i}\ \forall i=0,...,n\}.}$

In the same way, for the particular case of ${\displaystyle \mathbb {G} =\mathbb {Z} }$, it follows that to define a shift space ${\displaystyle \Lambda =X_{F}}$ we do not need to specify the index of ${\displaystyle \mathbb {G} }$ on which the forbidden words of ${\displaystyle F}$ are defined, that is, we can just consider ${\displaystyle F\subset \bigcup _{n\geq 1}A^{n}}$ and then

${\displaystyle X_{F}=\{\mathbb {x} \in A^{\mathbb {Z} }:\ \forall i\in \mathbb {Z} ,\ \forall k\geq 0,\ (x_{i}...x_{i+k})\notin F\}.}$

However, if ${\displaystyle \mathbb {G} =\mathbb {N} }$, if we define a shift space ${\displaystyle \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 ${\displaystyle \sigma (X_{F})=X_{F}}$. In fact, to define a shift space ${\displaystyle X_{F}\subset A^{\mathbb {N} }}$ such that ${\displaystyle \sigma (X_{F})\subsetneq X_{F}}$ it will be necessary to specify from which index on the words of ${\displaystyle F}$ are forbidden.

In particular, in the classical framework of ${\displaystyle A}$ being finite, and ${\displaystyle \mathbb {G} }$ being ${\displaystyle \mathbb {N} }$) or ${\displaystyle \mathbb {Z} }$ with the usual addition, it follows that ${\displaystyle M_{F}}$ is finite if and only if ${\displaystyle F}$ is finite, which leds to classical definition of a shift of finite type as those shift spaces ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ such that ${\displaystyle \Lambda =X_{F}}$ for some finite ${\displaystyle F}$.

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 ${\displaystyle A}$ is finite, a shift space ${\displaystyle \Lambda }$ is a shift of finite type if we can take a finite set of forbidden patterns ${\displaystyle F}$ such that ${\displaystyle \Lambda =X_{F}}$, and ${\displaystyle \Lambda }$ is a sofic shift if it is the image of a shift of finite type under sliding block code[1] (that is, a map ${\displaystyle \Phi }$ that is continuous and invariant for all ${\displaystyle g}$-shift maps ). If ${\displaystyle A}$ is finite and ${\displaystyle \mathbb {G} }$ is ${\displaystyle \mathbb {N} }$ or ${\displaystyle \mathbb {Z} }$ with the usual addition, then the shift ${\displaystyle \Lambda }$ is a sofic shift if and only if ${\displaystyle W(\Lambda )}$ is a regular language.

The name "sofic" was coined by Weiss (1973), based on the Hebrew word סופי meaning "finite", to refer to the fact that this is a generalization of a finiteness property.[4]

When ${\displaystyle A}$ is infinite, it is possible to define shifts of finite type as shift spaces ${\displaystyle \Lambda }$ for those one can take a set ${\displaystyle F}$ of forbidden words such that

${\displaystyle M_{F}:=\{g\in \mathbb {G} :\ \exists N\subset \mathbb {G} {\text{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},}$

is finite and ${\displaystyle \Lambda =X_{F}}$.[3] 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.[3] Both, the finiteness of ${\displaystyle M_{F}}$ and the additional conditions the sliding block codes, are trivially satisfied whenever ${\displaystyle A}$ is finite.

Shift spaces are the topological spaces on which symbolic dynamical systems are usually defined.

Given a shift space ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ and a ${\displaystyle g}$-shift map ${\displaystyle \sigma ^{g}:\Lambda \to \Lambda }$ it follows that the pair ${\displaystyle (\Lambda ,\sigma ^{g})}$ is a topological dynamical system.

Two shift spaces ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ and ${\displaystyle \Gamma \subset B^{\mathbb {G} }}$ are said to be topologically cojugate (or simply conjugate) if for each ${\displaystyle g}$-shift map it follows that the topological dynamical systems ${\displaystyle (\Lambda ,\sigma ^{g})}$ and ${\displaystyle (\Gamma ,\sigma ^{g})}$ are topologically cojugate, that is, if there exists a continuous map ${\displaystyle \Phi$ :\Lambda \to \Gamma } such that ${\displaystyle \Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi }$. Such maps are known as generalized sliding block codes or just as sliding block codes whenever ${\displaystyle \Phi }$ is uniformly continuous.[3]

Although any continuous map ${\displaystyle \Phi }$ from ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ to itself will define a topological dynamical system ${\displaystyle (\Lambda ,\Phi )}$, in symbolic dynamics it is usual to consider only continuous maps ${\displaystyle \Phi$ :\Lambda \to \Lambda } which commute with all ${\displaystyle g}$-shift maps, i. e., maps which are generalized sliding block codes. The dynamical system ${\displaystyle (\Lambda ,\Phi )}$ is known as a 'generalized cellular automaton' (or just as a cellular automaton whenever ${\displaystyle \Phi }$ is uniformly continuous).

The first trivial example of shift space (of finite type) is the full shift ${\displaystyle A^{\mathbb {N} }}$.

Let ${\displaystyle 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, ${\displaystyle \{0,1\}^{\mathbb {N} }}$ is called the Bernoulli process. It is isomorphic to the Cantor set.

The bi-infinite space of strings in two letters, ${\displaystyle \{0,1\}^{\mathbb {Z} }}$ is commonly known as the Baker's map, or rather is homomorphic to the Baker's map.

• Tent map
• Bit shift map
• Gray code

• Ceccherini-Silberstein, T.; Coornaert, M. (2010). Cellular automata and groups Springer Monographs in Mathematics. Springer Verlag. ISBN 978-3-642-14034-1.
• Lind, Douglas; Marcus, Brian (1995). An Introduction to Symbolic Dynamics and Coding. Cambridge UK: Cambridge University Press. ISBN 0-521-55900-6.
• Lothaire, M. (2002). "Finite and Infinite Words". Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0-521-81220-8. Retrieved 2008-01-29.
• Morse, Marston; Hedlund, Gustav A. (1938). "Symbolic Dynamics". American Journal of Mathematics. 60 (4): 815–866. doi:10.2307/2371264. JSTOR 2371264.
• Sobottka, M. (2022). "Some Notes on the Classification of Shift Spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts". Bulletin of the Brazilian Mathematical Society. New Series. 53 (3): 981–1031. arXiv:2010.10595. doi:10.1007/s00574-022-00292-x. S2CID 254048586.