Shift space

In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words representing the evolution of a discrete system. In fact, shift spaces and "symbolic dynamical systems" are often considered synonyms.

Notation

Let "A" be a finite set of states. An "infinite" (respectively "bi-infinite") "word" over "A" is a sequence $mathbf\; x=(x\_n)\_\{nin\; M\}$, where $M=mathbb\; N$ (resp. $M=mathbb\; Z$) and $x\_n$ is in "A" for any integer "n".The shift operator acts on an infinite or bi-infinite word by shifting all symbols to the left, i.e.,:$(sigma(mathbf\; x))(n)=x\_\{n+1\}$ for all "n".In the following we choose $M=mathbb\; N$ and thus speak of infinite words, but all definitions are naturally generalizable to the bi-infinite case.

Definition

A set of infinite words over "A" is a "shift space" if it is closed with respect to the natural product topology of $A^mathbb\; N$ and invariant under the shift operator. Thus a set $Ssubseteq\; A^mathbb\; N$ is a subshift if and only if
# for any (pointwise) convergent sequence $(mathbf\; x\_k)\_\{kgeq\; 0\}$ of elements of "S", the limit $lim\_\{k\; oinfty\}mathbf\; x\_k$ also belongs to "S"; and
# $sigma(X)=X$.

A shift space "S" is sometimes denoted as $(S,sigma)$ in order to emphasize the role of the shift operator.

Some authors [cite journal|author = Thomsen, K.|title = On the structure of a sofic shift space|url = http://www.imf.au.dk/publications/pp/2003/imf-pp-2003-6.pdf |format = PDF Reprint|accessdate = 2008-01-29|journal = Transactions of the American Mathematical Society|volume = 356|year = 2004|pages = 3557–3619|doi = 10.1090/S0002-9947-04-03437-3 ] use the term "subshift" for a set of infinite words which is just invariant under the shift, and reserve the term "shift space" for those which are also closed.

Characterization and sofic subshifts

A subset "S" of $A^mathbb\; N$ is a shift space if and only if there exists a set "X" of finite words such that "S" coincides with the set of all infinite words over "A" having no factor in "X".

When "X" is a regular language, the corresponding subshift is called sofic. In particular, if "X" is finite then "S" is called a subshift of finite type.

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.

Further reading

* cite book
author = Lind, Douglas
coauthors = Marcus, Brian
title = An Introduction to Symbolic Dynamics and Coding
year = 1995
publisher = Cambridge University Press
location = Cambridge UK
isbn = 0521559006
* cite book
author = Lothaire, M.
title = Algebraic Combinatorics on Words
url = http://www-igm.univ-mlv.fr/~berstel/Lothaire/AlgCWContents.html
accessdate = 2008-01-29
year = 2002
publisher = Cambridge University Press
location = Cambridge UK
isbn = 0521812208
chapter = Finite and Infinite Words
chapterurl = http://www-igm.univ-mlv.fr/%7Eberstel/Lothaire/ChapitresACW/C1.ps
* cite journal
author = Morse, Marston
authorlink = Marston Morse
coauthors = Hedlund, Gustav A.
title = Symbolic Dynamics
url = http://links.jstor.org/sici?sici=0002-9327(193810)60%3A4%3C815%3ASD%3E2.0.CO%3B2-4
format = JSTOR
accessdate = 2008-01-29
journal = American Journal of Mathematics
volume = 60
year = 1938
pages = 815–866
doi = 10.2307/2371264

References