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.
Contents
Notation
Let A be a finite set of states. An infinite (respectively bi-infinite) word over A is a sequence
In the following we choose
Definition
A set of infinite words over A is a shift space if it is closed with respect to the natural product topology of
- for any (pointwise) convergent sequence
( x k ) k ≥ 0 lim k → ∞ x k -
σ ( S ) = S .
A shift space S is sometimes denoted as
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
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.
Examples
The first trivial example of shift space (of finite type) is the full shift
Let