JOSÉ Jorge Almeida

AND Carlos Costa
email: jcosta@math.uminho.pt

Marc Zeitoun

José Carlos Costa

ITERATED PERIODICITY OVER FINITE APERIODIC SEMIGROUPS

Keywords: 2000 Mathematics Subject Classification. 20M05, 20M07, 20M35, 68Q45, 68Q70 Aperiodic semigroup. Free profinite semigroup. Pseudoword. ω-term. McCammond normal form. Rational language. Anti-chain. Semigroupoid

This paper provides a characterization of pseudowords over the pseudovariety of all finite aperiodic semigroups that can be described from the free generators using only the operations of multiplication and ω-power. A necessary and sufficient condition for this property to hold turns out to be given by the conjunction of two rather simple finiteness conditions: the nonexistence of infinite anti-chains of factors and the rationality of the language of McCammond normal forms of ω-terms that define factors of the given pseudoword. The relationship between pseudowords with this property and arbitrary pseudowords is also investigated.

Introduction

Since the mid nineteen seventies, the theory of finite semigroups has seen a significant boost thanks to its connections and applications in computer science. The now classical framework for the relationships between the two areas is provided by Eilenberg's correspondence between pseudovarieties of finite semigroups and varieties of rational languages [START_REF] Eilenberg | Automata, languages and machines[END_REF], whose importance is also corroborated by the fact that it has been the object of many extensions [START_REF] Gehrke | Duality and equational theory of regular languages[END_REF]. The typical application consists in the solution (positive or negative) of an algorithmic problem about rational languages or finite automata by translating it to a membership problem in a suitable pseudovariety of semigroups. Concomitantly, such applications have served as a guide in the theory of finite semigroups, pointing out the most interesting pseudovarieties to study.

Unlike varieties of algebras, pseudovarieties do not in general have free algebras. In the following decade, a substitute for relatively free algebras emerged and found many applications in the context of pseudovarieties of semigroups: the relatively free profinite algebras. The common algebraic and combinatorial properties of the semigroups in a pseudovariety become encoded in the algebraic and topological properties of their free profinite semigroups which, over a given finite alphabet, can be viewed as the Stone dual for the Boolean algebra of languages over that alphabet recognized by semigroups in the pseudovariety [START_REF] Almeida | Finite semigroups and universal algebra[END_REF][START_REF] Gehrke | Duality and equational theory of regular languages[END_REF][START_REF] Rhodes | The q-theory of finite semigroups[END_REF]. The difficulty, of course, is to obtain sufficient structural information about these profinite semigroups for the intended applications.

Through the seminal work of Ash [START_REF] Ash | Inevitable graphs: a proof of the type II conjecture and some related decision procedures[END_REF] and its generalizations found by the first author and Steinberg [START_REF]Hyperdecidable pseudovarieties and the calculation of semidirect products[END_REF][START_REF]Syntactic and global semigroup theory, a synthesis approach[END_REF][START_REF] Almeida | On the decidability of iterated semidirect products and applications to complexity[END_REF], an important property that a pseudovariety V may enjoy has emerged: the so-called tameness. Roughly speaking, it serves as a strong form of decidability, entailing that it is decidable whether a finite system of equations with rational constraints over a finite alphabet X admits a solution in every Xgenerated semigroup from V. By a standard compactness argument, the existence of such solutions can be reduced to the existence of solutions in the pro-V semigroup freely generated by X. Basically, the idea of tameness is to reduce the search of solutions in such a semigroup, which is often uncountable, to a countable subsemigroup, namely a subalgebra generated by the same set X with respect to a suitable signature, which turns out to be itself a relatively free algebra. The signature in question should be made up of "natural" operations on profinite semigroups, including the multiplication. Among such operations, the most encountered is the pseudoinversion, or (ω -1)-power. In the group case, this operation is the group inversion and the corresponding countable subsemigroup of the free profinite group is just the free group on the same generating set. In the aperiodic case, the (ω -1)-power reduces to the perhaps more familiar ω-power which, in a finite semigroup, gives the unique idempotent power of an element. In this case, let us call an algebra in our signature simply an ω-semigroup.

To prove tameness, one must establish that the word problem for the chosen relatively free algebra is decidable and, since the existence of solutions of certain systems in the relatively free profinite semigroup must be shown to entail the existence of solutions in the chosen subalgebra, it is important to understand well how the subalgebra fits the profinite semigroup. For the case of the pseudovariety of all finite groups, a restricted form of tameness was first proved within the framework of semigroup theory [START_REF] Ash | Inevitable graphs: a proof of the type II conjecture and some related decision procedures[END_REF], but also independently a special case was proved using methods from profinite group theory [START_REF] Ribes | On the profinite topology on a free group[END_REF]29], and later was rediscovered as a model-theoretic result [START_REF] Herwig | Extending partial automorphisms and the profinite topology on free groups[END_REF][START_REF] Almeida | Sur certains systèmes d'équations avec contraintes dans un groupe libre[END_REF][START_REF]Sur certains systèmes d'équations avec contraintes dans un groupe libre-addenda[END_REF].

For the pseudovariety A of all finite aperiodic semigroups, tameness has been announced by John Rhodes at the International Conference on Algorithmic Problems in Groups and Semigroups (Lincoln, Nebraska, U.S.A., May 1998) but no published proof has yet appeared except for the solution of the word problem for the relatively free ω-semigroup in the variety of ω-semigroups generated by A, which has been obtained by McCammond [24]. This seems to be explained, at least in part, by the fact that a gap was discovered in the proof of a key result from [START_REF] Almeida | Profinite categories and semidirect products[END_REF] used in [START_REF] Almeida | On the decidability of iterated semidirect products and applications to complexity[END_REF] to reduce the decidability of the Krohn-Rhodes complexity of finite semigroups [START_REF] Krohn | Complexity of finite semigroups[END_REF] (see [START_REF] Rhodes | The q-theory of finite semigroups[END_REF]) to the tameness of the pseudovariety A.

McCammond's solution of the word problem is obtained by constructing a normal form, to which every ω-term may be reduced, preserving its action on semigroups from A, and then showing that two distinct ω-terms in normal form act differently on some finite aperiodic semigroup by using his own solution of the word problem for certain free Burnside semigroups [START_REF] Mccammond | The solution to the word problem for the relatively free semigroups satisfying t a = t a+b with a ≥ 6[END_REF].

The present paper is intended as a contribution to a deeper understanding of how the ω-subsemigroup generated by X fits in the free pro-A semigroup F on the finite alphabet X. The main result provides a characterization of the elements u of the ω-subsemigroup in terms of simple finiteness conditions: in any infinite set of factors of u in F , at least one of them is a factor of another one; the language of ω-terms in normal form that determine elements of F that are factors of u is rational. This may be viewed as a sort of iterated periodicity result, by interpreting the operation of taking the ω-power as the infinite iteration of its argument.

The paper is organized as follows. Section 2 gathers most of the preliminary material including some remarks on uniformly recurrent right infinite words, a description of McCammond's normal form and algorithm to compute it, as well as some important properties of the pseudovariety A. Section 3 gives a characterization of pseudovarieties V such that the set of all finite elements of the free pro-V semigroup Ω X V over a finite set of free generators X is always open and some related complementary observations to results of [START_REF]Profinite groups associated with weakly primitive substitutions[END_REF] on uniformly recurrent pseudowords. In Section 4, we introduce a notion of rank for elements of a semigroup inspired by McCammond's rank of ω-terms. Section 5 investigates some properties of Green's relations in the semigroup of ω-words over A. Several characterizations of periodicity for uniformly recurrent pseudowords over pseudovarieties containing all finite local semilattices are the theme of Section 6 which brings forth the relevance of properties like the rationality of the set of finite factors of a pseudoword as well as various chain conditions.

Sections 7 to 9 contain the main technicalities necessary for the main theorem, which is proved in Section 10. Section 7 establishes necessary conditions for a pseudoword to be describable by an ω-term, from which emerges the notion of slim pseudoword, which is investigated in Section 8. Section 9 gives a way to encode slim pseudowords over A as pseudopaths in suitable profinite categories, tools whose introduction is postponed to this point, rather than included in Section 2 for they play no role earlier in the paper. It is the iterative application of this encoding procedure that allows us to show how to construct an ω-term description of a pseudoword over A satisfying suitable finiteness conditions.

Preliminaries

Throughout this paper, we assume that the reader is familiar with the general basic theory of pseudovarieties and specifically with the central role played by relatively free profinite semigroups. A quick introduction, both to the theory and to the applications, is found in [START_REF]Profinite semigroups and applications, Structural Theory of Automata, Semigroups, and Universal Algebra[END_REF]. For more comprehensive treatments, see [START_REF] Almeida | Finite semigroups and universal algebra[END_REF][START_REF] Rhodes | The q-theory of finite semigroups[END_REF].

We adopt the following notation. A general finite alphabet is denoted X. For a pseudovariety V of (finite) semigroups, the pro-V semigroup freely generated by X is represented by Ω X V. It may be constructed for example as the projective limit of all X-generated semigroups from V or as the completion of the free semigroup X + on X with respect to the uniform structure generated by all congruences θ such that X + /θ ∈ V.

The above construction of Ω X V provides a natural mapping ι V : X + → Ω X V. While this may not be injective, it is injective for many pseudovarieties of interest. Elements of Ω X V are called implicit operations or pseudowords over V; if no reference to a pseudovariety is made, it is assumed to be S, the pseudovariety of all finite semigroups. The elements of ι V (X + ) are said to be finite while the remaining elements of Ω X V are called infinite pseudowords.

The letter A denotes the pseudovariety of all finite aperiodic semigroups, consisting of all finite semigroups all of whose subsemigroups that are groups are trivial. The pseudovariety LSl consists of all finite semigroups S such that, for every idempotent e ∈ S, the monoid eSe is a semilattice, that is eSe is a commutative semigroup in which every element is idempotent.

By a right infinite word over an alphabet X we mean an infinite sequence s = a 1 a 2 • • • of letters of X. Its finite factors are the words of the form u = a i • • • a j with i ≤ j; we then also say that u occurs in s starting at position i. We denote by F (s) the set of all finite factors of s.

We say that the right infinite word s = a 1 a 2 • • • is periodic if there exists n such that a i+kn = a i for all k ≥ 0 and all i. We concatenate a finite word w = b 1 • • • b m with a right infinite word s to obtain the right infinite word ws

= b 1 • • • b m a 1 a 2 • • • .
We say that the right infinite word t is ultimately periodic if it is of the form ws for some finite word w and some periodic right infinite word s.

By K and D we denote the pseudovarieties consisting of all finite semigroups in which idempotents are left zeros, respectively right zeros. Let K n and D n be the pseudovarieties consisting of all finite semigroups satisfying respectively the identities

x 1 • • • x n y = x 1 • • • x n and xy 1 • • • y n = y 1 • • • y n .
The structure of Ω X K is easy to describe. The mapping ι K : X + → Ω X K is injective and its image is a discrete subspace, which we identify with X + . The elements of Ω X K \ X + have unique prefixes in X + of any given length and they are completely determined by these prefixes, and so they may be identified with right infinite words, that is with elements of X N , where N denotes the set of all natural numbers. The infinite elements of Ω X K are left zeros and multiplication on the left by a finite word is obtained by concatenation. The topology of the subspace of infinite pseudowords, identified with infinite words, is precisely the product topology of X N , so that this space is homeomorphic to the Cantor set of reals. A sequence of finite words converges to an infinite word if every finite prefix of the latter is a prefix of all but finitely many terms of the sequence. The structure of Ω X D is dual.

By a quasi-order on a set we mean a reflexive and transitive binary relation ≤. The associated strict order < is defined by x < y if x ≤ y and y ≤ x. A quasi-order is a well-quasi-order (wqo for short) if it admits no infinite descending chains x 1 > x 2 > • • • and no infinite anti-chains, that is infinite sets in which, for any two distinct elements x and y, x ≤ y. Equivalently, given any sequence (x k ) k , there exist m, n such that m < n and x m ≤ x n .

Given two elements s and t of a semigroup S, we write s ≥ J t and say that s lies J-above t if t may be written as a product in which s appears as a factor. Theorem 2.4 below may be expressed by saying that Ω κ X A forms a filter in Ω X A with respect the quasi-order relation ≤ J . We write J for the equivalence relation ≤ J ∩ ≥ J . In general, when we talk about anti-chains in this paper, we mean anti-chains for the factor ordering ≥ J .

Similarly, we write s ≥ R t if s is a left factor (or prefix) of t in a given semigroup S and s ≥ L t if s is a right factor (or suffix) of t. The corresponding equivalence relations are R = ≤ R ∩ ≥ R and L = ≤ L ∩ ≥ L . The remaining Green relations are H = R ∩ L and D = R • L = L • R, where • denotes the composition of binary relations. It is well known that the maximal subgroups of a semigroup S are precisely those H-classes that contain idempotents. In the case of a finite aperiodic semigroup, H is the equality relation.

A language L ⊆ X + is factorial if it is closed under taking factors. If L is infinite, we say that L is uniformly recurrent if, for every u ∈ L there is an integer n such that, for all w ∈ L with |w| ≥ n, u is a factor of w. The right infinite word s is uniformly recurrent if the language F (s) is uniformly recurrent. The following combinatorial properties of right infinite words will be useful in the sequel. We do not know if they have been observed elsewhere.

Lemma 2.1. Let s be a right infinite word such that F (s) has no infinite anti-chains. Then s is of the form ut, where u is finite and t is uniformly recurrent.

Proof. Suppose that every factorization s = ut, where u is a finite word, is such that t is not uniformly recurrent. We construct a sequence (f n ) n of factors of s which is an anti-chain, which produces a contradiction and therefore proves the lemma.

Since s itself is not uniformly recurrent, there exists an arbitrarily long factor f 1 of s that is not a factor of infinitely many factors of s. If f 1 occurs infinitely often as a factor of s, then there are infinitely many factors of s of the form f 1 uf 1 in which f 1 appears only as prefix and suffix. Since such factors constitute an anti-chain, it follows that there is a factorization s = u 1 s 1 such that f 1 / ∈ F (s 1 ). Applying the same argument to s 1 , we deduce that there is some factorization s 1 = u 2 s 2 and some

f 2 ∈ F (s 1 ) \ F (s 2 ) such that |f 2 | > |f 1 |.
Iterating this procedure, we obtain the announced anti-chain (f n ) n , which completes the proof of the lemma. Lemma 2.2. Let s be a uniformly recurrent right infinite word such that the language F (s) is rational. Then s is periodic.

Proof. This could be deduced from Theorem 6.2 below, but we give a direct proof. Since the language F (s) is rational, infinite, and factorial, there is some word u ∈ A + such that every finite power of u is a factor of s.

Let s = u 1 u 2 • • • u n • • • be the factorization of s in factors of length |u|. Since s is uniformly recurrent, for each n, u 1 • • • u n is
a factor of some power of u. Hence, since all u i have the same length as |u|, it follows that they are all equal (to some conjugate of u). Since this is true for all n, it follows that s is periodic.

Combining the two preceding lemmas, we obtain the following result. Proposition 2.3. Let s be a right infinite word. Then s is ultimately periodic if and only if the language F (s) is rational and it contains no infinite J-anti-chains.

Proof. Suppose first that s is ultimately periodic, say s = uv ∞ , where v ∞ stands for the right infinite periodic word with period v. Then F (s) is the language of factors of uv * and, therefore, it is a rational language. More precisely, the finite factors of s are the factors of u together with the words of the form xv k y, where x is a suffix of either u or v, k ≥ 0, and y is a prefix of v, and it is immediate to deduce that there are no infinite J-anti-chains of such words.

Conversely, if there are no infinite anti-chains of finite factors of s then, by Lemma 2.1, s has a factorization of the form s = ut, where u is a finite word and t is a uniformly recurrent infinite word. We claim that the language F (t) is rational which, by Lemma 2.2, entails that t is periodic and, therefore, that s is ultimately periodic.

To prove the claim, note that, since t is uniformly recurrent, the factors of t are precisely the factors v of s such that, for every n, there exists x ∈ X + of length n with xv ∈ F (s). By hypothesis, F (s) is a rational language, whence there is a finite deterministic automaton A recognizing the reverse L of this language, consisting of the reversed words. In this context, we consider automata as recognizing devices only for nonempty words. Since L is factorial, all states from which a terminal state is accessible are also terminal, that is, either there is only one state or we may as well assume that the only state which is not terminal is a sink. If we change to nonterminal those states from which no strongly connected component of terminal states is accessible, we obtain an automaton A ′ that recognizes the set of all words v ∈ L which can be extended arbitrarily to the right to other words from L. Hence F (t) is rational.

Going back to the profinite world, we recall that implicit operations over V can be naturally interpreted in pro-V semigroups as follows: given w ∈ Ω X V and a profinite semigroup S, the interpreted operation w S : S X → S associates to each function ϕ : X → S the element φ(w) ∈ S, where φ is the unique extension of ϕ to a continuous homomorphism Ω X V → S.

