# Sturmian and infinitely desubstitutable words accepted by an $\omega$-automaton

Pierre Béaur, Benjamin Hellouin de Menibus

<figure><img src="image_1.png" /></figure>

To cite this version:

Pierre Béaur, Benjamin Hellouin de Menibus. Sturmian and infinitely desubstitutable words accepted by an $\omega$-automaton. WORDS 2023, Martin Berglund; Johanna Björklund; Frank Drewes; Lena Strobl, Jun 2023, Umeå, Sweden. 10.1007/978-3-031-33180-0_8. hal-04034705

HAL Id: hal-04034705

https://hal.science/hal-04034705

Submitted on 17 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Sturmian and infinitely desubstitutable words accepted by an $\omega$-automaton

Pierre Béaur¹[0000-0002-4050-7709] and Benjamin Hellouin de Menibus¹[0000-0001-5194-929X]

Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91400, Orsay, France

**Abstract.** Given an $\omega$-automaton and a set of word homomorphisms, we look at which accepted words have such a substitutive structure, and in particular if there is at least one. We introduce a method using desubstitution of $\omega$-automata to describe the structure of preimages of accepted words under arbitrary sequences of homomorphisms: this takes the form of a meta-$\omega$-automaton.

We decide the existence of an accepted purely substitutive word, as well as the existence of an accepted fixed point. In the case of multiple substitutions (non-erasing homomorphisms), we decide the existence of an accepted infinitely desubstitutable word, with possibly some constraints on the sequence of substitutions (e.g. Sturmian words or Arnoux-Rauzy words). As an application, we decide when a set of finite words codes e.g. a Sturmian word. As another application, we also show that if an $\omega$-automaton accepts a Sturmian word, it accepts the image of the full shift under some Sturmian morphism.

**Keywords:** Substitutions · $\omega$-automata · Sturmian words · decidability.

## 1 Introduction

One-dimensional symbolic dynamics is the study of infinite words and their associated dynamical structures, and is linked with combinatorics on words. Two classical methods to generate words are the following: on the one hand, sofic shifts are the set of walks on a labeled graph (which can be considered as an $\omega$-automaton) [10]; on the other hand, the substitutive approach consists in iterating a word homomorphism on an initial letter. The latter method was introduced by Axel Thue as a way to create counterexamples to conjectures in combinatorics on words [3]. It is then natural to ask whether a given $\omega$-automaton accepts a word with a given substitutive structure. Carton and Thomas provided a method to decide this question in the case of substitutive or morphic words on Büchi $\omega$-automata, using verification theory and semigroups of congruence [6]. This result was partially reproved by Salo [13], using a more combinatorial point of view. For the last 20 years, the substitutive approach (iterating a single homomorphism) has been generalized to the S-adic approach [7] that lets one alternate between multiple substitutions. This more general framework lets us describe other natural classes, such as the family of Sturmian words.
In this paper, we develop a new method based on desubstitutions of $\omega$-automata. We can express the preimages of an $\omega$-automaton by any sequence of substitutions through a meta-$\omega$-automaton, whose vertices are $\omega$-automata and whose edges are labeled by substitutions. We use this meta-$\omega$-automaton to decide whether an $\omega$-automaton accepts a purely substitutive word (giving an alternative proof of [6]), or a fixed point of a substitution, or a morphic word, or an infinitely desubstitutable word (by a set of substitutions). The method is flexible enough to allow for additional constraints on the directive sequences of substitutions, which is powerful enough for example to decide whether an $\omega$-automaton accepts a Sturmian word. A consequence is the decidability of whether a given set of finite words codes some Sturmian word (or from any family with an $S$-adic characterization). We also describe the set of directive sequences of words accepted by some $\omega$-automaton, which is an $\omega$-regular set.

The meta-$\omega$-automaton also provides a more combinatorial insight on how Sturmian words and $\omega$-regular languages interact: namely, that an $\omega$-automaton accepts a Sturmian word if, and only if, it accepts the image of the full shift under a Sturmian morphism.

# 2 Definitions

## 2.1 Words and $\omega$-automata

An alphabet $\mathcal{A}$ is a finite set of symbols. The set of finite words on $\mathcal{A}$ is denoted as $\mathcal{A}^*$. A (mono)infinite word is an element of $\mathcal{A}^N$. It is usual to write $x = x_0x_1x_2x_3...$ where $x_i = x(i) \in \mathcal{A}$. If $x$ is a word, $|x|$ is the length of the word (if $x$ is infinite, then $|x| = \infty$). For a word $x$ and $0 \le j \le k < |x|$, $x_{[j,k]}$ is the word $x_jx_{j+1}x_{j+2}\dots x_{k-1}x_k$ and is called a factor of $x$. For a finite word $w$ and $x$ a (possibly infinite word), $w \le_f x$ means that $w$ is a factor of $x$, and $w \sqsubseteq_p x$ means that $w$ is a prefix of $x$.

It is possible to endow $\mathcal{A}^N$ with a topology, called the prodiscrete topology. The prodiscrete topology is defined by the clopen basis $[w]_n = \{x \in \mathcal{A}^N | x_n x_{n+1} \dots x_{n+|w|-1} = w\}$ for $w \in \mathcal{A}^*$. To this topology, we can adjunct a dynamic with the shift operator $S$:

$$S: \left( \begin{array}{ccc} \mathcal{A}^N & \to & \mathcal{A}^N \\ x = x_0x_1x_2x_3\dots & \mapsto & S(x) = x_1x_2x_3x_4\dots \end{array} \right)$$

A set $X \subseteq \mathcal{A}^N$ is called a shift (space) if it is stable by $S$ and closed for the prodiscrete topology. In particular, $\mathcal{A}^N$ is a shift space, called the full shift (space).

Another fundamental class of shifts is the one of sofic shifts. Although the traditional way to define them uses labeled graphs (see [10]), we will here use the notion of $\omega$-automata, which is equivalent.

**Definition 1 ($\omega$-automaton).** An $\omega$-automaton $\mathfrak{A}$ over an alphabet $\mathcal{A}$ is a tuple $(Q, I, T, \text{Acc})$, where $Q$ is a finite set of states, $I \subseteq Q$ is the set of initial states, $T \subseteq Q \times \mathcal{A} \times Q$ is the set of transitions of $\mathfrak{A}$ and $\text{Acc} \subseteq Q^N \cup Q^*$ is an acceptance condition (see the following definition).
We extend several classical notions from finite automata. We write transitions as $q_s \xrightarrow{a} q_t \in T$.

