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 1 Notation 2 Definition 3 Characterization and sofic subshifts 4 Examples 5 Further reading 6 References

[edit] Notation

Let A be a finite set of states. An infinite (respectively bi-infinite) word over A is a sequence , where (resp. ) 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.,

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

1. for any (pointwise) convergent sequence of elements of S, the limit also belongs to S; and
2. σ(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

1. ^ Thomsen, K. (2004). "On the structure of a sofic shift space" (PDF Reprint). Transactions of the American Mathematical Society 356: 3557-3619.