Jean Berstel
email: berstel@univ-mlv.fr

Luc Boasson

Olivier Carton

Isabelle Fagnot

Sturmian Trees

Keywords: Sturmian word, Labeled tree, Minimal automaton, Moore algorithm J. Berstel ( ), I. Fagnot

We consider Sturmian trees as a natural generalization of Sturmian words. A Sturmian tree is a tree having n + 1 distinct subtrees of height n for each n. As for the case of words, Sturmian trees are irrational trees of minimal complexity.

We prove that a tree is Sturmian if and only if the minimal automaton associated to its language is slow, that is if the Moore minimization algorithm splits exactly one equivalence class at each step. We give various examples of Sturmian trees, and we introduce two parameters on Sturmian trees, called the degree and the rank. We show that there is no Sturmian tree of finite degree at least 2 and having finite rank. We characterize the family of Sturmian trees of degree 1 and having finite rank by means of a structural property of their minimal automata.

Introduction

Sturmian words have been extensively studied for many years (see e.g. [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF][START_REF] Pytheas-Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF] for recent surveys). We propose here an extension to trees.

A Sturmian tree is a complete labeled binary tree having exactly n + 1 distinct subtrees of height n for each n. Thus Sturmian trees are defined by extending to trees one of the numerous equivalent definitions of Sturmian words. Sturmian trees share the same property of minimal complexity than Sturmian words: indeed, if a tree has Fig. 1 The top of a uniform tree for the word abaaba • • • . Node label a is represented by •, and label b is represented by •. This tree will be seen to have infinite degree and rank 0 at most n distinct subtrees of height n for some n, then the tree is rational, i.e. it has only finitely many distinct infinite subtrees.

This paper presents many examples and some results on Sturmian trees. The simplest method to construct a Sturmian tree is to choose a Sturmian word and to repeat it on all branches of the tree. We call this a uniform tree, see Fig. 1. However, many other categories of Sturmian trees exist.

Contrary to the case of Sturmian words, and similarly to the case of episturmian words, there seems not to exist equivalent definitions for the family of Sturmian trees. This is due to the fact that, in our case, each node in a tree has two children, which provides more degrees of freedom. In particular, only one of the children of a node needs to be the root of a Sturmian tree to make the whole tree Sturmian.

Each tree labeled with two symbols can be described by the set of words labeling paths from the root to nodes sharing a distinguished symbol. The (infinite) minimal automaton of the language has quite interesting properties when the tree is Sturmian. The most useful is that the Moore equivalence algorithm produces just one additional equivalence class at each step. We call these automata slow.

We have observed that two parameters make sense in studying Sturmian trees: the degree of a Sturmian tree is the number of disjoint infinite paths composed of nodes which are all roots of Sturmian trees. The rank of a tree is the number of distinct rational subtrees it contains. Both parameters may be finite or infinite.

The main result of this paper is that the class of Sturmian trees of degree one and with finite rank can be described by infinite automata of a rather special form. The automata are obtained by repeating infinitely many often a distinguished path in some finite slow automaton, and intertwining consecutive copies of this path by letters taken from some Sturmian infinite word. Another property is that a Sturmian tree with finite degree at least 2 always has infinite rank.

Here is a table summarizing the relations between degree and rank for Sturmian trees. A tree with rank 0 always has infinite degree since there is no rational node. The class of Sturmian trees seems to be quite rich. We found several rather different techniques to construct Sturmian trees. To the best of our knowledge, there is only one paper on Sturmian trees prior to the present one, by Carpi, De Luca and Varricchio [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF].

The paper is organized as follows. Section 2 contains the basic definitions, and the proof that a tree with fewer subtrees is rational. This was already known before, in particular in [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF]. We give the easy proof for sake of completeness. Section 3 recalls several basic properties of automata, just observing that these properties also hold for infinite automata. In the case of slow automata, the way classes are split in the Moore equivalence algorithm is analyzed, for later use. The next section is devoted to Rauzy graphs. These are a useful construct for Sturmian words, and we show how they characterize Sturmian trees. As a byproduct, we obtain new insight in the nature of Rauzy graphs for Sturmian words: they are the graphs obtained in the Moore minimization process of an infinite automaton over a single letter alphabet.

In Sect. 5, we define the rank and the degree of a tree. In Sect. 6, we consider Sturmian trees with finite rank, that is with finitely many rational subtrees. We prove the main result, namely that Sturmian trees with finite rank and of degree one correspond precisely to extensions of automata obtained as an extension of a finite slow automaton by repeating some finite path infinitely many often, and by intertwining consecutive copies of this path with the successive letters taken from some Sturmian infinite word.

Section 7 is concerned with trees with infinite rank. It contains examples of Sturmian trees and of the corresponding automata showing that the general case might be quite intricate.

Sturmian Trees

We are interested in complete labeled infinite binary trees, and we consider finite trees insofar as they appear inside infinite trees.

In the sequel, D denotes the alphabet {0, 1}. A tree domain is a prefix-closed subset P of D * . Any element of a tree domain is called a node. Let A be an alphabet. A tree over A is a map t from a tree domain P into A. The domain of the tree t is denoted dom(t). For each node w of t, the letter t (w) is called the label of the node w. A complete tree is a tree whose domain is D * . The empty tree is the tree whose domain is the empty set. A (finite or infinite) branch of a tree t is a (finite or infinite) word x over D such that each prefix of x is a node of t.

Example 1 (Dyck tree) Let A be the alphabet {a, b}. Let L be the set of Dyck words over D = {0, 1}, that is the set of words generated by the context-free grammar with Fig. 2 The top of the Dyck tree of Example 1 and two of its factors, of height 3 and 2, respectively. Again, a is represented by • and b by • productions S → 0S1S + ε. The Dyck tree is the complete tree defined by

t (w) = a if w ∈ L, b otherwise. ( 1
)
The top of this tree is depicted in Fig. 2. The first four words ε, 01, 0101 and 0011 of L correspond to the four occurrences of the letter a as label on the top of the tree.

More generally, the characteristic tree of any language L over D is defined to be the tree t given by [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF]. Conversely, for any tree t over some alphabet A, and for any letter a in A, there is a language L = t -1 (a) of words labeled with the letter a. The language L = t -1 (a) is called the a-language of t. In the sequel, we deal with the two-letter alphabet A = {a, b}, and we fix the letter a, and we simply call language of t its a-language.

We shall see that the language of a tree t is regular if and only if the tree t is rational.

For any word w and any language L, the expression w -1 L denotes the set w -1 L = {x | wx ∈ L}. Let t be a tree over A and w be a word over D. We denote by t[w] the tree with domain w -1 dom(t) defined by t[w](u) = t (wu) for each u in w -1 dom(t). The tree t[w] is sometimes written as w -1 t, for instance in [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF]. If w is not a node of t, the tree t[w] is empty. A tree of the form t[w] is the suffix of t rooted at w. Suffixes are also called quotients or subtrees in the literature.

Let t be a tree over A and let w be a word over D. For a positive integer h, we denote by D <h the set (ε + D) h-1 of words over D of length at most h -1. We set D <0 = ∅.

Let h be a nonnegative integer. The truncation of a tree t at height h is the restriction of t to the domain D <h . Any tree obtained by truncation is called a prefix of t. A factor of t is a prefix of a suffix of t. More precisely, for any word w and any nonnegative integer h, we denote by t[w, h] the factor of height h rooted at w, that is the tree of domain w -1 dom(t) ∩ D <h and defined by t[w, h](u) = t (wu). A factor of height 0 is always the empty tree. A factor t[w, 1] of height 1 can be identified with the letter t (w) of A that labels its root. A prefix is a tree of the form t[ε, h].

Factors of height h are sometimes considered to have height h -1 in the literature (e.g. [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF]). In this paper, the height of a finite tree is the number of nodes along a maximal branch and not the number of steps in-between. Our convention will be justified by Proposition 1 which extends a similar result for words in similar terms.

The following equation for any words w and w over D and any positive integers h and h holds:

t[w, h][w , h ] = t[ww , min(h -|w |, h )] for |w | ≤ h.
A tree is rational if it has finitely many distinct suffixes. Recall (see e.g. [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF]) that a tree over an alphabet A is rational if and only if t -1 (a) = {w ∈ D * | t (w) = a} is a regular subset of D * for each letter a of A. For instance the Dyck tree t of Example 1 is not rational since t -1 (a) is the Dyck language which is not regular [7].

The following proposition gives a characterization of complete rational trees using factors. It extends to trees the characterization of ultimately periodic words by means of their subword complexity [START_REF] Coven | Sequences with minimal block growth[END_REF]. This statement appears also in [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF], we give the proof for sake of completeness.

Proposition 1 A complete tree t is rational if and only if there is an integer h such that t has at most h distinct factors of height h.

Proof It is clear that if t has k distinct suffixes, it has at most k distinct factors of height h for any h.