Given u, v ∈ Ω X V, we call the formal equality u = v a pseudoidentity (over V). For a pro-V semigroup S, we then say that S satisfies the pseudoidentity u = v and write S |= u = v if u S = v S . For a set Σ of pseudoidentities, we let Σ denote the class of all finite semigroups that satisfy all pseudoidentities from Σ. It is easy to check that Σ is a pseudovariety and Reiterman [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF] showed that every pseudovariety is of this form.

For a set σ of implicit operations, one may in particular use natural interpretation of the elements of σ to define the σ-subalgebra of Ω X V generated by X, which is denoted Ω σ X V. Formal terms over a finite alphabet X in the signature σ are called σ-terms. Since our multiplication is always associative, without further reference, we identify terms that only differ by the order in which multiplications are to be carried out.

Following [START_REF] Almeida | On the decidability of iterated semidirect products and applications to complexity[END_REF], we denote by κ the set consisting of the operations of multiplication and pseudoinversion x → x ω-1 , where, for an element s of a finite semigroup, s ω-1 stands for the inverse of ss ω in the maximal subgroup of the subsemigroup generated by s, whose idempotent is denoted s ω . In general, for a profinite semigroup S, one may define s ω+k = lim n s n!+k for k ∈ Z and s m ω = lim n s m n! for m ≥ 1 [START_REF]Profinite semigroups and applications, Structural Theory of Automata, Semigroups, and Universal Algebra[END_REF]. For k, ℓ ∈ Z with ℓ > 0, we have s ω+(k+ℓ) = s ω+k s ℓ .

Note that, for pseudovarieties contained in A, since the subgroup in question is trivial, the operations x ω-1 and x ω coincide. Since this paper is concerned mainly with the pseudovariety A, our κ-terms will use the operation x ω rather than x ω-1 and such terms are also, abusively, called ω-terms. More formally, an ω-term on a set X is an element of the unary semigroup U X freely generated by X.

We will sometimes adopt the simplified notation of McCammond [START_REF]Normal forms for free aperiodic semigroups[END_REF] for ω-terms under which the curved parenthesis (α) stands for α ω . This allows us to refer to ω-terms as words over an extended alphabet X ∪ {(, )}, which is particularly useful for McCammond's solution of the word problem for Ω κ X A and is also instrumental in the formulation of our main result. Note that the words in the extended alphabet that represent ω-terms are precisely those for which the opening and closing parentheses match, that is, by removing all other letters we obtain a Dyck word. In fact, it is easy to check that the ωsubsemigroup of the free semigroup (X ∪ {(, )}) + generated by X, where the ω-power is interpreted as the operation w → (w), is freely generated by X as a unary semigroup. Thus, we identify U X with the set of well-parenthesized words over the alphabet X.

In particular, there is a natural homomorphism of ω-semigroups ǫ : U X → Ω κ X A that fixes each x ∈ X when we view X as a subset of U X and Ω κ X A in the natural way. To avoid ambiguities in the meaning of the parentheses, we will write ǫ[w] for the image of w ∈ U X under ǫ. The elements of Ω κ X A will sometimes be called ω-words. Whenever we say that an ω-term over the alphabet X is a factor of another, we mean that that is the case in the free semigroup (X ∪ {(, )}) + .

The ω-word problem for A (over X), consists in deciding when two elements of U X have the same image under ǫ. To solve this problem, McCammond described a normal form for ω-terms over A that we will use extensively in this paper. For its description, a total order is fixed on the underlying alphabet X; on the extended alphabet, we set ( < x < ) for every x ∈ X. A primitive word is a word that cannot be written in the form u n with n > 1. Two words u and v are said to be conjugate if there are factorizations of the form u = xy and v = yx, with the words x and y possibly empty. A Lyndon word is a primitive word that is lexicographically minimum in its conjugacy class. The rank of a word in the extended alphabet is the maximum number of nested parentheses in it.

A rank 0 normal form ω-term is simply a finite word. Assuming that rank i normal form terms have been defined, a rank i + 1 normal form term is a term of the form α 0 (β

1 )α 1 (β 2 ) • • • α n-1 (β n )α n ,
where the α j and β k are ω-terms such that (a) each β k is a Lyndon word; (b) no intermediate α j is a prefix of a power of β j or a suffix of a power of β j+1 ; (c) replacing each subterm (β k ) by β k β k , we obtain a rank i normal form term; (d) at least one of the properties (b) and (c) is lost by canceling from α j a prefix β j (in case j > 0) or a suffix β j+1 (in case j < n).

McCammond also described a method to transform an arbitrary ω-term into one in normal form with the same image under ǫ. Moreover, he proved that if two ω-terms in normal form have the same image under ǫ, then they are equal. Since we will need to refer to McCammond's procedure to transform an arbitrary ω-term into one in normal form, we proceed to describe its steps. The procedure consists in applying elementary changes that obviously retain the value of the ω-term under ǫ. The types of changes are given by the following rules:

1. ((α)) = (α) 2. (α k ) = (α) 3. (α)(α) = (α) 4. (α)α = (α), α(α) = (α) 5. (αβ)α = α(βα)
If a subterm given by the left side of a rule of type 1-4 is replaced in a term by the right side of the rule, then we say there is a contraction of that type. If the replacement is done in the opposite direction than we say that there is an expansion of that type. For the rules of type 4, we may add an index L or R to indicate on which side of the ω-power the base was added or deleted.

The steps in McCammond's normal form algorithm may now be described as follows.

(1) In case the given term is a word, do nothing and stop.

(2) Apply all possible contractions of type 1.

(3) Apply all possible contractions of type 2. The resulting term may be written as a product of the form

(1) α 0 (β 1 )α 1 (β 2 ) • • • α n-1 (β n )α n
where each subterm α j and β k has strictly smaller rank. (4) Apply recursively the algorithm to each subterm α j and β k , to put it in normal form.

(5) If some β k is an idempotent (that is, it has the same normal form as its square), then remove the parentheses around it in the expression (1), join it with the adjacent α subterms and apply again the previous item to the new α subterms. ( 6) By means of an expansion of type 4 L and an expansion of type 4 R and a shift of parentheses by application of the rule 5, write each remaining subterm of the form (β k ) in the form ε 1 (γ)ε 2 where: (i) γ is a Lyndon word in the extended alphabet;

(ii) ε 1 γε 2 is the normal form of β 3 k ; (iii) ε 1 ε 2 is the normal form of β 2 k ; (iv) ε 2 ε 1 has the same normal form as γ 2 ; (v) the rank of each of ε 1 and ε 2 is rank[β k ]. [START_REF] Almeida | Complete reducibility of systems of equations with respect to R, Portugal[END_REF] Using contractions of types 3 and 4, replace maximum rank subterms of the form (γ)γ ℓ (γ) by (γ).

The remaining maximum rank subterms of the form (γ)ε(δ), where rank

[γ] = rank[δ] ≥ rank[ε],
are called crucial portions, whereas the prefix ε(δ) and the suffix (γ)ε, with similar assumptions on γ, δ, ε, are called respectively the initial portion and the final portion. An initial portion ε(δ) with ε = 1 (the empty word) is said to be trivial and similarly for final portions. (8) Standardize each crucial portion (γ)ε(δ) by using expansions of type 4 R on (γ) and of type 4 L on (δ) until the intermediate term ε ′ is no longer a prefix of a power of γ nor a suffix of a power of δ, as a word in the extended alphabet, and apply contractions of type 4 R on the left and of type 4 L on the right while that property holds. (9) Reduce the initial portion ε(δ) by dropping the largest suffix of ε that is a power of δ as a word in the extended alphabet; proceed dually with the final portion. It is not very hard to check that the above normal form algorithm does indeed transform an arbitrary ω-term into one in normal form. Since all the rewriting rules are based on identities of ω-semigroups that are valid in A, every ω-term over X has the same image under ǫ as its normal form. To prove that distinct ω-terms in normal form have different images in Ω κ X A, McCammond used his solution of the word problem for certain free Burnside semigroups [START_REF] Mccammond | The solution to the word problem for the relatively free semigroups satisfying t a = t a+b with a ≥ 6[END_REF]. We have obtained a direct combinatorial proof of the same result which leads to many other applications, including the following two theorems, the first of which plays an important role in this paper and which does not apparently follow easily from McCammond's results. The paper containing our proof is under preparation and will appear elsewhere.

Theorem 2.4. If v ∈ Ω κ X A and u ∈ Ω X A is a factor of v, then u ∈ Ω κ X A.
It is well know that the Green relations J and D coincide in every compact semigroup, and so in particular they coincide in every finite semigroup. In fact, this property holds more generally in so-called stable semigroups (cf. [START_REF] Lallement | Semigroups and combinatorial applications[END_REF]), that is in semigroups S such that, s ≥ R t (respectively s ≥ L t) and s J t implies s R t (respectively s L t).

Corollary 2.5. The semigroup Ω κ X A is stable. Hence the Green relations J and D of Ω κ X A coincide, while H is the equality relation.

Proof. If the relations s ≥ R t J s hold in the subsemigroup Ω κ X A then they also hold in Ω X A. Since Ω X A, like any compact semigroup, is stable, we deduce that there exists u ∈ (Ω X A) 1 such that su = t. If u = 1, then s = t. Otherwise, u ∈ Ω κ X A by Theorem 2.4, and so s R t holds in Ω κ X A in any case. It was already pointed out that stability implies J = D. That H is trivial in Ω κ X A is actually true for every subsemigroup of Ω X A since, if two elements are H-equivalent in a subsemigroup of Ω X A, then they are also H-equivalent in Ω X A. It is well known that H is trivial in Ω X A (cf. [1, Corollary 5.6.2]): if s H t and s = t, then there exists a continuous homomorphism ϕ : Ω X A → S onto a finite aperiodic semigroup S such that ϕ(s) = ϕ(t). But, since the Green relations are preserved by applying homomorphisms, ϕ(s) H ϕ(t). Since the Green relation H is trivial in finite aperiodic semigroups, we reach a contradiction. Hence H is trivial in Ω κ X A. Following [START_REF] Mcknight | Equidivisible semigroups[END_REF][START_REF] Lallement | Semigroups and combinatorial applications[END_REF], we say that a semigroup S is equidivisible if, for any two factorizations xy = zt of the same element of S, there exists u ∈ S 1 such that, either x = zu and uy = t, or xu = z and y = ut. It follows that any two factorizations of the same element of S may be refined by further factorizating some of the factors so as to reach the same factorization.

We also say that a pseudovariety V is equidivisible if Ω X V is equidivisible for every finite set X. The following result, which can be easily derived using results from [6, Section 2] is very useful. Details will be given in a forthcoming paper where equidivisibilty is extensively explored.

Theorem 2.6. The pseudovariety A is equidivisible.

Set of all finite words open

Let N = x ω = 0 be the pseudovariety of all finite nilpotent semigroups. The following result completes well-known properties of N.

Theorem 3.1. The following conditions are equivalent for a pseudovariety V:

(a) V ⊇ N; (b) if V satisfies a pseudoidentity of the form u = v, where u is a finite word, then u = v; (c) if V satisfies a two-letter pseudoidentity of the form u = v, where u is a finite word, then u = v; (d

) for every finite alphabet A, the natural homomorphism ι

A : A + → Ω A V is

injective and its image is an open discrete subset; (e) for the two-letter alphabet A = {a, b}, the natural homomorphism ι

A : A + → Ω A V is injective and the subset {x n : n ≥ 1} is open in Ω {x} V.
Proof. (a)⇒(b) This is well-known. Simply observe that, if the word u over the finite alphabet A has length n, then the Rees quotient S of A + by the ideal A n A + is a nilpotent semigroup which satisfies no non-trivial pseudoidentity of the form u = v. (b)⇒(a) This is also well-known. Indeed, by Reiterman's Theorem [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF], it suffices to show that N satisfies every non-trivial pseudoidentity u = v which holds in V. By (b), for such a pseudoidentity, u and v are both infinite pseudowords, whence they have factors of the form w ω (cf. [1, Corollary 5.6.2]). Hence, N satisfies the pseudoidentities u = 0 = v.

(b)⇒(c) and (d)⇒(e) are obvious. (b)⇒(d) That V satisfies no non-trivial identities u = v with u, v ∈ A + is clearly equivalent to the statement that ι A is injective. Suppose that Im ι A is not an open discrete subset. Then there is an injective sequence (w n ) n which converges to a word u in Ω A V. Since the sequence is injective, if it has infinitely many terms which are finite words (meaning that they belong to Im ι A ), then it contains arbitrarily long words, which implies that the limit u is of the form u = xy ω z for some x, y, z ∈ Ω A V. Hence V satisfies the non-trivial pseudoidentity u = xy ω z, in contradiction with (b). Note that in this argument, we worked with a fixed finite alphabet. (c)⇒(e) follows from the particular case of a two-letter alphabet.

(e)⇒(b) Let A = {a, b} be a two-letter alphabet and let C = {c 1 , . . . , c n } be an arbitrary finite alphabet with n letters. Then the homomorphism ϕ :

C + → A + defined by ϕ(c i ) = b i a is injective. Let φ : Ω C V → Ω A V be the continuous homomorphism defined by φ(ι C (c i )) = ι A (b i a)
, that is so that the following diagram commutes:

C + ιC / / ϕ Ω C V φ A + ιA / / Ω A V Since ι A • ϕ is injective, it follows that ι C is also injective, that is V satisfies no non-trivial identity on the alphabet C.
Note that, if V satisfies some non-trivial pseudoidentity u = v, with u ∈ C + , then V satisfies some pseudoidentity of the form x k = x ω+k and hence lim n x (2•3 ••• pn) ω +k = x k , where p n denotes the nth prime. The assumption that x + is an open subset of Ω {x} V entails that V satisfies x (2•3 ••• pn) ω +k = x mn , with m n finite, for all sufficiently large n. If ℓ ∈ {1, . . . , n}, n is sufficiently large, and r is so large that p r ℓ does not divide m nk, then the pseudoidentity x (2•3 ••• pn) ω +k = x mn fails in the cyclic group Z/p r ℓ Z, whence this group does not belong to V. It follows that, for every prime p, there is the largest exponent r = r p ≥ 0 such that Z/p r Z ∈ V.

Next, for each n ≥ 1, let w n denote an accumulation point of the sequence x (pnpn+1•••pm) ω m . We claim lim n w n = x ω+1 in Ω {x} S, from which it follows that lim n w n = x k+1 in Ω {x} V. Before establishing the claim, note that the assumption that x + is open now implies that, for all sufficiently large n, V |= w n = x ℓn for some finite exponent ℓ n ≥ 1. It follows that, for some n, ℓ n is divisible by all p rs s with s ≥ n, whence r s = 0 for all s greater than or equal to some n. We deduce that

V |= x k = x k+ i<n p r i i , which contradicts the assumption that ι A is injective.
It remains to establish the claim that lim n w n = x ω+1 , which means that every monogenic finite semigroup S satisfies the pseudoidentity w n = x ω+1 for all sufficiently large n. This amounts to an elementary exercise which we solve for the sake of completeness. Since both w n and x ω+1 are infinite, the substitution of x by x ω+1 leaves the pseudoidentity w n = x ω+1 unchanged. Hence it suffices to consider the case where S is a cyclic group, say of order r. Then, for every k relatively prime to r, the fact that k is invertible in the multiplicative monoid of Z/rZ means that S |= x k ω = x. Since, for all sufficiently large n and all m ≥ n, p n • • • p m is relatively prime to r, this proves the claim.

Just by itself, the property that the set of all finite words is open in Ω X V has some interesting consequences.

Proposition 3.2. For every pseudovariety V such that the set of all finite words is open in

Ω X V, every infinite pseudoword in Ω X V is J-below some pseudoword that is J-maximal among all infinite pseudowords.
Proof. By Zorn's Lemma, it suffices to show that every J-chain C of infinite pseudowords has an upper bound in the set of infinite pseudowords. We consider C as a net, indexed by itself. Since the space Ω X V is compact and the set of finite words is open, the subspace of infinite pseudowords is compact as well, whence there is some convergent subnet (d i ) i∈I , given by d i = ϕ(i), where ϕ : I → C is an order-preserving mapping which is cofinal in the sense that, for every c ∈ C, there exists i ∈ I with c ≤ J ϕ(i). Note that cofinality implies that C and {d i : i ∈ I} have the same upper bounds. Hence, it suffices to show that the limit d = lim d i is such an upper bound. Since the subnet (d j ) j∈I, j≥i also converges to d and it consists of elements that are J-above d i , it follows that indeed d ≥ J d i .

Let now w ∈ Ω X V be an arbitrary pseudoword. We denote by F (w) the set of all u ∈ X + such that ι V (u) is a factor of w. We say that w ∈ Ω X V is uniformly recurrent if the language F (w) is uniformly recurrent. By [4, Theorem 2.6], if V contains LSl then a pseudoword w ∈ Ω X V is uniformly recurrent if and only if w is J-maximal among all infinite pseudowords. We will use this fact from hereon without further reference. Proposition 3.3. Let V be a pseudovariety containing LSl and let v, w ∈ Ω X V be such that F (v) ⊆ F (w), w is uniformly recurrent, and v / ∈ X + . Then v is J-equivalent to w and, in particular, it is uniformly recurrent.

