Abstract
We present a new framework for studying C ∞ -words, that are arbitrarily many times differentiable words over the alphabet Σ = {1, 2}. After introducing an equivalence relation on C ∞ -words, whose classes are called minimal classes and represent all the C ∞ -words, we define a vertical coding of these words based on a three-letter alphabet, and a set of functions operating over this representation. We show that the minimal classes of C ∞ -words can be represented on an infinite directed acyclic graph, which, as well as all the functions introduced for the vertical coding, can be defined recursively with no explicit reference to C ∞ -words. This new representation adequately expresses the combinatorial structure of C ∞ -words, and brings new perspectives in the study of the Kolakoski word and its factors.

words are called smooth words [3, 1] . Nevertheless, the existence of a smooth word such that the set of its factors is equal to the whole set C ∞ is still an open question.

Another renowned open problem is to decide whether the Kolakoski word (or any other smooth word) is recurrent (every factor appears infinitely often) or even uniformly recurrent (consecutive occurrences of the same factor appear with bounded gap). Should Conjecture 1.1 be true, the Kolakoski word would be recurrent [6] .

In addition to the aforementioned problems, there is a conjecture of Keane [9] stating that the frequencies of 1's and 2's in the Kolakoski sequence exist and are equal to 1 2. Chvátal [5] showed that if these limits exist, they are very close to 1 2 (actually, between 0.499162 and 0.500838).

Up to now, only few combinatorial properties of C ∞ -words have been established. Weakley [13] started a classification of C ∞ -words and obtained significant results on their complexity function. Carpi [4] proved that the set C ∞ contains only a finite number of squares, and does not contain cubes (see also [12] and [2] ).

This result generalizes to repetitions with gap, i.e., to the words in C ∞ of the form uzu, for a non-empty z.

Indeed, Carpi [4] proved that for every k > 0, only finitely many C ∞ -words of the form uzu exist with z not longer than k. In a recent paper [7] , we proved that for any u ∈ C ∞ , there exists a z such that uzu ∈ C ∞ , and uzu ≤ C u 2.72 , for a suitable constant C. In the same paper, we proposed the following conjecture:

Universal Glueing Conjecture. For any u, v ∈ C ∞ , there exists z such that uzv ∈ C ∞ .

Despite the Universal Glueing Conjecture being a weaker assumption than Conjecture 1.1, it remains an open question. Its validity would imply, among other things, that for any integer n > 0, there exists a C ∞ -word containing as factors all the C ∞ -words of length n.

Let w be a C ∞ -word. Recall that any word v such that w is the derivative of v is called a primitive of w. For example, the primitives of the word 21 are 2212, 1121, 12212 and 21121. The C ∞ -words having the property that each derivative is obtained from the shortest primitive are called minimal words. Analogously, C ∞ -words having the property that each derivative is obtained from the longest primitive are called maximal words. Moreover, a C ∞ -word is single-rooted if its last non-empty derivative is a word of length one (that is, 1 or 2), or double-rooted if its last non-empty derivative is a word of length two (that is, 12 or 21).

In this paper, we mostly focus on single-rooted minimal words. Indeed, we show in Theorem 2.3 that every C ∞ -word w of height k > 0 (the height of a C ∞ -word w is defined as the least integer k such that the k-th derivative of w is the empty word) contains exactly one single-rooted minimal factor of height k (if w is single-rooted) or two single-rooted minimal factors of height k (if w is double-rooted). The first single-rooted minimal factor of height k appearing in a C ∞ -word w is called the minimal part of w. Thus, every C ∞ -word is an extension of its minimal part preserving the height. This allows us to consider classes of C ∞ -words having the same minimal part (that we call minimal classes).

We recall a framework for dealing with C ∞ -words that we introduced in a recent paper [7] , based on a three-letter alphabet. We define, for every C ∞ -word w, two words U 0 and V 0 over the alphabet Σ 0 = {0, 1, 2}, called respectively the left frontier and the right frontier of w, which code respectively the sequences of the first and the last symbols of the derivatives of w. The pair (U 0 , V 0 ) uniquely determines w, and is called the vertical representation of w (Theorem 3.1). Minimal words do not have 0's in their vertical representation, that is, are coded by left and right frontiers over the alphabet Σ = {1, 2}. As a consequence, single-rooted minimal words (and hence minimal classes) are in bijection with Σ * . We then define the functions Γ s and Γ d , which map the left frontier of a C ∞ -word into its right frontier.