Conversely, we prove by induction on h that if t has at most h factors of height h, then t is rational. If h = 1, all nodes in t have the same label and clearly t is rational. Suppose now that h > 1 and that t has h factors f 1 , . . . , f h of height h. Each factor of height h -1 of t is a prefix f i [ε, h -1] of some factor f i . If there are at most h -1 such factors, then t is rational by the induction hypothesis. Otherwise, each factor of height h -1 is the prefix of exactly one factor of height h. But this means that each suffix is determined by its prefix of height h -1. Consequently, t has h suffixes and therefore is rational.

A tree is Sturmian if it is complete and if it has h + 1 factors of height h for any integer h. Since the factors of height 1 are the letters t (w) a Sturmian tree is defined over a two letter alphabet. In what follows, we always assume that this alphabet is {a, b}.

Remark 1 In a Sturmian tree t, each subtree of height h has infinitely many occurrences. This does not mean that all infinite subtrees of t are Sturmian, see for instance the Dyck tree (Fig. 2).

We will prove later that the Dyck tree given in Example 1 is indeed Sturmian. We start with some simpler examples of Sturmian trees.

In the first of these examples, the same infinite word is repeated along each branch of the tree. Example 2 (Uniform trees) Let x = x 0 x 1 x 2 • • • be an infinite word over an alphabet A, where x 0 , x 1 , x 2 , . . . are letters. The uniform tree of x is the complete tree t defined by t (w) = x |w| . This means of course that all nodes of the same level n in the tree are labeled with the same symbol x n . If x is a Sturmian word, then its uniform tree t is a Sturmian tree. Figure 1 shows the top of the uniform tree of the Fibonacci word

x = abaaba • • • . Example 3 (Left branch tree) Let x = x 0 x 1 x 2 • • •
be an infinite word over A, where x 0 , x 1 , x 2 , . . . are letters. We define a complete tree t by t (w) = x |w| 0 . (Recall that |w| d is the number of occurrences of d in w.)

The label of each node w is the letter x n of x, where n is the number of symbols 0 occurring on the path from the root to w. The label of the root node is x 0 . If the label of w is x n , the labels of w0 and w1 are respectively x n+1 and x n .

In particular, the letters of the word x label the nodes of the leftmost branch of the tree, and all nodes on a rightmost branch share the same label. Figure 3 shows the top of the left branch tree of the Fibonacci word x = abaaba • • • . Example 4 (Indicator tree) Let x be an infinite word over D. The indicator tree of x is the complete tree t defined by

We write x[n, h] for the factor x n x n+1

t (w) = a if w is a prefix of x, b otherwise.
In other terms, there is exactly one infinite path in t with all its nodes labeled by the letter a. The letters of this path are the letters of the word x. Equivalently, the indicator Fig. 4 The top of the indicator tree for the Fibonacci word 01001010 • • • . The only nodes labeled a are on the Fibonacci path tree of the infinite word x is the characteristic tree of the language composed of its (finite) prefixes. Figure 4 shows the indicator tree of the Fibonacci word. It can be easily proved that x is a Sturmian word if and only if its indicator tree t is a Sturmian tree.

The following Example 5 is a variation on Example 4. For a finite word w and an infinite word x, we denote by d(w, x) the integer |w| -|u| where u is the longest common prefix of w and x.

Example 5 (Band indicator tree) Let x = x 0 x 1 x 2 • • • be an infinite word over D and let k be a non-negative integer. The band indicator tree of width k is the complete tree t defined by

t (w) = a if d(w, x) ≤ k, b otherwise.
The same argument shows that x is a Sturmian word if and only if t is a Sturmian tree. An example is given in Fig. 5. The band indicator tree of width 0 is the indicator tree defined in Example 4, since d(w, x) ≤ 0 if and only if w is a prefix of x.

Slow Automata

Let t be a complete tree over {a, b}. The language of t is the set t -1 (a). We study properties of trees by considering automata recognizing their language. In particular, minimization of automata will play a central role.

We recall elementary properties of automata, just observing that they hold also when the set of states is infinite. We only use deterministic and complete automata. An automaton A over a finite alphabet D is composed of a state set Q, a set F ⊆ Q of final states, and of a next-state function Q × D → Q that maps (q, d) to a state Fig. 5 The top of the band indicator tree of width 1 for the Fibonacci word 01001010 • • • . The nodes labeled a are at distance at most 1 from the Fibonacci path Fig. 6 Automaton of the Dyck language. State 0 is both the initial and the unique final state denoted by q • d. The next state function is extended to a function from Q × D * to Q by setting q • ε = q and q • wd = (q • w) • d for a word w ∈ D * and a letter d ∈ D. Given a distinguished state i, a word w over D is accepted by the automaton if the state i • w is final. When we emphasize the existence of state i, we call it the initial state as usual.

An automaton B is a subautomaton of an automaton A if its set of states is a subset of the set of states of A which is closed under the next-state function of A.

Example 6 (Dyck automaton) The following automaton accepts the Dyck language. The set of states is Q = N ∪ {∞}. The initial and unique final state is 0. The next state function is given by n

• 0 = n + 1 for n ≥ 0, n • 1 = n -1 for n ≥ 1, 0 • 1 = ∞ and ∞ • 0 = ∞ • 1 = ∞.
This automaton is depicted in Fig. 6. We call it the Dyck automaton. The singleton {∞} is the unique proper subautomaton of the Dyck automaton.

Given an arbitrary automaton A, we define inductively a sequence (∼ h ) h≥1 of equivalence relations on Q as follows.

q ∼ 1 q ⇐⇒ (q ∈ F ⇐⇒ q ∈ F ), q ∼ h+1 q ⇐⇒ (q ∼ h q and ∀d ∈ D q • d ∼ h q • d).

These are well-known in the case of finite automata, and many properties extend to general automata. We call ∼ h the Moore equivalence of order h. The index of ∼ h is the number of equivalence classes of ∼ h . The Moore minimization algorithm consists in computing inductively the Moore equivalences.

Example 7 We illustrate this definition on the Dyck automaton given in Example 6.

By definition the relation ∼ 1 has two classes: one contains all the final states and the other contains all other states. Here, these classes are {0} and Q \ {0}. One easily checks that the classes of ∼ 2 are the three sets {0}, {1} and Q \ {0, 1}. It is easily shown by induction that the classes of ∼ h are the h + 1 sets {0}, {1}, . . . , {h -1} and Q \ {0, 1, . . . , h -1}.

We define the Nerode equivalence relation ∼ by ∼= h≥1 ∼ h . It is clear that q ∼ q holds if and only if L A (q) = L A (q ) where L A (q) denotes the set of words accepted by A with initial state q. We state here a few properties of the relations ∼ h and ∼. They are well-known for finite automata but hold also in the general case -Each relation ∼ h has finite index.

-The relation ∼ has finite index iff ∼ equals ∼ h for some integer h.

-If ∼ h+1 =∼ h for some integer h, then ∼ h+k =∼ h for each k ≥ 0 and ∼=∼ h .

-If ∼ h has index at most h, then ∼ h =∼.

-The relation ∼ is a congruence. This means that for any states q and q and any letter d ∈ D, q ∼ q implies q • d ∼ q • d.

An automaton is minimal if its Nerode equivalence ∼ is the equality relation. Many results concerning minimal finite automaton remain valid for infinite ones. For each subset L of D * , there is a unique minimal automaton accepting it. This minimal automaton is equal to A/∼ for any automaton A accepting L. In particular, it can be obtained from the automaton based on the complete binary tree as described above.

A subautomaton B of a minimal automaton A is itself minimal. The Nerode equivalence of B is the restriction of the Nerode equivalence of A to the set of states of B.

Lemma 1 Let A be an automaton. For any states q, q and any positive integer h, one has

q ∼ h q ⇐⇒ (∀u ∈ D <h q • u ∈ F ⇐⇒ q • u ∈ F ) .
Proof The proof is an easy induction on h. Since D <1 = {ε}, the case h = 1 follows from the definition of ∼ 1 . The induction step follows then from the equality

D <h+1 = D <h ∪ DD <h .
The equivalence ∼ h+1 is a refinement of the equivalence ∼ h . Thus the index of ∼ h+1 is at least the index of ∼ h . An automaton is called slow if it is minimal and if the index of ∼ h is at most h + 1 for all h ≥ 1. If ∼ h and ∼ h+1 are different, that there is one class c of ∼ h which gives raise to two classes in ∼ h+1 . We say that ∼ h+1 splits class c, or that class c is split by ∼ h+1 .

It is sometimes useful to distinguish, in a minimal automaton, two kinds of states. A state p is rational if it has finitely many descendants in the automaton, viewed as a graph or, equivalently, if it generates a finite subautomaton. States which are not rational are called irrational. In the Dyck automaton of Example 7, the state ∞ is the only rational state. In the minimal automaton associated to the language of a tree, a state is rational if and only if it corresponds to the root of a rational tree.

In a slow automaton, the index of each ∼ h is exactly h + 1, as long as ∼ h is different from ∼ h-1 . As soon as these relations are equal, they are the identity relation.

