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 and the sofic shifts.
In the classical framework[1] a shift space is any subset of , where 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 , where is any non-empty set and is any monoid.[2][3]
Definition
Let be a monoid, and given , denote the operation of with by the product . Let denote the identity of . Consider a non-empty set (an alphabet) with the discrete topology, and define as the set of all patterns over indexed by . For and a subset , we denote the restriction of to the indices of as .
On , we consider the prodiscrete topology, which makes a Hausdorff and totally disconnected topological space. In the case of being finite, it follows that is compact. However, if is not finite, then is not even locally compact.
This topology will be metrizable if and only if 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 , and for each , let . The cylinder given by and is the set
When , we denote the cylinder fixing the symbol at the entry indexed by simply as .
In other words, a cylinder is the set of all set of all infinite patterns of which contain the finite pattern .
Given , the g-shift map on is denoted by and defined as
.
A shift space over the alphabet is a set that is closed under the topology of and invariant under translations, i.e., for all .[note 1] We consider in the shift space the induced topology from , which has as basic open sets the cylinders .
For each , define , and . An equivalent way to define a shift space is to take a set of forbidden patterns and define a shift space as the set
Intuitively, a shift space is the set of all infinite patterns that do not contain any forbidden finite pattern of .
Language of shift space
Given a shift space and a finite set of indices , let , where stands for the empty word, and for let be the set of all finite configurations of that appear in some sequence of , i.e.,
Note that, since is a shift space, if is a translation of , i.e., for some , then if and only if there exists such that if . In other words, and contain the same configurations modulo translation. We will call the set
the language of . 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 being finite, and being or with the usual addition, the language of a shift space is a formal language.
Classical framework
The classical framework for shift spaces consists of considering the alphabet as finite, and as the set of non-negative integers () with the usual addition, or the set of all integers () with the usual addition. In both cases, the identity element corresponds to the number 0. Furthermore, when , since all can be generated from the number 1, it is sufficient to consider a unique shift map given by for all . On the other hand, for the case of , since all can be generated from the numbers {-1, 1}, it is sufficient to consider two shift maps given for all by and by .
Furthermore, whenever is or with the usual addition (independently of the cardinality of ), due to its algebraic structure, it is sufficient consider only cylinders in the form
Moreover, the language of a shift space will be given by
where and stands for the empty word, and
In the same way, for the particular case of , it follows that to define a shift space we do not need to specify the index of on which the forbidden words of are defined, that is, we can just consider and then
However, if , if we define a shift space as above, without to specify the index of where the words are forbidden, then we will just capture shift spaces which are invariant through the shift map, that is, such that . In fact, to define a shift space such that it will be necessary to specify from which index on the words of are forbidden.
In particular, in the classical framework of being finite, and being ) or with the usual addition, it follows that is finite if and only if is finite, which leds to classical definition of a shift of finite type as those shift spaces such that for some finite .
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.
In the case when the alphabet is finite, a shift space is a shift of finite type if we can take a finite set of forbidden patterns such that , and is a sofic shift if it is the image of a shift of finite type under sliding block code[1] (that is, a map that is continuous and invariant for all -shift maps ). If is finite and is or with the usual addition, then the shift is a sofic shift if and only if is a regular language.
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.[4]
When is infinite, it is possible to define shifts of finite type as shift spaces for those one can take a set of forbidden words such that
is finite and .[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.[3] Both, the finiteness of and the additional conditions the sliding block codes, are trivially satisfied whenever is finite.
Topological dynamical systems on shift spaces
Shift spaces are the topological spaces on which symbolic dynamical systems are usually defined.
Given a shift space and a -shift map it follows that the pair is a topological dynamical system.
Two shift spaces and are said to be topologically conjugate (or simply conjugate) if for each -shift map it follows that the topological dynamical systems and are topologically conjugate, that is, if there exists a continuous map such that . Such maps are known as generalized sliding block codes or just as sliding block codes whenever is uniformly continuous.[3]
Although any continuous map from to itself will define a topological dynamical system , in symbolic dynamics it is usual to consider only continuous maps which commute with all -shift maps, i. e., maps which are generalized sliding block codes. The dynamical system is known as a 'generalized cellular automaton' (or just as a cellular automaton whenever is uniformly continuous).
Examples
The first trivial example of shift space (of finite type) 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 (this can be shown by using the pumping lemma).
The space of infinite strings in two letters, is called the Bernoulli process. It is isomorphic to the Cantor set.
The bi-infinite space of strings in two letters, is commonly known as the Baker's map, or rather is homomorphic to the Baker's map.
See also
Footnotes
- ^ It is common to reffer to a shift space using just the expression shift or subshift. However, some authors use the terms shift and subshift for sets of infinite parterns that are just invariant under the -shift maps, and reserve the term shift space for those that are also closed for the prodiscrete topology.
References
- ^ a b Lind, Douglas A.; Marcus, Brian (1995). An introduction to symbolic dynamics and coding. Cambridge: Cambridge University press. ISBN 978-0-521-55900-3.
- ^ Ceccherini-Silberstein, T.; Coornaert, M. (2010). Cellular automata and groups Springer Monographs in Mathematics. Springer Monographs in Mathematics. Springer Verlag. doi:10.1007/978-3-642-14034-1. ISBN 978-3-642-14033-4.
- ^ a b c d Sobottka, Marcelo (September 2022). "Some Notes on the Classification of Shift Spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts". Bulletin of the Brazilian Mathematical Society. New Series. 53 (3): 981–1031. arXiv:2010.10595. doi:10.1007/s00574-022-00292-x. ISSN 1678-7544. S2CID 254048586.
- ^ Weiss, Benjamin (1973), "Subshifts of finite type and sofic systems", Monatsh. Math., 77 (5): 462–474, doi:10.1007/bf01295322, MR 0340556, S2CID 123440583. Weiss does not describe the origin of the word other than calling it a neologism; however, its Hebrew origin is stated by MathSciNet reviewer R. L. Adler.
Further reading
- Ceccherini-Silberstein, T.; Coornaert, M. (2010). Cellular automata and groups Springer Monographs in Mathematics. Springer Verlag. ISBN 978-3-642-14034-1.
- Lind, Douglas; Marcus, Brian (1995). An Introduction to Symbolic Dynamics and Coding. Cambridge UK: Cambridge University Press. ISBN 0-521-55900-6.
- Lothaire, M. (2002). "Finite and Infinite Words". Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0-521-81220-8. Retrieved 2008-01-29.
- Morse, Marston; Hedlund, Gustav A. (1938). "Symbolic Dynamics". American Journal of Mathematics. 60 (4): 815–866. doi:10.2307/2371264. JSTOR 2371264.
- Sobottka, M. (2022). "Some Notes on the Classification of Shift Spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts". Bulletin of the Brazilian Mathematical Society. New Series. 53 (3): 981–1031. arXiv:2010.10595. doi:10.1007/s00574-022-00292-x. S2CID 254048586.