More precisely, for any U ∈ Σ * , Γ s (U ) is the word V ∈ Σ * such that (U, V ) is the vertical representation of the single-rooted minimal word having U as left frontier, whereas Γ d (U ) is the word V ′ ∈ Σ * such that (U, V ′ ) is the vertical representation of the double-rooted minimal word having U as left frontier. The functions Γ s and Γ d are idempotent and therefore establish bijections of Σ * . We also define the compositions Θ = Γ s ○ Γ d and Π = Γ d ○ Γ s , for which we are able to find a very compact recursive form (Corollary 4.3), that can be defined independently from the context of C ∞ -words (Theorem 4.4). The functions Γ s and Γ d , and therefore Θ and Π, can be naturally extended to words with 0's, that is, words coding the frontiers of any C ∞ -word.

We then show that any single-rooted minimal word u having left frontier U ∈ Σ * and height k > 0 has three extensions to the right of minimal length having height k + 1: the two single-rooted minimal words having left frontier U 1 and U 2 respectively, and the word having left frontier U 0. We show that the minimal part of this latter word is the single-rooted minimal word having left frontier Θ(U )2 (Theorem 5.1).

This allows us to define the graph of minimal classes G, whose set of nodes is Σ * and every node has three outgoing edges, labeled respectively by 1, 2 and 0. For every non-empty U ∈ Σ * there is an edge from U to U 1 labeled by 1, an edge from U to U 2 labeled by 2, and an edge from U to Θ(U )2 labeled by 0.

In [7] , we introduced an infinite state automaton for representing the (classes of) C ∞ -words. In fact, G is the graph of this automaton. As a consequence of the recursive formulae given for Θ and Π, we have that the graph G can be defined recursively with no explicit reference to C ∞ -words.

We end the paper by formulating conjectures on the graph G that imply conjectures on C ∞ -words and on the Kolakoski word. As a consequence of our approach, these conjectures can be stated in the context of directed acyclic graphs or even in that of recursive functions, that is, independently from the context of C ∞ -words.

The paper is organized as follows. In Sec. 2 we gather the background on C ∞ -words and we fix the notation. In Sec. 3 we introduce the frontiers of C ∞ -words and the vertical representation, whereas in Sec.

4 we define the functions on the frontiers of a C ∞ -word and derive recursive formulae for them. In Sec.

5 we show how a C ∞ -word can be extended to the right into another C ∞ -word from the point of view of the vertical representation, and present the graph G of minimal classes of C ∞ -words. Finally, in Sec. 6, we