Given an infinite slow automaton A, we denote, for h ≥ 0, by c h the class of ∼ h that is split by ∼ h+1 and, for h > 0, by c h and c h the classes of ∼ h obtained by splitting c h-1 in ∼ h .

The following easy property of slow automata is useful.

Lemma 2 Let A be an infinite slow automaton. For h > 0, there exists a letter a h+1 that maps all states of c h+1 into c h (or all states into c h ) and all states of c h+1 into the other of the classes c h or c h .

Proof Consider indeed c h = c h+1 ∪ c h+1 . There exist states q ∈ c h+1 and q ∈ c h+1 which are equivalent for ∼ h but which are not equivalent for ∼ h+1 . By definition, this means that there is a letter a = a h+1 such that q

• a ∼ h q • a, but q • a ∼ h-1 q • a.
In other terms, the class of ∼ h-1 containing both states q • a and q • a is split by ∼ h into classes c h and c h . Furthermore, the letter a maps all states of c h+1 into c h (or into c h ) and all states of c h+1 into the other of these two classes c h and c h , as claimed.

Observe that the lemma does not say anything about the letters distinct from a h+1 . However, since the automaton is slow, they also map the classes c h+1 and c h+1 into classes of ∼ h .

Corollary 1 Let A be an infinite slow automaton. There exists an infinite sequence of pairs (c h , c h ) of classes of ∼ h such that each c h ∪ c h is the equivalence class of ∼ h-1 split by ∼ h , and letters a h , such that each a h maps all states of c h into states of c h-1 , and all states of c h into states of c h-1 .

Proof This is a direct consequence of the previous lemma.

Remark that for this corollary also the other letters of the alphabet do not split other classes.

Let t be a complete tree over {a, b}. Recall that the language of t is the set t -1 (a). Let A be an automaton accepting t -1 (a). The following proposition shows that the classes of ∼ h are in a one to one correspondence with the factors of t of height h. Proposition 2 Let t be a complete tree and let A be an automaton over D accepting the language of t, with initial state i. For any words w, w ∈ D * and any positive integer h, one has

i • w ∼ h i • w ⇐⇒ t[w, h] = t[w , h].
Proof Set q = i • w and q = i • w .

q ∼ h q ⇐⇒ (∀u ∈ D <h q • u ∈ F ⇐⇒ q • u ∈ F ) ⇐⇒ (∀u ∈ D <h t (wu) = a ⇐⇒ t (w u) = a) ⇐⇒ t[w, h] = t[w , h] .
Corollary 2 Let t be a complete tree and let A be an automaton over D accepting the language of t. The tree t is Sturmian if and only if the minimal automaton of its language is infinite and slow.

Example 8 We have seen in Example 7 that the relation ∼ h for the Dyck automaton of Example 6 has h + 1 classes. Thus this automaton is slow and the Dyck tree given in Example 1 is Sturmian. The automaton of Fig. 6 is just one special case of an uncountable family of slow automata defined in a quite similar way and which provide an uncountable family of Sturmian trees. These automata differ from the Dyck automaton by the behavior of the next-state function for the letter 0: instead of having n • 0 = n + 1 for n ≥ 1, we require only that n • 0 ≥ n, and in addition that each state n is accessible from the initial state 0. An example is given in Fig. 7. It is easily checked that again that the classes of ∼ h are the h + 1 sets {0}, {1}, . . . , {h -1} and Q \ {0, 1, . . . , h -1}. So these automata are all slow.

We consider now the automata for the examples of Sturmian trees of the previous section.

Example 9 (Indicator tree) We consider the automaton of an indicator tree, as defined in Example 4. Let x = x 0 x 1 x 2 • • • be an infinite word over D. The indicator tree of x is the complete tree t defined by

t (w) = a if w is a prefix of x, b otherwise.
Recall that for d ∈ D, we write d for the opposite letter, that is 0 = 1 and 1 = 0. Let x = x 0 x 1 x 2 • • • be an infinite words over D and let us consider the tree t x defined in the previous example. The minimal automaton accepting the language t -1 x (a) has set of states Q = N ∪ {∞}, with initial state i = 0 and set of final states F = N. The nextstate function is given by n Let h be a positive integer. We claim that two states n and n satisfy n ∼ h n if and only if

• x n = n + 1, n • xn = ∞ and ∞ • 0 = ∞ • 1 = ∞.
x n • • • x n+h-2 = x n • • • x n +h-2 . Indeed, a word u ∈ D <h satisfy n • u ∈ F if and only if u is a prefix of x n • • • x n+h-2 .
For a word w of length k over D, we denote by N w the set {n | x n • • • x n+k-1 = w}. Note that N w is non empty if w is a factor of x. It follows then that the classes of ∼ h are the set {∞} and the h sets of the form N w where w is a factor of length h -1 of x. Therefore, the tree t x of Example 4 is Sturmian if and only if x is Sturmian.

Example 10 We give in Fig. 9 the automaton for a band indicator tree, as defined in Example 5.

Example 11 Let x and x be two Sturmian words over D that have exactly the same factors but share no common suffix: for each factorization x = uy, x = u y , one has y = y .

Such words do exist. Indeed, it is known that the set of Sturmian words having exactly the same fixed set of factors is a minimal subshift, and since it is infinite, it is uncountable. On the other side, for each (of the countably many) suffix of an infinite word, there are only countably many infinite words sharing this suffix. We define a tree t x,x by giving a (minimal) automaton accepting t -1

x,x (a). Let Q be the set N ∪ {n | n ∈ N} ∪ {∞}. The only final state is ∞. See Fig. 10.

To prove that t x,x is Sturmian, one shows that the automaton is slow and minimal. The automaton is indeed minimal because the two words share no common suffix, and it is slow because the two words are Sturmian and have the same set of factors.

Rauzy Graphs

We define here the Rauzy graphs of a tree. This notion extends to trees the Rauzy graphs of words [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF]. Recall that, for an infinite word x, the Rauzy graph of order h, or the Rauzy graph for short, is a graph whose vertices are the factors of length h of x, and whose edges are in bijection with the factors of length h + 1 of x as follows. The pair (u, v) is an edge if u = cw, v = wd for some letters c, d, and ud = cv is a factor of x, see Fig. 11. Rauzy graphs are special de Bruijn graphs.

The h-Rauzy graph of an infinite word x can be viewed as the quotient of an infinite automaton. Define indeed an infinite automaton A(x) = (N, 0, F ) over a one letter alphabet with next-state function n → n + 1, and set of final states F = {n | x n = a}. This automaton recognizes the set of prefixes of x ending with the letter a, Fig. 12 Automaton for the Fibonacci infinite word f . A state i is final if f i = a. The state 0 is initial. Final states are gray Fig. 13 An edge (t ε , t 0 , t 1 ) of a Rauzy graph. The factor t ε is the prefix of some factor f of height h + 1, and t 0 and t 1 are the left and right subtrees of height h of f Fig. 14 The three factors of height 2 of the Dyck tree, named α, β and γ see Fig. 12. The Moore equivalence ∼ h of order h of A(x) satisfies

n ∼ h n if and only if [n + i ∈ F ⇔ n + i ∈ F (0 ≤ i < h)]
thus n ∼ h n if and only if the factors x(n, n + h) and x(n , n + h) of x are equal. The quotient A(x)/∼ h has its vertices in bijection with the factors of length h of x, and there is an edge (u, v) precisely if u = x(n, n + h) and v = x(n + 1, n + 1 + h) for some n. This shows that the quotient A(x)/∼ h is precisely the Rauzy graph of x. Observe that if x is Sturmian, there is exactly one class of ∼ h that splits into two classes of ∼ h+1 . This corresponds to the unique right special factor of length h, that is to the state in A(x)/∼ h which has two outgoing states.

The situation for trees is more involved. Roughly speaking, the vertices of the h-Rauzy graph of a tree are the factors of height h and its edges are the factors of height h + 1. It turns out that these graphs are in fact hypergraphs since each edge is a triple of vertices.

Let t be a complete tree. For an integer h, the h-Rauzy graph of t is a graph whose vertices are the factors of height h of t. Its edges are triples of the form (t ε , t 0 , t 1 ) where t ε , t 0 and t 1 are three vertices, that is, three factors of height h of t. Each factor f of height h + 1 of t, define an edge (t ε , t 0 , t 1 ) by

t ε = f [ε, h], t 0 = f [0, h] and t 1 = f [1, h].
The edges of the h-Rauzy graph are in bijection with the factors of height h + 1 of t, since a factor of height h + 1 is entirely defined by its three factors of height h.

An edge (t ε , t 0 , t 1 ) of a Rauzy graph is drawn as in Fig. 13. If the tree t is Sturmian, its h-Rauzy graph has h + 1 vertices and h + 2 edges. Furthermore, since each factor of height h is the prefix of at least one factor of height h + 1, there is at least one edge starting in each vertex. Consequently, there is precisely one vertex which has two edges starting in it. The states of the 2-Rauzy graph are the three factors α, β and γ , and the edges are the four factors of height 3 are named r, s, t, and u.

