Jorge Almeida

Ondřej Klíma

New decidable upper bound of the second level in the Straubing-Th érien concatenation hierarchy of star-free languages

Keywords: formal languages, regular languages, concatenation hierarchies, level two, star-free languages

In a recent paper we gave a counterexample to a longstanding conjecture concerning the characterization of regular languages of level 2 in the Straubing-Thérien concatenation hierarchy of star-free languages. In that paper a new upper bound for the corresponding pseudovariety of monoids was implicitly given. In this paper we show that it is decidable whether a given monoid belongs to the new upper bound. We also prove that this new upper bound is incomparable with the previous upper bound.

Introduction

A well-known result due to Schützenberger [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF] gives a syntactic characterization of star-free regular languages. This prompted both Eilenberg's identification of the combinatorial properties of classes of regular languages [START_REF] Eilenberg | Automata, languages and machines[END_REF], leading to a natural correspondence between varieties of languages (excluding the empty word, i.e. +-languages, or possibly including it, i.e. * -languages) and pseudovarieties (respectively of semigroups or monoids), and Brzozowski's hierarchical construction of star-free +-languages. As acknowledged by Eilenberg [START_REF] Eilenberg | Automata, languages and machines[END_REF]Chapter IX], the reason to stick to +-languages was to avoid technical difficulties with the empty word, but these were later overcome by Thérien [START_REF] Thérien | Classification of finite monoids: the language approach[END_REF] and Straubing [START_REF] Straubing | Finite semigroup varieties of the form V * D[END_REF], who also established a simple syntactic connection between the Brzozowski hierarchy and what came to be known as the Straubing-Thérien hierarchy. The hierarchies were later refined by Pin [START_REF]Algebraic tools for the concatenation product[END_REF] by introducing intermediate (half) levels whose syntactic characterization depends on a stable quasiorder rather than just a congruence.

Starting from the trivial variety of languages, the levels of the refined Straubing-Thérien hierarchy are defined inductively by alternately taking polynomial and Boolean closures. While it is decidable whether a given regular language belongs to each of the levels 0, 1/2, 1 and 3/2, decidability remains an open problem for level 2 or higher. Via Eilenberg's correspondence, for the class V 2 of all languages from the second level, the problem translates to decidability of membership of an arbitrary given finite monoid in the corresponding pseudovariety of monoids V 2 . This is considered one of the main longstanding open problems in the algebraic theory of regular languages (cf. [START_REF] Pin | Syntactic semigroups, Handbook of Formal Languages[END_REF]).

Pin and Straubing [START_REF] Pin | Monoids of upper triangular matrices, Semigroups: structure and universal algebraic problems[END_REF] showed that the languages from the second level V 2 over a finite alphabet A are the finite Boolean combinations of languages of the form

A * 0 a 1 A * 1 a 2 • • • a k A * k ,
where the a i 's are letters and the A j 's are subsets of A. Work of several authors led to the conjecture that the equality V 2 = B 1 m Sl holds [START_REF]Polynomial closure and unambiguous product[END_REF][START_REF]A conjecture on the concatenation product[END_REF][START_REF]Semigroups and languages of dot-depth 2, Automata, languages and programming[END_REF][START_REF]Semigroups and languages of dot-depth two[END_REF][START_REF] Straubing | On a conjecture concerning dot-depth two languages[END_REF], where m is the Mal'cev product [START_REF] Pin | Syntactic semigroups, Handbook of Formal Languages[END_REF]Section 6], B 1 is the pseudovariety of finite semigroups corresponding to the +-variety of languages of dot-depth one, and Sl is the pseudovariety of finite semilattices. Indeed, Straubing [START_REF]Semigroups and languages of dot-depth 2, Automata, languages and programming[END_REF][START_REF]Semigroups and languages of dot-depth two[END_REF] established that the classes contain the same 2-generated monoids and Cowan [START_REF] Cowan | Inverse monoids of dot-depth two[END_REF][START_REF]A result on the dot-depth hierarchy for inverse monoids[END_REF] that they contain the same inverse monoids, while Pin and Weil [START_REF]Polynomial closure and unambiguous product[END_REF]Theorem 5.9] proved that a similar equality holds for all half levels.

In the recent paper [START_REF] Almeida | A counterexample to a conjecture concerning concatenation hierarchies[END_REF] we disproved the equality V 2 = B 1 m Sl. We discovered certain new pseudoidentities which are satisfied by members of V 2 and we showed an example of a monoid M ∈ B 1 m Sl which does not satisfy one of these pseudoidentities. The new pseudoidentities are all those of the form u ω = u ω vu ω where u and v are pseudowords such that V 3/2 satisfies the inequality u ≤ v; here V 3/2 is the pseudovariety of ordered monoids corresponding to level 3/2 in the Straubing-Thérien hierarchy. These new pseudoidentities define a pseudovariety of finite monoids F. Now the results from [START_REF] Almeida | A counterexample to a conjecture concerning concatenation hierarchies[END_REF] can be summarized in the following way: V 2 ⊆ F, M ∈ B 1 m Sl, and M ∈ F, so that M / ∈ V 2 . This implies

B 1 m Sl ⊆ F and V 2 = B 1 m Sl.
In this paper we also provide an example of a monoid which belongs to F and does not belong to B 1 m Sl, and so we also have F ⊆ B 1 m Sl. Hence the two upper bounds B 1 m Sl and F are incomparable and we get a new tighter upper bound for the class V 2 , namely (B 1 m Sl) ∩ F. One can hope that the inclusion V 2 ⊆ (B 1 m Sl) ∩ F turns out to be an equality. This equality would solve the main problem if one can show that the membership problem for the pseudovariety (B 1 m Sl) ∩ F is decidable. The main contribution of this paper is the decidability of the membership problem for the pseudovariety F from which the decidability of the membership problem for (B 1 m Sl) ∩ F follows.

Perhaps surprisingly, the membership problem for the pseudovariety F is not easy to solve. When we want to test whether the new pseudoidentities are satisfied in a given finite monoid M the following relation plays a crucial role. For a finite monoid M we define a relation τ 3/2 (M ) ⊆ M × M by the rule (s, t) ∈ τ 3/2 (M ) if there is a pair of pseudowords u, v such that V 3/2 |= u ≤ v and an evaluation ϕ such that ϕ(u) = s, ϕ(v) = t. Now we see that M ∈ F if and only if for every (s, t) ∈ τ 3/2 (M ) we have s ω = s ω ts ω . The latter condition is easy to test whenever we know the relation τ 3/2 (M ). Unfortunately, we do not know whether it is possible to compute this relation in general. Our solution of the membership problem is based on the trick that it is enough to compute the transitive closure of τ 3/2 (M ), because the condition s ω = s ω ts ω is satisfied for all pairs (s, t) from τ 3/2 (M ) if and only if the condition is satisfied for all pairs (s, t) from the transitive closure of τ 3/2 (M ).

The paper is organized as follows. In Section 2, we recall a few preliminaries and notation. Then in Section 3 we introduce the relation τ 3/2 (M ) and some other equivalent descriptions of this relation. Section 4 is devoted to the formal definition of the new upper bound F and the trick concerning the transitive closure of the relation τ 3/2 (M ). In Section 5 we prove the difficult part of the crucial characterization of the transitive closure of the relation τ 3/2 (M ). Here we apply the Factorization Forest Theorem [START_REF] Simon | Factorization forests of finite height[END_REF]. The decidability of F is also established, which achieves the purpose of this paper. Section 6 presents an example of a monoid which shows that F ⊆ B 1 m Sl.

Preliminaries

Stable quasiorders

In this paper the key notion is stable quasiorder in monoids. Here we recall some easy observations and we fix notation. Note that in this paper a monoid is either finite or a free (profinite) monoid.

For an arbitrary set M we say that a relation R, i.e. a subset of M × M , is a quasiorder if and only if it is reflexive and transitive. Such a relation R determines an equivalence relation

R e = R ∩ R -1 = {(s, t) ∈ M × M | (s, t) ∈ R and (t, s) ∈ R} .
Then we can consider the factor set M/R e which is naturally ordered by the relation R, i.e. sR e ≤ tR e if and only if (s, t) ∈ R. We will denote this ordered set (M/R e , ≤) simply by M/R. The number of classes in M/R is called the index of R.

If we take an arbitrary relation R on M then we can consider the smallest transitive relation containing R, so-called transitive closure, namely R * = i∈N R i , where R i is the composition of i copies of R. More formally, for each i ∈ N we define

R i = {(s, t) ∈ M × M | there exist s 0 , s 1 , . . . , s i ∈ M such that s = s 0 R s 1 R s 2 R • • • R s i = t} .
Note that if the original relation R is reflexive then we have R i ⊆ R j whenever i ≤ j. This implies that for two arbitrary pairs (s 1 , s 2 ), (t 1 , t 2 ) ∈ R * there is an exponent i such that (s 1 , s 2 ), (t 1 , t 2 ) ∈ R i .

For an arbitrary monoid M we say that a relation R is stable if for all s 1 , s 2 , t 1 , t 2 ∈ M we have If R is a stable reflexive relation on a monoid M then the transitive closure R * is a stable quasiorder on M . Indeed, for each i the relation R i is a stable relation on M and the reflexivity of R implies the claim. This basic observation means that if we have a relation R on M and we want to construct the smallest stable quasiorder containing R we can first extend R to a reflexive relation, which we then use to generate a submonoid in M × M , and finally we take the transitive closure.