Proof. Since LSl contains N, by Theorem 3.1 and Proposition 3.2, there exists some uniformly recurrent pseudoword y ∈ Ω X V such that y ≥ J v. Hence F (y) ⊆ F (v) ⊆ F (w). By [4, Corollary 2.10], it follows that y J w, whence F (y) = F (w). Hence F (v) = F (w), so that v is also uniformly recurrent. Applying [4, Corollary 2.10] again, we now conclude that v J w.

The rank

Given an ω-word w ∈ Ω κ X A, there are in general many ω-terms that represent it. But, by Mc-Cammond's results, there is only one such ω-term in normal form, which we call the normal form representation or simply the normal form of w.

The rank of w ∈ Ω κ X A is i if the normal form of w is a rank i normal form term or, equivalently, an ωterm of rank i. It is denoted rank [w]. In this section, we introduce structural, rather than combinatorial, notions of rank for elements of Ω κ X A and, more generally, for Ω X A. Given w ∈ Ω κ X A, define r(w) to be the supremum of the cardinalities of strict J-chains of idempotents of Ω κ X A which lie J-above w. Similarly, for w ∈ Ω X A, define r(w) to be the supremum of the cardinalities of strict J-chains of idempotents of Ω X A which lie J-above w. Note that the definition of r and r immediately implies that the value of any of these functions at a product is at least its value at each of the factors. Proof. According to the normal form algorithm, the only steps that change the depth of nested parentheses are the application of a rule of type 1 ((δ)) → (δ) or of the step that replaces (γ) by γ in case γ is idempotent. Now, such changes on the concatenation of two expressions which represent ω-terms (that is, which are properly parenthesized), can only take place entirely within one of the factors, and this is not possible since α and β are in normal form. Lemma 4.2. Let (α) and (β) be ω-terms in normal form. We further assume that |γδ| is minimal for this property. By McCammond's results, the normal form of γ(α)δ is (β). Again, the only way that the depth of nested parentheses might go down in the computation of the normal form for γ(α)δ would be within one of the three factors, which is impossible since they are assumed to be in normal form. Hence rank[γ] and rank[δ] are at most rank[(α)]. If, next, there are any contractions of type (ε)(ε) → (ε), then they take place at the junction of either γ and (α) or (α) and δ, and so there is no need for such contractions by the minimality assumption on |γδ|. The remaining phases of the normal form algorithm concern therefore the standardization of subterms of the form (ε) of highest rank and of the crucial portions. The first of these steps produces no changes since all subterms of the form (ε) of highest rank are already in normal form. For the second step, since we know that the end result is (β), the minimality assumption on |γδ| implies that γ = δ = 1, which contradicts the hypothesis that ǫ[(α)] lies strictly J-above ǫ[(β)] in Ω κ X A.

(a) If (α) is a subterm of β then ǫ[(α)] lies strictly J-above ǫ[(β)] in Ω κ X A. (b) If ǫ[(α)] lies strictly J-above ǫ[(β)] in Ω κ X A then rank[α] < rank[β]. Proof. (a) Since β is in normal form, the hypothesis that (α) is a subterm of β implies that rank[(α)] ≤ rank[β] and so that rank[(α)] < rank[(β)]. Moreover, the same hypothesis yields that ǫ[(α)] lies J- above ǫ[(β)] in Ω κ X A. On the other hand, if ǫ[(β)] lies J-above ǫ[(α)] in Ω κ X A
Lemma 4.3. Let w be an idempotent in Ω κ X A. Then there exists an ω-term (α), in normal form, such that w J ǫ[(α)].

Proof. Let β be the normal form of w. Then β is the normal form of ββ and so β is an idempotent in rank[β] in the sense of [START_REF]Normal forms for free aperiodic semigroups[END_REF]Definition 5.9]. By [24, Lemma 5.10], it follows that the normal form expression for β is of the form ε 0 (α)ε 1 and that the expression (α)ε

1 ε 0 (α) is rank[α]-equivalent to (α). Hence w = ǫ[β] J ǫ[(α)].
. . , (β n ) such that each (β i ) is a subterm of β i+1 (i < n) and of α (i ≤ n). By Lemma 4.2(a), {ǫ[(β 1 )], . . . , ǫ[(β n )]} constitutes a strict J-chain of idempotents J-above w. Hence r(w) ≥ n = rank[α].
Let e 1 , . . . , e m be a strictly descending J-chain of idempotents of Ω κ X A which lie J-above w. By Lemma 4.3, we may assume that each e i has a normal form of the form (β i ). By Lemma 4.2(b), since Since, by Theorem 2.4, the factors of an element of Ω κ X A are the same in Ω κ X A and in Ω X A, we also have the following result. Proposition 4.5. For every element w ∈ Ω κ X A, we have r(w) = r(w). Propositions 4.4 and 4.5 imply that, for an ω-term in normal form α, rank[α] = r(ǫ[α]) = r(ǫ[α]). For an arbitrary element w of Ω X A, we also call r(w) the rank of w.

e i = ǫ[(β i )] is strictly J-above e i+1 = ǫ[(β i+1 )], we have rank[(β i )] < rank[(β i+1 )] (i < m).

Properties of the Green relations on Ω κ

X A In this section, we examine some properties of the Green relations on the semigroup Ω κ X A.

Lemma 5.1. In every regular J-class of Ω κ X A there is a unique element which, in normal form, is of the form (α).

Proof. Let β = γ 0 (δ 1 )γ 1 • • • (δ r )γ r be an ω-term in normal form and suppose that u = ǫ[β] is a regular element of Ω κ X A. Then there exists w ∈ Ω κ X A such that uwu = u and wuw = w. Let u i = ǫ[γ i ] and v j = ǫ[δ j ]. By the normal form algorithm, r = 1 and v ω 1 u 1 • w • u 0 v ω 1 = v ω 1 , so that v ω 1 = v ω 1 u 1 • wuw • u 0 v ω 1 . Hence u J v ω 1 . Suppose that v ω is another ω-term in normal form in the J-class of u. Then rank[v] = rank[v 1 ] and there exist x, y ∈ Ω κ X A such that v ω 1 = xv ω y. Hence the normal form of v ω 1 xv ω y is v ω 1 .
This means that the application of the normal form algorithm must eliminate the crucial portion v ω 1 xv ω , since v ω 1 has no crucial portions. The only step where this can happen is Step [START_REF] Almeida | Complete reducibility of systems of equations with respect to R, Portugal[END_REF], which implies that v 1 = v. Proposition 5.2. In every regular R-class of Ω κ X A there is a unique element which, in normal form, is an initial portion.

Proof. Let u be a regular element of Ω κ X A. By Lemma 5.1, there is in the J-class of u a unique element e which, in normal form, is of the form (α). By Corollary 2.5, there exists a unique element of the form xe such that u R xe L e. Let y ∈ Ω κ X A be such that e = yxe and let β and γ be the normal forms of x and y, respectively. Then the normal form algorithm reduces γβ(α) to (α), which implies that the normal form of β(α) is an initial portion.

Suppose next that there is another element in the R-class of u whose normal form is an initial portion δ(ε). Let (γ)δ and λ(µ) be, respectively, the final and initial portions of the normal forms of x and y. Then the normal form of the ω-term (γ)δ(β)λ(µ) is a factor of α. Let ε be the normal form of δ(β)λ. There are two cases to consider.

First, Step [START_REF] Almeida | Complete reducibility of systems of equations with respect to R, Portugal[END_REF] of the normal form algorithm may apply to the crucial portion (γ)δ(β)λ(µ), in which case γ = µ and ε = γ n is a finite power of γ, which in turn is a factor of α. Since rank

[γ n ] < rank[α] and ǫ[ε] = ǫ[δ(β)λ],
by the induction hypothesis we obtain that (β) is a factor of γ n , and therefore also of α.

Second, Step [START_REF] Almeida | Complete reducibility of systems of equations with respect to R, Portugal[END_REF] does not apply to the crucial portion (γ)ε(µ), and applying the standardization procedure of Step ( 8), (γ)ε(µ) reduces to its normal form (γ)ε ′ (µ) by expansions and contractions of the forms (γ) → (γ)γ, (µ) → µ(µ), (γ)γ → (γ), and µ(µ) → (µ). It follows that there are some finite exponents k, ℓ such that ε is a factor of the ω-term γ k ε ′ µ ℓ , which has strictly smaller rank than α. Hence e is a factor of ǫ[γ k ε ′ µ ℓ ] in Ω κ X A. By the induction hypothesis, it follows that (β) is a factor of γ k ε ′ µ ℓ and, therefore, also of at least one of the factors γ, ε ′ and µ, whence of α.

Combining Lemmas 5.1 and 5.3, we obtain the following result.

Theorem 5.4. There are only finitely many regular J-classes ≥ J a given w ∈ Ω κ X A. Proof. By Lemma 5.1, all regular J-classes ≥ J a given ω-word w contain elements whose normal forms are of the form (α). By Lemma 5.3, all such elements are factors of the normal form of w. Hence there are only finitely many such J-classes.

Note that a regular J-class of Ω κ X A may be infinite. For instance, all the elements a n b(a ω b) ω , with n ≥ 1 lie in the J-class of the idempotent (a ω b) ω while they are all distinct by McCammond's Normal Form Theorem, since their given descriptions are already in normal form.

The following result is both a consequence of Theorem 2.6 and a special case of a much more general result [7, Lemma 4.7].

Proposition 5.5. Let w ∈ Ω X A and suppose that u and v are two prefixes of w. Then one of u and v is a prefix of the other.

In the terminology of [START_REF] Birget | Iteration of expansions-unambiguous semigroups[END_REF], Proposition 5.5 is expressed by stating that the semigroup Ω X A has unambiguous R-order. Dually, Ω X A also has unambiguous L-order. Taking into account Theorem 2.4, we immediately deduce that the semigroup Ω κ X A also has unambiguous R-order and L-order. More precisely, we have the following result.

Corollary 5.6. The set of prefixes of a given w ∈ Ω κ X A is wqo under the prefix order. Proof. By Proposition 5.5, we already know that the prefixes of w form a chain. Let [x n ] n be a sequence of prefixes of w and suppose that each x n+1 is a strict prefix of the preceding x n . In particular, the ranks of the x n constitute a non-increasing sequence of integers. Therefore, without loss of generality, we may assume that all x n have the same rank. By the normal form algorithm, we may assume that all x n have a common prefix u, where w = uv, and are of the form x n = uy n where the y n have smaller rank and are prefixes of v. An induction argument then shows that there exist indices m < n such that y m is a prefix of y n . Hence x m is a prefix of x n , which contradicts the hypothesis. This completes the proof of the corollary.

The prefix order on factors

The following proposition shows that the set of factors of a given w ∈ Ω X A may not be wqo under the prefix order, even under the restriction r(w) < ∞. It concerns an example which is taken from [1, Chapter 12] and satisfies r(w) = 2. In rank 1, we show that the existence of an infinite ascending R-chain converging to an idempotent is equivalent to periodicity of the idempotent.

Let (n 1,k ) k be a strictly increasing sequence of integers such that the sequence (b

n 1,k a • • • b 2 aba) k converges in Ω X A and call x 1 its limit. Assuming (n i,k ) k is a subsequence of (n i-1,k ) k for i = 2, . . . , ℓ such that the sequence (b n i,k a • • • b i+1 ab i a) k converges to x i in Ω X A for i = 1, . . . , ℓ, then there also exists a subsequence (n ℓ+1,k ) k of (n ℓ,k ) k such that (b n ℓ+1,k a • • • b ℓ+2 ab ℓ+1 a) k converges in Ω X A
and we denote by x ℓ+1 its limit. This recursive definition yields a sequence (x n ) n . The following proposition states some of its properties.

n i,k a • • • b i+1 ab i a) k on the right by b i-1 a, we obtain a subsequence of (b n i-1,k a • • • b i ab i-1 a) k .
Hence, taking limits, we conclude that x i-1 = x i b i-1 a. This proves (a) since ab i-1 a is a factor of x i-1 but not a factor of x i .

Given a finite aperiodic semigroup S and a continuous homomorphism ϕ : Ω X A → S, let N be such that S |= x ω = x N . Then, for n ≥ N and m ≥ n + N , we have

ϕ(b m a • • • b n+1 ab n a) = ϕ (b ω a) ω , which proves (b).
Since (d) is an immediate consequence of (c), it remains to prove (c). For this purpose, consider an idempotent e J-above x n . We claim that the finite factors of e are factors of b ω ab ω . A first remark in this direction is that a 2 is not a factor of x n , and therefore it cannot be a factor of e. Moreover, the set of finite factors of e is prolongable in both directions, meaning that every finite factor is both a proper prefix and a proper suffix of another finite factor. But the only finite factors of x n that can be prolonged indefinitely on the right are the finite factors of b ω ab ω : any other finite factor has at least a factor of the form ab k a, which can only be found once as a factor of x n , within fixed finite distance from its right end. Hence all finite factors of e are factors of b ω ab ω , which proves the claim.

If e does not contain the factor a, then it must be b ω . Otherwise, by the claim, every finite factor of e is a factor of b ω ab ω , so that e has no finite factor in which the letter a occurs more than once. We claim that e is J-equivalent to (b ω a) ω in Ω X A. Let (u m ) m be a sequence of words converging to e and let S be a finite aperiodic semigroup. Let N be such that S |= x ω = x N . Then, since lim m u 2 m = e, there exists m 0 such that, for all m ≥ m 0 , none of the words

ab k a is a factor of u 2 m for k = 0, 1, . . . , N -1. Hence u m is of the form b α ab β1 ab β2 • • • ab βp ab γ , for some α, β i , γ with β i ≥ N and α + γ ≥ N . It follows that S |= u m = b α (ab N ) p ab γ .
Hence, for all m sufficiently large,

S |= e = e ω = u ω m = b α (ab ω ) ω ab γ . Since b α (ab ω ) ω ab γ J (b ω a) ω , this proves (c).
We now turn to the rank 1 case. We say that w ∈ Ω X V is periodic if there is some finite x ∈ Ω X V such that x > J w ≥ J x ω . In this case, we also say that x is a period of w. We define the set of factors of a pseudoword w as

F(w) = {v ∈ Ω X V : v ≥ J w}.
Theorem 6.2. Let V be any pseudovariety containing LSl and let w ∈ Ω X V be uniformly recurrent.

Then the following conditions are equivalent: (a) w is periodic;

(b) the language F (w) is rational; (c) the set F(w) is open;

(d) w is not the limit of a sequence of words w n , none of which is a factor of w;

(e) there is no infinite strictly ascending J-chain in Ω X V converging to w; (f ) there is no infinite strictly ascending J-chain (w n ) n in Ω X V converging to w such that, for all n, all idempotents J-above w n are J-equivalent to w; (g) there is no infinite strictly ascending R-chain in Ω X V converging to w; (h) there is no infinite strictly ascending R-chain (w n ) n in Ω X V converging to w such that, for all n, all idempotents J-above w n are J-equivalent to w; (i) there is no sequence (u n ) n of words such that each u n is not a factor of w, its factors of length n are factors of w, and the suffix of length n of u n is also a suffix of w. (j) there is no sequence (u n ) n of words such that each u n is not a factor of w and its factors of length n are factors of w.

Proof. Since the set of factors of an element of a compact semigroup is always closed, the equivalence of conditions (a), (b), and (c) is the statement of [4, Theorem 2.11] for V = S and one can check that the results of [4, Section 2], with the same proofs, apply to any pseudovariety V containing LSl (see also [START_REF] Almeida | Infinite-vertex free profinite semigroupoids and symbolic dynamics[END_REF]Section 6] for an alternative approach). We proceed to establish the equivalence with the remaining conditions. Note that, if the set F(w) is open then, whenever w n → w, all terms in the sequence with sufficiently large index are factors of w. This trivially shows that (c)⇒(d) and (c)⇒(e). The implications (e)⇒(f )⇒(h), (e)⇒(g)⇒(h), and (i)⇒(j) are also straightforward.

(d)⇒(c) Suppose that (w n ) n is a sequence converging to w in which no term belongs to F(w). By (d), we may assume that all pseudowords w n are infinite. If every finite factor of w n is a factor of w then, since w is uniformly recurrent, w n has exactly the same finite factors as w and, by [4, Corollary 2.8], for uniformly recurrent pseudowords this condition implies that w n and w are J-equivalent and, therefore, w n ∈ F(w), in contradiction with the initial assumption. Hence, for each n, w n has some finite factor u n / ∈ F(w). By compactness, we may assume that the sequence u n converges to a limit u; continuity of multiplication yields u ∈ F(w). Let x, y ∈ Ω X V be such that w = xuy and let (x n ) n and (y n ) n be sequences of words converging respectively to x and y. Since u n is not a factor of w, neither is x n u n y n . By construction and continuity of multiplication again, we have x n u n y n → w, which contradicts (d). Hence there is no such sequence of non-factors of w converging to w which is equivalent to (c).