The states of the 3-Rauzy graph are the four factors r, s, t, and u, and its edges are the five factors given in the second row of Fig. 15 Let t be a complete tree over {a, b} and let A be an automaton accepting t -1 (a). Let h be an integer. We construct a hypergraph A/∼ h as follows. The vertices of A/∼ h are the equivalence classes of ∼ h . The edges of this graph are the triples of the form ([q], [q • 0], [q • 1]) where q ranges over the states of A and [q] denotes the class of q.

Proposition 3 Let t be a complete tree. The graph A/∼ h is the h-Rauzy graph of t.

Proof By Proposition 2, there is a one to one correspondence between vertices of A/∼ h and vertices of the h-Rauzy graph. Furthermore, two states satisfy [q] = [q ], [q • 0] = [q • 0], and [q • 1] = [q • 1] iff they satisfy q ∼ h+1 q . Again by Proposition 2, there is a one to one correspondence between edges of A/∼ h and edges of the h-Rauzy graph.

Rank and Degree

Recall that a branch of a tree is a (finite or infinite) word x over D such that each prefix of x is a node of the tree.

A node w of a tree t is called rational if the suffix t[w] is a rational tree. It is called irrational otherwise. The rank of a tree t is the number of distinct rational suffixes of t. This number is either a nonnegative integer or infinite.

If w is an irrational node, then its prefixes also are irrational. Furthermore, at least one of the two words w0 and w1 also is irrational. The set of irrational nodes of a tree is a tree domain in which any finite branch is the prefix of an infinite branch.

In a Sturmian tree t, a node w is irrational if and only if t[w] is a Sturmian tree.

The degree of a tree t is the number of infinite branches composed of irrational nodes. This number is either a nonnegative integer or infinite. If the degree is 0, the tree t is rational.

As a first example, consider the Dyck tree defined in Example 1. It has rank 1 and has infinite degree. A node w of this tree is rational if it is not a prefix of some Dyck word. The set of rational nodes is thus the set L1D * where L is the set of Dyck words. On the contrary, each branch in 00 * 10 ω only contains irrational nodes. The degree of the Dyck tree is thus infinite.

Next, let t be the indicator tree of a Sturmian word x, as defined in Example 4. A node w of t is irrational if and only if it is a prefix of x. Thus, the word x itself is the only infinite branch composed of irrational nodes, and therefore the degree of this tree is 1. All rational subtrees are the same, so this tree has rank 1.

These examples show that there are Sturmian trees of degree 1 or of infinite degree. It turns out that there exist also Sturmian trees of finite degree greater than 1. In Sect. 7, we construct a Sturmian tree of degree 2 but this construction is rather involved.

Here is a table summarizing the relations between degree and rank for Sturmian trees. A tree with rank 0 always has infinite degree since there is no rational node. The main result of the paper is the characterization of Sturmian trees of degree 1 and with finite rank by a structural property of the minimal automaton of its language.

Trees with Finite Rank

We start with an observation concerning the occurrences of subtrees of fixed height in a Sturmian tree of finite rank.

Let t be a Sturmian tree. For any h ≥ 0, each of the h + 1 factor trees of height h of t has infinitely many occurrences in t. Indeed, assume the contrary. Then there is an integer N such that some factor tree of height h does not occur in the subtrees t [w] with |w| ≥ N . But then these subtrees are all rational and t is rational, contradiction.

We now turn to the question of how these infinitely many occurrences are distributed in a Sturmian tree. This question arises as a natural extension of the same question concerning Sturmian words: one knows that every factor of a Sturmian word appears infinitely times (words sharing this property are called recurrent), and moreover the difference between consecutive occurrences of the same factor in a Sturmian word is bounded, for each factor (words with this property are called uniformly recurrent). For Sturmian trees, it is clearly false that every factor tree of height h appears on every infinite branch, because there exist infinite branches of rational nodes, as soon as the rank of the tree is positive. However, we have the following property which shows that there exist branches which are in some sense recurrent.

Proposition 4

In any Sturmian tree of finite rank, there exists an infinite branch composed of irrational nodes such that every factor tree having its root on this branch appears infinitely many times on this branch. Proof Let r be the rank of the Sturmian tree t and let t (1) , . . . , t (r) be the distinct rational subtrees of t. For each irrational node w, the irrational tree t[w] rooted at w is distinct from t (1) , . . . , t (r) . Therefore, there exists an integer H w such that the prefix t[w, H w ] of height H w of t[w] differs from the prefixes of height H w of t (1) , . . . , t (r) .

We claim that for every pair v, v of irrational nodes, and for every h > 0, there exists an irrational node v such that v is a proper descendent of v and t

[v, h] = t[v , h]. Indeed, let H ≥ max(h, H v ), where H v is defined as above. Since v is irrational, there exists a proper descendent v of v such that t[v , H ] = t[v, H ]. Since H ≥ H v , the tree t[v , H ] is not a prefix of one of the rational trees. Thus v is an irrational node. Since H ≥ h, one has t[v, h] = t[v , h].
The proposition is derived from the claim by constructing an infinite branch as follows, for h = 1, 2, . . . . For h = 1 the claim (with v = v = ε) shows that there exist an irrational node w = ε such that t (ε) = t (w). Denote by z 0 = ε, z 1 , . . . , z n = w the path from ε to w. For h = 1, consider the factor trees t[z 0 , h] and t[z 1 , h]. By the claim, there exists path z n , z n+1 , . . . , z n+m to an irrational node such that t[z 0 , h] = t[z n+m , h], and a path z n+m , z n+m+1 , . . . , z n+m+m to an irrational node z n+m+m

such that t[z 1 , h] = t[z n+m+m , h].
The general step is as follows. One considers the h factor trees t[z 0 , h], t[z 1 , h], . . . , t[z h-1 , h] that are rooted on the first h nodes of the irrational path z 0 , . . . , z m h already constructed. For each of these factor trees, one extends the irrational path by paths

z m h → z m h +p 0 , z m h +p 0 → z m h +p 1 , . . . , z m h +p h-2 → z m h +p h-1 in such a way that t[z 0 , h] = t[z m h +p 0 , h], t[z 1 , h] = t[z m h +p 1 , h], . . . , t[z h-1 , h] = t[z m h +p h-1 , h].
In this way, the irrational path has been extended from node z m h to node z m h +p h-1 , and on this path there is a copy of each of the factor trees of height h which are rooted on the first h nodes of the irrational path. This ensures that all factor trees of height at most h that are rooted on the first h nodes of the path appear at least twice, and in fact infinitely often when this construction is repeated. This concludes the proof.

Observe that we do not claim that for every infinite branch composed of irrational nodes, every subtree of height h appears infinitely many times (of course, at least one does so). Observe also that our proof does not show that subtrees of height h appear with bounded gaps. So we have shown that the subtrees appear as factors in a recurrent word, but we do not know if they may appear in some uniformly recurrent way.

We shall see later (Example 16) an example showing that the proposition does not hold if the tree has infinite rank.

A Tree of Degree One

In this section, we give an example of a family of Sturmian trees with finite rank and of degree 1. These trees are generalizations of the band indicator trees of Example 5. We describe the family of automata accepting their languages. These (infinite) automata are based on a finite slow automaton. In this automaton, a path (called a lazy path) is distinguished. The infinite automaton is obtained by repeating the lazy path and intertwining the copies with symbols taken from an infinite Sturmian word, as we will see below.

In the next section, we show that conversely, any Sturmian tree of degree 1 and with finite rank can be obtained by this construction.

Let A = (Q, {i}, F ) be a finite deterministic automaton over the alphabet D with N states. We assume that A has the two following properties. First, A is slow. Recall that by definition, this means that the automaton is minimal and that the Moore minimization algorithm splits just one equivalence class into two new classes at each step.

Next, we suppose that there is a lazy path in A: by definition, this is a path

π : q 0 a 0 -→ q 1 a 1 -→ q 2 • • • q h-1 a h-1 --→ q h
of length h, where q 0 and q h are the two states which are separated in the last step in the Moore algorithm together with the condition that q h-1 • āh-1 = q 0 or q h where ā = 1a for a ∈ D. If N ≥ 2, the first of these conditions means that q 0 ∼ N -2 q h and q 0 ∼ N -1 q h . As a consequence, the second property means that if the states q h-1 • āh-1 and q h-1 • a h-1 are distinct, they cannot be separated before the very last step of the Moore algorithm.

Example 13 The automaton  given in Fig. 17 has a subautomaton A composed of the states {p, s, r}. This subautomaton is slow: the first partition is into {p, r} and {s}, and the second partition is equality. The finite subautomaton A in Fig. 17 Given the finite slow automaton A, the lazy path π and an infinite word x = x 0 x 1 x 2 • • • over D, we now define an infinite automaton  which accepts the set of nodes labeled a of a tree t. The automaton  will be minimal as soon as x is not eventually periodic. We will show that if x is a Sturmian word, then t is a Sturmian tree of degree 1. This automaton is the extension of A by π and x, and is denoted by

 = A(π, x).
