In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite wordss 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 and the sofic shifts.

In the classical framework is a finite set is any monoid.

Definition

be a monoid (an alphabet) with the discrete topology.

, we consider the prodiscrete topology a Hausdorff and totally disconnected is compact is not even locally compact.

This topology will be metrizable is countable, and, in any case, the base. The cylinder is the set

.

.

, the g-shift map and defined as

1. .

A shift space..

. An equivalent way to define a shift space is to take a set of forbidden patterns and define a shift space as the set

.

Language of shift space

, i.e.,

contain the same configurations modulo translation. We will call the set

the language. In the general context stated here, the language of a shift space does not have the same meaning of that in Formal Language Theory, but in the classical framework with the usual addition, the language of a shift space is a formal language.

Classical framework

.

), due to its algebraic structure, it is sufficient consider only cylinders in the form

will be given by

stands for the empty word, and

and then

are forbidden.

.

Some types of shift spaces

Among several types of shift spaces, the most widely studied are the shifts of finite type and the sofic shifts.

is a shift of finite type is a sofic shift if it is the image of a shift of finite type under sliding block code is a regular language.

The name "sofic" was coined by , based on the Hebrew word meaning , to refer to the fact that this is a generalization of a finiteness property.

. In this context of infinite alphabet, a sofic shift will be defined as the image of a shift of finite type under a particular class of sliding block codes. and the additional conditions the sliding block codes is finite.

Topological dynamical systems on shift spaces

Shift spaces are the topological spaces on which symbolic dynamical systems are usually defined.

is a topological dynamical system.

are topologically conjugate. Such maps are known as generalized sliding block codes or just as sliding block codes is uniformly continuous.

is known as a 'generalized cellular automaton' (or just as a cellular automaton is uniformly continuous).

Examples

The first trivial example of shift space (of finite type) is the full shift.

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

is called the Bernoulli process. It is isomorphic to the Cantor set.

is commonly known as the Baker's map, or rather is homomorphic to the Baker's map.

See also

• Tent map

• Bit shift map

• Gray code

Footnotes

References

Further reading