(h)⇒(i) Suppose that (u n ) n is a sequence satisfying the conditions of (i). We show how to construct a sequence satisfying the conditions of (h). Denote by p n and s n respectively the prefix and the suffix of u n of length n. Since w is uniformly recurrent and s n+1 and p n are factors of w, for every n there exists a word v n such that s n+1 v n p n is a factor of w, and we may assume that

|v n | → ∞. Consider the sequence S m = (v n u n • • • v m+1 u m+1 v m u m ) n≥m .
There is a strictly increasing sequence of indices (n 1,k ) k whose corresponding subsequence of S 1 converges, and we call x 1 its limit. There is in turn a subsequence (n 2,k ) k of (n 1,k ) k such that the subsequence of S 2 which it determines converges, and we call x 2 its limit. And so on. Recursively, we obtain a sequence (x n ) n such that, for every n ≥ 1, [START_REF]A syntactical proof of locality of DA[END_REF] x n = x n+1 v n u n , so that, in particular, x n+1 ≥ R x n . Let x be the limit of a subsequence (x n k ) k for which we may assume that the sequences (s n k ) k and (v n k ) k both converge, to the respective limits s and v. Since s n is a suffix of both x n and w, s is a suffix of x and w.

Since v n is a prefix of v n u n • • • v m+1 u m+1 v m u m , it follows that v is a prefix of x m , for all m, hence v is a prefix of x.
Since Ω X V is stable, s and v are infinite pseudowords, and w is a J-maximal infinite pseudoword, it follows that s L w, whence w ≥ J x.

Let u be a finite factor of x. Then u is a factor of x n for all sufficiently large n, hence u is a factor of u n+1 v n u n for arbitrarily large n. It follows that there exists n ≥ |u| such that u is a factor of u n+1 v n u n . Hence, u is a factor of at least one of the words u n+1 , s n+1 v n p n , or u n . By hypothesis and the choice of v n , this implies that u is a factor of w. Since w ≥ J x, we conclude that x and w have the same finite factors, so that x is also uniformly recurrent. By [4, Corollary 2.10], it follows that x J w. Since s is a common infinite suffix, we must have x L w. Let t ∈ Ω X V be an infinite pseudoword such that w = tx and note that w ≥ R tx n for all n.

Since u n is a factor of tx n but not of w, by stability of Ω X V it follows that w > R tx n for every n, whence some subsequence of (tx n k ) k is a strictly ascending R-chain converging to w.

To complete the proof of (h)⇒(i), it suffices to show that every idempotent e that lies J-above tx 1 is J-equivalent to w. Let e be such an idempotent. Then the set of finite factors of e is a prolongable language. We claim that every finite factor u of e is a factor of w. Let (t n ) n be a sequence of finite words converging to t. Since u is a factor tx

1 = lim t k v n 1,k u n 1,k • • • v 1 u 1 and |v n | → ∞,
we conclude that, for all sufficiently large k, at least one of the following conditions holds:

(1) u is a factor of t k v n 1,k ; (2) u is a factor of v n 1,k u n 1,k • • • v 1 u 1 .
Suppose first that there are infinitely many values of k for which condition (1) holds. Then u is also a factor of the limit tv. Since v R x and tx = w, we have tv J w, whence u is a factor of w. Otherwise, (2) holds for all sufficiently large values of n. Since u is prolongable on the right to a factor of e, it follows that, if we assume that u is not a factor of w, then, for all n, there exists a word z n of length n such that uz n is a factor of some

v n 1,k u n 1,k • • • v 1 u 1 . If we take n ≥ |v |u|-1 u |u|-1 • • • v 1 u 1 | then we deduce that u is a factor of v n 1,k u n 1,k • • • v |u| u |u| .
By the hypothesis on the sequence (u k ) k , this implies that u is a factor of some factor of the form u m or s m+1 v m p m , for some m ≥ |u|. In both cases, the hypotheses imply that u is a factor of w, contrary to the assumption. This proves the claim that u is a factor of w. By Proposition 3.3, we finally conclude that e J w, thereby establishing that (h)⇒(i).

(j)⇒(a) Let G n be the Rauzy graph of order n of w, whose vertices are the factors of w of length n and for which there is an edge ax → xb, where a, b ∈ X, if axb is a factor (of length n + 1) of w; we label such an edge with the letter b. The label of a path is the concatenation of the labels of its edges. Note that, since w is uniformly recurrent, G n is strongly connected for every n. Hence G n has some cycle C. Let u be the label of C. Then u k is the label of the cycle obtained by going k times around C. If all such labels were factors of w, then u ω would also be a factor of w which, by [4, Corollary 2.10], implies that w J u ω , whence w is periodic. Hence, if w is not periodic then, for every n, there is some non-trivial path in G n whose label is a word u n in the conditions of (j), namely such that u n is not a factor of w but all its factors of length n are. This completes the proof.

Note that condition (h) of Theorem 6.2 implies that every uniformly recurrent pseudoword over a pseudovariety V containing LSl is the limit of a strictly ascending R-chain of rank 1 pseudowords.

Key properties of factors of ω-words over

A Given an ω-term α = γ 0 (β 1 )γ 1 • • • (β n )γ n with rank[γ i ], rank[β j ] < rank[α], we say that an ω-term of the form γ 0 β m 1 γ 1 • • • β m n γ n with m ≥ 1 is an expansion of α.
Lemma 7.1. Suppose that u, w ∈ Ω κ X A are such that u is a factor of w such that r(u) < r(w) and let α, β be the normal forms respectively of w, u. Then there is a portion ε of α such that β is a factor of an expansion of ε.

Proof. By hypothesis, there exist x, y ∈ (Ω κ X A) 1 such that w = xuy. Since multiplication does not raise the rank, at least one of the factors x and y must have the same rank as w. Accordingly, there are three similar cases to consider. We only treat the case in which both x and y have the same rank as w, as the other cases are similar.

Let γ, δ be the normal forms respectively of x, y. Since w = xuy, the normal form algorithm reduces γβδ to α. The hypotheses on the ranks of the factors x, u, y imply that the only standardization which may take place is in the product γ ′ βδ ′ , where γ ′ is the final portion of γ and δ ′ is the initial portion of δ. Such a standardization will produce either a crucial portion of α or a factor of the form (ε) of maximal rank. Moreover, the maximal rank idempotents in γ ′ and δ ′ determine bounding idempotents in the crucial portion of α in question, or they are equal to (ε). Since the normalization depends on applying the algorithm at a lower rank in the section of γ ′ βδ ′ between those two idempotents and using expansions and contractions of type 4, by replacing those idempotents by some finite powers of their bases, we conclude that β is a factor of the expansion of some portion of α.

The following marginal observation is an immediate consequence of the normal form algorithm. Remark 7.2. Suppose that u and v are ω-words of the same rank, whose normal forms have the same number of crucial portions, and trivial initial and final portions. If u ≥ J v then u = v.

Given w ∈ Ω κ X A, recall that F(w) is the set of all factors of w in Ω κ X A. We view F(w) as a quasi-ordered set under the factor ordering. Proof. Let (u n ) n be a sequence of factors of w. We claim that there exist indices m and n such that m < n and u m ≥ J u n . Let α and β n be the normal forms respectively of w and u n . Suppose first that there is a subsequence of the given sequence all of whose elements have the same rank as w. Then we may as well assume that, for all n, r(u n ) = r(w). By the normal form algorithm, for each n there are factorizations α = γ n δ n ε n and

β n = γ ′ n δ n ε ′ n where γ ′ n is a suffix of γ n , ε ′
n is a prefix of ε n , and both γ ′ n and ε ′ n have smaller rank than α. Since there are only finitely many such segments of w, we may as well assume that each of the sequences γ n , δ n , ε n is constant. It follows that all γ ′ n are suffixes of the same element of Ω κ X A and all ε ′ n are prefixes of the same element of Ω κ X A. By Corollary 5.6 and its dual, by taking subsequences, we may assume that each ǫ

[γ ′ n ] is a suffix of ǫ[γ ′ n+1 ] and each ǫ[ε ′ n ] is a prefix of ǫ[ε ′ n+1 ]. It follows that u n = ǫ[γ ′ n δ n ε ′ n ]
is a factor of u n+1 . Hence we may assume that r(u n ) < r(w) for all n. By Lemma 7.1, each β n is a factor of an expansion of some portion of α. Since there are only finitely many such portions, we may as well assume that the portion in question is the same for every n. One should now consider several cases according to the type of portion, initial, crucial, or final. Since the other cases are similar but somehwat simpler, we treat only the case where the portion is crucial, say (γ)δ(ε). For each n, let (k n , ℓ n ) be a lexicographically minimal pair of non-negative integers such that β n is a factor of γ kn δε ℓn . By taking subsequences, we may assume that both sequences (k n ) n and (ℓ n ) n are non-decreasing.

If (k n ) n is bounded by some k and (ℓ n ) n is bounded by some ℓ, then the β n are factors of an element of Ω κ X A of rank smaller than r(w), namely γ k δε ℓ . An induction argument then shows that there are indices m < n such that u m is a factor of u n , as desired.

There remain three cases to consider, depending on the boundedness of the sequences (k n ) n and (ℓ n ) n . We treat here only the case where (k n ) n is bounded and (ℓ n ) n is not. By taking subsequences, we may then assume that k n = k is constant and that (ℓ n ) n is strictly increasing. Then β n is a factor of γ k δε ℓn but not a factor of γ k δε ℓn-1 . We distinguish two subcases, according to whether k is zero or positive.

Assume first that k = 0. By the normal form algorithm, there is a factorization

β n = β ′ n ε mn β ′′ n , where β ′
n is a suffix of δε, β ′′ n is a prefix of ε, and m n < ℓ n . By Corollary 5.6 and its dual, we may assume that each

β ′ n is a suffix of β ′ n+1 , each β ′′ n is a prefix of β ′′ n+1
, and m n ≤ m n+1 . But then β n is a factor of β n+1 and, therefore, u n is a factor of u n+1 . The remaining cases are treated similarly.

Given w ∈ Ω X V, denote by F V (w) the set of all v ∈ X + such that v > J w. For L ⊆ X + , denote by cl V (L) the closure of L in Ω X V.
For a pseudovariety V and a fixed alphabet X, denote by p V the natural continuous homomorphism Ω X S → Ω X V determined by sending each generator x ∈ X to itself.

Lemma 7.4. If V contains LSl and w ∈ Ω X S, then F V (p V (w)) = F LSl (p LSl (w)). Proof. Note that, if W ⊆ V then F V (p V (w)) ⊆ F W (p W (w)). Hence F V (p V (w)) ⊆ F LSl (p LSl (w)).
For the converse, consider a sequence of words w n ∈ X + converging to w and suppose that v ∈ F LSl (p LSl (w)). Since the set cl LSl (X * vX * ) is open in Ω X LSl, we may as well assume that all words w n belong to cl LSl (X * vX * ) ∩ X + = X * vX * . Hence, we may factorize w n as w n = x n vy n , with x n , y n ∈ X * . By taking subsequences, we may further assume that x n → x and y n → y in (Ω X V) 1 . Then p V (w) = xvy, which shows that v ∈ F V (w).

Lemma 7.5. If w ∈ Ω κ X A then F A (w) is a rational language. Proof. By Lemma 7.4, it suffices to show that F LSl (w) is rational whenever w ∈ Ω κ X LSl. Note that, if v ∈ Ω κ X A has rank at least 1, then LSl |= v ω = v 2
since two elements of Ω X LSl are equal if and only if they have the same finite factors, the same finite prefixes, and the same finite suffixes, which is the case for v ω and v 2 since v is infinite. By induction on the rank, it follows that w is either a finite word, for which the result is obvious, or it is given by an ω-term of rank 1, say

w = u 0 v ω 1 u 1 • • • v ω r u r , where the u i , v j ∈ X + . Let w n = u 0 v n 1 u 1 • • • v n r u r .
Then a word v ∈ X + is a factor of w if and only if v is a factor of w n for all sufficiently large values of n. It follows that the finite factors of w are precisely the finite factors of a subterm of one of the forms

u 0 v ω 1 , v ω i u i v ω i+1 , or v ω r u r . Now, for instance, F LSl (v ω i u i v ω i+1
) is the set of all factors of the rational language v * i u i v * i+1 and, therefore, it is rational. The other cases are similar.

From hereon, for a pseudovariety V containing LSl and w ∈ Ω X S, we will write F (w) or F (p V (w)) for F S (w).

Slim pseudowords over A

For a non-negative integer n, we say that a pseudoword w ∈ Ω X A is n-slim if it has no infinite antichains of factors of rank at most n and the language F (w) ⊆ X + is rational. We say that w is slim if it is slim for all n ≥ 0. For example, since every uniformly recurrent pseudoword by its own definition has no infinite anti-chains of finite factors, and all its infinite factors are J-equivalent (cf. [START_REF]Profinite groups associated with weakly primitive substitutions[END_REF]), in view of Theorem 6.2 it is slim if and only if it is periodic. Thus, for a uniformly recurrent pseudoword, slimness is equivalent to being an ω-word. More generally, by Corollary 7.6, every ω-word is slim.

This section is dedicated to establishing some useful features of pseudowords that enjoy one or both defining properties of slim pseudowords. We start with a further preliminary observation involving uniformly recurrent pseudowords. Lemma 8.1. Let V be a pseudovariety containing LSl and let w 1 , . . . , w n ∈ Ω X V be uniformly recurrent pseudowords. If n i=1 F (w i ) is a rational language then every w i is periodic. Proof. By the pumping lemma and the fact that each F (w i ) is an infinite factorial language, at least one of the languages F (w i ) must contain all words of the form u k for a fixed word u. Without loss of generality, we may assume that i = 1. Since w 1 is J-maximal as an infinite pseudoword, we deduce that w 1 is periodic. Note also that, by a compactness argument and Proposition 3.3, if x, y ∈ Ω X V are uniformly recurrent but not J-equivalent, then F (x)∩F (y) is a finite language. It follows that n i=2 F (w i ) is still a rational language. An induction argument completes the proof of the lemma.

In analogy with the definition of reduced rank 1 crucial portions of ω-terms, we call a bridge factorization of a pseudoword from Ω X A a factorization of the form xyz such that: (f ) y has minimum length among all elements y ′ for which there exist x ′ , z ′ such that the preceding conditions hold for the triple (x ′ , y ′ , z ′ ) and x ′ y ′ z ′ = xyz.

We then also say that the product xyz is a bridge. The word y is called a middle of the bridge.

Lemma 8.2. Let x, z ∈ Ω X A be uniformly recurrent and y ∈ X * . Then the product xyz is either uniformly recurrent or it is a bridge.

Proof. Suppose that xyz is not uniformly recurrent. Since it is infinite, it follows from Proposition 3.3 that there is some finite factor u of xyz that is not a factor of x. Either u overlaps with y or it is a factor of z (cf. [START_REF] Almeida | Subword complexity of profinite words and subgroups of free profinite semigroups[END_REF]Lemma 8.2]). In either case, we conclude that there exist factorizations x = x 1 x 2 and z = z 1 z 2 such that x 2 yz 1 is a finite word that is not a factor of x. By symmetry and by further extending the suffix x 2 of x and the prefix z 1 of z, we may assume that x 2 yz 1 is a finite word that is a factor of neither x nor z, so that the factorization

x 1 • x 2 yz 1 • z 2 satisfies conditions (a)-(c). Conditions (d)
and (e) are obtained by first passing to x 1 all the beginning letters of x 2 yz 1 which fail (d) and then proceeding dually with suffix letters. Observe that in this procedure part or all of y may be removed. The resulting factorization x ′ y ′ z ′ of xyz satisfies conditions (a)-(e), and therefore there is such a factorization in which the length of y ′ is minimum, that is a bridge factorization of xyz.

We give a couple of examples to further help to understand our notion of bridge. Without condition (f ), we could have two middles of the same bridge of different lengths. For instance, the two factorizations a ω • ab • (cdbc) ω = a ω • bcd • bc(cdbc) ω both satisfy conditions (a)-(e). According to our definition of bridge, only ab is a middle of the bridge. On the other hand, further assuming condition (f ), as in our definition of bridge, even the middles of bridges may not be unique as the following two bridge factorizations show:

(abc) ω ab • cb • (abc) ω = (abc) ω • ba • bc(abc) ω . Lemma 8.3. If w ∈ Ω X A is a bridge then r(w) = 1.
Proof. Let w = xyz be a bridge factorization and suppose that e is an idempotent factor of w. Let p, q ∈ (Ω X A) 1 be such that w = peeeq. Then, by equidivisibility (cf. Theorem 2.6), e must be a factor of at least one of x and z. Since x and z are uniformly recurrent, whence J-maximal as infinite pseudowords, there are no idempotents strictly J-above e, which proves that r(w) = 1.

The previous result allows us to show that relatively weak hypotheses force the finiteness of the number bridge factors of a pseudoword. Lemma 8.4. Suppose that w ∈ Ω X A has no infinite anti-chains of factors of rank at most 1. Then there are only finitely many middles of bridge factors of w.