**Definition 2 (Computations and walks).** For $n \ge 1$ (or $n = \infty$), a sequence $(q_k)_{0 \le k \le n}$ with $q_k \in Q$ is a walk in $\mathfrak{A}$ if there is $(a_k)_{1 \le k \le n} \subseteq \mathcal{A}$ such that for all $k$, $q_k \xrightarrow{a_{k+1}} q_{k+1} \in T$. We then write $q_0 \xrightarrow{a_1} q_1 \xrightarrow{a_2} q_2 \xrightarrow{a_3} \dots \xrightarrow{a_n} q_n$. The word $w = (a_k)_{1 \le k \le n}$ labels the walk.

A walk $(q_k)_{0 \le k \le n}$ is accepting if it is in $\mathbf{Acc}$ and $q_0 \in I$. A word $w = (a_k)_{0 \le k \le n-1}$ is accepted by $\mathfrak{A}$ if it labels an accepting walk $(q_k)_{0 \le k \le n}$, and $q_0 \xrightarrow{a_1} q_1 \xrightarrow{a_2} q_2 \xrightarrow{a_3} \dots \xrightarrow{a_n} q_n$ is a computation accepting $w$.

To be clear, a computation is an accepting walk associated with an accepted word that labels it.

The most classical type of acceptance condition is the Büchi condition [15]: one chooses a set $Q_F \subseteq Q$ of final states, and only the walks visiting $Q_F$ infinitely many times are accepted. However, in contrast to much of the literature, in this paper, when $\mathbf{Acc}$ is not specified, we will consider that $\mathbf{Acc} = Q^\mathbb{N} \cup Q^*$, i.e. that every walk is accepted.

**Definition 3 (Language of an $\omega$-automaton).** Let $\mathfrak{A}$ be an $\omega$-automaton. The language of finite words of $\mathfrak{A}$ is $\mathcal{L}_F(\mathfrak{A}) = \{w \in \mathcal{A}^* \mid w \text{ is accepted by } \mathfrak{A}\}$. The language of infinite words of $\mathfrak{A}$ is $\mathcal{L}_\infty(\mathfrak{A})\{w \in \mathcal{A}^\mathbb{N} \mid w \text{ is accepted by } \mathfrak{A}\}$. Then, the language of $\mathfrak{A}$ is $\mathcal{L}(\mathfrak{A}) = \mathcal{L}_F(\mathfrak{A}) \cup \mathcal{L}_\infty(\mathfrak{A})$.

If all states of $\mathfrak{A}$ are initial ($I = Q$), its language of infinite words is a shift (called a *sofic shift*).

## 2.2 Substitutions

**Definition 4 (Homomorphisms and substitutions).** A homomorphism is a function $\sigma : \mathcal{A}^* \to \mathcal{A}^*$ such that $\sigma(uv) = \sigma(u)\sigma(v)$ for all $u, v \in \mathcal{A}^*$. $\sigma$ is extended to $\mathcal{A}^\mathbb{N} \to \mathcal{A}^\mathbb{N}$ by $\sigma(x_0x_1x_2x_3\dots) = \sigma(x_0)\sigma(x_1)\sigma(x_2)\sigma(x_3)\dots$. A substitution is a nonerasing homomorphism, that is, $\sigma(a) \neq \varepsilon$ for all letters $a \in \mathcal{A}$.

**Definition 5 (Fixed points, purely substitutive, substitutive and morphic words).** Let $\sigma, \tau : \mathcal{A}^\mathbb{N} \to \mathcal{A}^\mathbb{N}$ be two homomorphisms. An infinite word $x \in \mathcal{A}^\mathbb{N}$ is:

- a fixed point of $\sigma$ if $\sigma(x) = x$;

- a purely substitutive word generated by $\sigma$ if there is a letter $a \in \mathcal{A}$ such that $x = \lim_{n \to \infty} \sigma^n(a)$ and the limit is well-defined;

- a morphic word generated by $\sigma$ and $\tau$ if $x = \tau(y)$, where $y$ is a purely substitutive word generated by $\sigma$;

- a substitutive word generated by $\sigma$ if $x$ is a morphic word with $\tau$ being a coding, i.e. $\tau(\mathcal{A}) \subseteq \mathcal{A}$.
It is now possible to extend these definitions in the case we use multiple ho-
momorphisms. However, most of literature revolves around the use of multiple
non-erasing homomorphisms (substitutions), and we will stick to this case. Let
$(\sigma_n)_{n \in \mathbb{N}}$ be a sequence of substitutions. The equivalent of a fixed-point of one
homomorphism is an *infinitely desubstitutable word* by a sequence of substitu-
tions:

**Definition 6 (Infinitely desubstitutable words and directive sequences).**
Let $\mathcal{S}$ be a finite set of substitutions, and let $(\sigma_n)_{n \in \mathbb{N}} \subseteq \mathcal{S}$. An infinite word $x$ is infinitely desubstitutable by $(\sigma_n)_{n \in \mathbb{N}}$ (called a directive sequence of $x$) if, and only if, there exists a sequence of infinite words $(x_n)_{n \in \mathbb{N}}$ such that $x_0 = x$ and $x_n = \sigma_n(x_{n+1})$. An infinite word $x$ is infinitely desubstitutable by $\mathcal{S}$ if $x$ is infinitely desubstitutable by some directive sequence $(\sigma_n)_{n \in \mathbb{N}} \subseteq \mathcal{S}$.

Just like for words, we write $\sigma_{\llbracket i,j \rrbracket} = \sigma_i \circ \sigma_{i+1} \circ \cdots \circ \sigma_j$. Then $x$ is infinitely desubstitutable by $(\sigma_n)_{n \in \mathbb{N}}$ if, and only if, there is a sequence of infinite words $(x_n)_{n \in \mathbb{N}}$ such that $x = \sigma_{\llbracket 0,n \rrbracket}(x_{n+1})$ for all $n \ge 0$.

3 Finding substitutive and infinitely desubstitutable
words in ω-automata

**3.1 Desubstituting ω-automata**

In this section, we explain our main technical tool: an effective transformation of
ω-automaton, called desubstitution. We define it for the broad case of possibly
erasing homomorphisms.

