On the future cover of a sofic shift
Klaus Thomsen · 2025
Read On the future cover of a sofic shift by Klaus Thomsen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-01368.txt.
Introduction
Klaus Thomsen gives a new proof of a classic result on sofic shifts. A sofic shift is a set of symbol strings made by a labeled graph. Its future cover is a canonical graph built from what can follow each past. Krieger showed that cover is canonical.
Thomsen proves that claim by a fresh path. He also shows how to make new canonical covers from a given one. The new covers link to the future cover but tend to differ from it. Extra covers give scholars more tools to sort and compare symbol systems.
Catalog record
| CREATOR | Klaus Thomsen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01368
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the future cover of a sofic shift Klaus Thomsen Abstract . The paper contains a new proof of the theorem by Krieger which establishes the canonicity of the future cover of a sofic shift. In addition the paper describes a method to produce new canonical covers from a given one, resulting in canonical covers related to, but generally different from the future cover. August 10, 2026 2020 Mathematics Subject Classification Primary ; Secondary 1. Introduction A cover of a sofic shift Y is a subshift of finite type X together with a factor map \pi:X\to Y from X onto Y . Every sofic shift has a wealth of different covers, so the least one can do to simplify considerations regarding covers is to identify two covers \pi:X\to Y and \pi^{\prime}:X^{\prime}\to Y of the same sofic shift Y when they are isomorphic in the sense that there is a conjugacy \chi:X\to X^{\prime} such that \pi^{\prime}\circ\chi=\pi . Recall that a subshift of finite type can be realized as the edge shift X_{G} of a finite directed graph G and that a labeling of the set of edges E_{G} is a map L_{G}:E_{G}\to A , where A is a finite set. If Y=L_{G}(X_{G}) , where L_{G}:X_{G}\to Y\subseteq A^{\mathbb{Z}} is the map obtained by reading the labels of elements in X_{G} , we say that (G,L_{G}) is a presentation of Y . Then any cover of Y is isomorphic to one coming from a presentation of Y , see Theorem 3.2.1 in [ LM ] . But even after having reduced covers to labeled graphs, every sofic shift has an uncanny host of different presentations. Fortunately the future cover of Wolfgang Krieger, [ Kr1 ] , and its associated labeled graph which we denote by (\mathbb{K}(Y),L_{\mathbb{K}(Y)}) , stands out because it is canonical in the sense that a conjugacy \psi:Y\to Z of sofic shifts lifts to a conjugacy \psi_{\mathbb{K}}:X_{\mathbb{K}(Y)}\to X_{\mathbb{K}(Z)} such that \textstyle{X_{\mathbb{K}(Y)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{L_{\mathbb{K}(Y)}} \scriptstyle{\psi_{\mathbb{K}}} \textstyle{X_{\mathbb{K}(Z)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{L_{\mathbb{K}(Z)}} \textstyle{Y\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{\psi} \textstyle{Z} commutes. Thus the subshift of finite type X_{\mathbb{K}(Y)} and the factor map L_{\mathbb{K}(Y)} are both conjugacy invariants for Y . The same is of course also true for any other cover which is canonical in the same way. It must be emphasized that also components of a canonical cover that are not of maximal entropy as well as the wandering parts of the cover, which often arise even when Y is mixing, also give rise to conjugacy invariants for Y . This observation is the main motivation for the work and the results that are presented below. We start by giving a new proof of Krieger’s theorem. While his proof is a tour de force in handling sliding block codes, the proof given here is more conceptual and leads to an abstract characterization of the future cover analogous to the abstract characterization of the canonical cover of an irreducible sofic shift known as the minimal right-resolving cover or Fischer cover, [ F ] . Alternative proofs of parts of Krieger’s theorem have been given before; first by Boyle, Kitchens and Marcus in [ BKM ] and later by Nasu in [ N ] . The proof presented here is also different from those. The main new result of the paper is a theorem which out of a given canonical cover produces a new one. To appreciate this, recall that Krieger proved the uniqueness of the conjugacy \psi_{\mathbb{K}} in the diagram above. Without this additional requirement it is obvious that a canonical cover is not unique up to isomorphism; for example the disjoint union of two copies of the future cover will again be canonical in the sense used so far, but not with unique lifts of conjugacies. In the following we shall therefore refer to a construction of covers as weakly canonical when it gives lifts of conjugacies, but possibly lifts that are not unique, while a construction which gives rise to unique lifts of conjugacies, as the future cover does, will be called a strongly canonical cover. The main new result of the paper, Theorem 4.6 , describes a method to produce a strongly canonical cover out of a given weakly canonical one. An important point concerning the construction is that it produces new strongly canonical covers of sofic shifts. Up to now only two strongly canonical covers for sofic shifts have been known; at least when we for simplicity ignore the doubling coming from the passage from right-resolving to left-resolving covers that can be achieved by ’time-reversal’. Besides the future cover it is the minimal right-resolving cover, and only for irreducible sofic shifts. It is therefore interesting to compare the strongly canonical covers that can be produced using Theorem 4.6 with the future cover and, in the irreducible case, the minimal right-resolving cover. For this we introduce a method to find the future cover of a sofic shift starting from an arbitrary given presentation. This is based on a variation of the so-called subset construction described in §3.3 of [ LM ] . More specifically, it is shown that a restriction to a subset of the vertexes in the subset construction, applied to an arbitrary presentation of the sofic shift, gives rise to a labeled graph whose merged graph is isomorphic to the future cover. Thus the future cover is the factor obtained from a subgraph of the subset construction by identifying vertexes with the same follower set. This fact is used to produce the examples occurring in the paper, and makes it easy to show by examples that the new strongly canonical covers that can be obtained from Theorem 4.6 in general are different both from the future cover, and in the irreducible case, also the minimal right-resolving cover. Acknowledgement: I thank Brian Marcus, Tom Meyerovitch and Chengyu Wu for the collaboration that produced [ MMTW ] . I’m particularly grateful to Brian for renewing my interest in sofic shifts, and I thank him also for showing me his solution to Exercise 3.2.8 (e) in [ LM ] . 2. Krieger’s future cover and its canonicity 2.1. Setup and notation Let A be a finite set. The set A^{\mathbb{Z}} of bi-infinite sequences x=(x_{i})_{i\in\mathbb{Z}}=\cdots x_{-3}x_{-2}x_{-1}x_{0}x_{1}x_{2}x_{3}\cdots of elements from A is a compact metric space; a metric can be defined for example as in Example 6.1.10 of [ LM ] . The shift \sigma is the homeomorphism of A^{\mathbb{Z}} defined such that \sigma(x)_{i}:=x_{i+1}. A closed subset X\subseteq A^{\mathbb{Z}} is shift-invariant when \sigma(X)=X and it is then called a subshift . We shall mainly consider subshifts of finite type (abbreviated to SFT) and sofic shifts . See Definition 2.1.1 and Definition 3.1.3 in [ LM ] . The set \mathbb{W}(X) of words in a subshift X consists of the finite strings a_{1}a_{2}\cdots a_{n}\in A^{n} with the property that a_{1}a_{2}\cdots a_{n}=x_{1}x_{2}\cdots x_{n} for some element x=(x_{i})_{i\in\mathbb{Z}}\in X . Given an element x\in X and an integer j\in\mathbb{Z} we denote by x_{(-\infty,j]} the element \cdots x_{k}x_{k+1}x_{k+2}\cdots x_{j}\in A^{(-\infty,j]}, and by X(-\infty,j] the set X(-\infty,j]:=\left\{x_{(-\infty,j]}:\ x\in X\right\}. The symbols x_{[j,\infty)} and X[j,\infty) have a similar meaning. The same goes for expressions like x_{[i,j)} and x_{(i,j]} when i<j or x_{[i,j]} when i\leq j . The set of \sigma -periodic points of a subshift X will be denoted