(s 1 , s 2 ) ∈ R and (t 1 , t 2 ) ∈ R implies (s 1 t 1 , s 2 t 2 ) ∈ R. ( 2

Free profinite monoid

According to Reiterman's Theorem [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF], pseudovarieties of algebras are defined by pseudoidentities, that is formal equalities of implicit operations. In the case of interest for this paper, implicit operations are operations whose interpretation in finite monoids commutes with homomorphisms. Reiterman's Theorem has been extended independently by Molchanov [START_REF] Molchanov | Nonstandard characterization of pseudovarieties[END_REF] (see also [START_REF]On nonstandard axiomatization of elementarily non-axiomatizable classes of discrete algebraic systems[END_REF]), via the nonstandard approach, and by Pin and Weil [START_REF]A Reiterman theorem for pseudovarieties of finite first-order structures[END_REF] to first order structures, the latter having particularly in mind pseudovarieties of ordered monoids, for which the equality (of implicit operations) is replaced by the order relation. By endowing all unordered monoids from a given pseudovariety V by all possible stable partial orders, one obtains a pseudovariety of ordered monoids, which is identified with V.

Simple examples of implicit operations are the so-called explicit operations, given by words, and the ω-power, which associates to each element s of a finite monoid its unique idempotent power s ω = s n (n > 0).

The implicit operations over a fixed finite set A can be viewed as the elements of the projective limit F A of all A-generated finite monoids, which is the structure one is led to consider when trying to identify the "most general" such monoid. Here, finite monoids are viewed as topological monoids under the discrete topology. In general, projective limits of finite monoids are called profinite monoids. They may also be characterized as compact totally disconnected monoids. It turns out that F A is the free profinite monoid on the set A, in which the discrete submonoid generated by A, whose elements are the explicit operations, is a free monoid and thus is identified with A * . Thus, elements of F A become a generalization of usual words, which prompts calling them alternatively pseudowords. See [START_REF] Almeida | Finite semigroups and universal algebra[END_REF][START_REF]Profinite semigroups and applications, Structural Theory of Automata, Semigroups, and Universal Algebra[END_REF] for details.

Denote by P A the monoid of all subsets of A under the union operation. The mapping that sends each letter a ∈ A to the singleton {a} extends to a unique continuous homomorphism α : F A → P A . Its restriction to A * is the usual content function and, more generally, a letter a ∈ A belongs to α(u) for a given pseudoword u ∈ F A if and only if there is a factorization of the form u = xay with x, y ∈ F A (cf. [1, Section 8.1]). For this reason, α is also called the content function.

Note that P A is a semilattice, i.e. a commutative and idempotent monoid. Moreover, for u, v ∈ F A , we have Sl |= u = v if and only if α(u) = α(v). For a subset B of an alphabet A we denote by [B] the set of all words over A such that their content is

B, i.e. [B] = {u ∈ A * | α(u) = B} = α -1 (B) ∩ A * . In particular, for B = ∅ we write [ ] = [∅] = {ǫ}
where ǫ is the empty word.

Regular languages and syntactic quasiorder

We recall the concept of syntactic quasiorder, which was introduced by Pin under the name syntactic order (see e.g. [START_REF] Pin | Syntactic semigroups, Handbook of Formal Languages[END_REF]).

For an arbitrary language L ⊆ A * we define relation ≤ L on A * in the following way. For u, v

∈ A * we write u ≤ L v if (∀x, y ∈ A * ) (xvy ∈ L =⇒ xuy ∈ L).
The relation ≤ L is a stable quasiorder on the monoid A * and it is called the syntactic quasiorder of L.

In this paper we deal only with regular languages, for which ≤ L has finite index. The reason is that for a regular language L there are only finitely many languages of the form

x -1 Ly -1 = {u ∈ A * | xuy ∈ L}.
We denote M L = A * /≤ L which is a finite ordered monoid, called the ordered syntactic monoid of L.

The natural projection φ

L : A * → M L is called the syntactic morphism. Note that φ L (L) is an ideal in (M L , ≤) and that φ -1 L (φ L (L)) = L. Now we consider the extension of φ L to the continuous morphism φ L : F A → M L of compact monoids. The relation on F A consisting of the pairs (u, v) such that φ L (u) ≤ φ L (v) is still denoted by ≤ L .
Note that it is a stable quasiorder on F A . Thus if we speak about syntactic quasiorder and syntactic morphism we can consider these extensions to F A .

Using the continuous morphism φ L we see that the topological closure

L of L is clopen in F A and that φ -1 L (φ L (L)) = L.
An alternative definition of the relation ≤ L is given by the next lemma, whose proof amounts to an easy exercise. Lemma 2.1 Let L be a regular language over an alphabet A and let u, v ∈ F A be pseudowords. Then the following statements are equivalent:

(i) u ≤ L v, (ii) for all x, y ∈ F A , xvy ∈ L implies xuy ∈ L, (iii) for all x, y ∈ A * , xvy ∈ L implies xuy ∈ L.

Some known results on the Straubing-Th érien hierarchy

We recall the characterizations of V 3/2 , the level 3/2 of the Straubing-Thérien hierarchy. The first is implicitly contained in [START_REF] Pin | Monoids of upper triangular matrices, Semigroups: structure and universal algebraic problems[END_REF].

Proposition 2.2 ([13, Theorem 8.8]) A language over an alphabet A is of level 3/2 if and only if it is a finite union of languages of the form

A * 0 a 1 A * 1 a 2 • • • a k A * k ,
where each A i ⊆ A and each a j ∈ A. Proposition 2.3 ([18, Theorem 8.7], [13, Theorem 8.9]) A language is of level 3/2 if and only if its ordered syntactic monoid satisfies the pseudoidentity u ω vu ω ≤ u ω for all pseudowords u, v over some finite alphabet satisfying α(u) = α(v).

The following proposition from [START_REF] Almeida | A counterexample to a conjecture concerning concatenation hierarchies[END_REF] gives new pseudoidentities for the pseudovariety V 2 . The proof is also recalled as it is quite easy.

Proposition 2.4 ([3, Proposition 2]) Let u and v be pseudowords such that

V 3/2 |= u ≤ v. Then V 2 |= u ω = u ω vu ω . Proof: Since V 2 is the Boolean closure of V 3/2 , we have V 2 |= x = y if and only if V 3/2 |= x = y, i.e. if and only if V 3/2 |= x ≤ y and V 3/2 |= y ≤ x.
From the assumption

V 3/2 |= u ≤ v, we deduce that α(u) = α(v) because Sl ⊆ V 3/2 . From Proposition 2.3, we obtain immediately V 3/2 |= u ω vu ω ≤ u ω .
When we multiply u ≤ v by u ω from both sides, we obtain

u ω uu ω ≤ u ω vu ω . Since V 3/2 |= x ω+1 = x ω , we conclude that V 3/2 |= u ω ≤ u ω vu ω . 2
3 Relations on monoids related to level 3/2

For each finite alphabet A and natural number m we denote U m (A) the set of all languages over A of the form

[A 0 ] a 1 [A 1 ] a 2 [A 2 ] • • • [A k-1 ] a k [A k ] , (3.1)
where k ≤ m, a 1 , . . . , a k ∈ A and A 0 , . . . , A k ⊆ A. Since A is finite, so is each of the sets U m (A). We denote U(A) their union over all m ≥ 0. The languages of level 3/2 over an alphabet A are exactly the finite unions of languages from U(A), because for each finite alphabet B one can express the language B * as the finite union of all languages of the form [C] with C ⊆ B, which in turn are of level 1. Now, we define a relation A m on the free profinite monoid F A in the following way:

u A m v if, for all L ∈ U m (A), v ∈ L implies u ∈ L.
Note that if u A m v for some u, v ∈ F A then the implication v ∈ L =⇒ u ∈ L is satisfied also for each language L which is a finite union of finite intersections of languages from U m (A). One can prove that such languages form a positive variety of languages. This claim is a special case of [START_REF]Algebraic tools for the concatenation product[END_REF]Theorem 5.1] or alternatively of [9, Theorem 1]. One can also prove it directly by showing that each morphic preimage and also each derivative of a language from the class U m (A) is a finite union of finite intersections of languages from U m (A). This method is used in [START_REF] Mu | Opérations polynomiales et hiérarchies de concaténation[END_REF] to prove that the polynomial closure of a variety of languages constitutes a positive variety, although the formula for morphic preimage [4, Lemma 2.2.2] is not correct. (i) Lemma 3.1 Let A be an alphabet, m be a number and u, v ∈ F A be pseudowords. Then

u A m v if and only if, for all L ∈ U m (A), u ≤ L v.
In other words A m is the intersection of all relations ≤ L for L ∈ U m (A).

Proof: Let u, v ∈ F A be such that u A m v and let L ∈ U m (A). We want to show that u ≤ L v, which is equivalent to condition (iii) in Lemma 2.1. Let x, y ∈ A * be such that xvy ∈ L and we show that also xuy ∈ L. Since the set L is open, we may consider a sequence of words (v n ) n∈N converging to v such that for each n we have xv n y ∈ L. Hence v n ∈ x -1 Ly -1 and we see that v ∈ K for K = x -1 Ly -1 . The language K is a finite union of finite intersections of languages from U m (A) and the implication

v ∈ K ⇒ u ∈ K follows from u A m v.
Thus there is a sequence of words (u n ) n∈N converging to u such that u n ∈ K = x -1 Ly -1 for each n ∈ N. Hence xu n y ∈ L and we deduce that xuy ∈ L.

On the other hand, for u, v ∈ F A and L ∈ U m (A) we have

(u ≤ L v and v ∈ L) implies u ∈ L
because we can consider condition (iii) in Lemma 2.1 with x and y empty words. This property entails the implication "⇐".

Given X ⊆ F A , write u A X v if u, v ∈ F A and v ∈ X ⇒ u ∈ X. 2
Then A X is a quasiorder in which the elements of X are minima and the remaining elements are maxima.

Lemma 3.2

The following hold for every natural number m.

(i) For each A the relation A

m is a stable quasiorder on F A .

(ii) For every continuous morphism ψ :

F A → F B we have for all u, v ∈ F A , u A m v implies ψ(u) B m ψ(v).
(iii) The equivalence relation determined by the quasiorder A m has index at most 2 |Um(A)| .

(i) The problem lies in the fact that the formula does not take into account the possibility of a letter covering several of the distinguished letters. For instance, the formula fails for the homomorphism ϕ :

a * → b * defined by ϕ(a) = b 2 , for which ϕ -1 ([ ] b [ ] b [ ]) = {a} = [ ] a [ ],
while the language given by Arfi's formula is empty, since at least one of the derivatives in the languages in the union is empty.

Proof: By Lemma 3.1, the relation A m is the intersection of all stable quasiorders ≤ L with L ∈ U m (A), and therefore it is itself a stable quasiorder, which proves (i). On the other hand, since A m is also the intersection of the quasiorders of the form A L , each of which has index 2, we obtain (iii). (ii) Let u, v ∈ F A be such that u A m v, let L ∈ U m (B), and suppose that ψ(v) ∈ L. From the continuity of ψ, we obtain the equality

ψ -1 (L) = ψ -1 (L). Now K = ψ -1 (L) ⊆ A * is a finite union of finite intersections of languages from U m (A). Since v ∈ K and u A m v we have u ∈ K. Hence ψ(u) ∈ L, which proves that ψ(u) B m ψ(v). 2
From Lemmas 3.1 and 3.2 one can also state that the ordered monoid F A / A m is a free (pro)finite ordered monoid in the pseudovariety of ordered monoids corresponding to the positive variety of languages generated by all U m (B).

By a system of relations ρ we mean an operator which determines, for each finite alphabet A, a relation ρ A on the free profinite monoid F A . E.g. for each m we have a system of relations m . We call a system of relations ρ a fully invariant system of stable quasiorders if it satisfies conditions (i) and (ii) of Lemma 3.2. If every relation ρ A has finite index in F A , then we speak of a fully invariant system of stable quasiorders of finite index.

Another example of a fully invariant system of stable quasiorders of finite index is given by the kernel of the content function α. More precisely we consider the relation ≡ A on F A given by the following rule for u, v ∈ F A :

u ≡ A v if α(u) = α(v).
Further, we define a relation A on F A as the intersection of all relations A m , i.e.

u A v if, for all L ∈ U(A), v ∈ L implies u ∈ L.
The following is an immediate consequence of Lemmas 3.1 and 3.2.

Proposition 3. [START_REF] Almeida | A counterexample to a conjecture concerning concatenation hierarchies[END_REF] The system of relations is a fully invariant system of stable quasiorders. For each alphabet A, the relation A is the intersection of all relations ≤ L for L ∈ U(A). 2

Let ϕ : F A → M be a continuous morphism to a finite monoid M . For a binary relation R on F A , we define the relation ϕ(R) on the monoid M by the rule

ϕ(R) = {(s, t) ∈ M × M | there exist u, v ∈ F A such that u R v, ϕ(u) = s and ϕ(v) = t} .
Note that if R is a stable relation on F A then ϕ(R) is a stable relation on M . But ϕ(R) need not be a quasiorder even if R is. We show that the definition of ϕ(R) does not depend on ϕ or A when we consider a fully invariant system of stable quasiorders. Lemma 3.4 Let ϕ : F A → M and β : F B → M be a pair of continuous morphisms. Further, let ρ be a fully invariant system of stable quasiorders.

(i) If β is onto then ϕ(ρ A ) ⊆ β(ρ B ).
(ii) If both ϕ and β are onto then ϕ(ρ A ) = β(ρ B ).

Proof:

The second statement follows from applying the first one twice. So, assume that β is onto and let (s, t) ∈ ϕ(ρ A ). Then by the definition of ϕ(ρ A ) we have u, v ∈ F A such that (u, v) ∈ ρ A , ϕ(u) = s, and ϕ(v) = t. Since β is onto and B * is dense in F B , we can consider for each a ∈ A a word u a ∈ B * such that β(u a ) = ϕ(a) ∈ M . Then there is a continuous morphism ψ :

F A → F B such that ψ(a) = u a for all a ∈ A, so that ϕ = β • ψ. Since ρ is fully invariant we obtain (ψ(u), ψ(v)) ∈ ρ B from (u, v) ∈ ρ A .
From the definition of β(ρ B ) we get

