Shift space

Short description: Set of infinite words

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 $\mathrm{\Lambda }$ of $A^{\mathbb{\mathbb{Z}}}:=\{(x_i{)}_{i\in \mathbb{\mathbb{Z}}}:x_i\in A\mathrm{\forall }i\in \mathbb{\mathbb{Z}}\}$, 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 $A^{\mathbb{𝔾}}$, where $A$ is any non-empty set and $\mathbb{𝔾}$ is any monoid.

Definition

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

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

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

$[(a_i{)}_{i\in D}{]}_D:=\{\mathbf{𝐱}\in A^{\mathbb{𝔾}}:x_i=a_i,\mathrm{\forall }i\in D\}.$

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 $[(a_i{)}_{i\in D}{]}_D$ is the set of all set of all infinite patterns of $A^{\mathbb{𝔾}}$ which contain the finite pattern $(a_i{)}_{i\in D}\in A^{|D|}$.

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

${\sigma }^g((x_i{)}_{i\in \mathbb{𝔾}})=(x_{gi}{)}_{i\in \mathbb{𝔾}}$.

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

For each $k\in {\mathbb{\mathbb{N}}}^{*}$, define ${{𝒩}}_k:=\bigcup _{\genfrac{}{}{0ex}{}{N\subset \mathbb{𝔾}}{\mathrm{\#}N=k}}{A}^N$, and ${{𝒩}}_{A^{\mathbb{𝔾}}}^f:=\bigcup _{k\in \mathbb{\mathbb{N}}}{{𝒩}}_k=\bigcup _{\genfrac{}{}{0ex}{}{N\subset \mathbb{𝔾}}{\mathrm{\#}N<\mathrm{\infty }}}{A}^N$. An equivalent way to define a shift space is to take a set of forbidden patterns $F\subset {{𝒩}}_{A^{\mathbb{𝔾}}}^f$ and define a shift space as the set

$X_F:=\{\mathbf{𝐱}\in A^{\mathbb{𝔾}}:\mathrm{\forall }N\subset \mathbb{𝔾},\mathrm{\forall }g\in \mathbb{𝔾},{({\sigma }^g(\mathbf{𝐱}))}_N={\mathbf{𝐱}}_{gN}\notin F\}.$

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 $\mathrm{\Lambda }\subset A^{\mathbb{𝔾}}$ and a finite set of indices $N\subset \mathbb{𝔾}$, let $W_{\mathrm{\varnothing }}(\mathrm{\Lambda }):=\{ϵ\}$, where $ϵ$ stands for the empty word, and for $N\ne \mathrm{\varnothing }$ let $W_N(\mathrm{\Lambda })\subset A^N$ be the set of all finite configurations of $A^N$ that appear in some sequence of $\mathrm{\Lambda }$, i.e.,

$W_N(\mathrm{\Lambda }):=\{(w_i{)}_{i\in N}\in A^N:\mathrm{\exists }\mathbf{𝐱}\in \mathrm{\Lambda }\text{ s.t. }{x}_i=w_i\mathrm{\forall }i\in N\}.$

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

$W(\mathrm{\Lambda }):=\bigcup _{\genfrac{}{}{0ex}{}{N\subset \mathbb{𝔾}}{\mathrm{\#}N<\mathrm{\infty }}}{W}_N(\mathrm{\Lambda })$

the language of $\mathrm{\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{𝔾}$ being $\mathbb{\mathbb{N}}$ or $\mathbb{\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{𝔾}$ as the set of non-negative integers ($\mathbb{\mathbb{N}}$) with the usual addition, or the set of all integers ($\mathbb{\mathbb{Z}}$) with the usual addition. In both cases, the identity element ${\mathbf{𝟏}}_{\mathbb{𝔾}}$ corresponds to the number 0. Furthermore, when $\mathbb{𝔾}=\mathbb{\mathbb{N}}$, since all $\mathbb{\mathbb{N}}\setminus \{0\}$ can be generated from the number 1, it is sufficient to consider a unique shift map given by $\sigma (\mathbf{𝐱}{)}_n=x_{n+1}$ for all $n$. On the other hand, for the case of $\mathbb{𝔾}=\mathbb{\mathbb{Z}}$, since all $\mathbb{\mathbb{Z}}$ can be generated from the numbers {-1, 1}, it is sufficient to consider two shift maps given for all $n$ by $\sigma (\mathbf{𝐱}{)}_n=x_{n+1}$ and by ${\sigma }^{-1}(\mathbf{𝐱}{)}_n=x_{n-1}$.

Furthermore, whenever $\mathbb{𝔾}$ is $\mathbb{\mathbb{N}}$ or $\mathbb{\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

$[a_0{a}_1...a_n]:=\{(x_i{)}_{i\in \mathbb{𝔾}}:x_i=a_i\mathrm{\forall }i=0,..,n\}.$

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

$W(\mathrm{\Lambda }):=\bigcup _{n\ge 0}{W}_n(\mathrm{\Lambda }),$

where $W_0:=\{ϵ\}$ and $ϵ$ stands for the empty word, and

$W_n(\mathrm{\Lambda }):=\{((a_i{)}_{i=0,..n}\in A^n:\mathrm{\exists }\mathbf{𝐱}\in \mathrm{\Lambda }s.t.x_i=a_i\mathrm{\forall }i=0,...,n\}.$

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

$X_F=\{\mathbb{𝕩}\in A^{\mathbb{\mathbb{Z}}}:\mathrm{\forall }i\in \mathbb{\mathbb{Z}},\mathrm{\forall }k\ge 0,(x_i...x_{i+k})\notin F\}.$

However, if $\mathbb{𝔾}=\mathbb{\mathbb{N}}$, if we define a shift space $\mathrm{\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 $\sigma (X_F)=X_F$. In fact, to define a shift space $X_F\subset A^{\mathbb{\mathbb{N}}}$ such that $\sigma (X_F)⊊X_F$ 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{𝔾}$ being $\mathbb{\mathbb{N}}$) or $\mathbb{\mathbb{Z}}$ with the usual addition, it follows that $M_F$ is finite if and only if $F$ is finite, which leds to classical definition of a shift of finite type as those shift spaces $\mathrm{\Lambda }\subset A^{\mathbb{𝔾}}$ such that $\mathrm{\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 $\mathrm{\Lambda }$ is a shift of finite type if we can take a finite set of forbidden patterns $F$ such that $\mathrm{\Lambda }=X_F$, and $\mathrm{\Lambda }$ is a sofic shift if it is the image of a shift of finite type under sliding block code (that is, a map $\mathrm{\Phi }$ that is continuous and invariant for all $g$-shift maps ). If $A$ is finite and $\mathbb{𝔾}$ is $\mathbb{\mathbb{N}}$ or $\mathbb{\mathbb{Z}}$ with the usual addition, then the shift $\mathrm{\Lambda }$ is a sofic shift if and only if $W(\mathrm{\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.

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

$M_F:=\{g\in \mathbb{𝔾}:\mathrm{\exists }N\subset \mathbb{𝔾}\text{ s.t. }g\in N\text{ and }(w_i{)}_{i\in N}\in F\},$

is finite and $\mathrm{\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 $\mathrm{\Lambda }\subset A^{\mathbb{𝔾}}$ and a $g$-shift map ${\sigma }^g:\mathrm{\Lambda }\to \mathrm{\Lambda }$ it follows that the pair $(\mathrm{\Lambda },{\sigma }^g)$ is a topological dynamical system.

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

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

Examples

The first trivial example of shift space (of finite type) is the full shift $A^{\mathbb{\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, $\{0,1{\}}^{\mathbb{\mathbb{N}}}$ is called the Bernoulli process. It is isomorphic to the Cantor set.

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

See also

• Tent map
• Bit shift map
• Gray code

Further reading

• 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. http://www-igm.univ-mlv.fr/%7Eberstel/Lothaire/ChapitresACW/C1.ps. Retrieved 2008-01-29. 
• Morse, Marston (1938). "Symbolic Dynamics". American Journal of Mathematics 60 (4): 815–866. doi:10.2307/2371264. 
• "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. 2022. doi:10.1007/s00574-022-00292-x.