**Definition 7 (Desubstitution of an ω-automaton).** Let $\mathfrak{A} = (Q, I, T)$ be an $\omega$-automaton, and $\sigma$ a homomorphism. Then, we define $\sigma^{-1}(\mathfrak{A})$ as the $\omega$-automaton $(Q, I, T')$ where, for all $q_1, q_2 \in Q$ and $a \in \mathcal{A}$, $q_1 \xrightarrow{a} q_2 \in T'$ iff $q_1 \xrightarrow{\sigma(a)} * q_2$ is a computation in $\mathfrak{A}$.

In particular, in this case, we consider that $q \xrightarrow{\epsilon} q$ is a computation. Thus, if
$\sigma(a) = \epsilon$, the desubstituted automaton $\sigma^{-1}(\mathfrak{A})$ has a loop labeled by $a$ on every
state.

For example, consider the following $\omega$-automaton $\mathfrak{A}$ and substitution $\sigma$ (Figure 1(a,b)).

We build the $\omega$-automaton $\sigma^{-1}(\mathfrak{A})$. Start from an empty automaton on the same set of states. For every computation in $\mathfrak{A}$ labeled by $01 = \sigma(0)$ — say, $q \xrightarrow{\sigma(0)} * r$ — add an edge $q \xrightarrow{0} r$ to the automaton (Figure 1(c)). To conclude, do this with $\sigma(1) = 0$ (Figure 1(d)).

It is a classical construction in the theory of finite automata, and it satisfies
the following property :

**Proposition 1.** An infinite word $u$ is accepted by $\sigma^{-1}(\mathfrak{A})$ if and only if $\sigma(u)$ is accepted by $\mathfrak{A}$. In other words, $\mathcal{L}_{\infty}(\sigma^{-1}(\mathfrak{A})) = \sigma^{-1}(\mathcal{L}_{\infty}(\mathfrak{A}))$.
<figure><img src="image_3.png" /><figcaption>Fig. 1: Desubstitution of the $\omega$-automaton $\mathfrak{A}$ by $\sigma$</figcaption></figure>

*Proof.* Let $u$ be accepted by $\sigma^{-1}(\mathfrak{A})$. Consider the associated accepting walk $(q_i)_{i \in \mathbb{N}}$. By definition of $\sigma^{-1}(\mathfrak{A})$, for every $i \in \mathbb{N}$, there exists a computation $q_i \xrightarrow{\sigma(u_i)} * q_{i+1}$ in $\mathfrak{A}$. By concatenating these computations, we get an infinite computation $q_0 \xrightarrow{\sigma(u_0)} * q_1 \xrightarrow{\sigma(u_1)} * q_2 \xrightarrow{\sigma(u_2)} * \dots$ in $\mathfrak{A}$ that accepts $\sigma(u)$ in $\mathfrak{A}$.

Conversely, suppose there is a word of the form $\sigma(u)$ accepted by $\mathfrak{A}$. Consider the states $(q_i)_{i \in \mathbb{N}}$ obtained after reading each $\sigma(a)$ for $a \in \mathcal{A}$. This defines an accepting walk labeled by $u$ in $\sigma^{-1}(\mathfrak{A})$.

There is a more precise equivalent for finite words:

**Proposition 2.** Let $w$ be a finite word, $\mathfrak{A}$ be an $\omega$-automaton and $\sigma$ a homomorphism. Then $q_s \xrightarrow{\sigma(w)} * q_t$ is a computation in $\mathfrak{A}$ iff $q_s \xrightarrow{w} * q_t$ is a computation in $\sigma^{-1}(\mathfrak{A})$.

An easy but significant property is the composition of desubstitution of $\omega$-automata:

**Proposition 3.** Let $\mathfrak{A}$ be an $\omega$-automaton, and $\sigma$ and $\tau$ be two homomorphisms. Then, $(\sigma \circ \tau)^{-1}(\mathfrak{A}) = \tau^{-1}(\sigma^{-1}(\mathfrak{A}))$.

*Proof.* These two $\omega$-automata share the same sets of states and of initial states. We prove that they have the same transitions. We have indeed:

$$ 
\begin{align*}
q_s \xrightarrow{a} q_t \text{ in } (\sigma \circ \tau)^{-1}(\mathfrak{A}) &\iff q_s \xrightarrow{\sigma \circ \tau(a)} * q_t \text{ in } \mathfrak{A} \\
&\iff q_s \xrightarrow{\tau(a)} * q_t \text{ in } \sigma^{-1}(\mathfrak{A}), \text{ by Proposition 2} \\
&\iff q_s \xrightarrow{a} q_t \text{ in } \tau^{-1}(\sigma^{-1}(\mathfrak{A})), \text{ by Proposition 2 again.}
\end{align*}
$$

## 3.2 The problem of the purely substitutive walk

When desubstituting automata, the following property is crucial:

**Fact 1** Let $\mathfrak{A}$ be an $\omega$-automaton on the alphabet $\mathcal{A}$, let $\mathfrak{S}(\mathfrak{A})$ be the set of all $\omega$-automata which have the same set of states and the same initial states as $\mathfrak{A}$. For any homomorphism $\sigma$ on $\mathcal{A}$, $\sigma^{-1}(\mathfrak{A})$ is an element of $\mathfrak{S}(\mathfrak{A})$.
In particular, remark that $\mathfrak{S}(\mathfrak{A})$ is finite: given $\mathfrak{A} = (Q, I, T)$, an element of $\mathfrak{S}(\mathfrak{A})$ is identified by its transitions, which form a subset of $(Q \times \mathcal{A} \times Q)$, so $\text{Card}(\mathfrak{S}(\mathfrak{A})) = 2^{|Q|^2 \times |\mathcal{A}|}$. We could work on a subset of $\mathfrak{S}(\mathfrak{A})$ by identifying $\omega$-automata with the same language [2], but finiteness is sufficient for our results.

Given $\mathfrak{A}$ an $\omega$-automaton, and $\sigma$ a homomorphism, $\sigma^{-1}$ defines a dynamic on the finite set $\mathfrak{S}(\mathfrak{A})$. By the pidgeonhole principle:

**Fact 2** Let $\mathfrak{A}$ be an $\omega$-automaton, and $\sigma$ be a homomorphism. Then there exist $n < m \in \mathbb{N}$ such that $\sigma^{-n}(\mathfrak{A}) = \sigma^{-m}(\mathfrak{A})$.

In the remainder of the section, we prove that, given an $\omega$-automaton $\mathfrak{A}$ and a substitution $\sigma$, the problems of finding a fixed point of $\sigma$ or a purely substitutive walk generated by $\sigma$ accepted by $\mathfrak{A}$ are decidable.

A purely substitutive word generated by an erasing homomorphism $\sigma$ is also generated by a non-erasing homomorphism $\tau$ (that is, a substitution) that can be effectively constructed. Thus, we assume $\sigma$ itself is a substitution.

**Proposition 4.** Let $\mathfrak{A}$ be an $\omega$-automaton, let $\sigma$ be a substitution and let $n < m \in \mathbb{N}$ be as in Fact 2. Then, $\mathfrak{A}$ accepts a fixed point for $\sigma^k$ for some $k \ge 1$ iff $\mathcal{L}_\infty(\sigma^{-n}(\mathfrak{A}))$ is nonempty.

*Proof.* We have $n < m \in \mathbb{N}$ as in Fact 2, so that $\sigma^{-n}(\mathfrak{A}) = \sigma^{-m}(\mathfrak{A})$.

If $\mathcal{L}_\infty(\sigma^{-n}(\mathfrak{A}))$ is empty, then $\mathcal{L}_\infty(\sigma^{-p}(\mathfrak{A}))$ is empty for every $p \ge n$. Let $k \ge 1$: if there were a fixed point $x$ for $\sigma^k$ accepted by $\mathfrak{A}$, we would have $x = \sigma^k(x) = \sigma^{kn}(x)$ by iterating. So $x$ would be in $\mathcal{L}_\infty(\sigma^{-kn}(\mathfrak{A}))$ which is empty. By contradiction, there is no fixed point for any $\sigma^k$.

If $\mathcal{L}_\infty(\sigma^{-n}(\mathfrak{A}))$ is nonempty, let $x$ be a word accepted by $\sigma^{-n}(\mathfrak{A})$. Because $\sigma^{-n}(\mathfrak{A}) = \sigma^{-m}(\mathfrak{A}) = \sigma^{-(m-n)}(\sigma^{-n}(\mathfrak{A}))$, $x$ is accepted by $\sigma^{-j(m-n)}(\sigma^{-n}(\mathfrak{A})) = \sigma^{-(n+j(m-n)}(\mathfrak{A})$ for all $j \in \mathbb{N}$. This means that $\sigma^{n+j(m-n)}(x)$ is accepted by $\mathfrak{A}$ for all $j \in \mathbb{N}$. Consider an adherence value $\tilde{x}$ of the sequence $(\sigma^{n+j(m-n)}(x))_{j \in \mathbb{N}}$. By compacity of the language of an $\omega$-automaton, $\tilde{x} \in \mathcal{L}_\infty(\sigma^{-n}(\mathfrak{A}))$.

Let $NG_{\sigma^{m-n}} \subseteq \mathcal{A}$ be the set of non-growing letters for $\sigma^{m-n}$, i.e. $\forall a \in NG_{\sigma^{m-n}}, \forall j \ge 1, |\sigma^{j(m-n)}(a)| = 1$. Let $k = \inf\{i \in \mathbb{N} \mid \tilde{x}_i \notin NG_{\sigma^{m-n}}\}$ ($k$ may be infinite). Then, for $i < k$, because $\sigma$ is a (nonerasing) substitution and every letter in $\tilde{x}_{[0,k-1]}$ is non-growing, $\sigma^{(m-n)}(\tilde{x})_i = \sigma^{(m-n)}(\tilde{x}_i)$. In addition, because $\tilde{x}$ is an adherence value of $(\sigma^{n+j(m-n)}(x))_{j \in \mathbb{N}}$, there is $p(\tilde{x}_i) \ge 1$ such that $\sigma^{p(\tilde{x}_i) \cdot (m-n)}(\tilde{x}_i) = \tilde{x}_i$ for every position $i < k$. Since $\mathcal{A}$ is finite, $(p(\tilde{x}_i))_{0 \le i < k}$ contains only finitely many values, so we can define $p = \text{lcm}\{p(\tilde{x}_i)\}$.

When $k < \infty$, there exists $q \ge 1$ such that $|\sigma^{q(m-n)}(\tilde{x}_k)| > 1$ and $\tilde{x}_k \subseteq_p \sigma^{q(m-n)}(\tilde{x}_k)$, for the same reason that $\tilde{x}$ is an adherence value of $(\sigma^{n+j(m-n)}(x))_{j \in \mathbb{N}}$. If $k = \infty$, we set $q = 1$.

Then, by concatenation, $\tilde{x}_{[0,k]} \subseteq_p \sigma^{pq(m-n)}(\tilde{x}_{[0,k]})$. Thus, $(\sigma^{jpq(m-n)}(\tilde{x}))_{j \in \mathbb{N}}$ has a limit, which is a fixed point for $\sigma^{pq(m-n)}$, and by compacity of $\mathcal{L}_\infty(\mathfrak{A})$, is accepted by $\mathfrak{A}$.

Because the emptiness of the language of an $\omega$-automaton is decidable:
**Corollary 1.** *The following problem is decidable:*

**Input:** An $\omega$-automaton $\mathfrak{A}$ and a substitution $\sigma$

**Question:** Does $\mathfrak{A}$ accept a fixed point of $\sigma^k$ for some $k$?

As is, this method alone cannot determine, for instance, whether $\mathfrak{A}$ accepts a fixed point for $\sigma$ itself (without power). This problem is still decidable, as we show later in Proposition 6 with a refinement of this method. In appendix, we provide examples where $\mathfrak{A}$ accepts fixed points for some $\sigma^k$ where $k$ does not correspond to $m-n$ where $n < m$ are the minimal powers such that $\sigma^{-n}(\mathfrak{A}) = \sigma^{-m}(\mathfrak{A})$.

Now, we come back to purely substitutive words. A purely substitutive word generated by $\sigma$ is also a fixed point for some $\sigma^k$ (in fact, it is a fixed point for every $\sigma^j$ with $j \ge 1$).

**Proposition 5.** Let $\mathfrak{A}$ be an $\omega$-automaton, $\sigma$ a substitution and $n < m \in \mathbb{N}$ be as in Fact 2. Let $RP_\sigma \subseteq \mathcal{A}$ be the set of letters that are right-prolongable for $\sigma$, i.e. $\forall b \in RP_\sigma, b \not\equiv_p \sigma(b)$. Then, $\mathfrak{A}$ accepts a purely substitutive word generated by $\sigma$ iff $\sigma^{-n}(\mathfrak{A})$ accepts an infinite word beginning with an element of $RP_\sigma$.

*Proof.* If $\mathfrak{A}$ accepts a purely substitutive word $u$ generated by $\sigma$, $u = \lim_{j \to \infty} \sigma^j(b)$ begins by an element of $RP_\sigma$. Since $\sigma(u) = u$, $\sigma^n(u)$ is accepted by $\mathfrak{A}$ so $u$ is accepted by $\sigma^{-n}(\mathfrak{A})$.

On the converse, suppose that $\sigma^{-n}(\mathfrak{A})$ accepts an infinite word beginning by $b \in RP_\sigma$. Then, $\sigma^{m-n}(b)$ labels a accepting walk on $\sigma^{-m}(\mathfrak{A}) = \sigma^{-n}(\mathfrak{A})$. By iteration, for every $k \ge 1$, we have that $\sigma^{k(m-n)}(b)$ labels a accepting walk on $\sigma^{-n}(\mathfrak{A})$, so $\sigma^{n+k(m-n)}(b)$ always labels an accepting walk on $\mathfrak{A}$. By compacity, $u = \lim_{k \to \infty} \sigma^{n+k(m-n)}(b)$ is accepted by $\mathfrak{A}$. Now, because $b \in RP_\sigma$, the word $\lim_{j \to \infty} \sigma^j(b)$ is defined and equal to $u$. Therefore $u$, the purely substitutive word generated by $\sigma$ on the letter $b$, is accepted by $\mathfrak{A}$.

The following result already appeared in [13], but an erratum clarified that some cases were not covered [14]. It is a parallel to a result in [6]. Our proof is essentially the same, but writing the proof through the lens of desubstitution makes it easier to extend the result to other decision problems.

**Corollary 2.** *The problem of the purely substitutive walk is decidable:*

**Input:** an $\omega$-automaton $\mathfrak{A}$, a homomorphism $\sigma$.

**Question:** Does $\mathfrak{A}$ accept some purely substitutive word generated by $\sigma$?

This result extends to morphic words: a morphic word generated by $\sigma$ and $\tau$ in $\mathfrak{A}$ is a purely substitutive word generated by $\sigma$ in $\tau^{-1}(\mathfrak{A})$.

We now extend the method used to prove Proposition 5 to solve the question of finding a pure fixed point for a substitution $\sigma$ in an $\omega$-automaton. This improves Proposition 4 where we found a fixed point for some power of $\sigma$.

**Proposition 6.** *The problem of the fixed point walk is decidable:*

**Input:** an $\omega$-automaton $\mathfrak{A}$, a substitution $\sigma$.

**Question:** Does $\mathfrak{A}$ accept a fixed point for $\sigma$?
*Proof.* Let $x$ a fixed point for $\sigma$ and define $FP_{\sigma} = \{b \in \mathcal{A} \mid \sigma(b) = b\}$ be the set of letters which are fixed points under $\sigma$. There are two cases:

1. $x$ is an infinite word on the alphabet $FP_{\sigma}$.

2. there is a letter $a$ appearing in $x$ such that $\sigma(a) \neq a$. Suppose that $a$ is the first such letter in $x$. Then $x$ can be written as $x = pax'$ where $p$ is a word on $FP_{\sigma}$. We have that $x = \sigma(x) = \sigma(p)\sigma(a)\sigma(x') = p\sigma(a)\sigma(x')$. So $a \subseteq_p \sigma(a)$: $a$ is right-prolongable for $\sigma$, so $\lim_{n \to \infty} \sigma^n(a)$ exists. Since $x = \sigma^n(x) = p\sigma^n(a)\sigma^n(x')$ for every $n \in \mathbb{N}$, by compacity, $x = p \lim_{n \to \infty} \sigma^n(a)$.

The algorithm works as follows. First (case 1), check whether $\mathfrak{A}$ accepts a word on the alphabet $FP_{\sigma}$. Second (case 2), define a new automata $\mathfrak{A}'$ which is equal to $\mathfrak{A}$ except that the set of initial states is all the states reachable in $\mathfrak{A}$ by words in $FP_{\sigma}$, and check (by the previous algorithm) if $\mathfrak{A}'$ accepts a purely substitutive word generated by $\sigma$.

The algorithm outputs "yes" if either case is satisfied, and "no" otherwise.

### 3.3 The problem of the infinitely desubstitutable walk

In this section, we suppose that $\mathfrak{A}$ is an $\omega$-automaton and $S$ is a finite set of substitutions (i.e. nonerasing homomorphisms), as is usual when studying multiple homomorphisms. We prove that the problem of finding an infinitely desubstitutable (infinite) word is decidable. To study this question, we introduce a meta-$\omega$-automaton: each symbol is a substitution, and each state is an $\omega$-automaton.

**Definition 8 (The meta-$\omega$-automaton $S^{-\infty}(\mathfrak{A}))$.** Define the $\omega$-automaton $S^{-\infty}(\mathfrak{A}) = (D(\mathfrak{A}), \{\mathfrak{A}\}, \mathcal{T})$ on the alphabet $S$, with the set of states $D(\mathfrak{A}) = \{\sigma^{-1}(\mathfrak{A}), \sigma \in S^*\}$, $\mathfrak{A}$ the only initial state and set of transitions $\mathcal{T} = \{\mathfrak{B} \stackrel{\sigma}{\to} \sigma^{-1}(\mathfrak{B}) \mid \mathfrak{B} \in D(\mathfrak{A}), \sigma \in S\}$.

Because $D(\mathfrak{A}) \subseteq \mathfrak{S}(\mathfrak{A})$ is finite (see Fact 1), $S^{-\infty}(\mathfrak{A})$ is computable. We prove that directive sequences of words accepted by $\mathfrak{A}$ correspond to *non-nilpotent* walks in $S^{-\infty}(\mathfrak{A})$, that is, walks $(\mathfrak{B}_n)_{n \in \mathbb{N}}$ such that $\mathcal{L}_{\infty}(\mathfrak{B}_n) \neq \emptyset$ for all $n$.

**Proposition 7.** There exists $x$ an infinite word infinitely desubstitutable by $(\sigma_n)_{n \in \mathbb{N}}$ accepted by $\mathfrak{A}$ if, and only if, there is a non-nilpotent infinite walk in $S^{-\infty}(\mathfrak{A})$ labeled by $(\sigma_n)_{n \in \mathbb{N}}$.

This result has structural consequences on the set of directive sequences:

**Corollary 3.** Let $\text{Rep}(\mathfrak{A}, S) = \{(\sigma_n)_{n \in \mathbb{N}} \mid \exists x \in \mathcal{L}_{\infty}(\mathfrak{A}), x \text{ is inf. desub. by } (\sigma_n)\}$ be the set of directive sequences of words accepted by $\mathfrak{A}$. Then $\text{Rep}(\mathfrak{A}, S)$ is the language of some $\omega$-automaton. In particular, $\text{Rep}(\mathfrak{A}, S)$ is closed as a subset of $S^{\mathbb{N}}$.

*Proof (of Proposition 7).* First, let $x$ be an infinitely desubstitutable word with directive sequence $(\sigma_n)_{n \in \mathbb{N}}$, and let $(x_n)_{n \in \mathbb{N}}$ be the sequence of desubstituted
words. Then, by Proposition 1, $x_n \in \mathcal{L}_\infty((\sigma_1 \circ \cdots \circ \sigma_{n-1})^{-1}(\mathfrak{A}))$. So the walk $(\sigma_{[0,n]}^{-1}(\mathfrak{A}))_{n \in \mathbb{N}}$ is non-nilpotent and labeled by $(\sigma_n)_{n \in \mathbb{N}}$.

Second, let $(\sigma_n)_{n \in \mathbb{N}}$ label a non-nilpotent infinite walk in $S^{-\infty}(\mathfrak{A})$. It means that each language $(\sigma_1 \circ \cdots \circ \sigma_k)^{-1}(\mathcal{L}_\infty(\mathfrak{A}))$ is nonempty. Now, consider the sequence $((\sigma_1 \circ \cdots \circ \sigma_n)(\mathcal{L}_\infty((\sigma_1 \circ \cdots \circ \sigma_n)^{-1}(\mathfrak{A}))))_{n \in \mathbb{N}}$. It satisfies the following:

1. each element of the sequence is included in $\mathcal{L}_\infty(\mathfrak{A})$;

2. because $\mathcal{L}_\infty((\sigma_1 \circ \cdots \circ \sigma_n)^{-1}(\mathfrak{A})))$ is compact and nonempty, and $(\sigma_1 \circ \cdots \circ \sigma_n)$ is continuous, every element of the sequence is compact and nonempty;