(s, t) = (ϕ(u), ϕ(v)) = β(ψ(u)), β(ψ(v)) ∈ β(ρ B ),
which completes the proof of the lemma.

2

Thus, we can define for each fully invariant system of stable quasiorders ρ and every finite monoid M the relation ρ M on M by taking an arbitrary onto continuous morphism ϕ : F A → M and putting ρ M = ϕ(ρ A ). In particular, we can consider the relations M and M m for each m. The relation ≡ M is sometimes known in the literature as the set of Sl-pointlike pairs of elements of M (cf. [21, Subsection 2.4.1]).

We say that we have an effective description of a finite ordered monoid if its multiplication table and its order relation are known.

Useful properties of the relations M m and M are given in the following lemma. Some of them are formulated in a more general setting. Lemma 3.5 Let ϕ : F A → M be an arbitrary onto continuous morphism and let ρ be a fully invariant system of stable quasiorders; in particular ρ M = ϕ(ρ A ). Then the following properties hold.

(i) The relation ρ M is stable.

(ii) If the equivalence relation corresponding to ρ A has finite index then we have

ρ M = (s, t) ∈ M × M | there exist u, v ∈ A * such that u ρ A v, ϕ(u) = s and ϕ(v) = t .

Moreover, if we have an effective description of the finite ordered monoid F

A /ρ A then ρ M is com- putable.
(iii) For each m we have M m+1 ⊆ M m and the relation M is the intersection of all relations M m .

Proof: (i) We already mentioned that ϕ(R) is a stable relation whenever R is a stable relation.

(ii) The inclusion "⊇" is trivial. If we take (s, t) ∈ ρ M then we have (u, v) ∈ ρ A for some u, v ∈ F A such that ϕ(u) = s and ϕ(v) = t. We denote η the natural morphism from F A to the finite ordered monoid F A /ρ A . Since ϕ -1 (s) and η -1 (η(u)) are both clopen subsets in F A which contain u ∈ F A , it follows that their intersection is also non-empty and clopen in F A . This entails that it contains some word u ′ ∈ A * . Hence we have ϕ(u ′ ) = s and (u ′ , u) ∈ ρ A (and also (u, u ′ ) ∈ ρ A ). By the same argument we obtain

v ′ ∈ A * such that ϕ(v ′ ) = t and (v, v ′ ) ∈ ρ A . Since ρ A is a transitive relation we get (u ′ , v ′ ) ∈ ρ A .
We proved the first part of (ii).

For the second part we define a relational morphism π from M to

F A /ρ A as π = η • ϕ -1 . In other words π = {(ϕ(u), η(u)) | u ∈ A * }. In fact π is a submonoid of the finite monoid M × F A /ρ A and it is generated by the set G = {(ϕ(a), η(a)) | a ∈ A}.
Since we have an effective description of the finite ordered monoid F A /ρ A we can compute π as the submonoid of the finite monoid M × F A /ρ A generated by G. Now (s, t) ∈ ρ M if and only if there exist u ρ , v ρ ∈ F A /ρ A such that u ρ ≤ v ρ and (s, u ρ ) ∈ π and (t, v ρ ) ∈ π. By the above, the latter condition on the pair (s, t) can be effectively checked.

(iii) From the inclusions A ⊆ A m+1 ⊆ A m it follows that M ⊆ M m+1 ⊆ M m . It remains to show that m≥0 M m ⊆ M . So, suppose that s, t ∈ M are such that s M m t for all m ≥ 0. Then, for each m ≥ 0 there exist u m ∈ ϕ -1 (s) and v m ∈ ϕ -1 (t) such that u m A m v m . Since the space F A is compact, there is a sequence of indices m 1 < m 2 < • • • such that each of the subsequences (u m k ) k and (v m k ) k converges to the respective limit u and v. As ϕ is continuous, we have ϕ(u) = s and ϕ(v) = t. We claim that u A v, which will establish that s M t, as required. Indeed, given a language L ∈ U m (A), consider the syntactic morphism φ L : F A → M L , which is continuous. Hence there is some k such that

m k ≥ m and φ L (u m k ) = φ L (u) and φ L (v m k ) = φ L (v). Since u m k A m k v m k and L ∈ U m (A), we conclude in particular that u m k ≤ L v m k , whence also u ≤ L v, which proves the claim.
2

Recall that we have defined the relation τ 3/2 (M ) ⊆ M × M by the rule (s, t) ∈ τ 3/2 (M ) if there are a finite set of variables X, a pair of pseudowords u, v ∈ F X such that V 3/2 |= u ≤ v, and a continuous morphism ϕ : F X → M such that ϕ(u) = s, ϕ(v) = t. We show that the inequalities satisfied in V 3/2 are exactly given by the system of relations and that the relation τ 3/2 (M ) coincides with the previous relation M .

Proposition 3.6

Let A be a finite alphabet.

(i) For each u, v ∈ F A we have

V 3/2 |= u ≤ v if and only if u A v.
(ii) For every finite monoid M we have τ 3/2 (M ) = M . Proof: (i) Let u, v ∈ F A be such that V 3/2 |= u ≤ v. Then for each L ∈ U(A) and its syntactic morphism φ L : F A → M L we have φ L (u) ≤ φ L (v), i.e. u ≤ L v. This shows that u A v by Proposition 3.3. Now, let u A v. We want to show that for each L ∈ V 3/2 (B) and its syntactic morphism φ L : F B → M L onto the ordered syntactic monoid M L of L, we have M L |= u ≤ v. It is enough to prove it for languages L ∈ U(B) because V 3/2 is the positive variety of languages generated by all U(C). So, let L ∈ U(B) with syntactic morphism φ L : F B → M L and take ψ : F A → M L an arbitrary continuous morphism. Since the syntactic morphism φ L is onto we obtain ψ( A ) ⊆ φ L ( B ) from Lemma 3.4. Thus, as we are assuming that u A v, so that (ψ(u), ψ(v)) ∈ ψ( A ), we conclude that there are

u ′ , v ′ ∈ F B such that ψ(u) = φ L (u ′ ), ψ(v) = φ L (v ′ ), and u ′ B v ′ . Proposition 3.3 yields u ′ ≤ L v ′ and we get ψ(u) = φ L (u ′ ) ≤ L φ L (v ′ ) = ψ(v) in M L . We have thus proved that M L |= u ≤ v.
(ii) We fix the finite alphabet B = M and onto continuous morphism β : F B → M given by β| B = id B and we show that

τ 3/2 (M ) = β( B ). The inclusion β( B ) ⊆ τ 3/2 (M ) follows from (i). Let (s, t) ∈ τ 3/2 (M ).
Then there are a finite set of variables X, a pair of pseudowords u, v ∈ F X such that

V 3/2 |= u ≤ v and a continuous morphism ϕ : F X → M such that ϕ(u) = s, ϕ(v) = t. Hence we have u X v from (i). Lemma 3.4 then yields (s, t) ∈ ϕ( X ) ⊆ β( B ). 2
4 New upper bound

In the first section we have defined the pseudovariety of finite monoids

F = u ω = u ω vu ω | V 3/2 |= u ≤ v .
Our goal is to solve the membership problem for F. So, for a fixed monoid M we need to test whether

s ω = s ω ts ω (4.1)
for all (s, t) ∈ τ 3/2 (M ) = M . The crucial trick in our contribution is the following lemma.

Lemma 4.1 Let R be a reflexive stable relation on a given finite monoid M . Then condition (4.1) holds for every pair (s, t) from R if and only if condition (4.1) holds for every pair (s, t) from the transitive closure of R.

Proof: Assume that condition (4.1) holds for every pair (s, t) from R. We show by induction with respect to i that condition (4.1) holds for every pair (s, t) from R i . For i = 1, this is given. Let i > 1 and (s, t) ∈ R i be an arbitrary pair. Thus there is z ∈ M such that (s, z) ∈ R i-1 and (z, t) ∈ R. Since R is a stable relation we have (s ω zs ω , s ω ts ω ) ∈ R. Condition (4.1) holds for R, hence we have

(s ω zs ω ) ω = (s ω zs ω ) ω (s ω ts ω )(s ω zs ω ) ω .
On the other hand, by the induction hypothesis, since (s, z) ∈ R i-1 , we have s ω = s ω zs ω . Hence s ω = (s ω zs ω ) ω and we get

s ω = (s ω zs ω ) ω = (s ω zs ω ) ω (s ω ts ω )(s ω zs ω ) ω = s ω (s ω ts ω )s ω = s ω ts ω .
Now since condition (4.1) holds for every pair (s, t) from R i for every i, condition (4.1) holds for all pairs (s, t) from R * = i∈N R i . The opposite implication in the statement is trivial, because R ⊆ R * .

2

If we apply this observation to our relation M then we obtain the following basic characterization of the pseudovariety F. 2

We should show that the transitive closure of M can be computed. In fact, we give an alternative characterization of this relation which is motivated by Proposition 2.3. We define

S M = {(s, s) ∈ M × M | s ∈ M } ∪ (s ω ts ω , s ω ) ∈ M × M | s ≡ M t . (4.2)
Furthermore, we denote by S M the submonoid of the monoid M × M generated by the set S M and we denote the transitive closure of the relation S M , i.e. S M * , by T M . The two following results clarify the meaning of T M . was proved by I. Simon with the upper bound 9|M | in [START_REF] Simon | Factorization forests of finite height[END_REF] and with an exponential upper bound but with easier proof in [START_REF]The product of rational languages[END_REF]. In successive papers the upper bound has been improved (see e.g. [START_REF] Kufleitner | The height of factorization forests[END_REF] for references). The most recent paper on the topic [START_REF] Kufleitner | The height of factorization forests[END_REF] establishes the upper bound 3|M | -1 in the general case and the upper bound 2|M | in the case of aperiodic semigroups, which are both optimal for the respective classes of semigroups.

In our application the exact upper bound does not play any role, we use just the existence of it. So we may as well formulate the theorem in existential form. Now we can return to our considerations. The missing part of the proof of Proposition 4.4 is the following statement. Note that, for our purposes, it is irrelevant whether an integer m as in the statement of Proposition 5.2 is computable, although from the proof below and the Factorization Forest Theorem it follows that such an integer can be indeed be computed. Proposition 5.2 Let M be a finite monoid and ϕ : A * → M be a morphism. Then there exists an integer m such that ( M m ) * ⊆ T M .

Proof: Let d be a factorization forest of finite height which is Ramseyan modulo ϕ, whose existence is ensured by Theorem 5.1. For the purpose of this proof, we could choose any strict upper bound K of the height H d of d. For definiteness, we put K = H d + 1. We prove that the inclusion in the statement holds for m = 2 K+1 . Since T M is a transitive relation it is enough to establish that M m ⊆ T M . Let s, t ∈ M and suppose that (s, t) ∈ M m . By Lemma 3.5 (ii) we can take u, v ∈ A * such that ϕ(u) = s, ϕ(v) = t and u A m v. Intuitively, we take a factorization tree of v, and in every factorization used in this tree, i.e. d(x) = (x 1 , x 2 , . . . , x n ) we keep just the first and last factors, i.e. x 1 and x n , which we further factorize and instead of the middle part (x 2 , . . . , x n-1 ) we take just the product x 2 • • • x n-1 which we do not factorize any further. Thus at the end of the process we obtain a factorization of the word v of the form v = a 1 v 1 a 2 v 2 • • • v k-1 a k where a i ∈ A and v i ∈ A * . Moreover, since h d (v) < K we have k < 2 K+1 = m. We are led to consider the language

