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 word over A is a sequence, where 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.,
In the following we choose 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 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 convergent sequence of elements of S, the limit also belongs to S; and
  2. .
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

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.
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 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.