3. the sequence is decreasing for inclusion.

By Cantor's intersection theorem, there is a point $x$ in the intersection of every element of the sequence. This point $x$ is desubstitutable by any $\sigma_1 \circ \cdots \circ \sigma_k$, thus it is infinitely desubstitutable by the sequence $(\sigma_n)_{n \in \mathbb{N}}$.

With Proposition 7, we can deduce the decidability of the existence of an infinitely desubstitutable walk in an $\omega$-automaton $\mathfrak{A}$. First, build $S^{-\infty}(\mathfrak{A})$; second, remove the states corresponding to $\omega$-automata with an empty language; last, check whether there is an infinite walk.

**Proposition 8.** *The problem of the infinitely desubstitutable walk is decidable:*
**Input:** a finite set of substitutions $S$, an $\omega$-automaton $\mathfrak{A}$
**Question:** does $\mathcal{L}_\infty(\mathfrak{A})$ contain a word which is infinitely desubstitutable by $S$?

## 3.4 The problem of the Büchi infinitely desubstitutable walk

Proposition 8 does not apply directly to Sturmian words. Indeed, the classical characterization of Sturmian words restricts the possible directive sequences.

$S_{St}$ is the set containing the four following substitutions, called (elementary) Sturmian morphisms, as described by [4].