L = [ ] a 1 [α(v 1 )] a 2 • • • a k-1 [α(v k-1 )] a k [ ] ∈ U m (A). Since v ∈ L and u A m v we have u ∈ L. Thus we can write u = a 1 u 1 a 2 u 2 • • • a k-1 u k-1 a k where the u i ∈ A * are such that α(u i ) = α(v i ) for every i = 1, . . . , k -1.
Now, if we consecutively replace v i for u i in the mentioned factorization of v, where the order of replacements is given by the structure of the factorization tree of v, then the images under φ of the corresponding pairs of words in this sequence are in the relation T M . Thus at the end of the process we obtain (s, t) = (φ(u), φ(v)) ∈ T M . This is just the underlying idea of the proof which we now proceed to make more precise.

First, we consider a full binary tree of height K, i.e. T = K i=0 {1, 2} i = {p ∈ {1, 2} * | |p| ≤ K}, where each node p ∈ T which is not a leaf, i.e. |p| < K, has left child p1 and right child p2. The root of T, i.e. the empty word over the alphabet {1, 2}, is denoted by λ. For technical reasons, we want to distinguish this empty word from the empty word over the alphabet A, which is denoted ǫ. In fact the Now, let p be not a leaf and assume that (5.1) is true for the nodes p1 and p2. We distinguish between the cases (a)-(d) in the definition of χ v which were used for the definition of χ v (p).

In case (a), we have χ v (p) = ǫ which entails χ v (pq) = ǫ for all q ∈ T such that pq ∈ T. It follows that ξ(pq) = ǫ for all such q ∈ T. Consequently ξ(p) = ǫ and (5.1) is trivially satisfied.

In case (b), we have

χ v (p) = x ∈ A, χ v (p1) = χ v (p2) = ǫ. Since ξ is similar to χ v we have ξ(p) = χ v (p) = x and ξ(p1) = ξ(p2) = ǫ. Consequently ξ(p) = χ v (p) =
x and (5.1) is again trivially satisfied.

In case (c), we have χ v (p) = ǫ which implies ξ(p) = ǫ = χ v (p). Then ξ(p) = ξ(p1)ξ(p2) and χ v (p) = χ v (p1)χ v (p2). Since ϕ(ξ(p1)), ϕ(χ v (p1)) ∈ T M and ϕ(ξ(p2)), ϕ(χ v (p2)) ∈ T M we obtain (5.1) as a consequence of the fact that T M is a stable relation on M .

In case (d), we have

χ v (p1) = x 1 , χ v (p) = x 2 • • • x n-1 and χ v (p2) = x n , and consequently χ v (p) = x = x 1 x 2 • • • x n . Moreover, ϕ(x 1 ) = ϕ(x 2 ) = • • • = ϕ(x n ) = e is an idempotent in M . Since ξ is similar to χ v we have ξ(p) = w ∈ A * such that α(w) = α(x 2 x 3 • • • x n-1 ). This means that ϕ(w) ≡ M ϕ(x 2 x 3 • • • x n-1
) = e and we have (e • ϕ(w) • e, e) ∈ S M ⊆ T M . By induction hypothesis we have ϕ(ξ(p1)), ϕ(χ v (p1)) ∈ T M , where the second coordinate is e because χ v (p1) = x 1 and ϕ(x 1 ) = e. Thus ϕ(ξ(p1)), e ∈ T M and, analogously, ϕ(ξ(p2)), e ∈ T M . Since T M is a stable quasiorder we get the following sequence of T M -related elements of M . (Here we write T M in an infix notation to make the presentation more readable.)

ϕ(ξ(p)) = ϕ(ξ(p1)) • ϕ(ξ(p)) • ϕ(ξ(p2)) T M e • ϕ(w) • e T M e = ϕ(x 1 x 2 • • • x n ) = ϕ(χ v (p)).
This achieves the proof of Lemma 5.4.

2

From Lemmas 5.3 and 5.4 it immediately follows that Proof: It is decidable whether M belongs to the pseudovariety B 1 m Sl. Indeed, Straubing's description [START_REF]Semigroups and languages of dot-depth 2, Automata, languages and programming[END_REF][START_REF]Semigroups and languages of dot-depth two[END_REF] of this upper bound is obviously decidable; alternatively using the description by the Mal'cev product, the decidability result is contained in [START_REF] Pin | Profinite semigroups, mal'cev products and identities[END_REF]. Hence the statement follows from Theorem 5.6. 2

(s, t) = (ϕ(u), ϕ(v)) = ϕ(ξ(T)), ϕ(χ v (T)) ∈ T M .

Thus we have proved the inclusion

6 The new versus the old upper bound By [START_REF] Almeida | A counterexample to a conjecture concerning concatenation hierarchies[END_REF] there is a monoid M ∈ B 1 m Sl such that M / ∈ F. This means (B 1 m Sl) ⊆ F. In this section we exhibit a monoid N ∈ F such that N / ∈ B 1 m Sl. Let A = {a, b} and L be the language of all words that after every factor a 2 contain a factor b 2 . This means that L = (A * a 2 (A * b 2 A * ) c ) c , where the exponent c stands for complementation in A * . Note that the language A * b 2 A * = A * b ∅ * bA * is of level 2. Hence (A * b 2 A * ) c is also of level 2 and consequently L is a language of level 3. We consider the syntactic monoid N = M L of this language and show that N / ∈ B 1 m Sl and that N ∈ F. Consequently, N / ∈ V 2 , so that L is not in level 2. In order to compute N , we first note that the minimal automaton of L is the one described in Figure 1(a), where 1 is the initial state and 1 and 2 are the final states. We show that N / ∈ B 1 m Sl. It is known (see e.g. (8.1) at page 732 in [START_REF] Pin | Syntactic semigroups, Handbook of Formal Languages[END_REF]) that B 1 m Sl is defined by all pseudoidentities (u ω w 1 v ω w 2 u ω ) ω w 1 v ω w 4 (u ω w 3 v ω w 4 u ω ) ω = (u ω w 1 v ω w 2 u ω ) ω (u ω w 3 v ω w 4 u ω ) ω which is satisfied in B 1 m Sl. To check that N fails the pseudoidentity (6.2), we simply evaluate x = a and y = b in N , so that the left hand side of (6.2) evaluates to a 2 b while the right hand side gives b 2 . It remains to show that N ∈ F. To prove it, in view of Theorem 5.5, it suffices to show that s ω = s ω ts ω for every pair (s, t) ∈ T N . Recall that T N is the transitive closure of the submonoid S N of the monoid N × N , where S N is defined in (4.2). We start by noting that the relation ≡ N is an equivalence relation with two classes, namely {1} and N \ {1}. Taking into account that the only idempotents in the non-singleton ≡ N -class that are not right zeros are ab and ba, we conclude that the only non-diagonal pairs in S N are the following: (b 2 , ab), (a 2 b, ab), (a 2 , ba), and (b 2 a, ba). Hence all non-diagonal pairs (s, t) ∈ T N are such that s is a right zero, and so s ω = s ω ts ω , thereby showing that N ∈ F.

The constructed monoid N and its properties established above yield the following statement. Proposition 6.1 F ⊆ B 1 m Sl. 2

From the example from [START_REF] Almeida | A counterexample to a conjecture concerning concatenation hierarchies[END_REF] and Proposition 6.1 we know that (B 1 m Sl) ∩ F is a smaller pseudovariety of monoids than each of B 1 m Sl and F. Hence (B 1 m Sl) ∩ F is currently the best known decidable upper bound for V 2 . We leave as an open question whether (B 1 m Sl) ∩ F = V 2 .

Proposition 4 . 2

 42 Let M be a finite monoid. Then M ∈ F if and only if the condition (4.1) holds for every pair (s, t) from the transitive closure of the relation M . Proof: The statement is an easy consequence of the definition of the class F, and Proposition 3.6 and Lemma 4.1.

Theorem 5 . 1 (

 51 [START_REF] Simon | Factorization forests of finite height[END_REF][START_REF]The product of rational languages[END_REF]) Let M be a finite monoid and ϕ : A * → M be a morphism. Then there exists a factorization forest of finite height which is Ramseyan modulo ϕ.

2 CombiningTheorem 5 . 5 2 FromTheorem 5 . 6 2 Corollary 5 . 7

 255256257 M m ⊆ T M and the proof of Proposition 5.2 is finished. Propositions 4.2, 4.4 and 5.2, we obtain the following characterization of our new upper bound F. The pseudovariety F consists of all finite monoids M such that s ω = s ω ts ω whenever (s, t) ∈ T M . Proof: By Proposition 4.4, which is a consequence of Proposition 5.2, the relation T M is equal to the transitive closure of M . Hence we get the statement by applying Proposition 4.2. Theorem 5.5, we obtain the following main result of this paper. It is decidable whether a given finite monoid M belongs to the pseudovariety F.Proof: It suffices to observe that the necessary and sufficient condition on a finite monoid M to belong to F given by Theorem 5.5 can be effectively checked, which follows from Lemma 4.3. It is decidable whether a given finite monoid M belongs to the pseudovariety (B 1 m Sl)∩F.

  It is then routine to compute the presentationN = a, b : aba = a, bab = b, a 3 = ba 2 = a 2 , ab 2 = b 3 = b 2and the eggbox picture of the monoid N , which is represented in Figure1(b), where the * 's mark the idempotents.

1 aFig. 1 :

 11 Fig. 1: Structural information about the language L

(6. 1 )

 1 where u, v, w i ∈ F A (i = 1, . . . , 4) are such that α(u) = α(v) = α(w 1 ) = α(w 2 ) = α(w 3 ) = α(w 4 ). We consider such a pseudoidentity where we put u = v = w 3 = w 4 = (xy) ω , w 1 = xyx 2 and w 2 = yxy 2 to obtain the pseudoidentity (xy) ω xyx 2 (xy) ω yxy 2 (xy) ω ω xyx 2 (xy) ω = (xy) ω xyx 2 (xy) ω yxy 2 (xy) ω ω (6.2)

Acknowledgements

The authors wish to thank the referees, whose comments and suggestions helped to improve readability of the paper.

The work of the first author was supported, in part, by Fundac ¸ão para a Ciência e a Tecnologia (FCT) through the Centro de Matemática da Universidade do Porto and by the FCT project PTDC/MAT/65481 /2006, which is partly funded by the European Community Fund FEDER. The work of the second author was supported, in part, by the Ministry of Education of the Czech Republic under the project MSM 0021622409 and by the Grant no. 201/09/1313 of the Grant Agency of the Czech Republic. The work leading to this paper has also been carried out within the framework of the ESF programme "Automata: from Mathematics to Applications (AutoMathA)", benefiting in particular from an exchange grant for the visit of the second author to the University of Porto.

Lemma 4.3 For each finite monoid M the relation T M is a computable stable quasiorder.

Proof: Since M is finite and ≡ is a fully invariant system of stable quasiorders of finite index, the relation ≡ M is computable by Lemma 3.5. Hence one can compute also the relation S M . Generating the submonoid S M and then the transitive closure S M * = T M is routine. The fact that T M is stable follows from a general observation concerning the transitive closure of a stable relation.

2

Proposition 4. [START_REF] Mu | Opérations polynomiales et hiérarchies de concaténation[END_REF] Let M be a finite monoid. Then the transitive closure of M is T M .

Proof:

We have S M ⊆ M by Proposition 2.3 and Proposition 3.6 (ii). By Lemma 3.5 (i), we have S M ⊆ M . Thus the transitive closure of S M , i.e. T M , is a subset of the transitive closure of M . Thus we proved that T M ⊆ ( M ) * . The reverse inclusion ( M ) * ⊆ T M is much more difficult. By Lemma 3.5 (iii) we know that M ⊆ M m for every natural number m. Hence we have ( M ) * ⊆ ( M m ) * for every m. To prove ( M ) * ⊆ T M it is therefore enough to prove that there is a number m with the property ( M m ) * ⊆ T M . This statement is contained in Proposition 5.2 in the next section. 2

Application of the Factorization Forest Theorem