The set of states of  is Q ∪ N. For convenience, we use a mapping q : N → {q 0 , . . . , q h-1 } defined by q(n) = q n mod h for any n ∈ N. Here and below q 0 , . . . , q h are the states of the lazy path of A and a 0 , . . . , a h-1 are the letters labeling the path. The initial state of  is 0 and its set of final states is F ∪ q -1 (F ). The next-state function of A is extended to  by setting, for n ∈ N,

(α) if n ≡ h -1 mod h, then n • a n mod h = n + 1 and n • ān mod h = q(n) • ān mod h , (β) if n = ih + h -1 for some i ≥ 0, then n • x i = n + 1 and n • xi = q 0 .
The infinite path through the integer states of the automaton  is composed of an infinite sequence of copies of the lazy path of A. For each state q(n) inside each of the copies of the lazy path, the next-state for the "other" letter, that is the letter ān mod h , maps q(n) back into A. Two consecutive copies of the lazy path, say the ith and i + 1th, are linked together by the letter x i of the infinite word x driving the automaton (see Fig. 17).

Proposition 5 Let  = A(π, x) be the extension of the finite slow automaton A by a lazy path π and an infinite word x. If the word x is Sturmian, then  defines a tree t which is Sturmian, of degree 1, and having finite rank.

The tree defined by this automaton has degree 1 since the only irrational states are the integer states n and they all lie on a single branch. Its rank is the number of states of the automaton A. We claim that this tree is also Sturmian. The proof is through three lemmas.

We denote by ∼ k the Moore equivalence on the states. The next three lemmas just prove that the automaton has the required properties. We fix the automaton A, set N to be the number of its states, and we fix the lazy path π :

q 0 a 0 -→ q 1 a 1 -→ • • • a h-1 --→ q h .
We also use the notation q(n) = q n mod h . However, in the three following lemmas, x is not required to be Sturmian. Proof By induction on k. The result clearly holds for k = 1 since the set of final states is F ∪ q -1 (F ). Assume that n ∼ k q(n) for any n ≥ 0 and k ≤ N -2. We prove that n ∼ k+1 q(n) holds for any n ≥ 0.

If

n ≡ h -1 mod h, then setting a = a n mod h , one has n • a = n + 1 ∼ k q(n + 1) = q(n) • a and n • ā = q(n) • ā. From n ∼ k q(n), it follows that n ∼ k+1 q(n).
Suppose now that n = ih + h -1 for some i ≥ 0. One has n • x i = n + 1 ∼ k q 0 , n • xi = q 0 and q h-1 • x i , q h-1 • xi ∈ {q 0 , q h }. Furthermore, q 0 ∼ k q h because k ≤ N -2. This, together with n ∼ k q(n), shows that q(n) ∼ k+1 q h-1 .

Example 13 (continued) In our example, one has h = 4 and q(n) = p if n ≡ 0, 2 mod h, and q(n) = s otherwise. Also, the first two Moore equivalence classes group together integer states with their images by the mapping q. Observe that each class in ∼ 2 contains exactly one state of the {p, s, r}.

Lemma 4 Let k, ≥ 0 be integers with k

+ = h -1. 1. If (n mod h) < , then n ∼ N +k q(n). 2. If (n mod h) ≥ , then n ∼ N +k p for any p ∈ Q, and n ∼ N +k n iff n ≡ n mod h.
Example 13 (continued) In our example, the next h steps (with h = 4) split away classes of integer states, in the decreasing order of their labels mod 4: first the states n ≡ 3 mod h, then the states n ≡ 2 mod h and so on. After these steps, the states p, s, r are singleton classes.

Proof of Lemma 4

The proof is by induction on k.

First, assume k = 0, that is = h -1. If 0 ≤ n mod h ≤ h -2, then n ≡ h -1 mod h.
By the previous lemma, one has n ∼ N -1 q(n). Setting a = a n mod h for short, one has n • a = n + 1 ∼ N -1 q(n + 1) = q(n) • a and n • ā = q(n) • ā. This proves that n ∼ N q(n).

If n = ih + h -1, then for the first claim, it suffices to prove that n ∼ N q(n). To show this, observe that the letter a h-1 separates n and q(n) = q h-1 . Indeed, first one has q h-1 • a h-1 = q h and second, n

• x i = n + 1 ∼ N -1 q 0 and n • xi = q 0 . Conse- quently, n • a h-1 ∼ N -1 q 0 ∼ N -1 q h .
This proves the first claim.

For the second claim, consider n ≡ n mod h and set n = h + h -1. Then n ∼ N -1 n by the previous lemma, and moreover n

• x i = n + 1 ∼ N -1 q 0 , n • xi = q 0 , and n • x i = n + 1 ∼ N -1 q 0 , n • xi = q 0 .
This proves that n ∼ N n . Suppose conversely that n ≡ h -1 mod h. One has n ∼ N q(n ) by Claim [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF] and n ∼ N p for any p ∈ Q. Thus n ∼ N n . This proves that n ∼ N n iff n ≡ n mod h.

Assume now that k > 0 and that the result holds for k -1. If n is such that n mod h < , then n + 1 mod h < + 1 and by the induction hypothesis, one has n + 1 ∼ N +k-1 q(n + 1). Setting a = a n mod h for short, one has n

• a = n + 1 ∼ N +k-1 q(n + 1) and n • ā = q(n) • ā. Since n ∼ N +k-1 q(n) holds by induction, this shows that n ∼ N +k q(n).
Let n be such that ≤ n mod h. If + 1 ≤ n mod h, then n ∼ N +k-1 p for each p ∈ Q which implies that n ∼ N +k p for each p ∈ Q. In the last case n mod h = , it suffices to show that n ∼ N +k q(n). For this, observe that by the induction hypothesis, one has n + 1 ∼ N +k-1 q(n + 1). Next, n • a = n + 1 and q(n) • a = q(n + 1) where a = a n mod h . This proves that n ∼ N +k q(n).

Suppose now that n ≡ n mod h and set again n

= ih + h -1, n = i h + h -1. If n ≡ h -1 mod h, then n • x i = n + 1, n • xi = q 0 , n • x i = n + 1 and n • xi = q 0 ,
and it follows from n ∼ N +k-1 n and n + 1

∼ N +k-1 n + 1 ∼ N +k-1 q 0 that n ∼ N +k n .
If, on the contrary, n ≡ h -1 mod h, then n • a = n + 1, n • a = n + 1 and n • ā = n • a = q(n + 1), and it follows from n ∼ N +k-1 n and n + 1

∼ N +k-1 n + 1 that n ∼ N +k n .
In order to prove the converse, suppose now that n ∼ N +k n . Set m = n mod h and m = n mod h. Assume that m = m and without loss of generality m < m . If m < , then by Claim (1), n ∼ N +k q(n) and n ∼ N +k q(n ), a contradiction because

q(n) ∼ N q(n ). Thus m ≥ . Set = m and k = h --1. Then k ≤ k and m < = m . Therefore, n ∼ N +k q(n) and n ∼ N +k p for any p ∈ Q. This implies n ∼ N +k n and also n ∼ N +k n since k ≤ k. Lemma 5 Let k, ≥ 0 be integers with k + = h -1. Let n ≡ n mod h and set i = n/ h and i = n /h . For all integer j ≥ 1, n ∼ N +jh+k n ⇐⇒ x i • • • x i+j -2 = x i • • • x i +j -2 if (n mod h) < , x i • • • x i+j -1 = x i • • • x i +j -1 otherwise.
The proof is very similar to that of the previous lemma and it is therefore omitted.

Example 13 (continued) In our example, the infinite word is the Fibonacci word

x 0 x 1 • • • = 01001 • • • and h = 4.
The first partition is into states ih + h -1 with

x i = 0 and with x i = 1. After 4 steps, the next partition is into states ih + h -1 with x i x i+1 = 00, with x i x i+1 = 01 and with x i x i+1 = 10.

Proof of Proposition 5

It suffices to count the number of trees of a given height in t, and by Corollary 2, it suffices to show that  is slow. For this purpose, we compute the index of ∼ n . By Lemma 3, the index of ∼ N -1 is N , by Lemma 4 the index of ∼ N +h-1 equals N + h, and by Lemma 5, the index of the equivalence ∼ N +jh+h-1 is equal to N +hc x (j ) where c x (j ) is the number of distinct factors of length j in x. If x is Sturmian, then c x (j ) = j + 1, and thus the index of ∼ N +jh+h-1 is N + h(j + 1).

We have shown that the index of ∼ n is n + 1 for infinitely many n, and this implies immediately that the index is n + 1 for all n.

Characterization

In this section, we give a characterization of Sturmian trees of degree 1 which have finite rank by describing the family of automata accepting their languages. These (infinite) automata are extensions of a finite automaton by a lazy path and a Sturmian word.

