# Shift space

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.

## Notation

Let *A* be a finite set of states. An *infinite* (respectively *bi-infinite*) *word* over *A* is a sequence , where (resp. ) and is in *A* for any .
The shift operator acts on an infinite or bi-infinite word by shifting all symbols to the left, i.e.,

- for all
*n*.

In the following we choose 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* (or *subshift*) if it is closed with respect to the natural product topology of and invariant under the shift operator. Thus a set is a subshift if and only if

- for any (pointwise) convergent sequence of elements of
*S*, the limit also belongs to*S*; and - .

A shift space *S* is sometimes denoted as to emphasize the role of the shift operator.

Some authors[1] use the term *subshift* for a set of infinite words that is just invariant under the shift, and reserve the term *shift space* for those that are also closed.

## Characterization and sofic subshifts

A subset *S* of 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 (substring) in *X*.

In particular, if *X* is finite then *S* is called a subshift of finite type and more generally when *X* is a regular language, the corresponding subshift is called **sofic**.
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.[2]

## Examples

The first trivial example of shift space (of finite type) is the *full shift* .

Let . 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).

## See also

## References

- Thomsen, K. (2004). "On the structure of a sofic shift space" (PDF Reprint).
*Transactions of the American Mathematical Society*.**356**(9): 3557–3619. doi:10.1090/S0002-9947-04-03437-3. Retrieved 2012-01-27. - Weiss, Benjamin (1973), "Subshifts of finite type and sofic systems",
*Monatsh. Math.*,**77**: 462–474, doi:10.1007/bf01295322, MR 0340556. Weiss does not describe the origin of the word other than calling it a neologism; however, its Hebrew origin is stated by MathSciNet reviewer R. L. Adler.

## Further reading

- 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. - Teschl, Gerald (2012).
*Ordinary Differential Equations and Dynamical Systems*. Providence: American Mathematical Society. ISBN 978-0-8218-8328-0.