Proof. Let tuv and xyz be two bridge factorizations and suppose that xyz = ptuvq for some p, q ∈ (Ω X A) 1 . Since Ω X A is equidivisible by Theorem 2.6, the two factorizations have a common refinement. We claim that in such refinements, u and y must overlap. Indeed, otherwise, one of the following two symmetric cases must hold: ptu is a prefix of x or uvq is a suffix of z. In the first case, since t is infinite and x is uniformly recurrent, we have u ≥ J x J t, which contradicts the hypothesis that tuv is a bridge factorization. The symmetric case is similarly shown to be impossible.

By symmetry, we may as well assume that there are t ′ , y 1 , y 2 ∈ (Ω X A) 1 such that x = pt ′ , t = t ′ y 1 , y = y 1 y 2 , and y 2 z = uvq. Since y is finite, so is y 1 and, therefore, since t is infinite, so is t ′ . As pt ′ is a factor of the uniformly recurrent pseudowords x and t, we deduce that x, t, t ′ are all J-equivalent. Considering the equality y 2 z = uvq, we conclude similarly that z, v, vq are all J-equivalent. It follows that xyz and pt • u • vq are two bridge factorizations of the same pseudoword. By condition (f ) of the definition of bridge, we deduce that y and u have the same length. Now, if there are infinitely many middles of bridge factors of w, then there is a sequence of such bridges whose middles have strictly increasing length and the above shows that no element in such a sequence is a factor of another. Since we assumed that there are no infinite anti-chains of factors of w of rank at most 1, in view of Lemma 8.3 we conclude that there are only finitely many middles of bridge factors of w.

We next prove some properties of general factors of 1-slim pseudowords. Proposition 8.5. Let w ∈ Ω X A be a 1-slim pseudoword. Then the following conditions hold. (a) If w ′ is a factor of w then every element of F (w ′ ) is a factor of at least one of the following: a finite prefix of w ′ , a finite suffix of w ′ , a uniformly recurrent factor of w ′ , or a bridge factor of w ′ . (b) Every uniformly recurrent factor of w is periodic and the number of J-classes of such factors is finite. (c) If u is an infinite factor of w then p K (u) and p D (u) are ultimately periodic.

Proof. Suppose that u is an infinite factor of w. Since F (p K (u)) ⊆ F (u) ⊆ F(w), by Lemma 2.1 there is a factorization p K (u) = u 1 s, where u 1 is a finite word and s is a uniformly recurrent right infinite word. Let p n be the prefix of length n of s. Then u = u 1 p n r n for some pseudoword r n . Let (u 2 , u 3 ) be an accumulation point in Ω X A×Ω X A of the sequence (p n , r n ) n . Then F (u 2 ) = F (s) and so u 2 is uniformly recurrent. By continuity of multiplication, we conclude that there is a factorization u = u 1 u 2 u 3 , where u 1 is finite and u 2 is uniformly recurrent. Dually one could require instead of u 1 being finite that u 3 be finite.

Suppose next that uv is a factor of w. If u and v are both infinite then, by the preceding paragraph there are factorizations u = u 1 u 2 u 3 and v = v 1 v 2 v 3 such that u 2 and v 2 are uniformly recurrent and u 3 , v 1 ∈ X * . By Lemma 8.2, the product u 2 u 3 v 1 v 2 is either uniformly recurrent or it is a bridge.

Given a factorization xyz of some w ′ ∈ F(w) with y ∈ X + , if one of x or z is finite then y is respectively a factor of p K (w ′ ) or p D (w ′ ), while otherwise we may apply the preceding paragraph say to the factor x • yz of w. It follows that the finite factors of w ′ ∈ F(w) are those of p K (w ′ ), of p D (w ′ ), and of the uniformly recurrent and bridge factors of w ′ , from which (a) follows.

Since there are only finitely many middles of bridge factors of w by Lemma 8.4 and only finitely many J-classes of uniformly recurrent factors of w, as they are all ≤ J -incomparable rank 1 pseudowords and w is 1-slim (which includes the rationality of the language F (w)), and also taking into account Lemma 2.1 and its dual, we deduce that the (finitary) union of the languages of factors of the uniformly recurrent factors of w is a rational language. By Lemma 8.1, the uniformly recurrent factors of w must be periodic, which proves (b).

In the notation of the first paragraph, we conclude that u 2 is periodic and, therefore, so is s. This proves (c) and completes the proof of the proposition.

The following is an immediate application of Proposition 8.5.

Corollary 8.6. Let w ∈ Ω X A be an infinite 1-slim pseudoword. Then the set of rank 1 idempotent factors of w is finite and nonempty, and consists of ω-words of the form u ω , where u ∈ X + .

Proof. It has already been observed that the rank 1 idempotents are the uniformly recurrent idempotents and whence periodic by Proposition 8.5. To complete the proof, it remains to observe that the J-class of a pseudoword of the form u ω with u ∈ X + contains only finitely idempotents. Namely, they are of the form v ω , where v is an arbitrary conjugate of u.

We are now ready to prove the following result. Theorem 8.7. For n ≥ 1, every factor of an (n-)slim pseudoword is also (n-)slim.

Proof. Let w ∈ Ω X A be an n-slim pseudoword and let w ′ be a factor of w. Since, in case w is finite, the result is obvious, we assume that w is infinite. By Proposition 8.5, the finite factors of w ′ are factors of factors of w of the form u ω with u ∈ X + , of which there are only finitely many by Corollary 8.6, or of factors of one of the forms pu ω , u ω zt ω , or u ω s, with p, s, t, u, z ∈ X + , and where p and s are fixed and we may restrict the choices of z to a finite set of words. It follows that F (w ′ ) is a rational language, which shows that w ′ is n-slim.

The following couple of examples describe some non-slim pseudowords.

Example 8.8. Let w be an accumulation point of the infinite expression

(((ab) ω ab 2 ) ω ab 3 ) ω • • • ,
meaning an accumulation point of the sequence of truncated expressions

(• • • ((ab) ω ab 2 ) ω • • • ab n ) ω .
We claim that the rank 1 idempotent factors of w are the following: (ab) ω , (ba) ω , b ω . Indeed, every finite factor of w is a factor of some pseudoword of the form (ab) ω ab 2 ab 3 • • • ab n (ab) ω . Hence no uniformly recurrent factor can have a factor of any the forms ab k and b k a with k > 1. This implies that the only possibilities for the sets of finite factors of idempotent uniformly recurrent factors of w are the finite factors of (ab) ω and b ω .

Note also that F (w) is not rational by the Pumping Lemma since it contains arbitrarily long words of the form ab 2 ab 3 • • • ab n a, none of which admits a factorization of the form xyz such that xy m z ∈ F (w) with |x|, |y|, |z| bounded. Since the pseudowords of the form (ab) ω ab 2 ab 3 • • • ab n (ab) ω constitute an antichain of factors of w, we deduce that w fails both conditions for being 1-slim. Example 8.9. Let w be an accumulation point of the infinite expression

(((a ω b) ω a ω b 2 ) ω a ω b 3 ) ω • • • .
Then the factors of the form a ω b n a ω constitute an anti-chain. Note that the set F (w) = a * b * a * is rational.

We claim that, like in the preceding example, there are only finitely many rank 1 idempotent factors of w. More precisely, we claim that the only rank 1 idempotent factors of w are a ω and b ω . Indeed, all finite factors are factors of a pseudoword of the form a ω b n a ω . Hence there are no finite factors of the form ba r b with r > 0 and so a uniformly recurrent factor cannot contain both a and b as factors, whence it must be either a ω or b ω . On the other hand, while a ω is obviously a factor, being even a prefix, b ω is a factor because every finite power of b is a factor. We say that v ∈ F(w) is a special ω-factor of w if v = u ω for some Lyndon word u. In this case, the Lyndon word u is called a special base of w. A factor v of w is called a special factor if it is of the form u ω 1 zu ω 2 , where z ∈ X + and u ω 1 , u ω 2 are special ω-factors and v is not itself a special ω-factor. Note that every special factor is a bridge. We say that a prefix v of w is special if v is of the form zu ω , where z ∈ X + and u ω is a special ω-factor. The definition of special suffix of w is dual.

Corollary 8.10. Every infinite 1-slim pseudoword has at least one special ω-factor.

Proof. This is an immediate consequence of Corollary 8.6.

For special factors, we have the following result. Lemma 8.11. If w is 1-slim, then it has only finitely many special ω-factors, finitely many special factors, and precisely one special prefix and one special suffix. of categories and their relevance for the theory of pseudovarieties of finite semigroups. See also [START_REF] Almeida | Infinite-vertex free profinite semigroupoids and symbolic dynamics[END_REF] for caveats and pitfalls that one should be aware of when handling pseudovarieties of categories, particularly when profinite techniques are involved.

We view small categories as directed graphs with an associative partial composition of edges which has local identities. We say that a functor f : C → D is a quotient if it is surjective and its restriction to vertices is injective. We say that the functor f : C → D is faithful if its restriction to each hom-set C(p, q) is injective. A category C divides a category D if there is a pair of functors f : E → C and g : E → D such that f is a quotient and g is faithful. A pseudovariety of categories is a class of finite categories that contains the trivial, one-vertex one-edge, category and is closed under taking finite products and divisors.

The hom-set C(p, p) of loops at a vertex p of a category C forms a monoid, called the local monoid at p. Conversely, a monoid is viewed as a category by adding a virtual vertex and viewing the elements of the monoid as loops at that vertex, which are composed as they are multiplied in the monoid. Given a pseudovariety V of semigroups, the class of all finite categories which divide some monoid in V is a pseudovariety of categories which is denoted gV. The class of all finite categories whose local monoids belong to V is also a pseudovariety of categories which is denoted ℓV.

By a congruence on a category C we mean an equivalence relation ≡ on its set of edges which only identifies edges with the same ends and such that, if u ≡ u ′ and v ≡ v ′ and the composite uv is defined, then uv ≡ u ′ v ′ . Then C/≡ is the quotient category, with the same vertex set, and edges the ≡-classes of edges of C.

Given a finite graph Γ, the category freely generated by Γ is denoted Γ * and has the same set of vertices as Γ while its edges are the finite paths in Γ. Given a pseudovariety W of categories, by a pro-W category we mean a finite-vertex compact category C whose edges are separated by continuous quotient functors into members of W. The congruences ≡ on Γ * for which the quotient Γ * /≡ belongs to W generate a uniform structure on Γ * . The completion of Γ * with respect to this uniform structure is the pro-W category freely generated by Γ and is denoted Ω Γ W. The subcategory of Ω Γ W generated by Γ is denoted Ω Γ W. Note that the ω-power x → x ω is a well-defined operation on loops of Ω Γ W. The subcategory closed under this operation generated by Γ is denoted Ω κ Γ W. Let ι W denote the natural mapping Γ → Ω Γ W. In analogy with the terminology for the semigroup case, and taking into account that the elements of Γ * are effectively viewed as paths, the elements of Ω Γ W are called pseudopaths while those of Ω Γ W \ Γ * are said to be infinite pseudopaths. Elements of Ω κ Γ W may be called ω-paths.

A pseudovariety of semigroups V is said to be monoidal if it is generated by (its) monoids. Equivalently, S ∈ V implies S 1 ∈ V and so, certainly A is monoidal. For a monoidal pseudovariety V, the unique continuous homomorphism

γ V : Ω Γ gV → (Ω E(Γ) V) 1
that sends each edge to itself (and all vertices to the virtual vertex) is faithful [START_REF]A syntactical proof of locality of DA[END_REF]. In case w ∈ Ω X A is infinite and 1-slim, we also consider the unique continuous homomorphism

λ w : Ω Γ(w) gA → Ω X A
that sends each edge ezf : e → f to the pseudoword ezf . Given a semigroupoid S, that is a category without the requirement for local identities, denote by S c the category which is obtained from S by adding the missing local identities. Recall that

Sl * D 1 = xyxzx = xzxyx, x 3 = x 2 , (xy) 2 x = xyx
is the pseudovariety of two-testable semigroups, which is generated by the languages whose membership is characterized by the first letter, the last letter and the two-letter factors (cf. [START_REF] Almeida | Finite semigroups and universal algebra[END_REF]Chapter 10]). It is also the pseudovariety generated by the real matrix semigroup

A 2 = 1 1 0 0 , 0 0 1 1 , 1 0 0 0 , 0 0 1 0 , 0 0 0 0 under matrix multiplication.
The following lemma can probably be considered folklore.

Lemma 9.1. Let Γ be a finite graph and V a pseudovariety containing A 2 . Suppose that v ∈ Ω Γ gV and u ∈ Ω E(Γ) V are such that u is a factor of γ V (v). Then there exists u ′ ∈ Ω Γ gV such that γ V (u ′ ) = u and u ′ is a factor of v.

Denote by A k the pseudovariety x k+1 = x k . Note that A ω = A * D n = A.

Lemma 9.3. Let w ∈ Ω X A be 1-slim, periodic at the ends, and let n be a common multiple of the lengths of all special bases of w. Let k be a positive integer or ω. Then there is a unique mapping τ k such that the following diagram commutes:

(4) Ω Γ(w) gA τ k λw / / Ω X A \ X ≤n / / Ω X A p k Ω Gn(w) gA k / / Ω Bn gA k Ω X (A k * D n ) \ X ≤n ΦA k n o o / / Ω X (A k * D n )
where p k is the natural continuous homomorphism. Moreover the mapping τ k is a continuous homomorphism.

Proof. Let τ k : Ω Γ(w) gA → Ω Gn(w) gA k denote the continuous graph homomorphism which maps each vertex x ω to the vertex i n (x ω ) = t n (x ω ) and each edge x ω yz ω to the "pseudopath reading the successive factors of length n + 1". More precisely, τ k is defined so that the diagram (4) commutes. The uniqueness, existence, and continuity of the mapping τ k is justified by the observation that the composite mapping ΦA k n • p k • λ w takes its values in Ω Gn(w) gA k . It remains to show that τ k is a semigroupoid homomorphism. For this purpose, it suffices to show that it is a homomorphism on the subsemigroupoid generated by Γ(w), since this subsemigroupoid is dense in Ω Γ(w) gA. A finite path in Γ(w) is a sequence of edges of the form x ω i-1 y i x ω i :

x ω i-1 → x ω i (i = 1, . . . , r). Its image under λ w is the product x ω 0 y 1 x ω 1 • • • y r x ω r .
Hence it suffices to observe that, for every finite whose length divides n and x, z ∈ Ω X (A k * D n ), the following equality holds:

(5) ΦA k n (xy ω z) = ΦA k n (xy ω ) ΦA k n (y ω z)
. By the definition of ΦA k n , to prove (5) it suffices to show that η A k maps both sides to the same element of

X n × Ω X n+1 A k × X n . The left side is mapped to (6) ι A k (xy ω z) = η A k ΦA k n (xy ω z) = i n (xy ω ), γ A k ΦA k n (xy ω z)
, t n (y ω z) while, since γ A k is a homomorphism, the right side is mapped to [START_REF] Almeida | Complete reducibility of systems of equations with respect to R, Portugal[END_REF] η

A k ΦA k n (xy ω ) ΦA k n (y ω z) = i n (xy ω ), γ A k ΦA k n (xy ω ) γ A k ΦA k n (y ω z) , t n (y ω z) . Since ι A k is a homomorphism, we have ι A k (xy ω z) = ι A k (xy ω )ι A k (y ω z
) which shows that the triple in (6) may be rewritten as the product [START_REF] Almeida | Sur certains systèmes d'équations avec contraintes dans un groupe libre[END_REF] i n (xy ω ), γ A k ΦA k n (xy ω ) ΦA k n t n (xy ω ) i n (y ω z) γ A k ΦA k n (y ω z) , t n (y ω z) Hence, to prove (5) it suffices to establish the equality of the middle components of the triples in [START_REF] Almeida | Complete reducibility of systems of equations with respect to R, Portugal[END_REF] and [START_REF] Almeida | Sur certains systèmes d'équations avec contraintes dans un groupe libre[END_REF], which in turn follows from the stronger equality [START_REF]Sur certains systèmes d'équations avec contraintes dans un groupe libre-addenda[END_REF] γ

A k ΦA k n (xy ω ) = γ A k ΦA k n (xy ω ) ΦA k n t n (y ω ) i n (y ω ) .
Since n is a multiple of the length of y, t n (y ω ) i n (y ω ) = y s for some integer s ≥ 2. On the other hand, since γ A k and ΦA k n are continuous, [START_REF] Almeida | On the decidability of iterated semidirect products and applications to complexity[END_REF] γ

A k ΦA k n (xy ω ) = lim ℓ γ A k ΦA k n (xy ℓ ) . Now, for ℓ ≥ ms, γ A k ΦA k n (xy ℓ
) is a word in the alphabet X n+1 which admits Φ A k n (y s ) m as a suffix.

By compactness, it follows that Φ