Theorem 1 Let t be a Sturmian tree of degree one having finite rank, and let  be the minimal automaton of the language of t. Then  is the extension of a slow finite automaton A by a lazy path π and a Sturmian word x, i.e.  = A(π, x).

We start with a general lemma which will also be of use later. Consider a tree t having finite rank. Let  be the minimal automaton of the language of t. Each of the finitely many distinct rational subtrees of t contributes a state to this automaton. Let Q be the finite set of states corresponding to rational subtrees. Recall that a state in Q is what we called a rational state. The next-state function maps rational states into rational states, so that the restriction of  to the set Q is a subautomaton that we denote by A. This subautomaton is itself minimal.

Given a tree t and some Moore equivalence ∼ h on its minimal automaton, it is convenient to call an equivalence class of ∼ h an irrational class if it is entirely composed of irrational states. It is a rational class otherwise. A rational class contains at least one rational state, and may contain even infinitely many irrational states.

Lemma 6 Let  be the minimal automaton of some (not necessarily Sturmian) tree t. Assume that, for some integer h, the equivalence ∼ h only splits irrational classes. Then for all h ≥ h, ∼ h only splits irrational classes. Proof Let Q be the set of rational states in Â. Let P be the union of the rational classes of ∼ h-1 . Then P ⊃ Q, and at least one class c that is split in ∼ h is disjoint from P . The set P is stable for the next-state function: indeed, each state p in P is equivalent for ∼ h-1 to some state q in Q. The states p and q are mapped, by each letter a, into the same class for ∼ h-1 because ∼ h does not split any class contained in P . Thus both states q • a and p • a are in P . This shows that P is the set of states of a subautomaton, and since ∼ h-1 and ∼ h are identical on this subautomaton, it is minimal and there will never be any splitting of one of its classes. So all splittings concern only classes that do not contain any element in Q.

Note that if the tree t in Lemma 6 has infinite rank, then each ∼ h also splits a rational class. Note also that if t is Sturmian and has infinite rank, there is no irrational class at all. Thus the lemma is of interest for trees with finite rank.

Corollary 3 Let t be a Sturmian tree with finite rank. Let  be the minimal automaton of the language of t. Assume that, for some integer h, the equivalence ∼ h splits some irrational class. Then for all h ≥ h, ∼ h always splits an irrational class.

Lemma 7 Let t be a Sturmian tree with finite rank. Let N be the number of rational states. The Moore equivalence ∼ N -1 has index N and each of these contains exactly one rational state.

Proof This is because the subautomaton composed of rational states is slow and minimal.

Lemma 8 Let t be a Sturmian tree with finite rank. Either there is an integer n such that all rational classes of ∼ n are singletons, or there exists, for each irrational state, an integer n such that the class of this state in ∼ n is a singleton. Proof Assume that the first of the two possibilities is not realized. Then for all n, there exists a class containing both rational and irrational states. We call here such a class a mixed class. Thus a mixed class is a rational class which contains at least one irrational state. We consider an n ≥ N , where N is the number of rational states, so each mixed class contains exactly one rational state, and at least one irrational state. For each n ≥ N the class split in ∼ n must be a mixed class, because otherwise in view of Corollary 3, this class will never be split. The same argument shows that every irrational class is a singleton. Let p be any irrational state in some mixed class c, containing a unique rational state, say r. Since p = r and the automaton is minimal, there exists an integer m such that r and p are in different classes for ∼ m . The class of p is irrational because r is in another class for ∼ m . In view of Corollary 3, the class of p will never split, so it is a singleton class.

We will see later examples of Sturmian trees of degree greater than one. In these examples, the trees have finite rank. This is due to the following property of Sturmian trees.

Proposition 6

The degree of a Sturmian tree with finite rank is either one or infinite. Proof Let t be a Sturmian tree with finite rank, and assume it has finite degree d > 1. A node w of t is a fork if both w0 and w1 are irrational nodes. Since t has degree d, it has exactly d -1 fork nodes.

A state of the minimal automaton of t is a fork state if it is the state of a fork node. The automaton has at most d -1 fork states. We want to show that for large enough n, an equivalence class of ∼ n containing a fork state is a singleton.

In view of Lemma 8, there are two cases. Either there is an integer n such that all rational states are singletons for ∼ n . Then a class of ∼ n containing a fork state contains only fork states since indeed a state that is not a fork state maps to a rational state by at least one letter, whereas a fork state does not. So any class containing a fork state is finite, and therefore will be split eventually into singleton classes.

In the other case described by Lemma 8, every irrational state will be in singleton classes for large enough n. Since there are only finitely many fork states, each of these will be in a singleton irrational class of ∼ n for some n.

Consider now an integer H such that each fork state is a singleton class of ∼ H . This means that the Nerode equivalence and the equivalence ∼ H coincide for these states, and consequently two fork nodes in the tree define the same state in the automaton if and only if they are the roots of the same subtree of height H . According to Remark 1, there are infinitely many occurrences of any subtree of height H in Sturmian tree, there are infinitely many nodes that correspond to the same fork state, so there are infinitely many fork nodes. This yields the desired contradiction.

Assume now that the tree t has degree 1. Each of the subtrees of the infinite irrational branch contributes a state to Â. Denote by N the set of states of the infinite branch. We number these states so that the next-state function of  maps a state n in N to the state n + 1 in N by one of the two letters, and to a rational state by the other.

The next statements show that after some additional steps, each of the rational states constitutes a singleton class of the corresponding Moore equivalence. Recall that an equivalence class is an irrational class if it is composed only of irrational states, and a rational class otherwise.

Lemma 9 If the tree t is Sturmian and has degree one, then there is some integer n such that ∼ n splits an irrational class.

Proof Assume the contrary: at each step, the class c n-1 split by ∼ n contains a rational state. We assume n ≥ N , so each class of these classes contains exactly one rational state.

In view of Corollary 1, there exists an infinite sequence of pairs

(c n , c n ) of classes of ∼ n such that each c n-1 = c n ∪ c n is the equivalence class of ∼ n-1 which is split by ∼ n .
There are also letters a n , such that each a n maps all states of c n into states of c n-1 , and all states of c n into states of c n-1 . One of the classes c n , c n contains the rational state. If this holds for c n , then it holds for c n-1 since a rational state is mapped into a rational state. Next, the classes c n never split since they are irrational classes. Since the automaton is minimal, this implies that these classes are singleton classes. Set c n = {r n }. Then there is an infinite path

• • • r n a n -→ r n-1 a n-1 --→ • • • a N+1
---→ r N , which is impossible since then 0 ≤ r n = r n-1 -1 < r n-1 for all n, and the r n are a strictly decreasing sequence of positive integers.

From now on, the tree t is assumed to be a Sturmian tree of degree 1 and with finite rank. In particular, the previous lemma holds. Proof Indeed consider a rational class c of ∼ H -1 . By Lemma 3, the class c will never be split again. Since the automaton is minimal, it must be a singleton.

Lemma 10 Let H be the smallest integer such that ∼ H splits an irrational class, and set h = H -N , where N is the number of rational states. Then there is a lazy path

π : q 0 b 0 -→ q 1 b 1 -→ • • • q h-1 b h-1 --→ q h
with q h-1 • bh = q 0 or q h , where q 0 , . . . , q h are rational states, and q 0 ∼ N -2 q h . Proof According to the previous statements, the equivalence ∼ N -1 contains N classes, and each of its classes contains exactly one rational state. The equivalence ∼ H -1 contains H classes. N of theses classes are singleton classes composed of a rational state, the H -N other classes are irrational classes. Each of the equivalence relations ∼ n , for n = N, . . . , H -1, splits a rational class c n-1 containing a single rational state into a (smaller) class c n containing this state, and an irrational class c n . See Fig. 19.

In view of Corollary 1, there are letters a n such that states of c n are mapped into states of c n-1 by a n and states of c n are mapped by a n into states of c n-1 .

Each of the rational classes c n is mapped, by one letter, into the class c n-1 , and by the other letter into some rational class, whereas each of the irrational classes c n is mapped, by one letter, into the irrational class c n-1 and by the other letter into a rational class.

The H -N irrational classes produced during these steps will not be changed before ∼ H : so all these irrational classes produced during these steps are also classes of ∼ H -1 . Indeed, otherwise a relation splits an irrational class, and by Lemma 3 the classes containing rational states will not be split anymore. Denote by s n the rational

s H -1 a H -1 ---→ s H -2 a H -2 ---→ • • • a N+3 ---→ s N +2 a N+2 ---→ s N +1 a N+1 ---→ s N .
Also, s N is mapped by each letter to a rational state. see Fig. 20.

Consider now the equivalence ∼ H ; it contains two fresh classes c H and c H , obtained by splitting a class c H -1 of ∼ H -1 . Since all rational classes are singletons in ∼ H -1 , the class c H -1 is an irrational class. This means that c H -1 is one of the H -N irrational classes c N , c N , . . . , c H -1 . We prove that c H -1 = c N .

