Shift space
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] Notation
Let A be a finite set of states. An infinite (respectively bi-infinite) word over A is a sequence , where (resp. ) and xn 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.,
- 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.
[edit] Definition
A set of infinite words over A is a shift space 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
- σ(X) = X.
A shift space S is sometimes denoted as (S,σ) in order to emphasize the role of the shift operator.
Some authors[1] 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.
[edit] 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 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.
[edit] Examples
The first trivial example of shift space (of finite type) is the full shift .
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.
[edit] Further reading
- Lind, Douglas; Marcus, Brian (1995). An Introduction to Symbolic Dynamics and Coding. Cambridge UK: Cambridge University Press. ISBN 0521559006.
- Lothaire, M. (2002). "Finite and Infinite Words", Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0521812208. Retrieved on 2008-01-29.
- Morse, Marston; Hedlund, Gustav A. (1938). "Symbolic Dynamics" (JSTOR). American Journal of Mathematics 60: 815-866.
[edit] References
- ^ Thomsen, K. (2004). "On the structure of a sofic shift space" (PDF Reprint). Transactions of the American Mathematical Society 356: 3557-3619.