A k n (y s ) m is a suffix of γ A k ΦA k n (xy ω
) for all m, and therefore so is Φ A k n (y s ) ω . Aperiodicity now implies the equality [START_REF]Sur certains systèmes d'équations avec contraintes dans un groupe libre-addenda[END_REF], which completes the verification of the equality [START_REF]Profinite semigroups and applications, Structural Theory of Automata, Semigroups, and Universal Algebra[END_REF] and the proof of the lemma.

As a consequence of Lemma 8.11, we may associate to each infinite 1-slim pseudoword w a positive integer ν(w) = m ′ m ′′ where m ′ is a multiple of the length of each special base of w and m ′′ ≥ 8 is such that m ′′ > |xyz| for every special factor x ω yz ω of w in normal form. Lemma 9.4. Let w ∈ Ω X A be a 1-slim pseudoword that is periodic at the ends, let n = ν(w), and let u = u ′ au ′′ be a factor of w of length 3n where |u ′ | = n and a ∈ X. If u ′ occurs in a special ω-factor x ω of w and u ′ a does not occur in x ω , then u occurs in a unique special factor of w of the form x ω yz ω . Moreover, u may be written uniquely in the form x ′ yz ′ where x ′ is a suffix of x ω and z ′ is a prefix of z ω with |x ′ | ≤ n and n ≤ |z ′ | < 2n.

Proof. Since w is 1-slim, we know from Lemma 8.11 that it has only finitely many special ω-factors and finitely many special factors. If w would have no special factors, then by Lemma 8.14 it would be a special ω-factor v ω and the Lyndon word v would be the only special base of w. In that case, since by hypothesis x ω is a special ω-factor of w, we would have v = x which contradicts the hypotheses that u is a factor of w and that u ′ a does not occur in x ω . Therefore w has special factors and, by Lemma 8.13, u is a factor of one of them, say of t ω 1 yt ω 2 written in normal form. Now, notice that since x is a special base of w, the definition of n implies the existence of a positive integer k > |t 1 yt 2 | such that n = k|x|. Hence, from the hypotheses that u ′ is a factor of x ω and |u ′ | = n, we deduce that u ′ = v k for some conjugate v of x.

Since k > |t 1 yt 2 | and u ′ is a factor of t ω 1 yt ω 2 , it follows that v k-2 occurs in t ω 1 or in t ω 2 . As k -2 > |t 1 yt 2 | -2 ≥ |t 1 |, if v k-2 occurs in t ω 1 , then v is a conjugate of t ℓ
1 for some ℓ ≥ 1 by Lemma 9.2. Therefore v and t 1 are conjugates because v is a primitive word, whence x is a conjugate of t 1 . As x and t 1 are Lyndon words, this shows that they are equal. In the second case, we would deduce analogously that x = t 2 . However, since v is a conjugate of x, if the second case holds, then va does not occur in t ω 2 since otherwise a would be the first letter of v and so u ′ a(= v k a) would occur in x ω (= t ω 2 ). Therefore, the first case holds necessarily, whence x = t 1 and u occurs in the special factor x ω yz ω , where z = t 2 . Moreover, since u ′ a is not a factor of x ω and taking into account that x ω yz ω is in normal form, the occurrence of u in x ω yz ω must be such that the a in question is found within y. Hence there is a factorization u = x ′ yz ′ with |x ′ | ≤ n a suffix of x ω and z ′ a prefix of z ω with |z ′ | < 2n, and so

|z ′ | = |u| -|x ′ | -|y| ≥ 3n -n -n = n.
To prove uniqueness, suppose that u occurs in special factors x ω y 1 z ω 1 and x ω y 2 z ω 2 in normal form. Then one deduces from the above that u may be written in the forms u

= x ′ y 1 z ′ 1 = x ′′ y 2 z ′ 2 , where x ′ and x ′′ are suffixes of x ω and z ′ i is a prefix of z ω i (i = 1, 2) with |x ′ |, |x ′′ | ≥ 2|x| and |z ′ i | ≥ |z 1 | + |z 2 |.
As x is a Lyndon word, it follows that x ′ = tx ℓ ′ and x ′′ = tx ℓ ′′ for some prefix t of x and positive integers ℓ ′ and ℓ ′′ . On the other hand, since z 1 and z 2 are Lyndon words which have powers with a common factor of length |z 1 | + |z 2 |, we deduce as above that z 1 = z 2 and that z

′ 1 = z m ′ 1 v and z ′ 2 = z m ′′ 1 v
for some suffix v of z 1 and positive integers m ′ and m ′′ . We thus conclude that x ω y 1 z ω 1 and x ω y 2 z ω 2 are equal. Since they are written in normal form, we finally deduce from McCammond's normal form algorithm that y 1 = y 2 . To conclude the proof, we notice that ℓ ′ = ℓ ′′ (i.e., x ′ = x ′′ ) and that m ′ = m ′′ (i.e., z ′ 1 = z ′′ 2 ) since otherwise y 1 would be a prefix of x ω or a suffix of z ω 1 , thus contradicting the definition of normal form. Given two pseudowords u, v ∈ Ω X A and a positive integer m, write u ≃ m v if u and v have precisely the same prefix, the same suffix and the same factors of length m. Lemma 9.5. Let w ∈ Ω X A be a 1-slim pseudoword that is periodic at the ends, let n = ν(w), and let k ≥ 1 be an integer. Suppose that v is a finite word such that w ≃ kn+1 v. Then every occurrence of a factor of v of length n which is a factor of some special ω-factor of w is found within a factor of v of length kn which occurs in the same special ω-factor.

Proof. Let v = v 1 uv 2 be a factorization such that |u| = n and u is a factor of a special ω-factor x ω of w.

Suppose first that |uv 2 | ≤ kn + 1. Then u is a factor of the suffix s of length kn + 1 of v. Since, by hypothesis, s is also a suffix of w and w is periodic at the ends, we deduce that s is a factor of the special suffix z ω of w. But n = ν(w) is at least twice the length of both x and z. Since u is a common factor of x ω and z ω and x and z are both Lyndon words, it follows from Fine and Wilf's Theorem (cf. [21, Proposition 1.3.5]) that x = z, which concludes the proof in this case. Thus, we may assume that |uv 2 | ≥ kn + 1. Similarly, we may also assume that |v 1 u| ≥ kn + 1.

Let up be the longest prefix of uv 2 that is a factor of x ω and suppose that |up| < kn for, otherwise, we are done. Let a be the first letter of v 2 and let s be the suffix of v 1 of length kn + 1 -|upa|. By hypothesis, the factor supa of v is also a factor of w. By Lemma 8.13, either (a) supa is a factor of a special ω-factor z ω or (b) supa is a factor of a special factor α ω βγ ω of w.

If some factor of length 2m ′ -1 of up is a factor of a special ω-factor t ω of w then, again by Fine and Wilf's Theorem, since x ω and t ω have a common factor of length |x| + |t|gcd(|x|, |t|) ≤ 2m ′ -1, we conclude that x = t. Thus case (a) is impossible as upa in particular would be a factor of x ω , contrary to our assumption and so it remains to treat case (b).

Since m ′′ ≥ 8, an elementary calculation shows that 4m ′ + m ′′ ≤ m ′ m ′′ = n. Let sup = y 1 y 2 y 3 y 4 be the factorization such that y 2 and y 4 both have length 2m ′ -1 and |y 3 | = m ′′ . Since supa is a factor of α ω βγ ω and |y 3 | = m ′′ > |β|, we deduce that either y 1 y 2 is a factor of α ω or y 4 a is a factor of γ ω . By the preceding paragraph, it follows that, in the former case, α = x and y 1 y 2 is a factor of x ω while, in the latter case, γ = x and y 4 a is a factor of x ω . Since the overlap of both y 1 y 2 and y 4 a with up has length at least |x| and x is primitive, [START_REF]Algebraic combinatorics on words[END_REF]Proposition 12.1.3] implies that, respectively, sup or upa is a factor of x ω , the latter being excluded by the choice of p. Hence the given occurrence of u as a factor v is found within the factor sup, of length kn, which is still a factor of x ω . Lemma 9.6. Let w ∈ Ω X A be a 1-slim pseudoword that is periodic at the ends, let n = ν(w), and let k ≥ 3 be an integer. Let w k be a finite word such that w k ≃ kn+1 w. Then there is some path w ′ k in Γ(w), starting and ending respectively at the special prefix and special suffix of w, such that

(11) τ k (w ′ k ) = ΦA k n (p k (w k )). Proof. We first note that ΦA k n (p k (w k )
) is a path in G n (w) which starts at the vertex i n (w k ) = i n (w), ends at t n (w k ) = t n (w), and goes through the edges determined by the successive occurrences of factors of w k of length n+ 1 of w k . Since w k and w have the same factors of length 3n ≤ kn+ 1, Lemma 9.4 shows that each such occurrence is either an occurrence in some special ω-factor, or it determines uniquely a special factor x ω yz ω in which it occurs. Lemma 9.4 shows moreover that the path ΦA k n (p k (w k )) determines uniquely an alternated sequence of special ω-factors and special factors of w, where the special ω-factors that come before and after the special factor x ω yz ω are respectively x ω and z ω . In other words, we have an associated path w ′ k in the graph Γ(w). It remains to show that (11) holds. From Lemma 9.5, it follows that the path ΦA k n (p k (w k )), whenever it enters an edge which is determined by a factor of a special ω-factor v ω , it must go at least k times around the cycle which reads the successive factors of v ω of length n + 1. The equality [START_REF]Syntactic and global semigroup theory, a synthesis approach[END_REF] now follows from the definition of τ k .

The following lemma is the core of our encoding of 1-slim pseudowords w as pseudopaths in the graph Γ(w). Lemma 9.7. If w ∈ Ω X A is 1-slim and has at least one special factor, then there are some edge w ′ ∈ Ω Γ(w) gA and some words x, y ∈ X * such that w = xλ w (w ′ )y.

Proof. By Corollary 8.12, we may as well assume that w is periodic at the ends. We will show that w = λ w (w ′ ) for a suitable w ′ ∈ Ω Γ(w) gA.

Let n be as in Lemma 9.4 and for this value of n, consider the continuous homomorphisms τ k (k ∈ {1, 2, . . . , ω}) of Lemma 9.3. In particular, the diagram (4) commutes. Combining the diagrams for positive integers k ≤ ℓ and ω, we obtain the following diagram, where p k , p ℓ,k , q k , and q ℓ,k are the natural continuous homomorphisms:

(12) Ω Γ(w) gA τω & & L L L L L L L L L L τ ℓ % % τ k & & λw ) ) Ω Gn(w) gA / / Ω Bn gA q ℓ q k } } Ω X A \ X ≤n ΦA n o o w w / / Ω X A p ℓ p k w w Ω Gn(w) gA ℓ / / Ω Bn gA ℓ q ℓ,k Ω X (A ℓ * D n ) \ X ≤n ΦA ℓ n o o / / Ω X (A ℓ * D n ) p ℓ,k Ω Gn(w) gA k / / Ω Bn gA k Ω X (A k * D n ) \ X ≤n ΦA k n o o / / Ω X (A k * D n )
The commutativity of the leftmost and rightmost rectangles is trivial, while for the rectangles in the middle it follows from the continuity of the mappings involved and the way the horizontal sides transform finite words. The commutativity of the leftmost triangles is now a consequence of the uniqueness of the mappings τ k , cf. Lemma 9.3. Hence the diagram (12) commutes. Let (w k ) k be a sequence of finite words converging to w such that, for all k, w k and w have the same factors, prefixes and suffixes of length kn + 1. Note that, by Lemma 9.5, if v ω is a special ω-factor of w, then every occurrence of a factor of v ω of length n as a factor of w k can be found within an occurrence of v k as a factor of w k .

The reason to consider τ k for finite k is that the image under τ k of each edge x ω yz ω ∈ Γ(w) is equal over gA k to a finite path. Hence, for finite k, τ k maps finite paths of Γ(w) to finite paths of G n (w).

By Lemma 9.6, there is some path w ′ k in Γ(w), starting and ending respectively at the special prefix and special suffix of w such that τ k (w ′ k ) = ΦA k n (p k (w k )) ∈ Ω Gn(w) gA k . By compactness, without loss of generality, we may assume that the sequence (w ′ k ) k converges to some w ′ in Ω Γ(w) gA. Then, in view of conclude the proof of (d) and (e), it now suffices to observe that

ψ • π k • λ w (v ′ ) = ϕ(v ′ ) = ϕ(x ′ t ′ z ′ ) = ϕ(x ′ y ′ z ′ ) = ψ • π k • λ w (u).
To prove (f ), suppose that u ∈ Ω κ X A and there exist v ∈ Im µ w and x, y ∈ (Ω κ X A) 1 such that ψ • π k (xuy) = ψ • π k (v), that is π k (xuy) is θ-equivalent to some element of π k (Im µ w ). Then, by (d), π k (xuy) ∈ π k (Im µ w ), that is π k (u) is a factor of some element of π k (Im µ w ), which establishes (f ) since the converse is trivial.

For (g), we need to bound the length of the words x and y. Since π k (xuy) ∈ π k (Im µ w ), by (b) there exists v ∈ Ω Γ(w) gA such that λ w (v) ∼ w,k xuy. By the definitions of λ w and ∼ w,k , there is some special ω-factor z ω of w and z ℓ is a prefix of xuy for some ℓ ≥ k. By the minimality hypothesis on the pair (x, y), it follows that |x| < (k + 1)|z| for, otherwise, writing x = zx ′ , we would still have λ w (v) ∼ w,k x ′ uy. This shows that |x| < (k + 1)m and the dual argument shows that we also have |y| < (k + 1)m. Note that m is an integer by Lemma 8.11. Hence the set of all pairs (x, y) in (g) for a given u is indeed finite.

The preceding lemma provides the technicalities required to prove the following rather natural result but for which we do not know of any simpler proof. Lemma 9.10. Let w ∈ Ω X A be an infinite 1-slim pseudoword. Then the homomorphism λ w is injective on edges of Ω Γ(w) gA.

Proof. Let u and v be distinct edges in Ω Γ(w) gA. We need to show that λ w (u) = λ w (v). There exist some monoid S ∈ A and some onto continuous homomorphism ϕ : Ω Γ(w) gA → S such that ϕ(u) = ϕ(v). Since K 1 ∪ D 1 ⊆ A, by taking the product mapping induced by ϕ and the natural continuous homomorphisms ̺ : Ω Γ(w) gA → Ω E(Γ(w)) K 1 and ς : Ω Γ(w) gA → Ω E(Γ(w)) D 1 , we obtain a continuous homomorphism into a finite aperiodic semigroup such that ϕ, ̺, ς factor through it. Hence, we may as well assume that ̺, ς factor through ϕ. Let n = ν(w) and let k = max{ind(S) + 1, n}. Then the hypotheses of Lemma 9.9 hold and we proceed to apply it. We obtain a commutative diagram (13) from which we extract the relevant part for our present purposes in diagram [START_REF] Ash | Inevitable graphs: a proof of the type II conjecture and some related decision procedures[END_REF] and add the nodes T and R and the arrows involving them which are described below. [START_REF] Ash | Inevitable graphs: a proof of the type II conjecture and some related decision procedures[END_REF] Im

k π k (Im µ w ) ψ / / Ω X A k / / _ _ _ ψ Ω X A k χ S / / _ _ _ _ _ _ T ρ / / _ _ _ _ _ R
As in Lemma 9.9(d) let θ denote the congruence on Ω X A k generated by ker ψ, so that θ saturates π k (Im µ w ) and its restriction to that subset coincides with ker ψ. Hence, if we denote by T the quotient semigroup Ω X A k /θ, then we may assume that S is a subsemigroup of T in such a way that ψ is the restriction of the natural homomorphism ψ : Ω X A k → T to π k (Im µ w ). At this point, we need to overcome an essential difficulty: the semigroup T may be infinite. We do so by taking a Rees quotient.

Let I = {t ∈ T : S ∩ T 1 t T 1 = ∅}. Then I is an ideal of T such that I ∩ S = ∅. Denote by R the Rees quotient T /I and let ρ : T → R be the natural homomorphism so that ρ • ϕ still distinguishes the edges u and v. We claim that R is finite. Since then, by construction, R ∈ A k , the homomorphism ρ • ψ factorizes through a continuous homomorphism χ : Ω X A k → R. This completes the commutative diagram [START_REF] Ash | Inevitable graphs: a proof of the type II conjecture and some related decision procedures[END_REF]. We thus obtain

χ • π k • λ w (u) = ρ • ϕ(u) = ρ • ϕ(v) = χ • π k • λ w (v)
which establishes that λ w (u) = λ w (v).

We proceed to establish that R is finite, which is equivalent to showing that T \ I is a finite set. By Lemma 9.9(f ), T \ I consists of all elements of the form ψ • π k (x) such that x ∈ Ω κ X A and π k (x) is a

Proof. The existence and uniqueness of w ′ is given, respectively, by Lemmas 9.7 and 9.10. Part (a) follows from Lemma 9.14(b) for the case where v ′ = w ′ since the language L of that lemma is finite. The general case is obtained taking into account Theorem 8.7 and Lemma 9.11.

