The extended future cover of a sofic shift

Klaus Thomsen · 2026

Read The extended future cover of a sofic shift by Klaus Thomsen (2026) 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-2603-09593.txt.

Introduction

Klaus Thomsen describes an extended future cover for sofic shifts, built as a cover of the future cover itself. The new cover is canonical in the same spirit as the future cover. In some cases it is isomorphic to the future cover, while in others it is a genuine extension of it. Thomsen then uses this construction to define the desynchronization of sofic shifts and describe it.

Catalog record

CREATORKlaus Thomsen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59524
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.09593

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The extended future cover of a sofic shift Klaus Thomsen Abstract . The paper describes a cover of the future cover of a sofic shift which is canonical in the same way as the future cover itself. In some cases the cover is isomorphic to the future cover and in other it is a genuine extension. 2020 Mathematics Subject Classification Primary ; Secondary 1. Introduction The purpose of this paper is to exhibit a natural extension of the future cover of a sofic shift. The future cover was introduced by Wolfgang Krieger in [ Kr1 ] and [ Kr2 ] and has the remarkable property that conjugacies of sofic shifts lift to unique conjugacies of the associated covers. His methods and results were extended in a recent work by the author, [ Th ] , giving rise to other canonical covers with the same nice property, but Krieger’s work and his future cover remains the source of all known examples of this sort. It is therefore useful to have a way to find the future cover of a sofic shift starting from an arbitrary presentation of it. This is the first goal here, and is really not that hard to achieve: An appropriate subgraph of what is termed the subset construction on page 76 of [ LM ] turns out to factor onto the future cover via what is called merging, or the merged graph in [ LM ] . The more difficult task is to show that when applied to an appropriate presentation of the given sofic shift, this subgraph of the subset construction is itself a cover which is strongly canonical in the same sense as the future cover is. Thus, by starting from a well-chosen presentation whose construction may or may not require merging, no additional merging is needed to get from the subset construction to a strongly canonical cover of both the future cover and the given sofic shift itself. The proof of this is based on a further development of the methods and results from [ Th ] where a first addendum to Krieger’s work was obtained in the form of a new canonical cover for sofic shifts. While that cover in general does not factor onto the future cover, the one we introduce here does; a result which can be considered as a second addendum to Krieger’s work and may justify to call this new canonical cover the extended future cover when the initial presentation is the future cover itself. 2. Terminology 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. 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 by \operatorname{Per}(X) . Let G be a finite directed graph with edges or arrows E_{G} and vertexes V_{G} . For e\in E_{G} let s_{G}(e)\in V_{G} be the start vertex and t_{G}(e) the terminal vertex of e . We extend the definition of t_{G} to finite and left-infinite paths in G , and the definition of s_{G} to finite and right-infinite paths in G , in the obvious way. We denote the edge shift of G by X_{G} . Thus X_{G} consists of the bi-infinite sequences (e_{i})_{i\in\mathbb{Z}} of edges in G such that s_{G}(e_{i+1})=t_{G}(e_{i}) for all i\in\mathbb{Z} , and the words in \mathbb{W}(X_{G}) are the finite paths in G that do not start at a source or terminate at a sink in G . We shall sometimes refer to the elements of X_{G} as rays in G . The set X_{G} is an SFT and every SFT is conjugate to X_{G} for some graph G by Theorem 2.3.2 in [ LM ] . In this paper the components in G and X_{G} will be important. Recall that a graph G is strongly connected when every pair of vertexes v,w\in V_{G} can be connected by a finite path in G ; that is, there is a finite path \gamma in G such that s_{G}(\gamma)=v and t_{G}(\gamma)=w . This happens if and only if X_{G} is transitive or irreducible. In a general finite directed graph G , the maximal strongly connected subgraphs C of G are the components of G and the corresponding subshifts X_{C}\subseteq X_{G} are the components of X_{G} . Then the disjoint union \bigsqcup_{C}X_{C}=\overline{\operatorname{Per}(X_{G})} consists of the non-wandering elements of X_{G} . Let A be a finite set (the alphabet) and L_{G}:E_{G}\to A a map considered as a labelling of the edges in G . We extend L_{G} to finite or infinite paths in the natural way. In particular, when x=(e_{i})_{i\in\mathbb{Z}}\in X_{G} , \displaystyle L_{G}(x):=\left(L_{G}(e_{i})\right)_{i\in\mathbb{Z}}=\cdots L_{G}(e_{-3})L_{G}(e_{-2})L_{G}(e_{-1})L_{G}(e_{0})L_{G}(e_{1})L_{G}(e_{2})L_{G}(e_{3})\cdots \displaystyle\in A^{\mathbb{Z}}. Then (G,L_{G}) is a labeled graph , Y:=L_{G}(X_{G})\subseteq A^{\mathbb{Z}} is a sofic shift and (G,L_{G}) is a presentation of Y , cf. §3.1 in [ LM ] . We extend the definition of L_{G} to paths in G in the natural way: Given a finite path \gamma:=x_{[i,j]}\in X_{G}[i,j] in G we define L_{G}(\gamma)\in Y[i,j] such that L_{G}(\gamma)_{k}:=L_{G}(x_{k}) for k\in[i,j] . The extension to left- and right-infinite paths is made in a similar way. When D\subseteq A^{\mathbb{N}} is a subset of A^{\mathbb{N}} and a\in A , we let \frac{D}{a} denote the set \frac{D}{a}:=\left\{x_{1}x_{2}x_{3}\cdots\in A^{\mathbb{N}}:\ ax_{1}x_{2}\cdots\in D\right\}=\left\{x\in A^{\mathbb{N}}:\ ax\in D\right\}; i.e. \frac{D}{a} is the set of elements of A^{\mathbb{N}} that are obtained from the elements of D that start with a by deleting the first coordinate. Let Y\subseteq A^{\mathbb{Z}} be a sofic shift. The future set F(y) of an element y\in Y is F(y):=\left\{w\in Y[0,\infty):\ y_{(-\infty,-1]}w\in Y\right\}. The future cover (\mathbb{K}(Y),L_{\mathbb{K}(Y)}) of Y is the labeled graph where V_{\mathbb{K}(Y)}:=\left\{F(y):\ y\in Y\right\} and there is a labeled arrow F(y)\overset{a}{\to}F(y^{\prime}) in \mathbb{K}(Y) when F(y^{\prime})=\frac{F(y)}{a}. The notion of regularity of a labeled graph played a significant role in [ Th ] , partly as a tool to characterize the future cover, and we shall need it here again. A labeled graph (X_{H},L_{H}) is regular when every vertex v\in V_{H} has the property that there is an element z\in X_{H} such that t_{H}(z_{(-\infty,-1]})=v and \left\{L_{H}(x):\ x\in X_{H}[0,\infty),\ s_{H}(x)=v\right\}=F(L_{H}(z)). We shall need at least two more properties that a labeled graph can have; it can be right-resolving , as in Definition 3.3.1 of [ LM ] , and it can be follower-separated as in Definition 3.3.7 of [ LM ] . 3. Constructing the future cover . In this section we give a recipe for

Read the complete text