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.
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.
A shift space S is sometimes denoted as to emphasize the role of the shift operator.
Some authors 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
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.
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).
- 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.
- 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.