To finish the proof of Proposition 4.4 we use the Factorization Forest Theorem of Imre Simon. In fact, our proof is inspired by the proof concerning polynomial closures given by Pin and Weil [START_REF]Polynomial closure and unambiguous product[END_REF] (see also [START_REF] Branco | Equations for the polynomial closure[END_REF]Section 3]). The following brief introduction to factorization forests is essentially borrowed from [START_REF]Polynomial closure and unambiguous product[END_REF]Section 4].

A factorization forest is a mapping from A 2 A * to n≥2 (A + ) n which associates to every word

The integer n is called the degree of the factorization d(x). Thus a factorization forest is a description of a recursive process to factorize words as products of letters. The height function of a factorization forest d is a mapping h d : A + → N defined by the rule

The height of a word x in a factorization forest d is simply h d (x) and the height of d is given by

For a given word x ∈ A + , we define recursively the so-called factorization tree of x as a tree with root x and direct descendants x 1 , x 2 , . . . , x n , where d(x) = (x 1 , x 2 , . . . , x n ), and the subtree with root x i being the factorization tree of x i .

Let M be a finite semigroup and let ϕ :

These definitions apply in particular if the semigroup M is a monoid. Because there is no interest in factorizations of the empty word, when we speak about a factorization forest modulo ϕ : A * → M we mean a factorization forest modulo ϕ|

The Factorization Forest Theorem states that for every morphism ϕ to a given finite semigroup M there exists a factorization forest of finite height which is Ramseyan modulo ϕ. Originally the theorem tree structure of T is not needed for the following proof, but it can help to follow it. We mention that

Now, for our propose, we define a certain order, denoted by ⊑, on the set T which is known in the literature under the names "in-order traversal" and "symmetric traversal" of the tree. For a pair of nodes p, q ∈ T we denote p, q ∈ T the longest common prefix of p and q and we put p ⊑ q if one of the following conditions is satisfied:

• p = p, q 1p ′ and q = p, q 2q ′ for some p ′ , q ′ ∈ T,

• p = p, q 1p ′ and q = p, q for some p ′ ∈ T,

• p = p, q and q = p, q 2q ′ for some q ′ ∈ T,

• p = p, q = q.

We write p ⊏ q if p ⊑ q and p = q. Taking arbitrary nodes p, q ∈ T, such that p = q, exactly one of the possibilities p ⊏ q and q ⊏ p occurs. Elementary computations check that ⊑ is also transitive. Altogether, the relation ⊑ is a linear ordering of T.

We say that a pair (χ, χ) is a compatible labeling on T if the following conditions are satisfied:

(i) both χ : T → A * and χ : T → A * are mappings;

(ii) for each leaf p ∈ T, i.e. p such that |p| = K, we have χ(p) = χ(p);

(iii) for each p ∈ T which is not a leaf, i.e. |p| < K, we have

We call the word χ(λ) ∈ A * the value of the compatible labeling on T and we also denote it χ(T).

Note that, for an arbitrary compatible labeling χ on T, we have

where p 1 ⊏ p 2 ⊏ • • • ⊏ p m-1 are all nodes from T. Indeed, one can prove by induction with respect to the tree T in bottom-up direction, that for each p ∈ T we have χ(p) = χ(pp 1 ) • • • χ(pp i ) where pp 1 ⊏ • • • ⊏ pp i are all nodes from T with the prefix p. Thus, if χ : T → A * is an arbitrary mapping, then there is a unique mapping χ such that the pair (χ, χ) forms a compatible labeling on T. For this reason a compatible labeling (χ, χ) is usually referred simply by χ.

We say that a labeling ξ on T is similar to a labeling χ on T if the following conditions are satisfied:

(i) for each p ∈ T we have α(ξ(p)) = α(χ(p));

(ii) for each p ∈ T such that χ(p) ∈ A we have ξ(p) = χ(p).

Note that this relation is not symmetric, because for some p ∈ T and a ∈ A we can have χ(p) = aaa and ξ(p) = a and in this case χ is not similar to ξ but ξ could be similar to χ.

For the word v we will define a certain compatible labeling (χ v , χ v ) on T. The definition is inductive in top-down direction with respect to the tree T and it reflects the factorization of v in the factorization forest d. First of all, we put χ v (λ) = v. Next, if for p ∈ T which is not a leaf, i.e. |p| < K, we have defined χ v (p) = x ∈ A * , then we define the values χ v (p), χ v (p1) and χ v (p2) as follows:

Finally, if for a leaf p ∈ T we have defined

Directly from the definition of the pair (χ v , χ v ) we see that it is a compatible labeling on T with the value

We have defined all technical notation and we can formulate the crucial observations which finish the proof of the proposition. Lemma 5.3 Let v ∈ A * be an arbitrary word and (χ v , χ v ) be the compatible labeling on T given by the previous definition. Let u ∈ A * be such that u A m v. Then there is a compatible labeling ξ on T which is similar to χ v and which has the value ξ(T) = ξ(λ) = u.

As v ∈ L ∈ U m (A) and u A m v, we deduce that u ∈ L and we can write u = u p1 a p1 u p2 a p2 • • • u p k a p k , where for each i = 1, . . . , k we have α(u pi ) = α(v pi ) = A i .

We define a compatible labeling ξ on T in the following way: if p / ∈ S, i.e. χ v (p) = ǫ, then we put ξ(p) = ǫ and if p ∈ S then we put ξ(p) = u p a p . Now for each p ∈ T we have α(ξ(p)) = α(χ v (p)). Moreover, if χ v (p) ∈ A then χ v (p) = a p and v p = ǫ, which entails u p = ǫ and, consequently, ξ(p) = a p = χ v (p). Thus the constructed compatible labeling ξ on T is similar to χ v . We know that ξ(λ) is the product of all ξ(p), for p ∈ T, in the order ⊏. Since ξ(p) = ǫ for p / ∈ S, this product is equal to u p1 a p1 u p2 a p2


Jakub Przybyło

Mariusz Woźniak

On a 1, 2 Conjecture

Keywords:

Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary G?

We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to use weights from 1 to 11, as well as from 1 to χ(G) 2 + 1, for an arbitrary graph G.

It might seem quite plausible in the face of the result by Addario-Berry, Dalal and Reed from [START_REF] Addario-Berry | Degree constrained subgraphs[END_REF], which says that for any fixed p ∈ (0, 1) the random graph G n,p (asymptotically) almost surely permits neighbourdistinguishing 2-edge-weighting.

In the following section we discuss the correspondence between χ(G) and τ (G). The obtained upper bound for τ (G) yields a positive verification of Conjecture 1 for the 3-colourable graphs, discussed, together with the results for the complete and 4-regular graphs, in Section 3. The last section, Sec. 4, is devoted to decreasing the general upper bound for τ (G) from 16 down to 11.

It is also worth mentioning here that our reasonings correspond with the recent study of Bača, Jendro ľ, Miller and Ryan. In (3) they introduced and studied a parameter called a total vertex irregularity strength, which is the smallest k for which there exists a k-total-weighting such that each vertex of a graph receive a different colour, i.e. w(u) + e u w(e) = w(v) + e v w(e) for each pair of vertices u, v (which do not have to be adjacent). This parameter, as well as the other mentioned in this section, may be viewed as descendants of the well known irregularity strength of a graph, see [START_REF] Chartrand | Irregular networks[END_REF] or [START_REF] Lehel | Facts and quests on degree irregular assignments[END_REF].

Due to a considerable amount of time consumed by the reviewing process, we conclude the introduction with a short list of up-to-date results in the field. All of these were however predated and (most of them) inspired by a manuscript of this paper. First Przybyło showed in [START_REF] Przybyło | A note on a neighbour-distinguishing regular graphs total-weighting[END_REF] that τ (G) ≤ 7 for all regular graphs. Then a huge break-through was a result of Kalkowski (5), who proved that τ (G) ≤ 3 for all graphs. Following and (considerably) modifying his algorithm led Kalkowski, Karoński and Pfender [START_REF] Kalkowski | Vertex-coloring edge-weightings: Towards the 1-2-3conjecture[END_REF] to decreasing the general bound of 16 to 5 in the case of edge-weightings. Also the list version of the "1,2 Conjecture" has been introduced by Wong and Zhu [START_REF] Wong | Total weight choosability of graphs[END_REF], and independently by Przybyło and Woźniak [START_REF] Przybyło | Total weight choosability of graphs[END_REF]. Among others one can read in either of these, that Proposition 9 of this paper can be extended to its list version. See also (2; 6; 11; 12; 14) for more related results.

Bounds for graphs with low chromatic number

Our aim is to show that τ (G) ≤ 2 for a simple graph G. Note that τ (G) = 1 iff there are no neighbours with the same degree in G. Since we wish to distinguish only neighbours, we may assume that G is a connected graph. Given a total-weighting w of G, let c w (v) := w(v) + e v w(e) (or c(v) for short if the weighting w is obvious) define the resulting colouring for each v ∈ V (G). We shall call c(v) a colour or a total weight of v. Surprisingly easily one may prove the following statement.

Proposition 2 τ (G) ≤ 2 for bipartite graphs.

Proof: Let us first arbitrarily assign weights 1 or 2 to the edges of G. Then put 1 or 2 at vertices so that the resulting total weights of the vertices in one colour class are even and the total weights of the vertices in the other colour class are odd.

2

Consequently, τ (G) = 2 if G is a single edge, hence our parameter makes sense for all graphs (while considering edge-weightings we must restrict ourselves to graphs without K 2 -components). Actually, similar reasoning provides us with a more general observation.

Proposition 3 Given a graph G and a set of target colours t v for all v ∈ V (G), there exists a 2-total-

weighting w of G such that c w (v) ≡ t v (mod 2) for each v ∈ V (G). 2
In this section we discuss a generalization of this statement. Consequently, we obtain an upper bound for τ (G) based on the chromatic number of G.

Lemma 4 Given a cycle C, a set of target colours t v for all v ∈ V (C), and a positive integer p ≥ 3, there exists a ( p 2 + 1)-total-weighting w of C such that c w (v) ≡ t v (mod p) for each v ∈ V (C).

Proof: Let v 1 , . . . , v n be the consecutive vertices on the cycle C, |C| = n. We may assume

t vi ∈ [3, p+2] for each i. Let V (C) = S ∪ L, where v i ∈ S if t vi ∈ [3, p 2 + 2] or v i ∈ L if t vi ∈ [ p 2 + 3, p + 2]. Denote t vi by s i if v i ∈ S or by l i if v i ∈ L, and set h = p 2 + 1.
We will use only weights 1, . . . , h. Note first, that if |L| is even, then we can easily find the required weighting. To do this, it is sufficient to use only numbers 1 and h as the weights of the edges. We start by setting w(v n v 1 ) = 1, and then assign 1 or h to the consecutive edges of C one after another, so that the two edges adjacent to v i obtain the same weights if v i ∈ S or different ones otherwise. This way, the arities (mod p) of the current total weights of the vertices in S belong to the set {1, 2} (depending on the evenness of p) and are equal to p 2 + 2 for the ones in L. Hence, it is now easy to complete the weighting using numbers from the set {1, . . . , h} as the weights of the vertices of C.

Let then |L| be odd and assume first that a vertex in L, say v 2 , has the two neighbours (v 1 and v 3 ) in S.

If s 1 -2 + s 3 -2 ≥ l 2 -h, (1)
then there exist

s 1 ∈ [1, s 1 -2], s 3 ∈ [1, s 3 -2] such that s 1 + s 3 = l 2 -h. Set w(v 1 v 2 ) = s 1 , w(v 2 ) = h and w(v 2 v 3 ) = s 3 to obtain c w (v 2 ) = l 2 . Then set w(v n v 1 ) = w(v 3 v 4 ) = 1 (we have v n v 1 = v 3 v 4 if C = C 3 )
. Since there remain an even number of weightless vertices in L, we apply the same reasoning as in the above second paragraph of the proof (by assigning weights 1 or h to the remaining edges of C first, and dealing with the vertices then) to obtain the desired weighting. On the other hand, if