$$L_0: \begin{cases} 0 \to 0 \\ 1 \to 01 \end{cases}, \quad L_1: \begin{cases} 0 \to 10 \\ 1 \to 1 \end{cases}, \quad R_0: \begin{cases} 0 \to 0 \\ 1 \to 10 \end{cases}, \quad R_1: \begin{cases} 0 \to 01 \\ 1 \to 1 \end{cases}$$

**Theorem 3 ([8]).** A word is Sturmian iff it is infinitely desubstitutable by a directive sequence $(\sigma_n)_{n \in \mathbb{N}} \subset S_{St}$ that alternates infinitely in type, i.e.: $\mathbb{N} \in \mathbb{N}$, $(\forall n \ge N, \sigma_n \in \{L_0, R_0\})$ or $(\forall n \ge N, \sigma_n \in \{L_1, R_1\})$.

This characterization is usually expressed in the $S$-adic framework, but is equivalent in this context [12]. In this section, we generalize Theorem 8 to Sturmian words and more general restrictions on the directive sequence.

**Proposition 9.** *The problem of the Sturmian walk is decidable:*
**Input:** an $\omega$-automaton $\mathfrak{A}$.
**Question:** is there a Sturmian infinite word accepted by $\mathfrak{A}$?

*Proof.* Consider the associated representation automaton $S_{St}^{-\infty}(\mathfrak{A})$. According to Proposition 7 combined with Theorem 3, there is a Sturmian infinite word accepted by $\mathfrak{A}$ if, and only if, there is an infinite walk accepted by $S_{St}^{-\infty}(\mathfrak{A})$ labeled
by a word $(\sigma_n)_{n \in \mathbb{N}}$ which alternates infinitely in type. This last condition is decidable: compute the strong connected components of $\mathfrak{A}$, and check that there is at least one strongly connected component $C$ which contains two edges labeled by substitutions in $\{L_0, R_0\}$ and $\{L_1, R_1\}$, respectively.