Since λ w is a homomorphism, the same result implies that a strict J-chain of idempotent factors of w ′ maps under λ w to a strict J-chain of idempotent factors of w, which proves (b). Moreover, we can always add at the top of such a chain an idempotent of the form z ω , where z is a Lyndon word, for instance by choosing the initial vertex of the topmost idempotent in the given chain.

Conversely, suppose that e 1 > J e 2 > J • • • > J e n ≥ J w, where the e i are idempotents. By Theorem 8.7, each e i is slim. By Lemmas 9.7 and 9.11, there exist factors e ′ i of w ′ in Ω Γ(w) gA and finite words x i , y i ∈ X * such that e i = x i λ w (e ′ i )y i for all i except possibly for i = 1 in case e 1 is the ω-power of a Lyndon word. Since e i is an idempotent, we deduce that x i λ w (e ′ i )y i = e i = e 3 i = x i λ w (e ′ i )y i e i x i λ w (e ′ i )y i . Say by Theorem 2.6, we may cancel the finite words x i and y i at the ends to deduce that λ w (e ′ i ) = λ w (e ′ i )y i e i x i λ w (e ′ i ), which show that λ w (e ′ i ) lies in the same J-class as e i . Moreover, since z ω y i e i x i t ω is still a factor of w, where e ′ i is an edge t ω → z ω , there is some v ′ i ∈ Ω Γ(w) gA such that λ w (e ′ i v ′ i e ′ i ) = λ w (e ′ i ). By Lemma 9.10, it follows that e ′ i v ′ i e ′ i = e ′ i , and so the idempotent e ′ i v ′ i is J-equivalent to e ′ i . By Lemma 9.12, we have a chain e ′ 1 > J e ′ 2 > J • • • > J e ′ n ≥ J w ′ , which proves both (c) and (d). Part (e) follows taking also into account Lemma 9.12.

The following is an elementary observation about the Dyck language which we need in the sequel. Lemma 10.2. Suppose that L is a rational language contained in the Dyck language n D n , where D 0 = {1}, D n+1 = (aD n b) * (n ≥ 0). Then L ⊆ D n for some n.

Proof. Since L is rational, L is recognized by a finite deterministic trim automaton, say with m states and initial state q 0 . We claim that, given any state q, the difference |w| a -|w| b is constant for w in the language {w ∈ {a, b} * : q 0 w = q}. Indeed, if w 1 and w 2 are two words in this language and v is any word such that qv is a terminal state, then w 1 v and w 2 v both belong to L and so |w i | a -|w i | b = |v| b -|v| a (i = 1, 2). Since every state is reachable from q 0 by a path of length at most m -1, it follows that L ⊆ D m-1 .

Iterating the application of Proposition 10.1, we obtain the following characterization of the elements of Ω X A which are given by ω-terms in terms of properties of their sets of factors, which is the main result of this paper. Proof. Suppose first that w ∈ Ω κ X A. Then w is slim by Corollary 7.6 and r(w) = r(w) < ∞ by Propositions 4.4 and 4.5. By Lemmas 9.7 and 9.13, there exist w ′ ∈ Ω κ Γ(w) gA and x, y ∈ X * such that w = xλ w (w ′ )y. Moreover, r(w ′ ) < r(w) by Proposition 10.1(c), so that, taking into account Lemma 9.1 and Proposition 9.8, we may view w ′ as an ω-word of smaller rank over a finite alphabet. Proceeding by induction on the rank, we may assume that P (w ′ ) is a rational language. By Lemmas 8.11, 7.5, and 9.14(a), it follows that P (w) is also a rational language.

To establish the converse, we first observe that, since P (w) is rational, so is the language which is obtained from it by erasing all letters of X. By Lemma 10.2, it follows that the elements of F(w) ∩ Ω κ X A have bounded rank. On the other hand, since the two finiteness hypotheses imply in particular that w is slim, by iterated application of Proposition 10.1 taking into account Corollary 8.12 Proposition 9.8, we obtain a sequence starting with the pseudoword w 0 = w, and continuing with edges w k+1 ∈ Ω Γ(w k ) gA, and words x 0 , y 0 ∈ X * and paths x k , y k in Γ(w k-1 ) such that [START_REF] Eilenberg | Automata, languages and machines[END_REF] w k = x k λ w k (w k+1 )y k , and this sequence can be constructed while k < r(w), each term being slim. Now, for w n we can determine factors of w which are ω-words of rank n: for n > 1, if it is not the last term in the sequence, then simply take any edge in Γ(w n ) and successively apply to it λ wn , λ wn-1 , . . . , λ w0 to obtain an ω-term of rank n + 1 which is a factor of w. Now, by the hypothesis that P (w) is rational and the argument at the beginning of this paragraph, the sequence must stop at some point, that is the graph is trivial, meaning that w n has no special factors. Since w n is slim, by Lemma 8.14 and Corollary 8.12, we deduce that either w n is finite or w n is a rank 1 ω-word of the form tu ω v, and therefore trivially an ω-word.

Applying successively equation ( 16) for k = n -1, n -2, . . . , 0, it follows that w is also an ω-word.

Lemma 4 . 1 .

 41 Let α and β be ω-terms in normal form and let γ be the normal form of αβ. Then rank[γ] ≥ max{rank[α], rank[β]}.

  then, by Lemma 4.1, rank[(β)] ≤ rank[(α)], which contradicts an earlier inequality. (b) Assume that indeed ǫ[(α)] lies strictly J-above ǫ[(β)]. By Lemma 4.1, we have rank[(α)] ≤ rank[(β)]. Since (α) and (β) are in normal form, it follows that rank[α] ≤ rank[β]. Suppose that rank[α] = rank[β]. By hypothesis, there exist possibly empty ω-terms in normal form γ and δ such that ǫ[γ(α)δ] = ǫ[(β)].

Proposition 4 . 4 .

 44 Let w ∈ Ω κ X A and let α be its normal form. Then r(w) = rank[α]. Proof. By definition, the rank of an ω-term in normal form is the largest number of nested parentheses. Hence, for n = rank[α], there are ω-terms in normal form (β 1 ), .

  On the other hand, by Lemma 4.1, since ǫ[(β m )] is J-above w = ǫ[α], we have rank[(β m )] ≤ rank[α]. Hence m ≤ rank[α], which shows that r(w) ≤ rank[α].

Lemma 5 . 3 .

 53 Let t = ǫ[δ] and f = ǫ[(ε)]. Since e J tf and δ(ε) is an initial portion, which in particular means that rank[δ] ≤ rank[ε] = rank[δ(ε)] -1, by Proposition 4.4 it follows that r(f ) = r(e) and so f J e since f ≥ J e. By Lemma 5.1, we deduce that ε = α. Hence all terms in the R-class of u which, in normal form, are initial portions, lie in the same H-class. Hence there is a unique such term since the Green relation H is trivial in Ω κ X A by Corollary 2.5. Of course, one has a dual result to Proposition 5.2 concerning L-classes and final portions. Let α and (β) be ω-terms in normal form and suppose that ǫ[(β)] ≥ J ǫ[α] in Ω κ X A. Then (β) is a factor of α. Proof. Let w = ǫ[α] and e = ǫ[(β)]. We proceed by induction on rank[α]. We assume inductively that the result holds for all ω-terms α ′ with rank[α ′ ] < rank[α]. Let x and y be ω-words such that w = xey. If rank[α] = rank[(β)], then the result follows from the normal form algorithm since it does not affect factors of the form (ξ) which are already in normal form. Otherwise, at least one of the factors x and y has the same rank as w. As the other cases are similar and simpler, we consider the case where r(x) = r(y) = r(w) = rank[α].

Proposition 6 . 1 .

 61 The following properties hold for the above sequence(x n ) n : (a) x n+1 > R x n for every n; (b) lim n x n = (b ω a) ω in Ω X A; (c)the only regular J-classes J-above any given x n are those of b ω and (b ω a) ω ; (d) r(x n ) = 2. Proof. Multiplying the terms of the sequence (b

Theorem 7 . 3 .

 73 Let w ∈ Ω κ X A. Then F(w) is wqo.

Corollary 7 . 6 .

 76 If w ∈ Ω κ X A then the following conditions hold: (a) for every v ∈ F(w), F (v) is a rational language; (b) F(w) is wqo. Proof. (a) follows from Theorem 2.4 and Lemma 7.5, while (b) is Theorem 7.3.

  (a) x and z are uniformly recurrent; (b) y is a finite word; (c) y is a factor of neither x nor z; (d) if y = av and xa R x, then v is a factor of at least one of x and z; (e) if y = vb and bz L z, then v is a factor of at least one of x and z.

Theorem 10 . 3 .

 103 Let w ∈ Ω X A. Then w ∈ Ω κ X A if and only if (a) there are no infinite anti-chains of factors of w and (b) P (w) is a rational language.

  λ w r

	Ω Γ(w) gA	o o	Ω Γ(w) gA ? _	µw	/ / Im µ w + r r r r r r r r r r 9 9 / / Ω κ X A	$ $ H H H H H H H H H / / Ω X A
					( (

λw . . ϕ . . π

Acknowledgements

This work was partly supported by the Pessoa French-Portuguese project Egide-Grices 11113YM Automata, profinite semigroups and symbolic dynamics. The work of the first author was supported, in part, by Fundação para a Ciência e a Tecnologia (FCT) through the Centro de Matemática da Universidade do Porto, by FCT. The work of the second author was supported, in part, by FCT through the Centro de Matemática da Universidade do Minho. Both the first and second authors were also supported by the project PTDC/MAT/65481/2006, which is partly funded by the European Community Fund FEDER. The work leading to this paper has also been carried out within the framework of the ESF programme "Automata: from Mathematics to Applications (AutoMathA)", whose support is gratefully acknowledged.

Proof. We claim that two special factors are either equal or J-incomparable. By the hypothesis that F(w) has no infinite J-anti-chains, it follows that w has only finitely many special factors. To prove the claim, let u ω 1 zu ω 2 and v ω 1 tv ω 2 be two special factors and suppose that the latter is a factor the former. Without loss of generality, we may assume that the given expressions are actually the normal forms of these ω-words. Let x, y ∈ (Ω X A) 1 be such that u ω 1 zu ω 2 = xv ω 1 tv ω 2 y. Then, by Theorem 2.4, we may assume that x, y are rank 1 ω-words. Then, by the normal form algorithm, we must have (u 1 )z(u 2 ) = (v 1 )t(v 2 ), since (v 1 )t(v 2 ) is a crucial portion in normal form of the normal form of the product xv ω 1 tv ω 2 y, which proves the claim. The proof that w has only finitely many special ω-factors is similar.

That w has some special prefix follows from Proposition 8.5(c). Suppose that xy ω and uv ω are both special prefixes of w. Then the right infinite words xyyy • • • and uvvv • • • coincide. It is an exercise in combinatorics on words to show that, for two Lyndon words such that the square of each is a factor of a power of the other, the two words coincide. Hence v = y and, because a Lyndon word is lexicographically minimum in its conjugacy class, we must have xy m = uv n for some m, n ≥ 0, which implies that xy ω = uv ω . The argument for suffixes is dual.

We say that an infinite 1-slim pseudoword is periodic at the ends if its special prefix and suffix are special ω-factors. Corollary 8.12. Let w ∈ Ω X A be 1-slim. Then there is a factorization w = xw ′ y, where x, y ∈ X * and w ′ ∈ Ω X A is periodic at the ends.

Proof. Let xu ω and v ω y be respectively the special prefix and suffix of w. Then there are factorizations w = xu ω s = tv ω y. By equidivisibility (cf. Theorem 2.6), and since powers of u and v can only overlap if they do so in a synchronized way, in the sense explained in the proof of Lemma 8.11, taking into account that u ω is an idempotent, we conclude that there is a factorization of the form w = xu ω zv ω y. Set w ′ = u ω zv ω to obtain, by Theorem 8.7, a 1-slim pseudoword which is periodic at the ends and therefore satisfies the requirements of the corollary. Proposition 8.5 (a) may be reformulated in terms of special factors as follows.

Lemma 8.13. Let the pseudoword w ∈ Ω X A be 1-slim and periodic at the ends. Then every finite factor of w is a factor of some special factor or of some special ω-factor of w.

Proof. Taking into account Proposition 8.5(a) and (b), it suffices to observe that every bridge factor of w is a factor of some special factor of w. Suppose then that u is a bridge factor of w. By Proposition 8.5(b), u is of the form x ω yz ω , with x, y, z ∈ X + and x and z primitive, although this is not necessarily a bridge factorization. By the normal form algorithm and since u is not uniformly recurrent, the normal form of u is of the form α(β)γ(δ)ε where β is a conjugate of x, α a suffix of β, δ a conjugate of z, and ε a prefix of δ. It follows that u is a factor of β ω γδ ω , which establishes our claim.

In the absence of special factors, we can say much more. Lemma 8.14. Let w ∈ Ω X A be 1-slim and periodic at the ends. If w has no special factor, then w = u ω for some Lyndon word u ∈ X + .

Proof. Since w is periodic at the ends, it has a special prefix, whence there is a factorization w = u ω v where u is a Lyndon word. Suppose that w = u ω . Let (v n ) n be a sequence of finite words converging to v and let v n = u in v ′ n , where i n ≥ 0 is maximum. By compactness, we may assume that the sequence (v ′ n ) n converges to some pseudoword v ′ that does not admit u as a prefix. Then we also have w = u ω v ′ and so we may as well assume that u is not a prefix of v. Since the special suffix of w is also periodic, v must be infinite.

By Proposition 8.5(c), v has a factorization of the form v = xy ω z, where xy ω is the special prefix. Since u is not a prefix of xy ω and u and y are Lyndon words, the factor u ω xy ω of w is a special factor, which contradicts the hypothesis that w has no such factors. Hence we must have w = u ω .

Encoding 1-slim pseudowords

Let w ∈ Ω X A. We denote by Γ(w) the directed multigraph whose vertices are the special ω-factors of w and which has an edge ezf : e → f if z ∈ X + is such that ezf is a special factor of w. By Lemma 8.11, Γ(w) is finite if w is an infinite 1-slim pseudoword.

In this section, we show how to encode 1-slim pseudowords w as "pseudopaths" in their graphs Γ(w). For this purpose, we need to introduce pseudovarieties of categories and their relatively free profinite associated categories, which we do as succintly as possible. See [START_REF] Tilson | Categories as algebra: an essential ingredient in the theory of monoids[END_REF] for the definition of pseudovarieties Proof. Suppose that w ∈ Ω E(Γ) V is such that all its two-letter factors can be read in the graph Γ. In case w ∈ E(Γ)

+ , w itself can be read in the graph Γ as a path w ′ such that γ V (w ′ ) = w. In general, let (w n ) n be a sequence in E(Γ) + converging to w. The hypothesis on V implies that we may assume that all w n have the same two-letter factors as w. Hence, for each n there exists a path w

Now, assuming that v ∈ Ω Γ gV, u ∈ Ω E(Γ) V, and γ V (v) = xuy, then the two-letter factors of each of x, u, y can be read in Γ. By the above, it follows that there exist x ′ , u ′ , y ′ ∈ (Ω Γ gV) c such that γ V (x ′ ) = x, γ V (u ′ ) = u, and γ V (y ′ ) = y. In case x = 1, then the last letter of x and the first letter of u are consecutive edges in Γ, since their product is a two-letter factor of γ V (v). Hence x ′ u ′ is an edge in Ω Γ gV and, similarly, so is u ′ y ′ , and, therefore, also x ′ u ′ y ′ . Since γ V (v) = xuy = γ V (x ′ u ′ y ′ ), the pseudowords γ V (v) and γ V (x ′ u ′ y ′ ) have the same first letter and the same last letter in E(Γ) and therefore the edges v and x ′ u ′ y ′ begin in the same vertex and end in the same vertex. Since γ V is faithful, it follows that v = x ′ u ′ y ′ , which completes the proof of the lemma.

The following elementary observation from combinatorics on words will be useful in the sequel. Lemma 9.2. Suppose that u, v ∈ X + and k > |v| are such that v is primitive and u k is a factor of v ω . Then u is a conjugate of a power of v.

Proof. The hypothesis that u k is a factor of v ω implies that u k is a prefix of z ω for some conjugate z of v. On the other hand, as k > |v|, we have

Therefore, by Fine and Wilf's Theorem, it follows that u and z are both powers of some word y. Now, z is primitive since it is a conjugate of a primitive word. Hence y = z and u is a power of z, say u = z ℓ for some ℓ ≥ 1. Therefore u is a conjugate of v ℓ , thus proving the lemma.

Given two pseudovarieties of semigroups V and W, V * W denotes the pseudovariety generated by all semidirect products S * T with S ∈ V and T ∈ W. The semidirect products of the form V * D n have been extensively studied in [START_REF] Almeida | Finite semigroups and universal algebra[END_REF]Chapter 10] as an approach to semidirect products of the form V * D, which in turn have received even more attention [START_REF] Eilenberg | Automata, languages and machines[END_REF][START_REF] Tilson | Categories as algebra: an essential ingredient in the theory of monoids[END_REF][START_REF] Straubing | Finite semigroup varieties of the form V * D[END_REF]. We need to recall here some technology from [1, Chapter 10].

Let V be a pseudovariety and n a positive integer. Let B n denote the de Bruijn graph of order n, whose set of vertices is X n and whose set of edges is X n+1 , where axb : ax → xb whenever a, b ∈ X and x ∈ X n-1 . Recall that the Rauzy graph G n (w) of a pseudoword w, which was introduced in the proof of Theorem 6.2, consists of the subgraph of B n whose vertices and edges are factors of w.

Denote by X ≤n the set of all words u ∈ X + such that |u| ≤ n. We define a continuous mapping ΦV n using the following diagram

and whose operation is given by

, where, for a word t of length at least n + 1, Φ V n (t) is the value in Ω X n+1 V of the word over the alphabet X n+1 which reads the successive factors of length n + 1 of t;

• the arrow η V is the continuous map that sends each edge u : x → y of the category Ω Bn gV to the triple (x, γ V (u), y); • the arrow ι V is the continuous homomorphism given by [1, Theorem 10.6.12]. Since η V is continuous and the image of the subsemigroupoid generated by B n is dense in Im ι V , we have Im η V = Im ι V . On the other hand, since γ V is faithful, η V is injective. Hence η V is a homeomorphism of E(Ω Bn gV) with Im ι V , and we may define the continuous mapping ΦV n to be the composite η -1 V • ι V . It is therefore just a reinterpretation of the mapping ι V . Note that each finite word w of length at least n + 1 is mapped by ΦV n to the path which starts at the prefix i n (w) of length n, ends at the suffix t n (w) of length n, and goes through the edges given by the successive factors of length n + 1 of w.

the commutativity of the diagram [START_REF] Almeida | Subword complexity of profinite words and subgroups of free profinite semigroups[END_REF] and the fact that the homomorphisms q k (k = 1, 2, . . .) suffice to separate points of Ω Bn gA, we obtain the following implications: 3) is an embedding, it follows that λ w (w ′ ) = w, which completes the proof of the lemma. 1 is a faithful homomorphism of categories. It maps edges of Γ(w) to themselves, viewed as letters. The following result shows how we can carry the theory of ω-words from Ω E(Γ(w)) A to Ω Γ(w) gA. Proposition 9.8. Let Γ be a finite graph and let u and v be two edges of

Recall that γ

In particular, all factors of ω-paths in Ω Γ gA are again ω-paths.

Proof. The forward implication follows from Lemma 9.1 and the reverse implication is a consequence of γ A being a homomorphism.

We also define the rank of a pseudopath of Ω Γ gA to be the rank of its image under γ A and the normal form of a pseudopath to be normal form of its image under γ A .

To proceed, we need a rather technical but unsurprising lemma which requires some further notation to state.

We denote by π k the natural continuous homomorphism Ω

by changing the exponents of factors of the form z p , keeping them at least k, where z is a primitive word such that z ω is a factor of w.

but the converse is false. For instance, the converse fails for w = a ω , u = b k , and v = b k+1 , in case X has at least two distinct letters a and b.

Noting that A is local, that is gA = ℓA (cf. [START_REF] Tilson | Categories as algebra: an essential ingredient in the theory of monoids[END_REF]), there is a natural continuous homomorphism,

For a finite semigroup S, we denote by ind(S) the smallest positive integer m such that S satisfies the pseudoidentity x ω+m = x m . Lemma 9.9. Let w ∈ Ω X A be an infinite 1-slim pseudoword and let ϕ : Ω Γ(w) gA → S be a continuous homomorphism onto some S ∈ A such that the natural continuous homomorphisms Ω Γ(w) gA → Ω E(Γ(w)) K 1 and Ω Γ(w) gA → Ω E(Γ(w)) D 1 factor through ϕ. Let n = ν(w) and let k = max{ind(S) + 1, n}. Denote by µ w the restriction of λ w to Ω Γ(w) gA. Let m be the supremum of the lengths of the special bases of w. Then the following properties hold:

is a suffix of x and y ′ is a prefix of y such that |x ′ y ′ | < |xy|, then (k + 1)m > max{|x|, |y|}; in particular, there are only finitely many such pairs (x, y).

Proof. To prove (a), it suffices to observe that, since λ w maps edges of Γ(w) to elements of Ω κ X A, McCammond's solution of the word problem for Ω κ X A allows us to recover a path in Γ(w) from its image under λ w .

Since S ∈ A k-1 and gA = ℓA ⊇ ℓA k-1 , ϕ factors through a continuous homomorphism ξ : Ω Γ(w) ℓA k-1 → S. For the remainder of the proof, it will be useful to keep in mind the following commutative diagram, where the existence of the mapping ψ is asserted in (c) and ψ is defined in (f ):

Suppose that u and v are as in (b). Since Ω X A k is the quotient of the ω-semigroup Ω κ X A by the least congruence which identifies x k , x k+1 , and x ω for every x ∈ Ω κ X A, there are v 0 , v 1 , . . . , v p ∈ Ω κ X A such that v 0 = λ w (u), v p = v and, for each i ∈ {1, . . . , p}, there are factorizations v i-1 = x i y αi i z i and

, and α i , β i ∈ {k, k + 1, . . . , ω}. Proceeding inductively to prove (b), we may as well assume that p = 1, and so drop subscripts, thus assuming that there are factorizations λ w (u) = xy α z and v = xy β z, with x, z ∈ (Ω κ X A) 1 , y ∈ Ω κ X A, and α, β ∈ {k, k + 1, . . . , ω}. Suppose that y ∈ X + . Then the choice of k implies that the α ≥ k occurrences of y which are distinguished in the factorization λ w (u) = xy α z are found within the same factor of the form t ω , where t is a primitive word. In this case, we may simply take u ′ = u. Thus we may assume that y / ∈ X + . It follows that y is a rank 1 ω-word. Let y = y 0 t ω 1 y 1 • • • t ω r y r be its normal form. Then xy 0 t ω 1 , t ω r y r z ∈ Im λ w so that v = λ w (u ′ ) for some u ′ which is obtained from u by replacing the exponent α -1 by β -1 for the cycle

To establish (c), we prove a slightly stronger property. Let u, v be two edges in Ω Γ(w) gA and suppose that π k • λ w (u) = π k • λ w (v). As above, there are v 0 , v 1 , . . . , v p ∈ Ω κ X A such that v 0 = λ w (u), v p = λ w (v) and, for each i ∈ {1, . . . , p}, there are factorizations v i-1 = x i y αi i z i and

for every i, from which it follows that ϕ(u) = ϕ(v). This proves (c) and establishes the existence of the homomorphism ψ of partial semigroups. Note that π k (Im µ w ) may not be a subsemigroup of Ω κ X A k . To prove (d) and (e), suppose that u ∈ Ω Γ(w) gA and v ∈ Ω κ X A are such that

and so we assume that p = 1 and we drop the indices, so that

), the hypothesis on the factorizability of ϕ through the natural continuous homomorphisms Ω Γ(w) gA → Ω E(Γ(w)) K 1 and Ω Γ(w) gA → Ω E(Γ(w)) D 1 implies that y and t are edges with the same ends.