p + s 1 -2h + p + s 3 -2h ≤ l 2 -1, (2)
then there exist

s 1 ∈ [p + s 1 -2h, h], s 3 ∈ [p + s 3 -2h, h] such that s 1 + s 3 = l 2 -1. Analogously as above, set w(v 1 v 2 ) = s 1 , w(v 2 ) = 1 and w(v 2 v 3 ) = s 3 to obtain c w (v 2 ) = l 2 .
Then put w(v n v 1 ) = w(v 3 v 4 ) = h and apply the technique from the second paragraph to finish the weighting. It is easy to verify that all the weights used were in the range [1, h], and that one of the inequalities (1) or (2) holds if only h ≥ 2.

Finally, we may assume that L contains two, say v 2 , v 3 , consecutive vertices of the cycle (and

|L| is odd). Let l 2 ≤ l 3 . Then h + l 2 -l 3 , l 3 -h -1 ∈ {1, . . . , h}, hence it is enough to set w(v 1 v 2 ) = 1, w(v 2 ) = h + l 2 -l 3 , w(v 2 v 3 ) = l 3 -h -1, w(v 3 ) = 1 and w(v 3 v 4 ) = h to obtain c w (v 2 ) = l 2 and c w (v 3 ) = l 3
. This time we are left with an odd number of weightless vertices in L. However, thanks to the weights assigned to v 1 v 2 and v 3 v 4 , we can again complete the weighting of C analogously as in the second paragraph.

2

Lemma 5 Given a connected graph G, u ∈ V (G), a set of target colours t v for all v ∈ V (G), and a positive integer p, there exists a

( p 2 + 1)-total-weighting w of G such that c w (v) ≡ t v (mod p) for each v ∈ V (G) \ {u}.
Proof: Given G and u ∈ V (G), we use weights 1, . . . , p 2 + 1 to obtain the desired weighting as follows. First assign weight 1 to all the edges and vertices of G. If the obtained colouring does not comply with our requirements, i.e. there exists v ∈ V (G) \ {u} with improper colour arity (not congruent to t v ) mod p, choose a path from v to u in G. By changing the weights of v and an edge from this path adjacent to v, we obtain c w (v) ≡ t v (mod p) for the resulting weighting w. Then continue traversing the path, at each step changing, if necessary, the weights of one consecutive vertex and one edge, so that at the end the colours of all the vertices from the path different from u have the proper arities mod p. Note, we do not change the total weights of the vertices that do not belong to the path. This way we have reduced the number of the vertices in V (G) \ {u} with improper colour arities. Therefore, applying the procedure described repeatedly yields the desired result.

2

Theorem 6 Given a connected graph G which is not a tree, a set of target colours t v for all v ∈ V (G), and a positive integer p ≥ 3, there exists a ( p 2 +1)-total-weighting w of G such that c w (v) ≡ t v (mod p) for each v ∈ V (G).

Proof: Since G is not a tree, it contains a subgraph C which is a cycle. Let u be an arbitrary vertex of this cycle. By Lemma 5 we may find such a weighting of G that the resulting total weights of all vertices v ∈ V (G) \ {u} are as required. Then put a temporary weight 0 at all the vertices and on each edge of C. Denote the resulting weighting of G by w , and let s v = c w (v) for v ∈ V (C). To obtain the desired weighting, it is enough to apply Lemma 4 to C with the target arities t v -s v for each vertex v of C. 2

Corollary 7 τ (G) ≤ χ(G)
2 + 1 for an arbitrary graph G.

Proof: By Theorem 6 (or Proposition 3) there is a ( χ(G) 2 + 1)-total-weighting of G such that the resulting total weights have distinct arities mod χ(G) for vertices in different colour classes. 2

In the last section of this paper we show that τ (G) ≤ 11, see Theorem 12, hence the above corollary provides us with a reasonable upper bound for graphs with χ(G) ≤ 19.

Exact values of τ (G)

By Corollary 7, we obtain the following one.

Corollary 8 Each 3-colourable graph permits a neighbour-distinguishing 2-total-weighting. 2

The next two results exemplify the fact that τ (G) not necessarily depends on χ(G). Though the following proposition is the consequence of (3), we present here our proof for the cohesion of the article.

Proposition 9 τ (G) = 2 for complete graphs.

Proof: We apply induction to show that it is enough to use 1 and 2 to obtain such a weighting of K n , that the colours of its vertices are n consecutive integers, either from n to 2n -1 or from n + 1 to 2n. The assertion is trivial for n = 2.

Assume then that n ≥ 3 and that we have found such a weighting for K n-1 . Let us add a new vertex v joining it by a single edge with each vertex of K n-1 . Note that the vertices of K n-1 carry colours from the interval [n -1, 2n -2] which are consecutive integers. If the greatest of them equals 2n -3, we put 2 at v and on all the edges incident with it. This way, the vertices of K n obtain n different colours from the interval [n + 1, 2n]. Analogously, if the greatest total weight at a vertex of K n-1 equals 2n -2, we put 1 at v and on all the edges incident with it.

2

Theorem 10 τ (G) = 2 for all 4-regular graphs.

Proof: Let G be a connected 4-regular graph. If G = K 5 or χ(G) ≤ 3, then we are done by Proposition 9 or Corollary 8, respectively. Hence, by Brooks' Theorem, we may assume χ(G) = 4. Choose the colour classes, A, B, C and D for G so that A is as large as possible, and, subject to the choice of A, B is also as large as possible, and finally, subject to the choice of A and B, C is as large as possible as well.

(v) = 10 if v ∈ A, c(v) = 6 if v ∈ D 1 , or c(v) = 8 if v ∈ D 2 .
For each edge xy ∈ E(B, C) where y ∈ C, we assign 2 to it if y has a neighbour in D 1 or 1 otherwise. Then choose the weights for each vertex u in B so that their total weights are odd. Since each of them is incident with at least one edge (in E(B, A)) with weight 2, we have c(u) ∈ {7, 9}. Now all adjacent vertices in A ∪ B ∪ D are distinguished. We will put 1 or 2 at the vertices in C and adjust the weights of some of the edges (in E(C, D 2 )) and vertices (in D 2 ), so that the colours of the vertices in A ∪ B ∪ D stay unchanged, while the vertices in C are distinguished from the others. Given an arbitrary vertex v in C, note that it is incident with at least one edge (in E(C, A)) with weight 2 and at least one with weight 1. Consider the four edges incident with v.

If After processing all the vertices v in C we obtain a weighting that is neighbour-distinguishing. 2

General bound

In (1), the following theorem was proved.

Theorem 11 Let G = (V, E) be a bipartite graph with bipartition V = X ∪ Y . For each v ∈ X, let a - v = d(v) 2 and set a + v = a - v + 1. For each v ∈ Y , fix any a - v , a + v such that a - v ≤ d(v) 2 ≤ a + v and a + v ≤ min d(v) + a - v 2 + 1, 2a - v + 1 . ( 3
)
Then there is a spanning subgraph H of G such that d H (v) ∈ {a - v , a + v } for all v ∈ V . We use it, together with the construction by Addario-Berry, Dalal and Reed from (1), to prove the following statement.

Theorem 12 Every graph permits a neighbour-distinguishing 11-total-weighting.

a v ∈ {a - v , a + v }, and for any a u ∈ {a - u , a + u }, we have c(v)+a v -(d B (v)-a v ) = c(u)+a u -(d B (u)-a u )
, where by c(v), c(u) we mean the current colours of v, u (and c(v) + a v -(d B (v) -a v ) will be the colour of v after the final step.) This is possible since each previously processed neighbour of v can prevent at most two choices for a - v and there are precisely 2d V5 (v) + 1 choices available for a - v . This set of degree choices satisfies the conditions of Theorem 11. Indeed, it is clear for the vertices in X. Also obviously a - v ≤ d B (v) 2 ≤ a + v for each v ∈ Y , so it remains to show that for all v ∈ Y , (3)

holds. Since a - v ≤ d B (v) 2 , then a + v = a - v + d B (v) 4 + 1 = d B (v) 4 + a - v 2 + a - v 2 + 1 ≤ d B (v) 2 + a - v 2 + 1. On the other hand, since a - v ≥ d B (v) 4 , then a + v = a - v + d B (v) 4 + 1 ≤ 2a - v + 1.
Thus, by Theorem 11, a subgraph H of B exists such that after performing the previously described additions and subtractions on the set of edges of B, all adjacent vertices in V 5 have distinct colours. Note that such changes may influence the total weights of the vertices in V 1 , adding 1 or 2 to some of them, or decreasing them by 1 (depending on the evenness of d B (v) and the choice of a - v or a + v ). Then however, for each such v ∈ V 1 (since 3 ≤ w(v) ≤ 10) we balance this change by subtracting 1 or 2, or by adding 1, respectively, to its weight w(v).

Note that the arities (mod 8) of colours of the vertices in V 5 remain as they are specified in Table 1 (they are even numbers), and that w(v), w(e) ∈ {1, . . . , 11} for all v ∈ V (G) and all e ∈ E(G), hence the described construction provides us with a neighbour-distinguishing 11-total-weighting.

2

  Consequently, each vertex in B ∪ C ∪ D has at least one neighbour in A, each vertex in C ∪ D has at least one neighbour in B, and each vertex in D has at least one neighbour in C. Let D = D 1 ∪ D 2 , where v ∈ D i if v has exactly i neighbours in A, and let for X, Y ⊂ V (G), E(X, Y ) denote the set of all edges between X and Y in G. We define a weighting w in the following way. Assign 2 to the edges in E(A, B ∪ C ∪ D), 1 to the edges in E(D, B ∪ C), 2 to the vertices in A ∪ D 2 , and 1 to the vertices in D 1 . This way the induced subgraph G[B ∪C] remains weightless, while c

  three of them have weight 1, hence N (v) ∩ D 1 = ∅, we set w(v) = 1, and thus c(v) = 6. If at least two of them have weight 2 and N (v) ∩ D 2 = ∅, we choose w(v) so that c(v) = 8. Finally, if at least two of them have weight 2 and there is a vertex y ∈ N (v) ∩ D 2 , then (by our construction) w(y) = 2, w(yv) = 1 and v has exactly one neighbour, say x, in B. Moreover, exactly two edges incident with v have weight 1. If c(x) = 9, we put 1 at v and get c(v) = 7. On the other hand, if c(x) = 7, set w(y) = 1, w(yv) = 2 and w(v) = 2. This way the colour of y remains unchanged, while c(v) = 9.

† The research of the first author was partially supported by MNiSW grant N N201 389134. ‡ The research of the second author was partially supported by polish ministry MNiSW 1365-8050 c 2010

