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 formula_1, where formula_2 (respectively formula_3) and formula_4 is in "A" for any formula_5. The shift operator formula_6 acts on an infinite or bi-infinite word by shifting  all symbols to the left, i.e., In the following we choose formula_2 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 formula_9 and invariant under the shift operator. Thus a set formula_10 is a subshift if and only if A shift space "S" is sometimes denoted as formula_14 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. A subset "S" of formula_9 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 , based on the Hebrew word סופי meaning "finite", to refer to the fact that this is a generalization of a finiteness property. Examples. The first trivial example of shift space (of finite type) is the "full shift" formula_9. Let formula_17. 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, formula_18 is called  Bernoulli process. It is isomorphic to the Cantor set. The bi-infinite space of strings in two letters, formula_19 is commonly known as the Baker's map, or rather is homomorphic to the Baker's map.