By (b), there exists u ′ ∈ Ω Γ(w) gA such that λ w (u ′ ) ∼ w,k xyz. Since y ∈ Im µ w , the definition of ∼ w,k and (a) imply that there exist x ′ , z ′ ∈ (Ω Γ(w) gA) c such that x ′ y ′ z ′ = u ′ , λ w (x ′ ) ∼ w,k x, and λ w (z ′ ) ∼ w,k z, where λ w is extended so as to map local identities to 1. Hence

factor of some element of π k (Im µ w ). By Lemma 9.9(g), the number of such elements is bounded by

where m is given by Lemma 9.9, which shows that R is finite.

The following is an immediate but useful observation. Lemma 9.11. Let w ∈ Ω X A be an infinite 1-slim pseudoword and let u be a factor of w. Then Ω Γ(u) gA is a closed subcategory of Ω Γ(w) gA and λ u is the restriction to Ω Γ(u) gA of λ w .

Proof. By Theorem 8.7, since u is a factor of the 1-slim pseudoword w, u is also 1-slim. On the other hand, from the definitions, we see that Γ(u) is a subgraph of Γ(w) and so Ω Γ(u) gA is a closed subcategory of Ω Γ(w) gA and it is immediate that λ u is the restriction to Ω Γ(u) gA of λ w .

A further important property of the homomorphism λ w is that it preserves the factor order in a strong sense. Lemma 9.12. Let w ∈ Ω X A be an infinite 1-slim pseudoword and suppose that there is an edge w ′ in the category Ω Γ(w) gA such that λ w (w ′ ) = w. Let u and v be edges in Ω Γ(w) gA that are factors of w ′ . Then u < J v if and only if λ w (u) < J λ w (v).

Proof. Note that, since x < J y means x ≤ J y and y ≤ J x, it suffices to show that [START_REF] Birget | Iteration of expansions-unambiguous semigroups[END_REF] u

The direct implication in [START_REF] Birget | Iteration of expansions-unambiguous semigroups[END_REF] follows immediately from the fact that λ w is a homomorphism. Conversely, assume that λ w (u) ≤ J λ w (v). Let s, t ∈ Ω X A be such that λ w (u) = sλ w (v)t. Since λ w (u) and λ w (v) are periodic at the ends, we may assume that so are s and t, with the infinite suffix of s having the same period as the infinite prefix of λ w (v) and the infinite prefix of t having the same period as the infinite suffix of λ w (v). By Theorem 8.7, s and t are 1-slim. Hence, by Lemmas 9.11 and 9.7, there exist s ′ , t ′ ∈ Ω Γ(w) gA such that λ w (s ′ ) = λ s (s ′ ) = s and λ w (t ′ ) = λ t (t ′ ) = t. Note that the matching of periods at the ends guarantees that s ′ vt ′ is an edge in the category Ω Γ(w) gA. Since λ w is a homomorphism, it follows that λ w (s ′ vt ′ ) = λ w (u). By Lemma 9.10, we deduce that s ′ vt ′ = u, which shows that u ≤ J v.

The next lemma describes in detail the encoding procedure on a pseudoword given by an ω-term. Lemma 9.13. Let w ∈ Ω κ X A be periodic at the ends and let w ′ ∈ Ω Γ(w) gA be such that λ w (w ′ ) = w. Then w ′ ∈ Ω κ Γ(w) gA. Moreover, if w ′ is an infinite pseudopath then w ′ has trivial initial and final portions if and only if so does w.

Proof. We assume w to be given by its normal form and we transform it according to the application, in order, of each of the following rules once to the parenthesized form of w:

(a) for each well-parenthesized factor of the form (u), where u / ∈ X + , replace it by (u)u; (b) for each maximal well-parenthesized occurrence of a factor of the form v(u)t, where u ∈ X + and v ∈ {(} * , replace it by (u)v(u)t, unless the occurrence in question is as a prefix or as a suffix of w; (c) for each factor of the form )(z), where z ∈ X + , replace it by (z)), unless the original factor is preceded by (z).

Once a rule has been applied to a given factor, it should not be applied again to that factor, although it may be applied to its factors. This guarantees that the procedure consisting in such application of the rules terminates. One can verify that each elementary step in the above procedure does not change the pseudoword that the ω-term represents in Ω κ X A, so that the output remains a representation of w. For condition (c), this is only true because we started with a κ-term in normal form and we first applied (a) and (b). Moreover, by induction on the rank of w, it is easy to show that, replacing in the output each factor of the form (x)y(z), where x, y, z ∈ X + by the corresponding edge (x)y(z) : (x) → (z) of the graph Γ(w), we obtain an ω-path w ′ ∈ Ω κ Γ(w) gA. Hence λ w (w ′ ) = w, which proves the lemma, in view of Lemma 9.10.

For example, for the ω-term w = (a)b a(b)c a(b), applying exhaustively each of the rules produces successively the following ω-terms where, in each step, we underline the new factors which come from or are changed by the application of the rules: The ω-path over this graph given by the proof of Lemma 9.13 is (e)f g (e)f h.

Note that, given an ω-word of rank 1 in normal form, its initial (respectively final) portion is trivial if and only if it is periodic at the corresponding end. For w ∈ Ω X A, let P (w) be the set of all normal forms, as well-parenthesized words u ∈ (X ∪ {(, )}) + , which are either of rank 0 or have trivial initial and final portions, such that ǫ(u) ∈ F(w). Note that, since F (w) = P (w) ∩ X + , if P (w) is rational then so is F (w). Lemma 9.14. Let w ∈ Ω X A be a 1-slim pseudoword that is periodic at the ends and let w ′ ∈ Ω Γ(w) gA be such that λ w (w ′ ) = w. Let L be the set of all special ω-factors of w. Then the following equalities hold:

Proof. (a) Let u ∈ P (w ′ ). Then u (as an element of Ω Γ(w) gA) is a factor of w ′ . Since λ w is a homomorphism, it follows that λ w (u) is a factor of λ w (w ′ ) = w, and since it is not a finite word, having rank at least 1, and it contains at least one special factor, it belongs to P (w) \ (L ∪ X + ). Conversely, suppose that u ∈ P (w) \ (L ∪ X + ). Then u (as an element of Ω X A), is a factor of w, that is w = xuy for some x, y ∈ (Ω X A) 1 . By Theorem 8.7, each of the pseudowords x, u, y is 1-slim and so the graphs Γ(x), Γ(u), and Γ(y) are well defined contained in Γ(w). Moreover, by definition of P (w), u is periodic at the ends and so, in case x or y are not empty factors, we may assume that they are also periodic at the ends, with the special suffix of x coinciding with the special prefix of u and the special suffix of u coinciding with the special prefix of y. By Lemma 9.7 and since u / ∈ L, there exist x ′ , y ′ ∈ (Ω Γ(w) gA) c and u ′ ∈ Ω Γ(w) gA such that λ w (x ′ ) = x, λ w (u ′ ) = u, and λ w (y ′ ) = y. The matching of special prefixes and suffixes guarantees that x ′ u ′ y ′ is an edge in Ω Γ(w) gA. Since λ w (w ′ ) = w = xuy = λ w (x ′ u ′ y ′ ) and λ w is injective on edges, we deduce that w ′ = x ′ u ′ y ′ . By Lemma 9.13, u ′ ∈ Ω κ Γ(w) gA. Hence the canonical form of u ′ belongs to P (w ′ ), which shows that u ∈ λ w P (w) .

(b) This follows from (a) and Lemma 9.10.

Main theorem

Putting together the main conclusions of the technical lemmas in the preceding section, we are now ready for the following result. Proposition 10.1. Let w ∈ Ω X A be n-slim, where n ≥ 1, periodic at the ends, and not the ω-power of a word. Then there is a unique w ′ ∈ Ω Γ(w) gA such that λ w (w ′ ) = w. Moreover, w ′ enjoys the following properties:

is infinite then so is r(w ′ ); (e) there are no infinite anti-chains of factors of w ′ of rank at most n -1. In particular, w ′ is (n -1)-slim.

Note that, for a singleton alphabet, both conditions (a) and (b) of Theorem 10.3 are trivially verified. For an alphabet X with at least two letters, there are uniformly recurrent non-periodic pseudowords w ∈ Ω X A. Since w is then J-maximal among infinite pseudowords, the very definition of uniformly recurrent pseudoword entails condition (a), whereas condition (b) fails by Theorem 6.2. We conjecture that condition (a) is always a consequence of condition (b). The following result proposes a considerable reduction in the proof of this conjecture. Proposition 10.4. Suppose that, for every finite alphabet X and every pseudoword w ∈ Ω X A such that P (w) is a rational language, there are no infinite anti-chains of factors of w of rank at most 1. Then, every pseudoword w ∈ Ω X A such that P (w) is a rational language is an ω-word.

Proof. Let w ∈ Ω X A be a pseudoword such that P (w) is a rational language. It has already been observed that the rationality of P (w) implies that the language F (w) is also rational. Note that, by Lemma 10.2, there is an upper bound on the rank of the members of P (w). Let M (w) be the least such upper bound. We proceed by induction on M (w) to show that w is an ω-word. If w is finite, then it is in particular an ω-word. Assume that w is infinite and, inductively, that, for every pseudoword v such that P (v) is rational and M (v) < M (w), v is an ω-word.

By hypothesis, w is 1-slim and infinite. Hence, by Corollary 8.12 and Proposition 10.1, w may be encoded as w = xλ w (w ′ )y for a unique edge w ′ ∈ Ω Γ(w) gA and some words x, y ∈ X * where w ′ is such that P (w ′ ) is rational. Moreover, by Proposition 10.1(c) and taking into account Lemma 9.11, the ranks of the elements of P (w ′ ) are bounded above by M -1. Hence, by the induction hypothesis, w ′ is and ω-word and, therefore, so is w. This completes the induction step and the proof of the proposition.

With a little extra effort, tracing through sections 8-10 where the anti-chain hypothesis has been used, one can actually weaken the hypothesis in Proposition 10.4 to the following condition: if P (w) is rational, then there are no infinite anti-chains of factors of w which are finite, idempotents or bridges.