In this case, the condition of alternating infinitely in type is easy to check: it can actually be described using a Büchi $\omega$-automaton on the alphabet $S$. Proposition 9 generalizes to every such condition.

**Definition 9.** Let $S$ be a set of substitutions, and $\mathfrak{R}$ a Büchi $\omega$-automaton on the alphabet $S$. Define $X_{\mathfrak{R}}$ as $\{x \in \mathcal{A}^\mathbb{N} \mid \exists(\sigma_n)_{n \in \mathbb{N}} \in \mathcal{L}_\infty(\mathfrak{R}), x \text{ is inf. desub. by } (\sigma_n)\}$.

**Proposition 10.** The following problem is decidable:

**Input:** an $\omega$-automaton $\mathfrak{A}$, a finite set of substitutions $S$, a Büchi $\omega$-automaton $\mathfrak{R}$ on the alphabet $S$

**Question:** is there an infinite word of $X_{\mathfrak{R}}$ accepted by $\mathfrak{A}$?

*Proof.* The question of the problem is equivalent to: is $\mathcal{L}_\infty(\mathfrak{R}) \cap \mathcal{L}_\infty(S^{-\infty}(\mathfrak{A})) \neq \emptyset$? The intersection between a Büchi $\omega$-automaton and an $\omega$-automaton is a Büchi $\omega$-automaton that can be effectively constructed, and checking the non-emptiness of a Büchi $\omega$-automaton is decidable.

The interest of Proposition 10 is that there exists a zoology of families of words which have a characterization by infinite desubstitution. For instance, Proposition 10 applies to Arnoux-Rauzy words [1] and to minimal dendric ternary words [9]. We also characterize the set of allowed directive sequences akin to Corollary 3: the set of directive sequences on $S$ accepted by the Büchi $\omega$-automaton $\mathfrak{R}$ that define a word accepted by $\mathfrak{A}$ is itself recognized a Büchi $\omega$-automaton.

Let us translate Proposition 10 in more dynamical terms:

**Proposition 11.** The following problem is decidable:

**Input:** a set of substitutions $S$, a Büchi $\omega$-automaton $\mathfrak{R}$ on the alphabet $S$ and a sofic shift $\mathcal{S}$.

**Question:** Is $\mathcal{S} \cap X_{\mathfrak{R}}$ empty?

## 3.5 Application to the coding of Sturmian words

Here is an example of a natural question from combinatorics on words that we solve on Sturmian words, even though the method generalizes easily. Let $W$ be a finite set of finite words on $\{0,1\}$. Consider $W^\omega$ the set of infinite concatenations of elements of $W$, i.e. $W^\omega = \{x \in \{0,1\}^\mathbb{N} \mid \exists (w_n)_{n \in \mathbb{N}} \subseteq W, x = \lim_{n \to \infty} w_0 w_1 \dots w_n\}$.