Since the class c H -1 is an irrational class, each of its states is mapped, by one letter, onto some rational state, and by the other letter onto an irrational state. Let a H be the letter that maps all states of c H onto the state s H -1 , and all states of c H into the irrational class c H -1 . It follows that the letter āH maps all states of c H (those mapped by a H onto the rational state) into some irrational class, and all states of c H (those mapped into irrational states by a H ) onto some rational state. See Fig. 21.

The class c H -1 = c H ∪ c H is a subset of an equivalence class of ∼ H -2 . Consequently each of the letters maps all states of c H -1 onto states that are equivalent mod ∼ H -2 , and so belong to a class mod ∼ H -2 containing both a rational state and irrational states. As we observed earlier, this class is c H -2 = c H -1 ∪ c H -1 .

Fig. 22 The class c N -1 of ∼ N -1 contains a rational state q , the class c N -1 contains a rational state q . The class c H -2 is a subset of c N -1 , and c N = c H -1

Thus the letter āH maps states of c H into c H -1 and states of c H onto s H -1 , that is, the letter āH has the opposite behavior of letter a H .

We have shown that each letter maps some of the states of the irrational class c H -1 to an irrational state, and at least one of its states to a rational one. Since each class c n , for N < n ≤ H -1, is mapped, by the letter a n , into an irrational class, the class c H -1 cannot be one of the classes c n for N < n ≤ H -1, and so c H -1 is the only remaining irrational class, that is c H -1 = c N .

Recall that s n denotes the rational state in class c n , for n = N, . . . , H -1, and that there is a path

s H -1 a H -1 ---→ s H -2 a H -2 ---→ • • • a N+3 ---→ s N +2 a N+2 ---→ s N +1 a N+1 ---→ s N .
The state s N is mapped by each letter to a rational state. Now the equivalence ∼ N -1 splits the class c N -2 of ∼ N -2 into two equivalence classes c N -1 and c N -1 , containing each one rational state, say q ∈ c N -1 and q ∈ c N -1 . Denote by a N the letter that maps c N into c N -1 and c N into c N -1 . The states q and q are the last rational states separated in Moore's algorithm. See Fig. 22.

The class c H -1 is mapped, by both letters, into the class c H -2 (see Fig. 21). The only rational state in c H -2 is s H -1 . The class c H -1 = c N is mapped by the letter a N into c N -1 . This implies that c H -2 ⊆ c N -1 and consequently s H -1 = q . Since the class c N is mapped by a N into c N -1 , the state s N is mapped by a N to q , and by āN to one of the two rational states in c N -2 , thus to q or to q .

In order to fit with the notations of the lazy path, it suffices now to set h = H -N , and q i = s H -1-i and b i = a H -1-i , and q h = q . Then the path becomes

q 0 b 0 -→ q 1 b 1 -→ • • • q h-2 b h-1 --→ q h-1 .
Moreover, there is a transition q h-1 • b h = q h , and for the other letter bh , either q h-1 • bh = q 0 or q h-1 • bh = q h , and indeed q 0 , q h are the rational states that are equivalent in ∼ N -2 .

According to the (proof of the) preceding lemma, the irrational classes of ∼ H -1 and of ∼ H behave as depicted in Figs. 23 and24. It remains to exhibit a Sturmian word x such that  is an extension of the claimed form. As already mentioned, each of the subtrees of the infinite irrational branch contributes a state to Â. The states of the infinite branch are denoted by N. They are numbered such that the next-state function of  maps a state n in N to the state n + 1 in N by one of the two letters, and to a rational state by the other.

The irrational path of the tree is labeled by an infinite word

y = y 0 y 1 y 2 • • • ∈ {0, 1} ω
and corresponds in  to the infinite path 0

y 0 -→ 1 y 1 -→ 2 -→ • • • -→ n y n+1 --→ n + 1 -→ • • • .
For each state n, the letter ȳn maps n into a rational state. It follows from the previous properties of

∼ H -1 that n ∼ H -1 n ⇐⇒ n ≡ n mod h .
We suppose for simplicity that 0 ∈ c H -1 , and we define the infinite word

x = x 0 x 1 • • • by x 0 = y h-1 , x 1 = y 2h-1 ,
n ∼ H +jh+k n ⇐⇒ x i • • • x i+j -1 = x i • • • x i +j -1 if (n mod h) < , x i • • • x i+j = x i • • • x i +j otherwise.
Observe that this is Lemma 5, but the assumptions are different. Indeed, in Lemma 5, the word x defines an automaton and a property of the Moore equivalences is looked for. Here we know the Moore equivalences and we want to describe a property of a word x that will allow us to show that it is Sturmian. However, the arguments of the proof are quite similar, so we sketch only one basic, but typical step.

The proof is by induction on H + jh + k. For j = k = 0, there is nothing to prove except when n ≡ h -1 mod h. In this case, the claim becomes that n ≡ H n if and only if

x i = x i , with n = ih + h -1.
By definition, one has n x i -→ n + 1 and n

x i -→ n + 1. Now, the equivalence relation ≡ H splits the irrational class c H -1 of ∼ H -1 containing both n, n into two irrational classes c H and c H of∼ H (see Figs. 23 and24). The states n, n are in the same of these classes iff they are mapped by the same letter x i into an irrational state. Thus

x i = x i .
It remains to count the number of factors of the word x. Set k = h -1, = 0 in the previous lemma. There are H + (j + 1)h classes in the equivalence relation ∼ H +jh+h-1 . Among them, N = Hh are rational classes, so there are (j + 2)h irrational classes. Any two classes containing integers n, n which are congruent modulo h define the same factor of length j + 1 of x, so there are exactly j + 2 distinct factors of length j + 1 in the infinite word x. This concludes the proof of Theorem 1.

Trees with Infinite Rank

There exist Sturmian trees with infinite rank. The following example gives a Sturmian tree with infinite rank and of degree 1.

Example 14 We define a tree by giving a (minimal) automaton accepting its language. The set of states of the automaton is Q = {n ∈ N | n ≥ 3} × {0, 1}. The set of final states is the set {(n, b) ∈ Q} with even n. The set E of transitions is defined as follows. Let n = 2 k m where m ≥ 1 is odd. The integer 2 k is the greatest power of 2 which divides n.

(n, b) • 0 = (2 k-1 + 1, 0) if m = 1 and b = 0, (n + 1, b) otherwise, (n, b) • 1 = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (3, 0) if k = 0, (4, 0) if k = 1, (4, 0) if k = 2, m = 1 and b = 0, (2 k-2 + 1, 0) if k > 2, m = 1 and b = 0, (2 k-1 + 1, 0) otherwise.
For making the description more readable, we write n for (n, 0) and n for (n, 1). In Fig. 25 we give a picture of this automaton.

The next table gives the explicit values of the next-state function for values of n up to 16. The states are arranged in order to make the state splitting more easy to follow. Recall that even states are final. In order to show that the automaton is slow, we describe how the Moore algorithm behaves. This will show that the automaton is minimal. We start by considering the very first splittings. We use the shorthand a + bN for the arithmetic progression {a + bm | m ≥ 0}.

The minimization algorithm starts with an equivalence relation composed of the two classes of even (final) and odd (nonfinal) states.

In the first step of partition refinement, only the letter 1 induces a splitting: it splits the even states into two classes, one composed of 4 and the states with numbers in 6 + 4N, the other containing 4 and the states with numbers in 8 + 4N. Observe that after this splitting, the siblings 4 and 4 are in distinct equivalence classes.

At the next step, again only one new class is created. The letter 0 splits the odd states into two classes, the first composed of 3 and of the states with numbers in 5 + 4N, the second composed of 3 and the states in 7 + 4N. Observe that at this stage, there are four equivalence classes, and the siblings 4 and 4 , and the siblings 3 and 3 are in distinct equivalence classes.

In the next step, the letter 0 isolates state 4 , that is 4 is a singleton class. Indeed, it is mapped on 3 whereas all states with numbers in 6 + 4N are mapped on states in 7 + 4N.

As a consequence, in the next step 3 is itself isolated, since it is mapped by 0 on 4 whereas the states in 5 + 4N are mapped on states in 6 + 4N. At this stage, there are six equivalence classes, namely the states 4 and 3 which are singletons and the classes composed of states with numbers in 5 + 4N and 6 + 4N, the class containing 4 and states with numbers in 8 + 4N, and finally the class containing 3 and states with numbers in 7 + 4N.

Consider one more step. The letter 1 splits the class containing 4 and states with numbers in 8 + 4N since 8 and states with numbers in 12 + 8N are mapped on 3 whereas 8 and states with numbers in 16+8N are mapped on 5 . Thus in particular, this step puts 8 and 8 in distinct equivalence classes.

We are now able to give an overview of the minimization process. It operates on the automaton by levels, each level taking care of the states up to the next power of two (both rational and irrational). Thus the first level operates on the four states numbered 3 and 4, the second level operates on the eight states numbered from 5 to 8, and so on.