Proof: Let G be a connected graph. For any ordering of a set of its vertices, let F (v i ) = {v j | v j ∈ N (v i ) and j > i} and B(v i ) = {v j | v j ∈ N (v i ) and j < i}. Call these sets the forward and the backward neighbours of v i , respectively. Choose an ordering of V (G) that maximizes k = max{j :

Put the first k vertices in V 1 and the remaining ones into a temporary set T . Note that k defined above does not decrease regardless of any reordering of the vertices within T . Moreover, d T (v) ≤ d V1 (v) for all v ∈ T . (Otherwise, we could move v to the (k + 1)'st position of the ordering and thereby create an ordering with a larger value of k.)

Next, apply the above described procedure to the induced graph G[T ], to find a set V 2 ⊆ T and a new ordering of the vertices in T . Remove the vertices of V 2 from the temporary set T . Then repeat this procedure twice more to find V 3 , V 4 and the final ordering of the vertices of G.

, has strictly fewer backward neighbours in V i than forward neighbours. By the observation at the end of the previous paragraph, for each

Consider the edges from V 5 to V 1 . Since every vertex v ∈ V 5 has at least 8d V5 (v) edges to V 1 , we can choose a subset (of these edges) where each v ∈ V 5 has exactly 8d V5 (v) edges to V 1 . Let B be the bipartite graph spanned by this reduced set of edges. Now set w(e) = 2 for each edge of G. Then assign weights between 3 and 10 to the vertices so that the resulting colour of each vertex has an arity mod 8 as specified in Table 1. We will modify this weighting

Tab. 1: Target arity for partition elements maintaining the specified colour arities mod 8 and eliminating possible internal conflicts within the sets V 1 , . . . , V 5 . Process the vertices of V 1 ∪ V 2 ∪ V 3 ∪ V 4 one after another according to the specified order. Given a vertex v ∈ V i , we add 8 to the weights of an arbitrary subset of the forward edges of v in order to distinguish its colour from the colours of its backward neighbours in V i . This is always feasible, since v has at least one more forward neighbour (not necessarily in V i ) than backward neighbours in V i .

After processing all the vertices in

for each edge e and each vertex v of G, while the arities (mod 8) of colours are as specified in Table 1. Moreover, every two neighbours from V 1 ∪ V 2 ∪ V 3 ∪ V 4 have distinct colours. In our final step, we adjust the weights of edges in B to distinguish adjacent vertices in V 5 . First we use Theorem 11 where

Then for each edge e of B we will add 1 to its weight if e ∈ E(H) or subtract 1 otherwise (we may do so, since w(e) ∈ {2, 10}). At the end we modify the weights of the vertices in V 1 so that their colours are as they were before this final step.

Define + 1. We make our choice to ensure that for any previously processed neighbour u ∈ V 5 of v, for any


which is expressible in terms of the remarkable constants ζ(3) and Li 4 ( 1 2 ) (a tetralogarithm). This and much more can be found in the papers (28; 5; 6; 11). The work (11) is a survey paper and covers much more general reduction schemes (transformation), e. g. the binary representation. The average-case analysis of these usually involves interesting numerical constants, like Wirsing's, Lévy's, Hensley's, and Vallée's constant. This is a quite challenging domain, with relations to Functional Analysis.

Continued fractions

The papers (8; 9; 10) deal with the interplay of continued fractions and combinatorics. Let us consider lattice paths, consisting of steps NORTHEAST, EAST, SOUTHEAST, starting at the origin, returning to the x-axis after n steps, and never being negative. The possible steps are denoted by the letters {a, b, c}, and an index i is additionally used when a step starts at altitude i. Thus, such a lattice path is a word in the variables {a 0 , a 1 , . . . , b 0 , b 1 , . . . , c 1 , . . . }.

The set of all paths (a formal language) is given by the infinite continued fraction

1 1 -c 0 - a 0 |b 1 1 -c 1 - a 1 |b 2 1 -c 2 - a 2 |b 3 • • •
, where (u|v)/w denotes uw -1 v, and w -1 is the quasi-inverse of languages (or formal power series).

There are many consequences of this continued fraction theorem, e. g. finite versions describe lattice paths of bounded height. Counting leads to a replacement of noncommuting variables by commuting variables. For instance, replacing all the variables by z gives the continued fraction for P Mnz n , Mn being a Motzkin number. Many combinatorial objects can be described by such lattice paths, with suitable specializations. Some examples: Set partitions (also with several restrictions), permutations (via tournament trees), involutions, etc. Some later developments can be found in (15; 20).

There are also applications to Computer Science, since several dynamic data structures can be described in this way, the simplest being a stack, but also Dictionaries, Priority queues, Linear lists, Symbol tables, and subspecies of these. Operations like Insertion, Query, Deletion have then an obvious interpretation in the path diagram. Several notions of costs can be discussed with conveniently in terms of continued fractions. These concepts were worked out in collaboration with Chéno, Franc ¸on, Puech, and Vuillemin (12; 14; 3; 13; 17; 18).

Numbertheoretic aspects of continued fractions

Gauss studied expansions of complex numbers into continued fractions. Here is an example.

35470 99661 + 315 9961 i = 1 3 - 1 5 + 1 1 3 + 7 5 i .
Consecutive digits are obtained by the recursive rule

ψ(z) = (z) + (z) ψ " (z) z -(z)
" ,

where x = x -1 2 and (z) = sign( (z) -(z) ).
The algorithm terminates if the resulting number falls into the domain {z ∈ C | 0 ≤ (z) ≤ 1 2 and |z| ≥ 1}. The average number of steps of this algorithm (in various continuous and discrete models) turns out to be linear, and the constant(s) involve the interesting quantity

X d≥1 (-1) d d 2 d X c=1 1 c 2 ,
The paper (8) has since 1998, when the previous lines were published, become a classic, and it was reprinted by Discrete Mathematics in a volume that comprised the most influential papers of the journal since its beginning [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF]. Since 1998, Flajolet's research on continued fractions has not stopped; here are the more recent papers on the subject (16; 21; 2).

It is my hope that Philippe (as I am allowed to call him) will like my own research on continued fractions as well.

We always represent our continued fractions in the form

z a 1 + z a 2 + z a 3 + z . . .
since this is convenient for our computations. It would be easy, however, to transform it, say, into the form:

zb 1 1 + zb 2 1 + zb 3 1 + zb 4 . . . Set a 0 = 1, then b i = 1 a i-1 a i
for all i = 1, 2, . . ..

Introduction

In this paper, we consider the functions

F (z) = n≥0 (-1) n z n [2n + 1] q ! q dn 2 , G(z) = n≥0 (-1) n z n [2n] q ! q dn 2 .
We use standard q-notation:

[n] q := 1 -q n 1 -q , [n] q ! := [1] q [2] q . . . [n] q .
For d = 0, 1, 2, we will find the following continued fraction expansions:

zF (z) G(z) = z a 1 + z a 2 + z a 3 + z . . .
(Replacing z by z 2 , we get z times a q-tangent function.)

zG(z) F (z) = z a 1 + z a 2 + z a 3 + z . . .
(Replacing z by z 2 , we get z 3 times a q-cotangent function.) These q-trigonometric functions are variants of Jackson's, see [START_REF] Jackson | A basic-sine and cosine with symbolic solutions of certain differential equations[END_REF].

The instance d = 0 of the q-tangent appeared in [START_REF] Prodinger | Combinatorics of geometrically distributed random variables: New q-tangent and q-secant numbers[END_REF], and the instance d = 1 in ( 23) and [START_REF] Prodinger | A continued fraction expansion for a q-tangent function: An elementary proof[END_REF]. Computer experiments indicate that, apart from trivial variations, these are the only cases where we get "nice" coefficients a k .

We treat all 6 instances in a systematic way:

We write

zF (z) G(z) = z N 0 = z a 1 + z N 1 = z a 1 + z a 2 + z N 2 = . . . ,
and set

N i = r i s i .
This means

N i = a i+1 + z N i+1 or z N i+1 = zs i+1 r i+1 = N i -a i+1 = r i s i -a i+1 = r i -a i+1 s i s i .
We can set r i = s i-1 and get the recursion

s i+1 z = s i-1 -a i+1 s i .
The initial conditions are s -1 = G(z) and s 0 = F (z).

Note that the a i 's are the unique numbers that make the s i 's power series expansions. In all instances, we are able to guess the numbers a k and the power series s k , and prove the guessed form by induction. In the cotangent case, F and G switch roles, of course. The proof by induction is a routine computation; the challenging part in this line of research is the guessing. Since the proofs are very similar, we present just one of them.

Not all of the results are new; the instance d = 0 is of course the classical case, and the instance d = 1 (tangent case) was published in (23; 27), but the other formulae are believed to be new. However, to be systematic, we collected all the results.

Tangent expansions

Here, we treat, as promised, the three instances d = 0, 1, 2.

d = 0

a k = (-1) k-1 [2k -1] q q k-1 , s k = (-1) k+1 2 q ( k+1 2 ) n≥0 z n (-1) n [2n + 2k + 1] q ! k j=1 [2n + 2j] q . 3.2 d = 1 a 2k = - [4k -1] q q (k+1)(2k-1) , a 2k+1 = [4k + 1] q q k(2k-1) . s 2k = (-1) k q k 2 n≥0 z n (-1) n [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q q n(n+2k) , s 2k+1 = (-1) k-1 q (k+1)(3k+2) n≥0 z n (-1) n [2n + 4k + 3] q ! 2k+1 j=1 [2n + 2j] q q n(n+2k+2) . 3.3 d = 2 a 2k = - [4k -1] q (1 -q 2k -q 2k+1 + q 4k-1 ) 2 (1 -q 2 ) 2 q 6k-3 , a 2k+1 = [4k + 1] q (1 -q 2 ) 2 q 2k-1 (1 -q 2k+2 -q 2k+3 + q 4k+3 )(1 -q 2k -q 2k+1 + q 4k-1 )
.

s 2k = (-1) k q 2k 2 n≥0 z n (-1) n [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q 1 + q 2n+2 (1 -q 2k )(1 -q 2k+1 ) 1 -q 2 q 2n(n+2k) , s 2k+1 = (-1) k-1 q 2k 2 +6k+3 n≥0 z n (-1) n [2n + 4k + 3] q ! 2k+1 j=1 [2n + 2j] q (1 -q 2 )q 2n(n+2k+2) 1 -q 2k+2 -q 2k+3 + q 4k+3 .

Cotangent expansions

Here are the three companion expansions related to the previous tangent expansions. [START_REF] Conrad | The Fermat cubic, elliptic functions, continued fractions, and a combinatorial excursion[END_REF].1 d = 0 a 1 = 1, and for k ≥ 1

a 2k = [4k -1] q [2k -1] 2 q [2k] 2 q q 6k-5 (1 + q) 2 , a 2k+1 = - [4k + 1] q (1 + q) 2 q 2k-2 [2k -1] q [2k] q [2k + 1] q [2k + 2] q . s 2k = (-1) k q k(2k-1) n≥0 z n (-1) n [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q [2n + 4k + 1] q + q 2 [2k] q [2k -1] q 1 + q , s 2k+1 = (-1) k q 2k 2 +5k+1 n≥0 z n (-1) n [2n + 4k + 3] q ! 2k+1 j=1 [2n + 2j] q 1 + q [2k + 1] q [2k + 2] q .
4.2 d = 1

a 1 = 1, and for k ≥ 1 a 2k = [4k -1] q [k(2k -1)] 2 q q (2k-1)(k+1) , a 2k+1 = - [4k + 1] q q k(2k-1) [k(2k -1)] q [(k + 1)(2k + 1)] q . s 2k = (-1) k q k 2 n≥0 z n (-1) n [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q [2n + 2k 2 + 3k + 1] q q n(n+2k) , s 2k+1 = (-1) k q (k+1)(3k+2) [(k + 1)(2k + 1)] q n≥0 z n (-1) n [2n + 4k + 3] q ! 2k+1 j=1 [2n + 2j] q q n(n+2k+2) .

d = 2

a 1 = 1, and for k ≥ 1

a 2k = [4k -1] q [2k -1] 2 q [2k] 2 q q 6k-3 (1 + q) 2 , a 2k+1 = - [4k + 1] q (1 + q) 2 q 2k-1 [2k -1] q [2k] q [2k + 1] q [2k + 2] q . s 2k = (-1) k q 2k 2 n≥0 z n (-1) n [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q q 2n(n+2k) [2n + 4k + 1] q + q 2n+2 [2k] q [2k -1] q 1 + q , s 2k+1 = (-1) k q 2k 2 +6k+3 (1 + q) [2k + 2] q [2k + 1] q n≥0 z n (-1) n [2n + 4k + 3] q ! 2k+1 j=1 [2n + 2j] q q 2n(n+2k+2) .
5 Proof of the cotangent case d = 1

We have by inspection that s 0 = G(z), and compute

s 1 = 1 z s -1 -s 0 = 1 z F (z) -G(z) = 1 z n≥0 z n (-1) n q n 2 [2n + 1] q ! 1 -q -1 + q 2n+1 1 -q = n≥1 z n-1 (-1) n q n 2 [2n + 1] q ! -q(1 -q 2n ) 1 -q = n≥1 z n-1 (-1) n-1 q n 2 +1 [2n -1] q ![2n + 1] q = q 2 n≥0 z n (-1) n q n(n+2) [2n + 1] q ![2n + 3] q ,
which checks, so we have the basis for our induction. And now we must show for all n that

[z n ] s 2k -a 2k+2 s 2k+1 = [z n-1 ]s 2k+2 , [z n ] s 2k-1 -a 2k+1 s 2k = [z n-1 ]s 2k+1 .
Let us start with the first one:

[z n ] s 2k -a 2k+2 s 2k+1 = (-1) k q k 2 (-1) n [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q [2n + 2k 2 + 3k + 1] q q n(n+2k) - [4k + 3] q [(k + 1)(2k + 1)] 2 q q (2k+1)(k+2) × × (-1) k q (k+1)(3k+2) [(k + 1)(2k + 1)] q (-1) n [2n + 4k + 3] q ! 2k+1 j=1 [2n + 2j] q q n(n+2k+2) = (-1) n+k q k 2 [2n + 4k + 1] q ! 2k j=1 [2n + 2j] q [2n + 2k 2 + 3k + 1] q q n(n+2k)

A generalization

Our computer calculations suggested to go for a generalization of the previous results. Note that h = 0 is the instance studied before.

The first 3 expansions are for the tangent, the following 3 are for the cotangent. We only give the quantities a k 's, but finding the expressions for the s k 's would be a good project for a student.

F h (z) = n≥0 (-1) n z n [2n + 1] q ! h j=1 [2n + 2j] q q dn 2 , G h (z) = n≥0 (-1) n z n [2n] q ! h j=1 [2n + 2j] q q dn 2 .
8.1 d = 0

a 2k = -[4k -1 + 2h] q q -2k+1-2h , a 2k+1 = [4k + 1 + 2h] q q -2k . 8.2 d = 1 a 2k = -[4k -1 + 2h] q q -2k 2 -k(2h+1)+1
, a 2k+1 = [4k + 1 + 2h] q q 2k 2 +k(2h-1) .

d = 2

a 2k = - [4k -1 + 2h] q ([k] q 2 -q 2k+1+2h [k -1] q 2 ) 2 q 6k-3+2h , a 2k+1 = [4k + 1 + 2h] q q 2k-1+2h ([k] q 2 -q 2k+1+2h [k -1] q 2 )([k + 1] q 2 -q 2k+3+2h [k] q 2 ) . 8.4 d = 0 a 1 = 1, and for k ≥ 1 a 2k = [4k -1 + 2h] q [2k -1 + 2h] 2 q [2k] 2 q q 6k-5+2h (1 + q) 2 , a 2k+1 = - [4k + 1 + 2h] q (1 + q) 2 q 2k-2 [2k -1 + 2h] q [2k] q [2k + 1 + 2h] q [2k + 2] q .
8.5 d = 1 a 1 = 1, and for k ≥ 1

a 2k = [4k -1 + 2h] q [k(2k -1 + 2h)] 2 q q (2k-1)(k+1)+2kh , a 2k+1 = - [4k + 1 + 2h] q q k(2k-1)+2kh [k(2k -1 + 2h)] q [(k + 1)(2k + 1 + 2h)] q .
8.6 d = 2

a 1 = 1, and for k ≥ 1

a 2k = [4k -1 + 2h] q [2k -1 + 2h] 2 q [2k] 2 q q 6k-3+2h (1 + q) 2 , a 2k+1 = - [4k + 1 + 2h] q (1 + q) 2 q 2k-1+2h [2k -1 + 2h] q [2k] q [2k + 1 + 2h] q [2k + 2] q .
9 More continued fraction expansions

The following expansions are not new, but they fit the same pattern, and they are very beautiful, so I decided to include them here to please Philippe. We employ the classic notation

(x; q) n := (1 -x)(1 -xq) . . . (1 -xq n-1 ). Let G(z) = n≥0
(y; q) n z n (x; q) n .

Then we have the continued fraction expansion

z G(z) = z a 1 + z a 2 + z a 3 + z a 4 + z . . .
with a 1 = 1, and for k ≥ 1

a 2k = (x; q) k-1 (1 -xq 2k-2 )(yq; q) k-1 (1 -y)(yq) k-1 ( x y ; q) k-1 (q; q) k-1 , a 2k+1 = - (1 -y)y k-1 ( x y ; q) k-1 (1 -xq 2k-1 )(q; q) k-1 (x; q) k (yq; q) k .
For the proof, we notice that a 1 is an exceptional value, and we only start the recursion with

s 0 = 1, s 1 = n≥0
(y; q) n+1 z n (x; q) n+1 .

Note that the numbers a i are uniquely determined by annihilating the constant term in s i-1 -a i+1 s i , making s i+1 a power series expansion. Our claim follows now by the following explicit formulae (for k ≥ 0)

s 2k = (-1) k q ( k 2 ) (q; q) k-1 n≥0
z n (q n+1 ; q) k-1 (yq; q) n+k (xq k ; q) n+k ,

s 2k+1 = (1 -y)y k ( x y ; q) k (-1) k q ( k+1 2 ) n≥0
z n (q n+1 ; q) k (yq k+1 ; q) n (x; q) n+2k+1 ,

provided we are able to establish these formulae by induction via the recursion. The initial values follow by inspection, and the induction step must be split into two computations, according to the parity of the indices.

s 2k -a 2k+2 s 2k+1 = (-1) k q ( k 2 ) (q; q) k-1 n≥0 z n (q n+1 ; q) k-1 (yq; q) n+k (xq k ; q) n+k - (x; q) k (qy; q) k (1 -xq 2k ) (qy) k ( x y ; q) k (1 -y)(q; q) k (1 -y)y k ( x y ; q) k (-1) k q ( k+1 2 ) n≥0 z n (q n+1 ; q) k (yq k+1 ; q) n (x; q) n+2k+1 = (-1) k q ( k 2 ) (q; q) k-1 n≥0 z n (q n+1 ; q) k-1 (yq; q) n+k (xq k ; q) n+k - (1 -xq 2k ) (q; q) k (-1) k q ( k 2 ) n≥0 z n (q n+1 ; q) k (yq; q) n+k (xq k ; q) n+k+1 = (-1) k q ( k 2 ) (q; q) k (1 -q k ) n≥0 z n (q n+1 ; q) k-1 (yq; q) n+k (xq k ; q) n+k -(1 -xq 2k ) n≥0 z n (q n+1 ; q) k (yq; q) n+k (xq k ; q) n+k+1 = (-1) k q ( k 2 ) (q; q) k n≥0 z n (q n+1 ; q) k-1 (yq; q) n+k (xq k ; q) n+k+1 (1 -q k )(1 -xq n+2k ) -(1 -xq 2k )(1 -q n+k ) = (-1) k q ( k 2 ) (q; q) k n≥0 z n (q n+1 ; q) k-1 (yq; q) n+k (xq k ; q) n+k+1 (-1)q k (1 -xq k )(1 -q n ) = (-1) k+1 q ( k+1 2 ) (q; q) k n≥0 z n (q n ; q) k (yq; q) n+k (xq k+1 ; q) n+k = zs 2k+2 ; a 2k+1 = - (1 -y)y k-1 (q; q) k-1 (yq; q) k .
Michael Joseph Schlosser has kindly informed me that the formulae could be deduced from results in [START_REF] Denis | On (a) generalization of (a) continued fraction of Gauss[END_REF].

A continued fraction of Ramanujan

This method of proof also applies to a continued fraction of Ramanujan, see [START_REF] Bhargava | On some continued fraction identities of Srinivasa Ramanujan[END_REF]. In slightly changed notation, we have

G(z) = n≥0 q ( n 2 ) (y; q) n z n (x; q) n (q; q) n ,
and H(z) = G(z)/G(qz). Then )y k-1 ( x y ; q) k-1 (-1) k-1 q ( k-1 2 ) (y; q) k , a 2k+1 = (1 -xq 2k-1 )(y; q) k (-1) k y k ( x y ; q) k q ( k+1 2 )

.

Here, the formulae follow from s 2k = y k ( x y ; q) k (-1) k q ( k 2 ) n≥0 z n (yq k ; q) n q ( n+k+1 2 ) (x; q) n+2k (q; q) n , s 2k+1 = n≥0 z n (y; q) n+k+1 q ( n+k+1 2 ) (x; q) n+2k+1 (q; q) n .

The celebrated Rogers-Ramanujan continued fraction expansion and companions

Set G(z) = n≥0 q n 2 z n (q; q) n and H(z) = G(z)/G(qz). Then a k = q -k 2 and s 2k = q k(k+1) n≥0 z n q n 2 +n(2k+1) (q; q) n , s 2k+1 = q (k+1) 2 n≥0 z n q n 2 +n(2k+2) (q; q) n .

Companion: Set H(z) = G(qz)/G(z). Then

a 2k = - (1 -q k ) 2 (1 -q) 2 q 3k-2 , a 2k+1 = - (1 -q) 2 q k-1 (1 -q k )(1 -q k+1 )
, and s 2k = n≥0 z n (1 + q n+1 1-q k 1-q )q (n+k) 2 (q; q) n , s 2k+1 = -q k (1 -q) 1 -q k+1 n≥0 z n q (n+k+1) 2 (q; q) n .

Another companion: Set H(z) = G(z)/G(q 2 z). Then a 2k = (1 -q) 2 q k-2 (1 -q k )(1 -q k+1 ) , a 2k+1 = (1 -q k+1 ) 2 (1 -q) 2 q 3k .

1 -

 1 xq 2k-2

-

(-1) n+k q k 2 [4k + 3] q [(k + 1)(2k + 1)] q [2n + 4k + 1] q ![2n + 4k + 3] q 2k j=1 [2n + 2j] q q n(n+2k+2) = (-1) n+k q (n+k) 2 [2n + 4k + 1] q ![2n + 4k + 3] q 2k j=1 [2n + 2j] q × × [2n + 4k + 3] q [2n + 2k 2 + 3k + 1] q -q 2n [4k + 3] q [(k + 1)(2k + 1)] q = (-1) n+k q (n+k) 2 [2n + 4k + 1] q ![2n + 4k + 3] q 2k j=1 [2n + 2j] q [2n] q [2n + 2k 2 + 7k + 4] q .

On the other hand

which is the same, as it should.

And now to the second one:

On the other hand,

which is the same, so that our proof is finished.

Another tangent expansion

7 The cotangent expansion as a companion

For k ≥ 0,

and a 1 = 1.

= (1 -y)y k ( x y ; q) k (-1) k q ( k+1 2 ) n≥0 z n (q n ; q) k (yq k+1 ; q) n-1 (x; q) n+2k = zs 2k+1 .

Remark.

Computer experiments indicate that we cannot add additional factors (u; q) n etc. in either numerator or denominator, as then the expressions for a i become very messy and don't factor nicely.

We note two special cases explicitly. Set y = 0, then

Another example

Set G(z) = n≥0 (z; q 2 ) n z n (zq; q 2 ) n , then we expand again z/G(z) and get: a 1 = 1, and a 2k = (-1) k-1 q ( k-1 2 ) (q; q) k-1 , a 2k+1 = (-1) k (q; q) k-1 q ( k+1 2 )

and s 2k = (-1) k q k 2 (q; q) k-1 n≥0

(q; q) n+k-1 (q; q) n ,

(q; q) n+k (q; q) n .