**Proposition 12.** The following problem is decidable:

**Input:** $W$ a finite set of words on $\{0,1\}$

**Question:** does $W^\omega$ contain a Sturmian word?

*Proof.* The language $W^\omega$ is $\omega$-regular: there is an $\omega$-automaton $\mathfrak{A}_W$ such that $\mathcal{L}_\infty(\mathfrak{A}_W) = W^\omega$. Then, $W^\omega$ contains a Sturmian word iff $\mathfrak{A}_W$ accepts a Sturmian word, which is decidable by Proposition 9.
# 4 About $\omega$-automata recognizing Sturmian words

In this Section, we focus on Sturmian words and show that the language of Sturmian words is as far as possible from being regular, in the sense that an $\omega$-automaton may only accept a Sturmian word if it accepts the image of the full shift under a Sturmian morphism.

**Theorem 4.** Let $S = S_{St}$ be the set of elementary Sturmian morphisms as defined earlier, and let $\mathfrak{A}$ be an $\omega$-automaton. If $\mathfrak{A}$ accepts a Sturmian word, then $\exists \sigma \in S_{St}^*, \sigma(\mathfrak{A}^N) \subseteq \mathcal{L}_{\infty}(\mathfrak{A})$.

This is equivalent to the presence of a total automaton in $S^{-\infty}(\mathfrak{A})$: an $\omega$-automaton $\mathfrak{A}$ is total if $\mathcal{L}_{\infty}(\mathfrak{A}) = \mathcal{A}^N$. Totality is a stable property under any desubstitution.

*Proof.* Let $x$ be a Sturmian word accepted by $\mathfrak{A}$. Consider the transformation of $\omega$-automata forget : $(Q, I, T) \mapsto (Q, \mathcal{O}(T))$ which makes all states initial. Then, forget($\mathfrak{A}$) also accepts $x$, and its language is shift-invariant: therefore, $O(x) \subseteq \mathcal{L}_{\infty}(\text{forget}(\mathfrak{A}))$. Let $\chi(x)$ be the Sturmian characteristic word associated with $x$ (see [11]): it belongs to $O(x)$, so it is accepted by forget($\mathfrak{A}$). Then, $\chi(x) = \lim_{n \to \infty} \sigma_0 \circ \cdots \circ \sigma_n(a_n)$ with $(\sigma_n)_{n \in \mathbb{N}} \subseteq S_{St}$ a sequence that alternates infinitely in type (see Theorem 3). But, because $\chi(x)$ is a characteristic word, it represents the orbit of zero when considering the point of view of circle rotation (see [11]): when combined with Proposition 2.7 of [5], it yields that $(\sigma_n)_{n \in \mathbb{N}} \subseteq \{L_0, L_1\}^N$. By the pigeonhole principle, there is an $\omega$-automaton $\mathfrak{B}$ that appears infinitely often in the sequence $(\sigma_{[0,n]}^{-1}(\text{forget}(\mathfrak{A})))_{n \in \mathbb{N}} \subseteq \mathfrak{S}(\text{forget}(\mathfrak{A}))$. Thus, we can find a substitution $\tau$ such that $\mathfrak{B} = \tau^{-1}(\mathfrak{B})$ and $\tau \in S_{St}^* \setminus (L_0^* \cup L_1^*)$. Because $\tau$ contains both $L_0$ and $L_1$, there are two cases:

1. $L_1 L_0 \subseteq_f \tau$: we can write $\tau = p_\tau L_1 L_0 s_\tau$. Let $\mathfrak{B}' = (p_\tau \circ L_1)^{-1}(\mathfrak{B})$ and $\tau' = L_0 \circ s_\tau \circ p_\tau \circ L_1$: we have that $\tau'^{-1}(\mathfrak{B}') = \mathfrak{B}'$.

2. $L_1 L_0 \not\subseteq_f \tau$: then, $\tau$ begins with a $L_0$ and ends with a $L_1$.

In both cases, we can come back to the case where $\tau$ begins with a $L_0$ and ends with a $L_1$.

We now prove the following technical lemma:

**Definition 10.** Let $\mathfrak{A}$ be an $\omega$-automaton on $\mathcal{A} = \{0,1\}$. A state $q$ of $\mathfrak{A}$ has property $(H)$ if $(\exists q_s, q \xrightarrow{0} q_s \to^\omega \cdots \in \mathfrak{A}) \Leftrightarrow (\exists q_t, q \xrightarrow{1} q_t \to^\omega \cdots \in \mathfrak{A})$, where $q_s \to^\omega \cdots$ means that there is an infinite computation starting from $q_t$ in $\mathfrak{A}$.

If all states of $\mathfrak{A}$ have property $(H)$, there are two possibilities: if there is no infinite computation starting on an initial state, the infinite language of $\mathfrak{A}$ is empty; otherwise, $\mathfrak{A}$ is total.

**Lemma 1.** Let $\mathfrak{C}$ be an $\omega$-automaton, and $\phi \in S_{St}^*$ starting with $L_0$ and ending with $L_1$ such that $\phi^{-1}(\mathfrak{C}) = \mathfrak{C}$. Then, every state of $\mathfrak{C}$ has property $(H)$.
*Proof (of Lemma 1).* Let $\mathfrak{C} = (Q_{\mathfrak{C}}, I_{\mathfrak{C}}, T_{\mathfrak{C}})$, and $q \in Q_{\mathfrak{C}}$. First, suppose that $q \xrightarrow{0} q_t \to^{\omega} \dots$ is a computation in $\mathfrak{C}$. Then $q \xrightarrow{0} q_t$ is also a transition of $\phi^{-1}(\mathfrak{C})$. So $q \xrightarrow{\phi(0)} * q_t$ is a computation in $\mathfrak{C}$. Because $\phi$ ends with $L_1$, $\phi(1) \subseteq_p \phi(0)$. So $q \xrightarrow{\phi(1)} * q_u \xrightarrow{m} * q_t \to^{\omega} \dots$ is a computation in $\mathfrak{C}$, with some $q_u \in Q_{\mathfrak{C}}$ and $\phi(0) = \phi(1)m$. Now, using $\mathfrak{C} = \phi^{-1}(\mathfrak{C})$, $q \xrightarrow{1} q_u \xrightarrow{m} * q_t \to^{\omega} \dots$ is a computation in $\mathfrak{C}$.