Each level is composed of a separation phase, followed by an isolation phase. Each step in the separation phase puts the states n and n in distinct equivalence classes. This separation phase is by decreasing numbers, starting with a power of two. The isolation phase creates singleton classes. Each step creates a singleton class n , again by decreasing numbers.

Thus the four steps of the two phases in level 1 are summarized by Thus the eight steps of the two phases in level 1 are summarized by 10 3 1 8 8 separated 010 3 1 7 7 separated 0010 3 1 6 6 separated 00010 3 1 5 7 separated 0 4 10 3 1 8 isolated 0 5 10 3 1 7 isolated 0 6 10 3 1 6 isolated 0 7 10 3 1 5 isolated

In the first column we have given a word that separates or isolates the corresponding states. This description shows why the automaton is minimal: states of the form n eventually become singleton classes, states of the form n never become singleton classes, but two such states will eventually be separated.

Remark 2

The automaton of the previous example may be modified in two ways, giving still a slow automaton.

(a) The first modification consists in defining mapping each state (n, b) with n odd by both letters onto the state (n + 1, b). One observes that the Moore minimization algorithm behaves in the same way. Now, both the rank and the degree of the tree are infinite. (b) The other modification is to map all states that where mapped on 3 in the initial automaton on state 3 . Again, the minimization process does not change. There are no rational states anymore, so the rank is 0 and the degree is infinite.

This second modification gives some additional information about the splitting of irrational states in a slow automaton. We have seen examples, as the Dyck automaton, where splitting is by isolating irrational states. There were also examples such as the automaton of the indicator trees, where irrational classes are never singletons. Here we get an example where some of the states are isolates (all states n ) and others are never (the states n ).

The previous example of a Sturmian tree of degree one having infinite rank can be extended to an example of a Sturmian tree of degree two which must have infinite rank in view of Proposition 6.

Example 15 We define a tree by giving a (minimal) automaton accepting its language. The set of states of the automaton is the following set In Fig. 26 we give a picture of this automaton; states of the form (n, 0) are drawn as circles n and states of the form (n, 1) as squares n and states of the form (n, 2) as lozenges n . The Moore algorithm here is again slow. It is more complicated. The circled and square states are used in a very similar way to that of Example 14, but with powers of 3. The powers of 3 work for circles and lozenges. It remains to check that the two processes never collide (which would produce more than a single split in some step). We leave the formal verification to the reader. In Fig. 27 we give a picture of this automaton; again states of the form (n, 0) are drawn as circles n and states of the form (n, 1) as squares n and states of the form (n, 2) as lozenges n .

Q Q = {(n, 0) | n ≥ 2} ∪ {(n,
The initial state (0, 1) is the only irrational state for which both outgoing edges lead to nonfinal states. Since it has no incoming edge, this ensures that it cannot appear in an irrational path in an other place than the root. Thus the example shows that Proposition 4 does not hold in this case. However this tree is Sturmian. In particular, observe that rational states (2 n , 2) correspond to rational nodes in the tree which share the same prefix tree of increasing finite height than the root (0, 1).

Concluding Remarks

We have introduced the notion of Sturmian trees and we have considered two parameters, the degree and the rank. We have described the structure of Sturmian trees of finite rank and finite degree. This is the main contribution of this paper.

We have given several examples of Sturmian trees of finite rank and infinite degree. We have also given examples of Sturmian trees of infinite rank. These have some kind of fractal structure. We have built Sturmian trees of infinite rank and of degree two, and with both infinite degree and infinite rank. These examples show that the structure of general Sturmian trees is quite involved, and there seems not to be such a concise characterization as it exists in the case of Sturmian words.

Fig. 3

 3 Fig.3The top of a left branch tree for the word abaaba • • •

Fig. 7

 7 Fig. 7 Automaton of an extension of the Dyck language

  Figure 8 shows the automaton accepting the prefixes of the Fibonacci word x = 01001010 • • • .

Fig. 8 Fig. 9

 89 Fig. 8 Automaton accepting the prefixes of 01001010 • • • . All states excepted ∞ are final

Fig. 10

 10 Fig. 10 Automaton of t x,x for x = 01001010 • • • and x = 10100100 • • •

Fig. 15

 15 Fig. 15 The four factors of height 3, and the five factors of height 4 of the Dyck tree

  tree (rank 1) Band width tree (rank d + 1) ≥ 2, finite empty byProposition 6 Example 15 infinite Uniform tree (rank 0) Example 14(a) Left branch tree (rank 0) Example 11 (rank 0) Dyck tree (rank 1)

-→ s 0 -→ p 0 -→ s 1 -

 001 admits for example the lazy path π : p 0 → r, and indeed s 0 -→ p. Here h = 4.

Fig. 17 A

 17 Fig. 17 A slow automaton  for the Fibonacci word x 0 x 1 • • • = 01001010 • • • . The final states are p, r, 0, 2, 4, . . .

Fig. 18

 18 Fig. 18The tree showing the evolution of the Moore equivalence relations on the automaton given in Fig.17. Each level describes a partition. Each level has one class splitting into two classes at the next level

Fig. 19

 19 Fig. 19 The class c n-1 of ∼ n-1 is split into two classes c n and c n of ∼ n . The letter a n maps states of c n-1 into states of the class c n-1 and states of the class c n-1 into states of the class c n-1 . Observe that the classes c n-1 and c n-1 are those created at the preceding step

Fig. 20

 20 Fig. 20 The classes of ∼ H -1 . The classes c N , c N +1 , . . . , c H -1 are irrational, and the (rational) classes containing the states s N , s N +1 , . . . , s H -1 are singletons

Fig. 23 1 Fig. 24

 23124 Fig. 23 The irrational classes of ∼ H -1

Fig. 25

 25 Fig. 25 Final states are dark. Observe the fractal-like structure, with a doubling of the size of each block

1 )

 1 | n = 3 or 3 k+2 -4 • 3 k + 1 ≤ n ≤ 3 k+2 with k ≥ 0} ∪ {(n, 2) | n ∈ {2, 3} or 3 k+2 -3 k + 1 ≤ n ≤ 3 k+2 with k ≥ 0}.The set of final states is the set {(n, b) ∈ Q mid n ≡ 0 mod 2}. The set E of transitions is defined as follows. Let n = 2 k 3 m where m ≡ 0 mod 2 and m ≡ 0 mod 3. The integers 2 k and 3 are the greatest powers of 2 and 3 which divide n.(n, b) • 0 = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ (3 -1 + 1, 0) if k = 0, m = 1 and b = 0, (3 +1 -4 • 3 -1 + 1, 1) if k = 0, m = 1 and b = 1, (3 -1 -2 • 3 -1 + 1, 2) if k = 0, m = 1 and b = 2, (n + 1, b) otherwise, if n = 2 and b = 2, (3, 0) if n = 3 or = 0, (3 -2 + 1, 0) if k = 0, ≥ 2 and m = 1, (3 -1 + 1, 0) if k = 0, ≥ 1 and m ≥ 2, (3 + 2, 0)otherwise.

Example 16

 16 We define a tree by giving a (minimal) automaton accepting its language. The set of states of the automaton isQ = {(n, 0) ∈ N | n ≥ 3} ∪ {(n, 1) ∈ N | n ≥ 0} ∪ {(2 k , 2) ∈ N | k ≥ 1}. The set of final states is the set {(n, b) ∈ Q} with even n.The set E of transitions is defined as follows. Let n = 2 k m where m ≥ 1 is odd. The integer 2 k is the greatest power of 2 which divides n. First (n, 2)• 0 = (n, 2) • 1 = (n + 1, 0) for all n. Next (0, 1) • 0 = (0, 1) • 1 = (1, 1). For n ≥ 1 and b = 0, 1, (n, b) • 0 = (2 k-1 + 1, 0) if m = 1 and b = 0, (n + 1, b) otherwise, (n, b) • 1 = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ (3, 0) if k = 0, (4, 0) if k = 1, (2 k-2 , 2) if k > 2, m = 1 and b = 0, (2 k-1 , 2) otherwise.

Fig. 26

 26 Fig. 26 Sturmian tree of degree 2

Fig. 27 A

 27 Fig. 27 A tree with infinite rank. Final states are dark

  • • • x n+h-1 of the word x. In Example 2, two factors t[w, h] and t[w , h] of height h are equal if and only if x[|w|, h] = x[|w |, h]. In Example 3, t[w, h] and t[w , h] are equal if and only if x[|w| 0 , h] = x[|w | 0 , h]. It follows that in these examples, the tree t is Sturmian if and only if the word x is Sturmian.

  and in general x i = y (i+1)h-1 . We prove that x is a Sturmian word, by showing that it has n + 1 factors of length n for each n ≥ 0.The key lemma is the following

Lemma 11 Let k, ≥ 0 be integers with k + = h -1. Let n ≡ n mod h and set i = n/ h and i = n /h . For all integer j ≥ 0,

Acknowledgements

We thank the referees for their careful reading of the manuscript and for their comments which greatly improved the exposition.