discuss conclusion and open problems.
C ∞ -words
We fix the two-letter alphabet Σ = {1, 2}. A word over Σ is a finite sequence of letters from Σ. The length of a word w is denoted by w . The empty word has length zero and is denoted by ε. The set of all words over Σ is denoted by Σ * . The set of all finite words over Σ having length n is denoted by Σ n . The i + 1-th symbol of a word w is denoted by w[i]. So, we write a word w of length n > 0 as
C ∞ -words
Let w ∈ Σ * . If w = uv for some u, v ∈ Σ * , we say that u is a prefix of w and v is a suffix of w. A factor of w is a prefix of a suffix of w (or, equivalently, a suffix of a prefix). The reversal of w is the wordw obtained by writing the letters of w in the reverse order. For example, the reversal of w = 11212 isw = 21211. The complement of w is the word w obtained by swapping the letters of w, i.e., by changing the 1's in 2's and the 2's in 1's. For example, the complement of w = 11212 is w = 22121.
C ∞ -words
A right-infinite word over Σ is a non-ending sequence of letters from Σ. The set of all right-infinite words over Σ is denoted by Σ ω . Let w be a word over Σ. Then w can be uniquely written as a concatenation of maximal blocks of identical symbols (called runs), i.e., w = x i1 1 x i2 2 ⋯x in n , with x j ∈ Σ, x j ≠ x j+1 , and i j > 0. The run-length encoding of w, noted ∆(w), is the sequence of exponents i j , i.e., one has ∆(w) = i 1 i 2 ⋯i n . The run-length encoding extends naturally to right-infinite words.
Definition 1.
[3] A right infinite word W ∈ Σ ω is called a smooth word over Σ if for every integer k > 0 one has that ∆ k (W) is still a word over Σ.
Definition 1.
The operator ∆ on right infinite words over Σ has two fixed points, namely the Kolakoski word
Definition 1.
and the word 1K. In this paper, we focus on the set C ∞ of factors of smooth words. We start by recalling some definitions.
Definition 2.
[6] A word w ∈ Σ * is differentiable if ∆(w) is still a word over Σ.
Definition 2.
Remark 1. Since Σ = {1, 2} we have that w is differentiable if and only if neither 111 nor 222 appear in w.
Definition 2.
The derivative is the function D ∶ Σ * → Σ * defined on the differentiable words by:
Definition 2.
In other words, the derivative D(w) is obtained from ∆(w) by erasing the first and/or the last symbol if they are equal to 1.
Definition 2.
is defined. By Remark 1, a word w is kdifferentiable if and only if for every 0 ≤ j < k the word D j (w) does not contain 111 nor 222 as factor. We use the convention that D 0 (w) = w. Clearly, if a word is k-differentiable, then it is also j-differentiable for every 0 ≤ j ≤ k.
Definition 2.
We denote by C k the set of k-differentiable words, and by C ∞ the set of words which are differentiable arbitrarily many times. Therefore,
Definition 2.
As a direct consequence of the definition, we have that the set C ∞ and, for any k ≥ 0, the set C k , are closed under reversal and complement.
Definition 2.
Therefore, the root of w belongs to {1, 2, 12, 21}. Consequently, w is single-rooted if its root has length one or double-rooted if its root has length two.
Definition 2.
It is easy to see that any C ∞ -word has two, four or eight distinct primitives (actually, it has two primitives if it starts and ends with 1, eight primitives if it starts and ends with 2, and four primitive else). For example, the word w = 22 has eight primitives (1122, 21122, 11221, 211221, 2211, 12211, 22112, 122112), whereas the word w = 121 has only two primitives (121121, 212212). However, every C ∞ -words admits exactly two primitives of minimal (maximal) length, one being the complement of the other.
Definition 7.
[7] Let w be a C ∞ -word of height k > 1. We say that w is minimal (resp. maximal) if for
Definition 7.
is a primitive of D j+1 (w) of minimal (resp. maximal) length. The words of height k = 1 are assumed to be at the same time minimal and maximal.
Definition 7.
We can define minimal and maximal words on one side only, in the following way.
Definition 8. [7] A word w ∈ C
∞ is left minimal (resp. left maximal) if it is a prefix of a minimal (resp. maximal) word. Analogously, w is right minimal (resp. right maximal) if it is a suffix of a minimal (resp. maximal) word.
Definition 8. [7] A word w ∈ C
Clearly, a word is minimal (resp. maximal) if and only if it is both left minimal and right minimal (resp. left maximal and right maximal). Example 1. The word 2211 is minimal, since 2211 is a primitive of 22 of minimal length and 22 is a primitive of 2 of minimal length; the word 21221121 is maximal, since 21221121 is a primitive of 1221 of maximal length and 1221 is a primitive of 2 of maximal length; the word 2122112 is left maximal but not right maximal. Note that 2211 is a proper factor of 21221121 and that the two words have the same height and the same root. 
Definition 8. [7] A word w ∈ C
Weakley started a classifications of C ∞ -words based on the extendability. Indeed, any C ∞ -word has arbitrary long left and right extensions in C ∞ . Indeed, for any C ∞ -word w at least one between 1w and 2w is a C ∞ -word. Analogously, at least one between w1 and w2 is a C ∞ -word.
Definition 9.
[13] A word w ∈ C ∞ is left doubly extendable (resp. right doubly extendable) if 1w and 2w
Definition 9.
(resp. w1 and w2) are both in C ∞ . Otherwise, w is left simply extendable (resp. right simply extendable).
Definition 9.
A word w ∈ C ∞ is fully extendable if 1w1, 1w2, 2w1 and 2w2 are all in C ∞ .
Definition 9.
It is worth noticing that a word can be at the same time left doubly extendable and right doubly extendable but not fully extendable. This is the case, for example, for the word w = 1.
Definition 9.
Note that, by definition, any C ∞ -word w can be extended to the left and to the right with simple extensions in a unique way, up to a left-and-right doubly extendable (but not necessarily fully extendable) word w ′ . Based on the previous definitions and on a result of Weakley ([13] , Proposition 3) one can establish the following structural result.
Definition 9.
The following conditions are equivalent:
Definition 9.
1. w is fully extendable (resp. w is left doubly extendable, resp. w is right doubly extendable).
Definition 9.
2. w is double-rooted maximal (resp. w is left maximal, resp. w is right maximal).
Definition 9.
3. w and all its derivatives (resp. w and all its derivatives longer than one) begin and end (resp. begin, resp. end) with two distinct symbols.
Definition 9.
Example 2. Consider the word w = 121. By Theorem 2.1, w is left doubly extendable and right doubly extendable. Nevertheless, w is not fully extendable, since it is single-rooted. Indeed, the word 2w2 is not in
Definition 9.
We report here a lemma given in [7] with a slightly different statement. Basically, it states that extending to the right by one letter a right maximal word (resp. extending to the left by one letter a left minimal word) results in a right minimal word (resp. a left minimal word). Recall that, by Theorem 2.1, a right (resp. left) maximal word is right (resp. left) doubly extendable.
Definition 9.
Lemma 2.2. [7] Let w ∈ C ∞ be a right maximal word (resp. a left maximal word). Then the words w1 and w2 are right minimal words (resp. 1w and 2w are left minimal words). Conversely, if wx, x ∈ Σ, is a right minimal word (resp. xw is a left minimal word), then w is a right maximal word (resp. w is a left maximal word).
Definition 9.
Let us summarize the previous results. Let v be a C ∞ -word of height k > 0. Then we know that v can be extended, to the left and to the right, with simple extensions (therefore, in a unique way) up to reaching a wordv, which is left doubly extendable and right doubly extendable (so,v is a maximal word). Moreover,v has the same root and the same height as v. Now, two substantially different cases arise: if v is double-rooted, then so isv, and thereforev is fully extendable, that is, the four words 1v1, 1v2, 2v1 and 2v2 are all C ∞ -words. In particular, there is a choice of x, y ∈ Σ such that the words xvy and xvy are minimal words of height k + 2 and root 2, and the words xvy and xvy are double-rooted minimal words of height k + 1. If instead v is single-rooted, then so isv, and thereforev is not fully extendable. In fact, only three among the four words 1v1, 1v2, 2v1 and 2v2 are C ∞ -words. In particular, there is a choice of x, y ∈ Σ such that the word xvy is a minimal word of height k + 1 and root 1. The words xvy and xvy are instead words of height k + 1 and root 2, but they are minimal on one side only, while the word xvy is not a C ∞ -word 2 .
Definition 9.
Example 3. The word v = 1122 is a single-rooted minimal word of height 3. It extends to the single-rooted maximal word (of height 3)v = 12112212. Table 1 shows the extensions ofv.
Definition 9.
Example 4. The word v = 1122122 is a double-rooted minimal word of height 3. It extends to the doublerooted maximal word (of height 3)v = 1211221221. One of the aims of this paper is to show that single-rooted minimal words are all one needs for dealing with C ∞ -words. The definition of minimal part induces an equivalence relation on the set of C ∞ -words (defined by the property of having the same minimal part). We call a class of C ∞ -words w.r.t. this equivalence a minimal class. As a direct consequence of Theorem 2.3, there is a one-to-one correspondence between minimal classes and single-rooted minimal words. We will show that there is also a one-to-one correspondence between the set of single-rooted minimal words and the set Σ * . Consequently, there are exactly 2 k single-rooted minimal words of height k (and so 2 k minimal classes of height k). Weakley [13] conjectured that for every k ≥ 0, any double-rooted maximal word (that is, by Theorem 2.1, any fully extendable word) of height k is shorter than any double-rooted maximal word of height k + 1. Weakley's conjecture can also be rephrased in terms of minimal words, i.e. it is equivalent to the following Conjecture 2.5. Any minimal word of root 2 and height k is shorter than any minimal word of root 2 and height k + 1.
Definition 9.
Indeed, any minimal word of root 2 and height k > 2 is of the form xwy, with x, y ∈ Σ and w is a double-rooted maximal word of height k − 2.
Definition 9.
One can wonder whether Weakley's conjecture holds true when double-rooted minimal words are replaced with single-rooted maximal words, i.e., whether any single-rooted maximal word of height k is shorter than any single-rooted maximal word of height k + 1. Note that any minimal word of root 1 and height k > 1 is of the form xwy, with x, y ∈ Σ and w is a single-rooted maximal word of height k − 1. Therefore, one can equivalently wonder whether any minimal word of root 1 and height k is shorter than any minimal word of root 1 and height k + 1. However, the answer to the above question is negative. For example, there exist minimal words w, w ′ of root 1 and height, respectively, 19 and 20, such that w = 3858 and w ′ = 3851. It is worth noticing that Weakley's conjecture is also equivalent to the following Conjecture 2.6. Any double-rooted minimal word of height k is shorter than any double-rooted minimal word of height k + 1.
Definition 9.
Indeed, as a consequence of Lemma 2.2, xw, x ∈ Σ, is a minimal word of root 2 and height k + 1 if and only if xw is a double-rooted minimal word of height k.
Vertical representation of C ∞ -words
We recall here the definition of vertical representation of a C ∞ -word [7] .
Vertical representation of C ∞ -words
We define a function Ψ for representing a C ∞ -word on a three-letter alphabet Σ 0 = {0, 1, 2}. This function is a generalization of the function Φ considered in [3] , that associates to any
Vertical representation of C ∞ -words
the sequence of the first symbols of the derivatives of w, that is, the function defined by Φ(w)
Vertical representation of C ∞ -words
If one takes the first and the last symbol of each derivatives of a C ∞ -word w, that is, the pair Φ(w), Φ(w), one gets a representation of C ∞ -words that is not injective. For example, take the two C ∞ -words w = 2211 and w ′ = 21121221. Then one has Φ(w) = Φ(w ′ ) = 222 and Φ(w) = Φ(w ′ ) = 122. In order to obtain an injective representation, we need an extra symbol. We thus introduce the following definition.
Vertical representation of C ∞ -words
We set Σ 0 = {0, 1, 2}. We also set 
Vertical representation of C ∞ -words
For the empty word, we set Ψ(ε) = ε. The right frontier of w is defined as Ψ(w). If U and V are respectively the left and right frontier of w, we call U V the vertical representation of w.
Vertical representation of C ∞ -words
In other words, to obtain the left (resp. the right) frontier of w, one has to take the first (resp. the last) symbol of each derivative of w and replace a 2 by a 0 whenever the primitive above is not left minimal (resp. is not right minimal).
Vertical representation of C ∞ -words
Example 6. Let w = 21221211221. We have:
Vertical representation of C ∞ -words
The word D 2 (w) = 122 is not a left minimal primitive of the word D 3 (w) = 2, and therefore Ψ(w) [3] , the fourth symbol of the left frontier of w, is a 0; analogously, the word w = 21221211221 is not a right minimal primitive of D(w) = 121122, and therefore Ψ(w) [1] , the second symbol of the right frontier of w, is a 0. Hence, the vertical representation of w is Ψ(w) Ψ(w) = 2110 1022.
Vertical representation of C ∞ -words
The following theorem is a direct consequence of the definition of vertical representation. Hence, we can state the following
Vertical representation of C ∞ -words
There is a one-to-one correspondence between the set of single-rooted minimal words and Σ * . This correspondence is given by the map Ψ.
Vertical representation of C ∞ -words
Therefore, there are exactly 2 k single-rooted minimal words of height k. Analogously, the map Ψ gives also a one-to-one correspondence between the set of double-rooted minimal words and Σ * , and therefore there are exactly 2 k double-rooted minimal words of height k. Clearly, if a smooth word contains all the single-rooted minimal words of height k + 1 as factors, then it will also contain as factors all the C ∞ -words of height k, by Theorem 2.3. So, in order to prove that a smooth word W over Σ contains as factors all the C ∞ -words, it is sufficient to prove that W contains as factors all the single-rooted minimal words. We end this section with a conjecture. Should Conjecture 3.3 be true, any smooth word over Σ would contain all the C ∞ -words as factors and would be uniformly recurrent. In particular, this would be true for the Kolakoski word.
Functions on the frontiers
Let U ∈ Σ * . Then, by Proposition 3.2, U is the left frontier of a unique single-rooted minimal word w. We denote by Γ s (U ) the right frontier of w. Analogously, U is the left frontier of a unique double-rooted minimal word w ′ . We denote by Γ d (U ) the right frontier of w ′ .
Functions on the frontiers
Example 7. Let U = 2122. Then Γ s (U ) = 2222 and Γ d (U ) = 1221. The situation is depicted in Fig. 2 .
Functions on the frontiers
We also define the compositions Θ = Γ s ○ Γ d , The functions Π and Θ allow us to describe, from the point of view of the vertical representation, how single-rooted minimal words can be extended, respectively to the left and to the right, into double-rooted minimal words of the same height. Let w ∈ C ∞ be a double-rooted minimal word and let U ∈ Σ * be its left frontier. Then w can be viewed as the overlap between two single rooted minimal words u and u ′ . The left frontiers of u and u ′ are then U and Θ(U ) respectively. Clearly, Π is the inverse of Θ.
Functions on the frontiers
Example 8. Let U = 2122. Then Θ(U ) = 1221 and Π(U ) = 1121. The situation is depicted in Fig. 3 . We now show that the functions Γ s , Γ d , and therefore Π and Θ, can be defined recursively and independently from the context of C ∞ -words.
Functions on the frontiers
We clearly have
Functions on the frontiers
Lemma 4.2. Let U ∈ Σ * . Then:
Functions on the frontiers
The lemma can be proved by simple observations on the compositions of the functions Γ s and Γ d (see Fig. 4 for an example).
Functions on the frontiers
From the recursive formulae for Γ s and Γ d we can derive recursive formulae for Π and Θ. Corollary 4.3. Let U ∈ Σ * . Then:
Functions on the frontiers
Note that the function Π (or, analogously, the function Θ) can be defined recursively by the formulae given in Corollary 4.3, with no explicit reference to C ∞ -words. Once the function Π has been so defined, one can derive a recursive definition of Γ s and Γ d . This allows us to give a very compact description of single-rooted minimal words, presented in the following theorem.
Functions on the frontiers
Theorem 4.4. Let U ∈ Σ * . Then:
Functions on the frontiers
The theorem is a consequence of the recursive definition of Π given in Corollary 4.3 and of simple arguments on the compositions of the functions over the frontiers (see Fig. 5 ). This reduces significantly the space needed for storing a C ∞ -word, since the ratio between the height of a C ∞ -word and its length is logarithmic.
Functions on the frontiers
The functions Γ s , Γ d , Θ and Π can be easily extended to Σ ++ 0 , as described below. Let U 0 ∈ Σ ++ 0 be a non-empty word, and let u be the shortest single-rooted C ∞ -word having U 0 as left frontier (hence u is a right minimal word). We define the function
Functions on the frontiers
that is, Γ s (U 0 ) is the right frontier of u. Let v be the shortest double-rooted C ∞ -word having U 0 as left frontier (hence v is a right minimal word).
Functions on the frontiers
We define the function Recursive formulae for Γ s , Γ d , Π and Θ as functions on words over Σ ++ 0 are derived below. We clearly have
Remark 5. For any word
U 0 ∈ Σ ++ 0 , one has (Π ○ Θ)(U 0 ) = (Θ ○ Π)(U 0 ) = Γ 2 s (U 0 ) = Γ 2 d (U 0 ) = U ∈ Σ * . SoΓ s (ε) = Γ d (ε) = Π(ε) = Θ(ε) = ε. Lemma 4.5. Let U 0 ∈ Σ ++ 0 . Then: 1. Γ s (U 0 1) = Γ d ○ Γ s ○ Γ d (U 0 )1 2. Γ s (U 0 2) = Γ d (U 0 )2 3. Γ s (U 0 0) = Γ d ○ Γ s ○ Γ d (U 0 )2 4. Γ d (U 0 1) = Γ d ○ Γ s ○ Γ d ○ Γ s ○ Γ d (U 0 )2 5. Γ d (U 0 2) = Γ d ○ Γ s ○ Γ d ○ Γ s ○ Γ d (U 0 )1 6. Γ d (U 0 0) = (Γ d ○ Γ s ○ Γ d ○ Γ s )(Γ d ○ Γ s ○ Γ d (U 0 ))1 7. Π(U 0 1) = Π(U 0 )2 8. Π(U 0 2) = Π 2 (U 0 )1 9. Π(U 0 0) = Π(U 0 )1 10. Θ(U 0 1) = Θ 2 (U 0 )2 11. Θ(U 0 2) = Θ(Γ 2 s (U 0 ))1 = Γ s (Γ d (U 0 ))1 12. Θ(U 0 0) = Θ(Θ(U 0 ))1
Right extensions
In this section, we describe how a C ∞ -word of height k can be extended to the right into a C ∞ -word of height k + 1. We do this from the point of view of the vertical representation. Indeed, an extension to the right of a C ∞ -words eventually results into an extension of one letter of its left frontier when the height of the word becomes k + 1. We restrict our attention to single-rooted minimal words. An analogous approach can be applied to the extensions on the left and the right frontier. Let u be a single-rooted minimal word with left frontier U ∈ Σ * , and let k > 0 be the height of u, that is the length of U .
Right extensions
What are the shortest C ∞ -words of height k + 1 having u as a prefix? These are exactly the shortest C ∞ -words of height k + 1 whose left frontiers have U as a prefix. That is, they are the shortest C ∞ -words having left frontier, respectively, U 1, U 2 and U 0. We call these three words, respectively, the right 1-extension, right 2-extension and the right 0-extension of the word u.
Right extensions
Note that the right 1-extension and the right 2-extension are single-rooted minimal words, whereas the right 0-extension is not minimal, since its left frontier does not belong to Σ * . So, what is the single-rooted minimal word corresponding to the right 0-extension of u? That is, what is the minimal part of the right 0-extension of u? The following theorem provides the answer to this question.
Right extensions
Theorem 5.1. Let u be a single-rooted minimal word of height k > 0, and U ∈ Σ k its left frontier. The word u can be extended to the right into two single-rooted minimal words of height k + 1: the right 1-extension of u, which is the single-rooted minimal word having left frontier U 1, and the right 2-extension of u, which is the single-rooted minimal word having left frontier U 2; and into a single-rooted (not minimal) word having left frontier U 0, called the right 0-extension of u.
Right extensions
Moreover, the minimal part of the right 0-extension of u is the single-rooted minimal word having left frontier Θ(U )2.
Right extensions
Remark 6. The right 0-extension and the right 1-extension of a word u are words that differ only on the last letter. The left 1-extension, the left 2-extension and the left 0-extension are defined analogously. We can now define an infinite directed acyclic graph for representing the minimal classes of C ∞ -words accordingly with the three right extensions (see Fig. 7 ). The graph of C ∞ -words [7] is the graph G is defined by
Right extensions
where V = Σ * and the set E of labeled edges is partitioned into three subsets:
Right extensions
Thus, G is obtained by adding to an infinite complete binary tree (with edge labels in Σ and node labels in Σ * ) one additional edge outgoing from each node (labeled by 0). A partial diagram of the graph G is depicted in Fig. 9 . The edges in E 0 are dashed. Clearly, one can define the graph G by means of Π instead of Θ (see Fig. 8 ), by defining
Right extensions
where V = Σ * and the set E ′ of labeled edges is partitioned into three subsets:
Right extensions
Remark 7. As a consequence of Theorem 4.4, the graph G can be defined recursively and with no explicit reference to C ∞ -words.
Right extensions
Let w be a C ∞ -word and (U 0 , V 0 ) its vertical representation, U 0 , V 0 ∈ Σ ++ 0 . Let u be the minimal part of w and (U, Γ s (U )) the vertical representation of u, U ∈ Σ * . If w is double-rooted, then w contains a double-rooted minimal factor u ′ having vertical representation (U, Γ d (U )), see Fig. 1 . By Theorem 2.3, the word w is a simple extension on the left of u, and it is a simple extension on the right of u (if w is single-rooted) or of u ′ (if w is double-rooted). The left frontier U 0 of w is the label of a path in G starting at the origin and ending in U . Analogously, the right frontier V 0 of w is the label of a path in G starting at the origin and ending in Γ s (U ) (if w is single-rooted) or in Γ d (U ) (if w is double-rooted). Conversely, any word U 0 ∈ Σ ++ 0 labeling a path in G starting at the origin and ending in U ∈ Σ * is the left frontier of a simple extension on the left of any C ∞ -word having U as left frontier, and, symmetrically it is also the right frontier of a simple extension on the right of any C ∞ -word having U as right frontier. An example is given in Fig. 10 . Thus, we have the following characterization of the minimal classes of C ∞ words by means of the graph G.
Right extensions
Theorem 5.2. Let U ∈ Σ * be the left frontier of a single-rooted minimal word u. The C ∞ -words having u as minimal part are exactly the words w having vertical representation (U 0 , V 0 ) such that U 0 labels a path in G starting at the origin and ending in U , and V 0 labels a path in G starting at the origin and ending in
Right extensions
In particular, the number of distinct paths in G starting at the origin and ending in U ∈ Σ * is equal to the number of simple extensions on the left (resp. on the right) of a single-rooted minimal word having U as left (resp. right) frontier.
Right extensions
This allows us to show that there exists a close relation between the paths in G and the length of the single-rooted minimal words.
Right extensions
Let U denote the length of the single-rooted minimal word u having left frontier U and U the number of distinct paths in G starting at the origin and ending in U .
Right extensions
From the definition of the graph G (see Fig. 8 ), one has U 1 = U and U 2 = U + Π(U ) . Since U is the number of simple-extensions to the left of u, we have that the length of the left 2-extension of u (that is, the single-rooted minimal word having left frontier Π(U )2) is equal to U + U (see Fig. 6 ). Symmetrically, the length of the right 2-extension of u (which is the single-rooted minimal word having left frontier U 2) is equal to Γ s (U ) + Γ s (U ) . Analogous considerations hold for the (left and right) 1-extensions. Note also that one has U = Γ s (U ) , Θ(U ) = Γ d (U ) , U 2 = U 2 and U 1 = U 0 .
Right extensions
We therefore deduce the following recursive formulae:
Right extensions
We think that these formulae show the interest of dealing with the graph G when considering problems on the C ∞ -words. For example, analogous formulae can be applied to compute the number of 1's and 2's in a C ∞ -word, thus giving a possible direction to investigate Keane's conjecture on the frequency of letters in the Kolakoski word.
Conclusion and open problems
The vertical representation is a compact representation of C ∞ -words that allows one to represent any C ∞ -word of length n by means of two words whose length is logarithmic in n (the frontiers). In this paper, we showed that this representation can be defined in terms of two simple recursive functions, that are naturally represented by a directed acyclic infinite graph G. The recursive definitions of the functions on the frontiers leads to a recursive definition of the graph G, therefore independent from the context of C ∞ -words.
Conclusion and open problems
Besides being more compact, we believe that the new representation presented here will allow the use of results from graph theory or poset theory in the study of the Kolakoski word. As an illustration, we formulate below two new conjectures on the graph G which, if proven, would imply the validity of important conjectures on C ∞ -words.
Conclusion and open problems
• We conjecture that for any U 1 , U 2 ∈ Σ * it is possible to find two words V 1 , V 2 ∈ Σ ++ 0 such that U 1 V 1 and U 2 V 2 label two paths in G starting at the origin and ending in the same node (see Fig. 11 ). This would imply that for any u, v ∈ C ∞ there exists z such that uzv ∈ C ∞ (see Fig. 12 ). This latter conjecture was referred to as the Universal Glueing Conjecture [7] .
Conclusion and open problems
• We also conjecture that there exists a linear function f (k) such that for every word Z ∈ Σ f (k) and every word U ∈ Σ k , there exists a word V ∈ Σ ++ 0 such that U V labels a paths in G starting at the origin and ending in Z. This would imply that any smooth word is uniformly recurrent. In particular, this would be true for the Kolakoski word.
Conclusion and open problems
The key step underlying the construction presented here is the recognition of the fundamental role of minimal words (and associated classes) in the structure of C ∞ -words. The simplicity of the representation of C ∞ -words in terms of their vertical representation strongly suggests that these are at the heart of the structure of the entire set. This is supported by the fact that, quite surprisingly, also the study of the densities of 1's and 2's in a C ∞ -word can be carried out using combinatorial properties of the graph G.

{'paper_id': '9192729', 'title': 'Vertical representation of $C^{\\infty}$-words', 's2_url': 'https://api.semanticscholar.org/CorpusID:9192729', 'source': 'S2ORC'}