Conversely, if $q \xrightarrow{1} q_t \to^{\omega} \dots$ is a computation in $\mathfrak{C} = \phi^{-1}(\mathfrak{C})$, there is also $q \xrightarrow{\phi(1)} * q_t \to^{\omega} \dots$. Because $\phi$ begins with $L_0$, $\phi(1) = 0m$ for some finite $m$. So the last computation can be written $q \xrightarrow{0} q_u \xrightarrow{m} * q_t \to^{\omega} \dots$. $\square$

Now, we apply Lemma 1 to show that every state of $\mathfrak{B}$ has property (H). $\mathfrak{B}$ can be written as $\psi^{-1}(\text{forget}(\mathfrak{A}))$ for some Sturmian morphism $\psi$. Since the transformation forget does not modify the transitions of an $\omega$-automaton, this yields that every state of $\psi^{-1}(\mathfrak{A})$ also has property (H). Since by assumption $\psi^{-1}(\mathfrak{A})$ accepts an infinite word, it follows that it is total.

By applying the proof of Theorem 4, we obtain an equivalent statement for the Fibonacci word:

**Corollary 4.** Let $f$ be the Fibonacci word, i.e. the substitutive word associated with the substitution $\sigma_f(0) = 01, \sigma_f(1) = 0$. Let $\mathfrak{A}$ be an $\omega$-automaton which accepts $f$. Then, there exists $n \in \mathbb{N}$ such that $\sigma_f^{-n}(\mathfrak{A})$ is total.

This combinatorial result can be thought in dynamical terms:

**Corollary 5.** A sofic subshift contains $f$ iff it contains some $\sigma_f^k(\mathcal{A}^n)$.

Because the Fibonacci word is aperiodic, containing $f$ means that there is a substitution $\tau$ such that $\tau(\mathcal{A}^n)$ is contained in $\mathfrak{S}$. Because the Fibonacci word is Sturmian, Berstel and Séébold [4] established that $\tau$ had to be a Sturmian morphism. This new analysis specifies that $\tau$ can be chosen a power of $\sigma_f$.

# 5 Open questions

- Following Proposition 8, find an algorithm to find an accepted $\mathcal{S}$-adic word. There are technical difficulties to take into account the growth of the directive sequence, which should be solvable using results from [12].

- Can our methods extend to Büchi $\omega$-automata, as in [6]? The difficulty is that the language of Büchi $\omega$-automata is not always compact, so Proposition 4 does not apply. It may be possible to extend methods from [6].

- For which sets of substitutions does Theorem 4 hold?
## References

1. Arnoux, P., Rauzy, G.: Représentation géométrique de suites de complexité 2n+1. Bulletin de la Société mathématique de France **119**, 101–117 (01 1991). https://doi.org/10.24033/bsmf.2164

2. Bassino, F., David, J., Sportiello, A.: Asymptotic enumeration of minimal automata. Leibniz International Proceedings in Informatics, LIPIcs **14** (09 2011). https://doi.org/10.4230/LIPIcs.STACS.2012.88

3. Berstel, J.: Axel thue’s papers on repetitions in words: a translation. in: Publications du lacim, vol. 20. u (1992)

4. Berstel, J., Séébold, P.: Sturmian Words. In: M., L. (ed.) Algebraic Combinatorics on Words. Cambridge University Press (2002)

5. Berthé, V., Holton, C., Zamboni, L.Q.: Initial powers of sturmian sequences. Acta Arithmetica (2006)

6. Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Information and Computation (2002)

7. Ferenczi, S.: Rank and symbolic complexity. Ergodic Theory and Dynamical Systems (1996)

8. Fogg, N.P.: Sturmian Sequences, chap. 6. Springer Berlin Heidelberg (2002)

9. Gheeraert, F., Lejeune, M., Leroy, J.: S-adic characterization of minimal ternary dendric subshifts. CoRR abs/2102.10092 (2021), https://arxiv.org/abs/2102.10092

10. Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). https://doi.org/10.1017/CBO9780511626302

11. Perrin, D., Restivo, A.: A note on sturmian words. Theoretical Computer Science (2012)

12. Richomme, G.: On sets of indefinitely desubstitutable words. Theoretical Computer Science (2021)

13. Salo, V.: Decidability and universality of quasiminimal subshifts. Journal of Computer and System Sciences **89**, 288–314 (2017). https://doi.org/10.1016/j.jcss.2017.05.017

14. Salo, V.: Notes and errata on "decidability and universality of quasiminimal subshifts" (2022), https://villesalo.com/notes/DaUoQSNotes.html

15. Thomas, W.: Languages, Automata, and Logic. Springer Berlin Heidelberg (1997)
# 6 Appendix

## 6.1 Counterexamples for Proposition 4

Using the notation of Proposition 4, consider $n < m$ minimal such that $\sigma^{-n}(\mathfrak{A}) = \sigma^{-m}(\mathfrak{A})$. There is no clear relationship between $n$, $m$ and $k$ the power of the fixed point accepted by $\mathfrak{A}$.

Here is an example with $m - n \ge 2$, but $\mathfrak{A}$ accepts a fixed point for $\sigma$.

<figure><img src="image_4.png" /><figcaption>Fig. 2: $n = 0$ and $m = 2$, but $\mathfrak{A}$ accepts $0^{\infty}$, which is a fixed point for $\sigma$.</figcaption></figure>

Next is an example where $m - n$ is lesser than the power required to have a fixed point:

<figure><img src="image_5.png" /><figcaption>Fig. 3: $\tau^{-1}(\mathfrak{B}) = \mathfrak{B}$, so $m = 1$ and $n = 0$. $\tau$ has no fixed point: $\mathfrak{B}$ cannot contain a fixed point for $\tau^{m-n}$. However, $\mathfrak{B}$ contains a fixed point for $\tau^2$.</figcaption></figure>

## 6.2 There is not always a total automaton in $S^{-\infty}(\mathfrak{A})$

Theorem 4 does not generalize straightforwardly to any set of substitutions: in general, $S^{-\infty}(\mathfrak{A})$ may not contain a total automaton, even under classical dynamical constraints. For instance, consider the following $\omega$-automaton $\mathfrak{A}_H$ and substitution $\sigma_H$:

<figure><img src="image_6.png" /><figcaption>Fig. 4: An $\omega$-automaton stable by desubstitution by $\sigma_H$.</figcaption></figure>

Notice that $\sigma_H$ is primitive, and that the three purely substitutive words generated by $\sigma_H$ are not eventually periodic. However, $\mathfrak{A}_H$ is not total, and $\sigma_H^{-1}(\mathfrak{A}_H) = \mathfrak{A}_H$, so there is no total automaton in $S^{-\infty}(\mathfrak{A})$. In dynamical terms, it means that the sofic shift contains the associated purely substitutive words, but contains no factor of the form $\sigma_H^k(\mathbb{A}^N)$.