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.
In the classical framework[1] a shift space is any subset
is a finite set, which is closed for the Tychonov topology and invariant by translations.
More generally one can define a shift space as the closed and translation-invariant subsets of
(an alphabet) with the discrete topology, and define
, we consider the prodiscrete topology, which makes
a Hausdorff and totally disconnected topological space.
is countable, and, in any case, the base of this topology consists of a collection of open/closed sets (called cylinders), defined as follows: given a finite set of indices
, we denote the cylinder fixing the symbol
[note 1] We consider in the shift space
, which has as basic open sets the cylinders
An equivalent way to define a shift space is to take a set of forbidden patterns
In the general context stated here, the language of a shift space has not the same mean of that in Formal Language Theory, but in the classical framework which considers the alphabet
The classical framework for shift spaces consists of considering the alphabet
) with the usual addition, or the set of all integers (
can be generated from the number 1, it is sufficient to consider a unique shift map given by
can be generated from the numbers {-1, 1}, it is sufficient to consider two shift maps given for all
), due to its algebraic structure, it is sufficient consider only cylinders in the form Moreover, the language of a shift space
stands for the empty word, and In the same way, for the particular case of
is a sofic shift if it is the image of a shift of finite type under sliding block code[1] (that is, a map
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.
[3] 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, are trivially satisfied whenever
-shift map it follows that the topological dynamical systems
are topologically conjugate, that is, if there exists a continuous map
to itself will define a topological dynamical system
, in symbolic dynamics it is usual to consider only continuous maps
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).