Dimitri Ara
email: ara@math.jussieu.fr

Franc ¸ois Métayer

The Brown-Golasiński model structure on strict ∞-groupoids revisited

Keywords: 2000 Mathematics Subject Classification. 18D05, 18G55, 55U35 ∞-category, ∞-groupoid, crossed complex, model category

We prove that the folk model structure on strict ∞-categories transfers to the category of strict ∞-groupoids (and more generally to the category of strict (∞, n)categories), and that the resulting model structure on strict ∞-groupoids coincides with the one defined by Brown and Golasiński via crossed complexes.

Introduction

In [START_REF] Brown | A model structure for the homotopy theory of crossed complexes[END_REF], Brown and Golasiński build a model structure on the category of crossed complexes. In an earlier work [START_REF] Brown | The equivalence of ∞-groupoids and crossed complexes[END_REF], Brown and Higgins established an equivalence of categories between crossed complexes and strict ∞-groupoids, whence a model structure on the latter category.

On the other hand, there is a "folk" model structure on strict ∞-categories recently discovered by Lafont, Worytkiewicz and the second author [START_REF] Lafont | A folk model structure on omega-cat[END_REF], which extends previously known model structures on categories [START_REF] Joyal | Strong stacks and classifying spaces[END_REF] and 2-categories [START_REF] Lack | A Quillen model structure for 2-categories[END_REF]. Note that this model structure is also known as the "natural" or the "categorical" model structure by various authors.

This immediately raised the questions whether the folk model structure on ∞-categories may be transferred to ∞-groupoids by inclusion, and in that case whether the Brown-Golasiński model structure may be recovered this way.

The purpose of the present work is to show that both questions have affirmative answers.

Our paper is organized as follows. In Section 1, we recall the basic definitions of strict ∞-categories and strict ∞-groupoids. Then, in Section 2, we describe the Brown-Golasiński model structure on crossed complexes and ∞-groupoids. In Section 3, we prove the transfer theorem leading to the definition of the folk model structure on strict ∞-groupoids. Our proof uses neither crossed complexes nor the existence of the Brown-Golasiński model structure. Moreover, it also applies to the category of strict (∞, n)categories for a fixed n (that is ∞-categories such that every m-arrow is invertible for m > n). Finally, in Section 4, we show that the two model structures previously defined on ∞-groupoids are in fact the same.

We thank Ronald Brown and Urs Schreiber, whose questions motivated us to go further in this work.

Strict ∞-groupoids

The purpose of this section is to introduce the definitions and notations about strict ∞-groupoids and their weak equivalences that we will use in the sequel of this paper. Our presentation is essentially the same as the one given in [START_REF] Ara | Sur les ∞-groupodes de Grothendieck et une variante ∞-catgorique[END_REF].

Globular sets

Let us denote by O the globular category, that is the category generated by the graph

0 σ 0 G G τ 0 G G 1 σ 1 G G τ 1 G G • • • σ i-1 G G τ i-1 G G i σ i G G τ i G G i + 1 σ i+1 G G τ i+1 G G . . .

under the coglobular relations

σ i+1 σ i = τ i+1 σ i and σ i+1 τ i = τ i+1 τ i , i ≥ 0.
A globular set or ∞-graph is a presheaf on O. A globular set X amounts to a diagram of sets

• • • s n+1 G G t n+1 G G X n+1 sn G G tn G G X n s n-1 G G t n-1 G G • • • s 1 G G t 1 G G X 1 s 0 G G t 0
G G X 0 satisfying the globular relations s i s i+1 = s i t i+1 and t i s i+1 = t i t i+1 , i ≥ 0.

For i ≥ j ≥ 0, we will denote by s i j and t i j the maps from X i to X j defined by

s i j = s j • • • s i-2 s i-1 and t i j = t j • • • t i-2 t i-1 .
If X is a globular set, we will call X 0 the set of objects of X and X n for n ≥ 0 the set of n-arrows or n-cells. The notation u : x → y will mean that u is an n-arrow for n ≥ 1 whose source is an (n -1)-arrow x (that is s n-1 (u) = x) and whose target is an (n -1)-arrow y (that is t n-1 (u) = y). We will say that two n-arrows u and v are parallel if either n = 0, or n ≥ 1 and u, v have same source and same target. For i ≥ j ≥ 0, if u is an i-arrow, we will often write s j (u) for s i j (u) and similarly t j (u) for t i j (u). If u and v are n-arrows, X(u, v) will denote the globular set whose k-arrows are the (n + k + 1)-arrows a of G such that s n (a) = u and t n (a) = v. In particular, X(u, v) 0 is the set of (n + 1)-arrows a : u → v in X.

Strict ∞-categories

An ∞-precategory is a globular set C endowed with maps * i j :

(X i , s i j ) × X j (t i j , X i ) → X i , i > j ≥ 0, k i : X i-1 → X i , i ≥ 1, such that 1. for every (u, v) in (X i , s i j ) × X j (t i j , X i ) with i > j ≥ 0, we have s i-1 (u * i j v) = s i-1 (v), j = i -1 s i-1 (u) * i-1 j s i-1 (v), j < i -1 ;
2. for every (u, v) in (X i , s i j ) × X j (t i j , X i ) with i > j ≥ 0, we have

t i-1 (u * i j v) = t i-1 (u), j = i -1 t i-1 (u) * i-1 j t i-1 (v), j < i -1 ;
3. for every u in X i with i ≥ 0, we have

s i k i+1 (u) = u = t i k i+1 (u).
For i ≥ j ≥ 0, we will denote by k j i the map from X j → X i defined by

k j i = k i • • • k j+2 k j+1 .
If u and v are n-arrows for n ≥ 1 of an ∞-precategory, we will often write u * k v for u * n k v. If u is an n-arrow, we will often write 1 u for the iterated identity k n m (u) in a dimension m ≥ n clear by the context. Definition 1.1. A strict ∞-category is an ∞-precategory X such that the following axioms are satisfied:

1. Associativity for every (u, v, w) in (X i , s i j ) × X j (t i j , X i , s i j ) × X j (t i j , X i ) with i > j ≥ 0, we have (u * j v) * j w = u * j (v * j w); 2. Exchange law for every (u, u ′ , v, v ′ ) in (X i , s i j ) × X j (t i j , X i , s i k ) × X k (t i k , X i , s i j ) × X j (t i j , X i ), with i > j > k ≥ 0, we have (u * j u ′ ) * k (v * j v ′ ) = (u * k v) * j (u ′ * k v ′ );
3. Units for every u in X i with i ≥ 1 and every j such that i > j ≥ 0, we have

u * j 1 s j (u) = u = 1 t j (u) * j u;
4. Functoriality of units for every (u, v) in (X i , s i j )× X j (t i j , X i ) with i > j ≥ 0, we have the following equality between (i + 1)-arrows:

1 u * j v = 1 u * j 1 v .
A morphism of strict ∞-categories or ∞-functor is a morphism of globular sets compatible with the maps * i j and k i .

We will denote by ∞-Cat the category of ∞-categories. This category is a full reflexive subcategory of the presheaf category of globular sets. Moreover, it is stable under filtered colimits. Hence, by Theorem 1.46 of [START_REF] Adámek | Locally presentable and accessible categories[END_REF], ∞-Cat is locally presentable.

Note that if u and v are two n-arrows of a strict ∞-category C, the globular set C(u, v) inherits a structure of strict ∞-category.

Strict ∞-groupoids

Let C be a strict ∞-category and u an i-arrow for i ≥ 1. For j such that 0 ≤ j < i, a * i j -inverse v of u is an i-arrow such that s j (v) = t j (u) and t j (v) = s j (u), satisfying

u * j v = 1 t j (u) and v * j u = 1 s j (u) .
It is easy to see that if it exists, such an inverse is unique. For i > j ≥ 0, we will say that C admits * i j -inverses if every i-arrow of C admits a * i j -inverse.

Definition 1.2. A strict ∞-groupoid is a strict ∞-category which admits * i j -inverses for every i > j ≥ 0. We will denote by ∞-Grp the full subcategory of ∞-Cat whose objects are strict ∞-groupoids.

Let n ≥ 0. A strict (∞, n)-category is a strict ∞-category which admits * i j -inverses for every i > j ≥ n. We will denote by (∞, n)-Cat the full subcategory of ∞-Cat whose objects are strict (∞, n)-categories. Note that for n = 0 we recover the category of strict ∞-groupoids.

The same argument as for ∞-Cat shows that ∞-Grp is a locally presentable category.

If G is a strict ∞-groupoid and u is an i-arrow of G for i ≥ 1, we will denote by w i j (u) or simply by w j (u) the * i j -inverse of u and by u -1 the * i i-1 -inverse. Note that if u and v are two n-arrows of a strict ∞-groupoid G, the strict ∞-category G(u, v) is a strict ∞-groupoid. Proposition 1.3. Let C be a strict ∞-category. Then the following assertions are equivalent:

1. C is a strict ∞-groupoid; 2. C admits * i i-1 -inverses for every i ≥ 1;

3. C admits * i 0 -inverses for every i ≥ 1;

4. for all i ≥ 1, there exists j satisfying 0 ≤ j < i such that C admits * i j -inverses.

Proof. By induction, it suffices to show that for every i > j > k ≥ 0, if C admits * j kinverses, then C admits * i k -inverses if and only if it admits * i j -inverses. By using the fact that the 2-graph

C i s i j G G t i j G G C j s j k G G t j k G G C k
has a natural structure of 2-category, one can assume that k = 0, j = 1 and i = 2. The result is thus a consequence of the following lemma.

Lemma 1.4. Let C be a 2-category whose 1-arrows are invertible. Then a 2-arrow is invertible for horizontal composition (i.e., * 2 0 ) if and only if it is invertible for vertical composition (i.e., * 2 1 ).

Proof. Let a : u → v be a 2-arrow. Suppose a admits a horizontal inverse a * . Then v * 0 a * * 0 u is a vertical inverse. Conversely, suppose a admits a vertical inverse a -1 . Then v -1 * 0 a -1 * 0 u -1 is a horizontal inverse.

Weak equivalences of strict ∞-groupoids

Let G be a strict ∞-groupoid. An n-arrow u of G is homotopic to another n-arrow v if there exists an (n + 1)-arrow from u to v. This implies that the arrows u and v are parallel. If u is homotopic to v, we will write u ∼ v. The relation ∼ is an equivalence relation on G n : the properties with respect to source and target of the maps k n+1 , w n n-1

and * n n-1 imply respectively that ∼ is reflexive, symmetric and transitive. Let us denote by G n the quotient of G n by ∼. The composition

* n n-1 : G n × G n-1 G n → G n induces a map * n n-1 : G n × G n-1 G n → G n
, thanks to the properties with respect to source and target of the composition * n+1 n-1 . For n ≥ 1, we can thus define a groupoid ̟ n (G) whose objects are (n -1)-arrows of G and whose morphisms are elements of G n . It is clear that ̟ n defines a functor from the category of strict ∞-groupoids to the category of groupoids.

Definition 1.5. The set of connected components of G is π 0 (G) = π 0 (̟ 1 (G)) = G 0 .
For n ≥ 1 and x an object of G, the n-th homotopy group of G at x is

π n (G, x) = π 1 (̟ n (G), 1 x ) = Aut ̟n(G) (1 x ).
By functoriality of the ̟ n 's, π 0 induces a functor from the category of strict ∞-groupoids to the category of sets, and π n , for n ≥ 1, induces a functor from the category of pointed strict ∞-groupoids to the category of groups. By the Eckmann-Hilton argument, the groups π n (G, x) are abelian for n ≥ 2. More generally, if u and v are two (n -1)-arrows for n ≥ 1 we set

π n (G, u, v) = Hom ̟n(G) (u, v) and π n (G, u) = π n (G, u, u). Definition 1.6. A morphism f : G → H of strict ∞-groupoids is a weak equivalence of strict ∞-groupoids if the map π 0 (f ) : π 0 (G) → π 0 (H) is a bijection and if for all n ≥ 1 and all object x of G, the morphism π n (f, x) : π n (G, x) → π n (H, f (x)
) is a group isomorphism. We will denote by W gr the class of such weak equivalences. Proposition 1.7. Let f : G → H be a morphism of strict ∞-groupoids. The following conditions are equivalent:

1. f is a weak equivalence of strict ∞-groupoids; 2. π 0 (f ) : π 0 (G) → π 0 (H) is a bijection and for all n ≥ 1 and every (n -1)-arrow u of G, f induces a bijection π n (G, u) → π n (H, f (u)); 3. ̟ 1 (f ) : ̟ 1 (G) → ̟ 1 (H)
is an equivalence of categories and for all n ≥ 2 and every pair (u, v) of parallel (n -1)-arrows of G, f induces a bijection

π n (G, u, v) → π n (H, f (u), f (v)); 4. ̟ 1 (f ) : ̟ 1 (G) → ̟ 1 (H)
is full and essentially surjective, and for all n ≥ 2 and every pair (u, v) of parallel (n -1)-arrows of G, f induces a surjection

π n (G, u, v) → π n (H, f (u), f (v)).
Proof. 1 ⇒ 2) The case n = 1 is obvious. Let n ≥ 2 and let u be an (n -1)-arrow of G.

Set x = s 0 (u). The map π n (G, x) → π n (G, u)
which sends an n-arrow a : 1 x → 1 x to the n-arrow 1 u * 0 a : u → u, is an isomorphism. Moreover f commutes with this isomorphism, that is the square

π n (G, x) G G π n (G, u) π n (H, f (x)) G G π n (H, f (u)) is commutative. The map π n (G, u) → π n (H, f (u)) is thus a bijection for n ≥ 2.
2 ⇒ 3) Let n ≥ 1 and let u, v be two parallel (n -1)-arrows of G. Suppose there exists an n-arrow a : u → v in G. The map

π n (G, u) → π n (G, u, v)
which sends an n-arrow b : u → u to the n-arrow a * n-1 b : u → v, is a bijection. Moreover f commutes with this bijection, that is the square

π n (G, u) G G π n (G, u, v) π n (H, f (u)) G G π n (H, f (u), f (v))
is commutative.

Thus to conclude it suffices to show that if there exists an n-arrow b : 3 ⇒ 4) Obvious.

f (u) → f (v) in H, then there exists an n-arrow a : u → v in G. It is clear when n = 1 by injectivity of π 0 (f ). Let n ≥ 2 and let b : f (u) → f (v) be an n-arrow of H. Set x = s n-2 (u). The arrow 1 f (u) -1 * n-2 b is an n-arrow of H from 1 f (x) : f (x) → f (x) to f (u) -1 * n-2 f (v) : f (x) → f (x). Since the map π n-1 (G, x) → π n-1 (H, f (x)) is injective, there exists an n-arrow a ′ of G from 1 x to u -1 * n-2 v. Then a = 1 u * n-2 a ′ is an n-arrow of G from u to v. 3 ⇒ 1) Obvious. 4 ⇒ 3) Let n ≥ 1,
2 The Brown-Golasiński model structure

In [START_REF] Brown | A model structure for the homotopy theory of crossed complexes[END_REF], Brown and Golasiński introduce a model category structure on the category of crossed complexes. By the equivalence of categories between crossed complexes and strict ∞-groupoids constructed in [START_REF] Brown | The equivalence of ∞-groupoids and crossed complexes[END_REF], this model structure induces a model structure on strict ∞-groupoids. The purpose of this section is to describe this model structure.

Crossed complexes

Let us denote by Grp the category of groups and by CGrp ≥2 the category of homological complexes of (not necessarily commutative) groups in dimension greater or equal to 2, that is of sequences of morphisms of groups

• • • → C n dn -→ C n-1 → • • • → C 3 d 3 -→ C 2
such that for every n ≥ 4, we have d n-1 d n = 1, where 1 denotes the unit element of C n-2 . We have an inclusion functor i 2 : Grp → CGrp ≥2 which sends a group G to the complex concentrated in degree 2 on G.

Let C ≤1 be a groupoid. We will denote by C 0 its set of objects and by C 1 (x, y) the set of morphisms from an object x to an object y in C ≤1 . Let C 1 : C ≤1 → Grp be the functor defined in the following way: an object x of C ≤1 is sent to the group

C 1 (x) = C 1 (x, x); a morphism u : x → y of C ≤1 is sent to the morphism of conjugation by u, i.e., C 1 (x) → C 1 (y) v → uvu -1 . Definition 2.1. A precrossed complex consists of • a groupoid C ≤1 ; • a functor C ≥2 : C ≤1 → CGrp ≥2 ; • an augmentation of C ≥2 over C 1 , that is a natural transformation d 2 : C ≥2 → i 2 C 1 .
Explicitly, a precrossed complex is given by

• for every x in C 0 , a complex C ≥2 (x) = • • • → C n (x) dn -→ C n-1 (x) → • • • → C 3 (x) d 3 -→ C 2 (x); • for every x in C 0 , a morphism d 2 : C 2 (x) → C 1 (x);
• for every n ≥ 2 and every morphism u :

x → y of C ≤1 , a morphism C n (x) → C n (y)
of groups functorial in u, such that for every morphism u :

x → y of C ≤1 , the diagram G G C n (x) dn G G C n-1 (x) G G • • • G G C 2 (x) d 2 G G C 1 (x) G G C n (y) dn G G C n-1 (y) G G • • • G G C 2 (y) d 2 G G C 1 (y),
where

C 1 (x) → C 1 (y) is the conjugation by u, is commutative.
If C is a precrossed complex we will denote by C(x) the augmented complex

• • • → C n (x) dn -→ C n-1 (x) → • • • → C 3 (x) d 3 -→ C 2 (x) d 2 -→ C 1 (x).
If u : x → y is a morphism of C ≤1 and n ≥ 1, we will call the map C n (x) → C n (y) the action of u on C n (x). In particular, an element of C 1 (x) acts on C n (x) for all n ≥ 1.

Definition 2.2. A precrossed complex C is a crossed complex if for all x in C 0 the following conditions are satisfied:

• for every n ≥ 3, the group C n (x) is abelian;

• for every u in C 2 (x), the element d 2 (u) of C 1 (x) acts
by conjugation by u on C 2 (x);

trivially on C n (x) for n ≥ 3.

Definition 2.3. Let C and D be two crossed complexes. A morphism of crossed complexes f : C → D consists of

• a functor f ≤1 : C ≤1 → D ≤1 ; • a natural transformation f ≥2 : C ≥2 → D ≥2 f ≤1 ,
such that f ≥2 is compatible with the augmentation, i.e., the square

C ≥2 d 2 G G D ≥2 f ≤1 d 2 f ≤1 i 2 C 1 G G i 2 D 1 f ≤1 is commutative.
Explicitly, a morphism f : C → D is given by

• a functor f ≤1 : C ≤1 → D ≤1 ;
• for every n ≥ 2 and every x in C 0 , a group morphism

f n : C n (x) → D n (f 0 (x))
, where f 0 denotes the restriction of f ≤1 to objects, such that for every x in C 0 , the diagram

G G C n (x) fn dn G G C n-1 (x) f n-1 G G • • • G G C 1 (x) f 1 G G D n (f 0 (x)) dn G G D n-1 (f 0 (x)) G G • • • G G D 1 (f 0 (x)),
where f 1 denotes the restriction of f ≤1 to C 1 (x), is commutative. We will often simply write f for f n . We will denote the category of crossed complexes by CrC .

The equivalence with strict ∞-groupoids

Let G be a strict ∞-groupoid. One can associate to G a precrossed complex C in the following way:

• the groupoid C ≤1 is the 1-truncation of G obtained from G by throwing out the n-arrows for n ≥ 2;

• C n (x) is the set of n-arrows u of G whose source is an iterated unit of an object, that is such that there exists an object x of G such that s n-1 (u) = 1 x ;

• the group law on C n (x) is induced by the composition

* n 0 : G n × G 0 G n → G n ; • d n : C n (x) → C n-1 (x) is induced by the target map t n-1 : G n → G n-1 ; • if u : x → y is a morphism in C ≤1 and v a morphism in C n (x) for n ≥ 2, the action of u on v is u * 0 v * 0 w 0 (u).
This precrossed complex is a crossed complex (see paragraph 3 of [START_REF] Brown | The equivalence of ∞-groupoids and crossed complexes[END_REF]). Moreover this construction defines a functor A : ∞-Grp → CrC.

Theorem 2.4 (Brown-Higgins). The functor A : ∞-Grp → CrC is an equivalence of categories.

Proof. See Theorem 4.1 of [START_REF] Brown | The equivalence of ∞-groupoids and crossed complexes[END_REF].

The model structure on crossed complexes

Definition 2.5. Let C be a crossed complex. The set of connected components of C is

π 0 (C) = π 0 (C ≤1 ).
For x in C 0 , the fundamental group of C at x is

π 1 (C, x) = Coker(d 2 : C 2 (x) → C 1 (x)),
and for n ≥ 2, the n-th homotopy group of C at x is

π n (C, x) = H n (C(x)).
It is clear that π 0 defines a functor from the category of crossed complexes to the category of sets and that for n ≥ 1, π n defines a functor from the category of pointed crossed complexes to the category of groups. Definition 2.6. A morphism f : C → D of crossed complexes is a weak equivalence of crossed complexes (see [START_REF] Brown | A model structure for the homotopy theory of crossed complexes[END_REF]) if the map π 0 (f ) : π 0 (C) → π 0 (D) is a bijection and if for every x in C 0 and every n ≥ 1, the morphism π n (f, x) : π n (C, x) → π n (D, f (x)) is an isomorphism. Definition 2.7. Let f : C → D be a morphism of crossed complexes. The morphism f is a trivial fibration of crossed complexes (see Proposition 2.2 (ii) of [START_REF] Brown | A model structure for the homotopy theory of crossed complexes[END_REF]) if the following conditions are satisfied:

• for every y in D 0 , there exists x in C 0 such that f (x) = y;

• for every x, y in C 0 and every morphism v : f (x) → f (y) in D ≤1 , there exists a morphism u : x → y in C ≤1 such that f (u) = v;

• for every n ≥ 2, x in C 0 , t in C n-1 (x) and every v in D n (f (x)) such that d n (v) = f (t), there exists u in C n (x) such that d n (u) = t and f (u) = v.
Theorem 2.8 (Brown-Golasiński). The weak equivalences and trivial fibrations of crossed complexes define a model category structure on the category of crossed complexes.

Proof. See Theorem 2.12 of [START_REF] Brown | A model structure for the homotopy theory of crossed complexes[END_REF].

The model structure on strict ∞-groupoids

One obtains a model category structure on strict ∞-groupoids by transferring the model structure on crossed complexes defined in the previous section via the equivalence of categories A : ∞-Grp → CrC. We will call this model structure the Brown-Golasiński model structure. A morphism f of strict ∞-groupoids is a weak equivalence (respectively a trivial fibration) for the Brown-Golasiński model structure if and only if A(f ) is a weak equivalence (respectively a trivial fibration) of crossed complexes. We will denote these classes by W cc and TF cc respectively. We now describe these two classes more explicitly.

Proposition 2.9. We have W cc = W gr . In other words, a morphism f : G → H of strict ∞-groupoids is a weak equivalence of strict ∞-groupoids if and only if the morphism A(f ) : A(G) → A(H) is a weak equivalence of crossed complexes.

Proof. Since the two notions of weak equivalences are defined in terms of homotopy groups, it suffices to show that the two notions of homotopy groups coincide. Let G be a groupoid. By definition, π 0 (G) = π 0 (A(G)). Let x be an object of G. By definition, π 1 (A(G), x) is the cokernel of the morphism A(G) 2 (x) → A(G) 1 (x). The set A(G) 1 (x) is the set of 1-arrows u : x → x in G and two such arrows u, u ′ are identified in the cokernel if and only if there exists a 2-arrow from 1 x to u * 0 u ′ -1 in G. This condition is equivalent to the existence of a 2-arrow from u to u ′ . Hence π 1 (G, x) = π 1 (A(G), x).

Let n ≥ 2. The kernel of the map ,x). Thus the same argument as in dimension 1 shows that π n (G, x) = π n (A(G), x). Proposition 2.10. A morphism f : G → H of strict ∞-groupoids is in TF cc if and only if it satisfies the following conditions:

d n : A(G) n (x) → A(G) n-1 (x) is the set G n (x
• for every object y of H, there exists an object x of G such that f (x) = y;

• for every pair (x, y) of objects of G, the map G(x, y) 0 → G(f (x), f (y)) 0 induced by f is a surjection;

• for all n ≥ 2, every object x of G and every (n -1)-arrow u : 1 x → 1 x , the map

G(1 x , u) 0 → H(1 f (x) , f (u)) 0 is surjective.
Proof. By definition, f is in TF cc if and only if A(f ) is a trivial fibration of crossed complexes. This proposition is then just a matter of translation using the definition of the functor A.

The folk model structure on ∞-Grp

This section shows that the folk model structure on ∞-Cat defined in [START_REF] Lafont | A folk model structure on omega-cat[END_REF] transfers to ∞-Grp via the inclusion functor

U : ∞-Grp → ∞-Cat.
We first give a brief review of the main results of [START_REF] Lafont | A folk model structure on omega-cat[END_REF], and introduce the material needed to prove the transfer theorem.

The folk model structure on ∞-Cat

Given an ∞-category C, we define reversible cells in C and the relation of ω-equivalence between cells of C by mutual coinduction on n ≥ 0. Definition 3.1. Let n ∈ N:

• an n-cell x is ω-equivalent to an n-cell y if there is a reversible (n+1)-cell u : x → y;

• an (n + 1)-cell u : x → y is reversible if there is an (n + 1)-cell ū : y → x such that ū * n u is ω-equivalent to 1 x and u * n ū is ω-equivalent to 1 y .

Note that, for each r ≥ 0, if two cells are r-equivalent in the sense of [START_REF] Street | The algebra of oriented simplexes[END_REF], then they are ω-equivalent, with the converse being false. We also refer to [START_REF] Jacobs | A tutorial on (co)algebras and (co)induction[END_REF] for a gentle introduction to coinductive methods. Remark also that if G is an ∞-groupoid, any (n + 1)-cell u of G is reversible and the cell ū whose existence is stated in Definition 3.1 is of course just u -1 .

Let W denote the class of those morphisms f : C → D satisfying the following two conditions:

1. for each 0-cell y in D, there is a 0-cell x in C such that f x is ω-equivalent to y; 2. for each pair (x, x ′ ) of parallel n-cells in C, where n ≥ 0, and each (n + 1)-cell v : f x → f x ′ , there is an (n + 1)-cell u : x → x ′ such that f u is ω-equivalent to v. Now for each n ≥ 0, we define the n-globe O n as the free ∞-category generated by the representable globular set Y (n) = O(n, -). Thus Y (n) has exactly one n-cell, two k-cells for each k < n and no k-cell for k > n. Let also ∂Y (n) be the globular set having the same cells as Y (n) except in dimension n where (∂Y (n)) n = ∅. We denote by ∂O n the free ∞-category on ∂Y (n). We finally have, for each n ≥ 0, an inclusion morphism

i n : ∂O n → O n .
The set {i n | n ∈ N} is denoted by I.

A map is a trivial fibration if it has the right-lifting property with respect to I and a cofibration if it has the left-lifting property with respect to all trivial fibrations. Proposition 3.2. Any ∞-functor f factors as f = p • k where p is a trivial fibration and k is a cofibration.

Proof. By a standard application of the small object argument, using the fact that ∞-Cat is locally presentable.

On the other hand the maps σ n , τ n : n → n + 1 in the globular category O (see Section 1) induce corresponding maps from O n to O n+1 , of the form i n+1 • σn and i n+1 • τn respectively, where σn , τn : O n → ∂O n+1 . Moreover, we get a pushout diagram

∂O n in G G in O n σn O n τn G G ∂O n+1 .

Now the above pushout determines a canonical map

o n : ∂O n+1 → O n such that o n • σn = o n • τn = id O n . Proposition 3.
2 applies to o n , yielding an object P n together with a trivial fibration p n : P n → O n and a cofibration k n : ∂O n+1 → P n satisfying o n = p n • k n . We finally define j n : O n → P n as k n • σn and

J = {j n | n ∈ N}. Theorem 3.3.
There is a cofibrantly generated model structure on ∞-Cat where W is the class of weak equivalences, I a set of generating cofibrations and J a set of generating trivial cofibrations. This statement is in fact [START_REF] Lafont | A folk model structure on omega-cat[END_REF]Theorem 4.39] and the main result of that article.

x x ♯ x ♭ y y ♯ y ♭ U ♮ U ♭ x o o y o o U ♯
U ♮ ? ? ? ? ? ? ? ? ? ?

' 5 ? ? ? ? ? ? ? ? ? ?

Figure 1: n-cylinders for n = 0, 1

Path object

Let C be an object in a model category and ∆ C : C → C × C be the diagonal map. A path object for C consists in an object P C together with a factorization of ∆ C of the form

C j G G ∆ C R R P C p G G C × C
where p is a fibration and j is a weak equivalence. Such a P C is not unique: in the case of ∞-Cat, one particular choice is given by the functor Γ we now describe. We first define, by induction on n, the notion of n-cylinder between n-cells x, y of an ∞-category C. A few notations will be useful: for each n-cell x we denote by x ♭ , respectively x ♯ its 0-source s 0 x, respectively 0-target t 0 x. Now let C be an ∞-category and x, y two 0-cells in it. There is an ∞-category C(x, y) whose n-cells are the (n + 1)-cells u of C such that u ♭ = x and u ♯ = y. Whenever u is such an (n + 1)-cell of C, we denote by [u] the corresponding n-cell of C(x, y). Finally, let x, y, z be 0-

cells of C. Each 1-cell u : x → y determines an ∞-functor -• u : C(y, z) → C(x, z) given by [v] • u = [v * 0 u]. Likewise u : y → z determines an ∞-functor u • -: C(x, y) → C(x, z) by u • [v] = [u * 0 v].
Definition 3.4.

1. A 0-cylinder U : x y in C is given by a reversible 1-cell U ♮ : x → y;

2. If n > 0, an n-cylinder U : x y in C is given by two reversible 1-cells U ♭ : x ♭ → y ♭ and U ♯ : x ♯ → y ♯ , together with some (n -1)-cylinder [U ] :

U ♯ • [x] [y] • U ♭ in the ∞-category [x ♭ , y ♯ ] = C(x ♭ , y ♯ ).
If U : x y is an n-cylinder in C, we write π 1 C U and π 2 C U for the n-cells x and y, or simply π 1 U and π 2 U . Figure 1 represents n-cylinders for n = 0 and n = 1. For each n ∈ N, any (n + 1)-cylinder W : z z ′ in an ∞-category C determines a pair of n-cylinders in C: Definition 3.5. The source n-cylinder U : x

x ′ and the target n-cylinder V : y y ′ of the (n + 1)-cylinder W : z z ′ between (n + 1)-cells z : x → y and z ′ : x ′ → y ′ are defined inductively by: If W has source U and target V we write W : U → V or W : U → V | z z ′ (see Figure 2). It turns out that the source and target maps so defined satisfy the globular relations, so that the correspondence n → {U | U is an n-cylinder in C} determines a globular set Γ(C). We now turn to trivial n-cylinders: Definition 3.6. The trivial n-cylinder τ x : x

• if n = 0, then U ♮ = W ♭ and V ♮ = W ♯ ; x ♯ x ′♯ x ♭ x ′♭ W ♭ W ♯ y j j x z z y ′ k k x ′ z z U ♮ " 0 V ♮ B P z 7 E R R R R R R R R R R R R R R z ′ 7 E W ♮ r Q e
• if n > 0, then U ♭ = V ♭ = W ♭ and U ♯ = V ♯ = W ♯ ,
x on the n-cell x is defined inductively by:

• if n = 0, then (τ x) ♮ = 1 x ; • if n > 0, then (τ x) ♭ = 1 x ♭ and (τ x) ♯ = 1 x ♯ , whereas [τ x] is the trivial cylinder τ [x] in [x ♭ , x ♯ ].
We write τ C x in case we need to mention the ambient ∞-category C.

Let us finally recall from [10, Appendix A] that Γ(C) becomes a strict ∞-category when defining units and compositions as follows: Definition 3.7. Let U : x y be an n-cylinder. We define the (n + 1)-cylinder 1 U :

U → U | 1 x
1 y by induction on n:

• if n = 0, then (1 U ) ♭ = (1 U ) ♯ = U ♮ , whereas [1 U ] = τ [1 U ♮ ]; • if n > 0, then (1 U ) ♭ = U ♭ and (1 U ) ♯ = U ♯ , whereas [1 U ] = 1 [U ] .
In order to define composition, we first introduce the operation of concatenation: Definition 3.8. Let U | x y and V | y z be two n-cylinders. The concatenation V * U | x z of U and V is defined by induction on n:

• if n = 0, then (V * U ) ♮ = V ♮ * 0 U ♮ ; If W ′ : V → U | x -1
y -1 is the 1-cylinder of G defined by

W ′♮ = y -1 * 0 W ♮ -1 * 0 x -1 , we get W ′ * 0 W = 1 U and W * 0 W ′ = 1 V ,
which proves the case n = 1.

• Let n > 1 and suppose that the property holds for n -1. Let G be an ∞-groupoid and W : U → V | x y an n-cylinder of G. We get 1-cells

W ♭ : x ♭ → y ♭ , W ♯ : x ♯ → y ♯ and an (n -1)-cylinder [W ]: [U ] → [V ] | W ♯ • [x] [y] • W ♭ in H = [x ♭ , y ♯ ]
. Now H is an ∞-groupoid, so that the induction hypothesis applies and there is an (n -1)-cylinder in H

[W ] ′ : [V ] → [U ] | W ♯ • x -1 y -1 • W ♭ such that [W ] ′ * n-2 [W ] = 1 [U ] and [W ] * n-2 [W ] ′ = 1 [V ] . Hence we may define an n-cylinder W ′ of G by W ′♭ = W ♭ , W ′♯ = W ♯ and [W ′ ] = [W ] ′ . By construction W ′ * n-1 W = 1 U and W * n-1 W ′ = 1 V .
Remark 3.12. Let n ≥ 0. The proof of the previous lemma actually shows that if G is a strict (∞, n)-category, then so is Γ(G).

Immersions

We now introduce a class of morphisms which plays an important part in the proof of the transfer theorem.

1. g is a retraction of f , that is g • f = id C ; 2. π 1 D • h = f • g and π 2 D • h = id D ; 3. h • f = τ D • f . In other words, h is trivial on f (C).
The following proposition summarizes the properties of immersions we need here.

Proposition 3.14. The class Z of immersions satisfies the following properties:

(i) Z is closed by pushout;

(ii) all trivial cofibrations are immersions;

(iii) all immersions are weak equivalences.

We refer to [START_REF] Lafont | A folk model structure on omega-cat[END_REF]Section 4.6] for the proofs of these statements. (C2) R preserves filtered colimits;

C f G G id C U U D g G G C D h f •g id D D Γ(D) π 1 D o o π 2 D G G D C f G G τ D •f 4
(C3) for each generating trivial cofibration j of C, if g is a pushout of L(j) in D, then R(g) is a weak equivalence of C.

Moreover, if these conditions hold, the model structure so defined is cofibrantly generated and has L(I) as a set of generating cofibrations and L(J) as a set of generating trivial cofibrations.

We now turn to the particular case where C = ∞-Cat, D = ∞-Grp and R is the inclusion functor U : ∞-Grp → ∞-Cat. Note that U has a left-adjoint F : ∞-Cat → ∞-Grp building the free ∞-groupoid on an ∞-category, as well as a right-adjoint M , building to the maximal ∞-groupoid in an ∞-category. Let us first establish a few properties about the adjunction F ⊣ U .

Let T be the monad U F on ∞-Cat. Remark that, for any ∞-groupoid G, the free ∞-groupoid on the underlying ∞-category U (G) is naturally isomorphic to G itself. In other words, the counit ε : F U → 1 is a natural isomorphism. It follows that, for any ∞-groupoid G, we get an isomorphism

η U (G) : U (G) → U F U (G), (1)
where η denotes the unit of the adjunction. Now, for each ∞-category C, T (C) is of the form U (G) where G is an ∞-groupoid, and so is ΓT (C) by Lemma 3.11, so that

η ΓT (C) : ΓT (C) → T ΓT (C) (2)
is an isomorphism, as a special case of (1). Thus, we may define a natural transformation

λ : T Γ → ΓT by λ C = η -1 ΓT (C) • T Γ(η C ). (3)
Note also that the monad multiplication µ : T 2 → T is also a natural isomorphism, and we get

T (η C ) = η T (C) = µ -1 C . (4)
We may now state the following result: (5)

π 1 D • h = f • g; (6)
π 2 D • h = id D ; (7)
h • f = τ D • f. (8)
Let g ′ = T (g) and h ′ = λ D • T (h). We need to establish the following equations:

g ′ • f ′ = id T (C) ; (9)
π 1 T (D) • h ′ = f ′ • g ′ ; ( 10
)
π 2 T (D) • h ′ = id T (D) ; (11)
h ′ • f ′ = τ T (D) • f ′ . (12)
Equation ( 9) is just functoriality. Let us prove [START_REF] Lafont | A folk model structure on omega-cat[END_REF]. First remark that π 1 is a natural transformation, so that the following diagram commutes:

Γ(D) Γ(η D ) π 1 D G G D η D ΓT (D) π 1 T (D)
G G T (D). (14)

In fact the upper square is the image of (13) by T and the lower square commutes by naturality of η. Hence

π 1 T (D) • h ′ = π 1 T (D) • λ D • T (h) = T (π 1 D ) • T (h) = T (π 1 D • h) = T (f • g) = f ′ • g ′
which gives [START_REF] Lafont | A folk model structure on omega-cat[END_REF]. Likewise, we get the following commutative diagram: Proof. By the two previous propositions, these model structures have the same weak equivalences and the same trivial fibrations.

T (D) T (h) G G id T (D)

  let u, v be two parallel (n -1)-arrows of G and let a, b be two n-arrows from u to v. Suppose we have f (a) = f (b) in π n (H, f (u), f (v)). Then there exists an (n + 1)-arrow of H from f (a) to f (b). By surjectivity of the map π n+1 (G, a, b) → π n+1 (H, f (a), f (b)), there exists an (n + 1)-arrow in G from a to b. Thus a = b in π n (G, u, v).

Figure 2 :

 2 Figure 2: source and target of a 2-cylinder

  whereas the two (n-1)-cylinders [U ] and [V ] are respectively defined as the source and the target of the n-cylinder[W ] in the ∞-category [z ♭ , z ′♯ ].

Definition 3 .

 3 13. An ∞-functor f : C → D belongs to the class Z of immersions if and only if there exist ∞-functors g : D → C and h : D → Γ(D) satisfying the following properties:

  Figure 4: Immersions

Lemma 3 .

 3 16. The monad T preserves immersions. Proof. Let f : C → D be an immersion, and f ′ = T (f ). By Definition 3.13, there are g : D → C and h : D → Γ(D) such that g • f = id C ;

Theorem 4 . 3 .

 43 hand triangle commutes by applying T to[START_REF] Jacobs | A tutorial on (co)algebras and (co)induction[END_REF], and the right hand triangle commutes by replacing π 1 with π 2 in (14). Hence π 2 T (D) • h ′ = id T (D) and (11) is proved. Finally, by using the naturality of τ instead of π 1 , we get a commutative diagram analogue to (14):T (D) T (τ D ) G G T (η D ) id T (D) TF folk .There is nothing to prove for the conditions in dimension 0 and 1. Let n ≥ 2 and let u, v be two parallel (n -1)-arrows. We want to show that the mapG(u, v) 0 → H(f (u), f (v)) 0 is surjective. Let b be an n-arrow from f (u) to f (v) in H. Set x = s 0 (u). Then b ′ = 1 w 0 (f (u)) * 0 b is an n-arrow of H from 1 f (x) to w 0 (f (u)) * 0 f (v). Since the map G(1 x , w 0 (u) * 0 v) 0 → H(f (1 x ), f (w 0 (u) * 0 v)) 0 is surjective, there exists an n-arrow a ′ of G from 1 x to w 0 (u) * 0 v such that f (a ′ ) = b ′ .Then, the n-arrow a = 1 u * 0 a ′ is from u to v and we havef (a) = f (1 u * 0 a ′ ) = 1 f (u) * 0 b ′ = 1 f (u) * 0 1 w 0 (f (u)) * 0 b = b.The Brown-Golasiński model structure and the folk model structure on strict ∞-groupoids coincide.

Definition 3.9. Let m ≥ 1, 0 ≤ n < m and U | x

x ′ , V | y y ′ two m-cylinders such that t n (U ) = s n (V ). The composition V * n U | y * n x y ′ * n x ′ is defined by induction on n as follows:

Note that explicit formulas may be found in [START_REF] Métayer | Resolutions by polygraphs[END_REF]. For example, Figure 3 shows the composition

, and the 0-cylinder [W ] of C(z ♭ , z ′♯ ) is the reversible 1-cell of C(z ♭ , z ′♯ ) given by the following corresponding reversible 2-cell of C: An additional property, of particular importance here, is that the functor Γ preserves ∞-groupoids:

which gives [START_REF] Street | The algebra of oriented simplexes[END_REF] and ends the proof.

Lemma 3.17. Let f : C → D be an immersion, and suppose that the following square is a pushout in ∞-Grp:

Then U (g) is an immersion.

Proof. As U is left adjoint to M , it preserves pushouts, so that the following square is a pushout in ∞-Cat:

By Lemma 3.16, T (f ) is an immersion, and so is its pushout U (g), by Proposition 3.14(i).

Lemma 3.18. If j is a generating trivial cofibration of ∞-Cat, and g is a pushout of F (j) in ∞-Grp, then U (g) is a weak equivalence of ∞-Cat.

Proof. Let j be a generating trivial cofibration of ∞-Cat, and g be a pushout of F (j) in ∞-Grp. By Proposition 3.14(ii), j is an immersion, and so is U (g), by Lemma 3.17. By Proposition 3.14(iii), U (g) is a weak equivalence.

We may finally state the main result of this section:

Theorem 3.19. The forgetful functor U : ∞-Grp → ∞-Cat creates a model structure on ∞-Grp in which the weak equivalences are the morphisms f such that U (f ) belongs to W. Moreover, the model structure so defined has (F (i k )) k∈N as a family of generating cofibrations, and (F (j k )) k∈N as a family of generating trivial cofibrations.

Proof. As the model structure on ∞-Cat is cofibrantly generated and ∞-Grp is locally presentable, Proposition 3.15 applies, and it suffices to check conditions (C1), (C2) and (C3). Condition (C1) is proved in [START_REF] Lafont | A folk model structure on omega-cat[END_REF], and condition (C2) follows from the fact

Comparison

In this section, we show that the folk model structure on strict ∞-groupoids defined in the previous section coincides with the Brown-Golasiński model structure. To see this, it suffices to prove that they have the same weak equivalences and the same trivial fibrations.

Proposition 4.1. We have W gr = W folk = W cc .

Proof. We first show that W folk = W gr . In a strict ∞-groupoid, two n-arrows f and g are ω-equivalent if and only if there exists an (n + 1)-arrow a : f → g, that is if and only if f and g are homotopic. Therefore a morphism of strict ∞-groupoids is in W folk if and only if it satisfies condition 4 of Proposition 1.7. The statement is thus exactly the equivalence between conditions 1 and 4 of this very proposition. By Proposition 2.9, we have W cc = W gr , hence the result.

Proposition 4.2. We have TF folk = TF cc .

Proof. To prove the equivalence between the two notions of trivial fibrations, we will use the descriptions of these notions provided by Propositions 2.10 and 3.21. The conditions for being in TF folk are a priori stronger. Let f : G → H be a in TF cc . Let us prove it


Antonine Poitevin

Louis Hennet

Catherine Lerouge

Guillaume Wille

Philippe Bataillard

Philippe Bataillard Charac

Characterization of mineralogical metal carriers in dredged sediments deposit

Characterization of mineralogical metal carriers in dredged sediments deposit

Antonine Poitevin 1,2 , Louis Hennet 2 , Catherine Lerouge 1 , Guillaume Wille 1 , Philippe Bataillard 1 1 BRGM, 3 avenue C. Guillemin BP 36009 45060 Orléans cedex 2, France, a.poitevin@brgm.fr, c.lerouge@brgm.fr, g.wille@brgm.fr, p.bataillard@brgm.fr 2 CNRS-CEMHTI, 1D avenue de la recherche scientifique 45071 Orléans cedex 2, France, louis.hennet@cnrs-orleans.fr

Sediments originating from periodic waterways dredging were traditionally deposited on soil without specific precaution or planed treatments. It may be of environmental concern especially when they came from historically heavy metalscontaminated areas (zinc, lead) like north French coal basin. The chemical risk is the breakdown of heavy metals-carrier phases (electronic structure: oxidation state and nature of chemical bonds; crystal chemistry) liberating toxic elements which can migrate to the underlying soil and groundwater. In this framework, dredged sediments are currently studied to determine heavy metal contents, their distribution among phases, and the stability of these phases.

The main purpose of this work is to better understand and constrain mobility and bioavailability of heavy metals along an annual cycle. More particularly, the study presented here aims to identify and characterize the Pb-and Zn-carrier minerals in a ten-years-old dredged sediment deposit by combining chemical and spectroscopic techniques.

Traditional chemical sequential extractions methods were applied on untreated sediments sampled at different depths of the deposit. Results indicate that Pb and Zn are rather concentrated in the "acido-soluble" fraction (assumed carbonates) and the "reducible" one (Fe and Mn oxides) than in other ones. Chemical analyses of major elements by X-ray fluorescence and diffraction showed that the sediment essentially consists of a silty and clay fractions and carbonates. Optical and scanning electron microscopy observations confirmed the major mineralogy of the sediment, but also revealed micro-phases and heterogeneous fined-grain matrix not detected by laboratory X-ray diffraction due to a low sensitivity. Among these phases, we identify iron oxihydroxides, phosphates (apatite, undetermined iron bearing phosphates), sulphides (inherited sphalerite, framboidal pyrite) and sulphates (gypsum, barite). Electron microprobe analyses provide evidence of significant Zn content in phosphates, low Zn content in carbonates, pyrite or sulfates and traces of zinc in the fined-grained silicate matrix. But, the estimated Zn content associated with the carbonate fraction is inconsistent with the Zn content determined by sequential chemical extraction. This demonstrates the lack of selectivity of the latter to distinguish heavy metals associated with carbonates and other unknown phases. Complementary microanalyses using synchrotron radiation techniques were performed at the Diamond Light Source (UK). They provide evidence of heterogeneous low zinc contents in carbonates, reactional textures involving ironoxides around carbonate grains, diffuse lead (and zinc) in the fine grained silicate matrix and well-correlated iron-zinc associations.

In this presentation, we will present a summary of the results obtained so far, the questions to be answered and our further works.


Olivier Finkel
email: finkel@logique.jussieu.fr

Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular ω-Language

Keywords: Decision problems, infinite Post Correspondence Problem, analytical hierarchy, high undecidability, infinitary rational relations, omega rational functions, topology, points of continuity

.

Introduction

Many classical decision problems arise naturally in the fields of Formal Language Theory and of Automata Theory. It is well known that most problems about regular languages accepted by finite automata are decidable.

On the other hand, at the second level of the Chomsky Hierarchy, most problems about context-free languages accepted by pushdown automata or generated by context-free grammars are undecidable. For instance it follows from the undecidability of the Post Correspondence Problem that the universality problem, the inclusion and the equivalence problems for contextfree languages are also undecidable. Notice that some few problems about context-free languages remain decidable like the following ones: "Is a given context-free language L empty ?" "Is a given context-free language L infinite ?" "Does a given word x belong to a given context-free language L ?" Sénizergues proved in [START_REF] Sénizergues | L(A)=L(B)? decidability results from complete formal systems[END_REF] that the difficult problem of the equivalence of two deterministic pushdown automata is decidable. Notice that almost proofs of undecidability results about context-free languages rely on the undecidability of the Post Correspondence Problem which is complete for the class of recursively enumerable problems, i.e. complete at the first level of the arithmetical hierarchy. Thus undecidability proofs about context-free languages provided only hardness results for the first level of the arithmetical hierarchy.

On the other hand, some decision problems are known to be located beyond the arithmetical hierarchy, in some classes of the analytical hierarchy, and are then usually called "highly undecidable". Harel proved in [START_REF] Harel | Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness[END_REF] that many domino or tiling problems are Σ 1 1 -complete or Π 1 1 -complete. For instance the "recurring domino problem" is Σ 1 1 -complete. It is also Σ 1 1complete to determine whether a given Turing machine, when started on a blank tape, admits an infinite computation that reenters infinitely often in the initial state. Alur and Dill used this latter result in [START_REF] Alur | A theory of timed automata[END_REF] to prove that the universality problem fot timed Büchi automata is Π 1 1 -hard. In [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF], Castro and Cucker studied many decision problems for ω-languages of Turing machines. In particular, they proved that the non-emptiness and the infiniteness problems for ω-languages of Turing machines are Σ 1 1 -complete, and that the universality problem, the inclusion problem, and the equivalence problem are Π 1 2 -complete. Thus these problems are located at the first or the second level of the analytical hierarchy. Using Castro and Cucker's results, some reductions of [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF][START_REF] Finkel | On the accepting power of two-tape Büchi automata[END_REF], and topological arguments, we have proved in [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF] that many decision problems about 1-counter ωlanguages, context free ω-languages, or infinitary rational relations, like the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are Π 1 2 -complete. Notice that the exact complexity of numerous problems remains still unknown. For instance the exact complexities of the universality problem, the determinizability, or the complementability problem for timed Büchi automata which are known to be Π 1 1 -hard, see [START_REF] Alur | A theory of timed automata[END_REF][START_REF] Finkel | Undecidable problems about timed automata[END_REF].

We intend to introduce here a new method for proving high undecidability results which seems to be unexplored. It was actually noticed by Harel in [START_REF] Harel | Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness[END_REF] that "one can define Σ 1 1 -complete versions of the well-known Post Correspondence Problem", but it seems that this possibility has not been later investigated. We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular ω-language is Σ 1 1 -complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result a new high undecidability result, proving that it is Π 1 1 -complete to determine whether two given infinitary rational relations are disjoint. Then we apply this Σ 1 1 -complete version of the Post Correspondence Problem to the study of continuity problems for ω-rational functions realized by finite state Büchi transducers, considered by Prieur in [START_REF] Prieur | How to decide continuity of rational functions on infinite words[END_REF][START_REF] Prieur | How to decide continuity of rational functions on infinite words[END_REF] and by Carton, Finkel and Simonnet in [START_REF] Carton | On the continuity set of an omega rational function[END_REF]. We prove that there is an amazing gap between two decision problems about ω-rational functions. Indeed Prieur proved in [START_REF] Prieur | How to decide continuity of rational functions on infinite words[END_REF][START_REF] Prieur | How to decide continuity of rational functions on infinite words[END_REF] that it is decidable whether a given ω-rational function is continuous, while we show here that it is Σ 1 1 -complete to determine whether a given ω-rational function has at least one point of continuity. Next we prove that it is Π 1 1 -complete to determine whether the continuity set of a given ω-rational function is ωregular. This gives the exact complexity of two problems which were shown to be undecidable in [START_REF] Carton | On the continuity set of an omega rational function[END_REF].

The paper is organized as follows. We recall basic notions on automata and on the analytical hierarchy in Section 2. We state in Section 3 the Σ 1 1 -completeness of the infinite Post Correspondence Problem in a regular ω-language. We prove our main new results in Section 4. Some concluding remarks are given in Section 5.

Recall of basic notions

We assume now the reader to be familiar with the theory of formal (ω)languages [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF]. We recall some usual notations of formal language theory. When Σ is a finite alphabet, a non-empty finite word over Σ is any sequence x = a 1 . . . a k , where a i ∈ Σ for i = 1, . . . , k , and k is an integer ≥ 1. Σ ⋆ is the set of finite words (including the empty word) over Σ. The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a 1 . . . a n . . ., where for all integers i ≥ 1, a i ∈ Σ. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) . . . σ(n) . . ., where for all i, σ(i) ∈ Σ, and σ[n] = σ(1)σ(2) . . . σ(n). The usual concatenation product of two finite words u and v is denoted u • v and sometimes just uv. This product is extended to the product of a finite word u and an ω-word v: the infinite word u • v is then the ω-word such that:

(u • v)(k) = u(k) if k ≤ |u| , and (u • v)(k) = v(k -|u|) if k > |u|.
The set of ω-words over the alphabet Σ is denoted by Σ ω . An ω-language over an alphabet Σ is a subset of Σ ω . Definition 2.1 A Büchi automaton is a 5-tuple A = (K, Σ, δ, q 0 , F ), where K is a finite set of states, Σ is a finite input alphabet, q 0 ∈ K is the initial state and δ is a mapping from K × Σ into 2 K . The Büchi automaton A is said to be deterministic iff: δ : K × Σ → K. Let σ = a 1 a 2 . . . a n . . . be an ω-word over Σ. A sequence of states r = q 1 q 2 . . . q n . . . is called an (infinite) run of A on σ, starting in state p, iff: 1) q 1 = p and 2) for each i ≥ 1, q i+1 ∈ δ(q i , a i ). In case a run r of A on σ starts in state q 0 , we call it simply "a run of A on σ ". For every run r = q 1 q 2 . . . q n . . . of A, In(r) is the set of states in K entered by A infinitely many times during run r. The ω-language accepted by A is:

L(A) = {σ ∈ Σ ω | there exists a run r of A on σ such that In(r)∩ F = ∅}.
An ω-language L ⊆ Σ ω is said to be regular iff it is accpted by some Büchi automaton A.

We recall that the class of regular ω-languages is the ω-Kleene closure of the class of regular finitary languages, see [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF]: an ω-language L ⊆ Σ ω is regular iff it is of the form L = 1≤i≤n U i • V ω i , for some regular finitary languages U i , V i ⊆ Σ ⋆ . Acceptance of infinite words by other finite machines like pushdown automata, Turing machines, Petri nets, . . . , with various acceptance conditions, has also been considered. In particular, the class of context-free ω-languages is the class of ω-languages accepted by Büchi pushdown automata, see [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF][START_REF] Engelfriet | X-automata on ω-words[END_REF].

The set of natural numbers is denoted by N, and the set of functions from N into N is denoted by F. We assume the reader to be familiar with the arithmetical hierarchy on subsets of N. We now recall the definition of classes of the analytical hierarchy which may be found in [START_REF] Rogers | Theory of Recursive Functions and Effective Computability[END_REF][START_REF] Odifreddi | Classical Recursion Theory[END_REF][START_REF] Odifreddi | Classical Recursion Theory[END_REF]. Definition 2.2 Let k, l > 0 be some integers. Φ is a partial computable functional of k function variables and l number variables if there exists z ∈ N such that for any (f 1 , . . . , f k , x 1 , . . . , x l ) ∈ F k × N l , we have

Φ(f 1 , . . . , f k , x 1 , . . . , x l ) = τ f 1 ,...,f k z (x 1 , . . . , x l ),
where the right hand side is the output of the Turing machine with index z and oracles f 1 , . . . , f k over the input (x 1 , . . . , x l ). For k > 0 and l = 0, Φ is a partial computable functional if, for some z,

Φ(f 1 , . . . , f k ) = τ f 1 ,...,f k z (0).
The value z is called the Gödel number or index for Φ. Definition 2.3 Let k, l > 0 be some integers and R ⊆ F k ×N l . The relation R is said to be a computable relation of k function variables and l number variables if its characteristic function is computable.

We now define analytical subsets of N l .

Definition 2.4 A subset R of N l is analytical if it is computable or if there exists a computable set S ⊆ F m × N n , with m ≥ 0 and n ≥ l, such that R = {(x 1 , . . . , x l ) | (Q 1 s 1 )(Q 2 s 2 ) . . . (Q m+n-l s m+n-l )S(f 1 , . . . , f m , x 1 , . . . , x n )},
where Q i is either ∀ or ∃ for 1 ≤ i ≤ m + nl, and where s 1 , . . . , s m+n-l are f 1 , . . . , f m , x l+1 , . . . , x n in some order. The expression (Q 1 s 1 )(Q 2 s 2 ) . . . (Q m+n-l s m+n-l )S(f 1 , . . . , f m , x 1 , . . . , x n ) is called a predicate form for R. A quantifier applying over a function variable is of type 1, otherwise it is of type 0. In a predicate form the (possibly empty) sequence of quantifiers, indexed by their type, is called the prefix of the form. The reduced prefix is the sequence of quantifiers obtained by suppressing the quantifiers of type 0 from the prefix.

We can now distinguish the levels of the analytical hierarchy by considering the number of alternations in the reduced prefix.

Definition 2.5 For n > 0, a Σ 1 n -prefix is one whose reduced prefix begins with ∃ 1 and has n -1 alternations of quantifiers. A Σ 1 0 -prefix is one whose reduced prefix is empty. For n > 0, a Π 1 n -prefix is one whose reduced prefix begins with ∀ 1 and has n -1 alternations of quantifiers. A Π 1 0 -prefix is one whose reduced prefix is empty.

A predicate form is a Σ 1 n (Π 1 n )-form if it has a Σ 1 n (Π 1 n )-prefix. The class of sets in some N l which can be expressed in Σ 1 n -form (respectively, Π 1 n -form) is denoted by Σ 1 n (respectively, Π 1 n ). The class Σ 1 0 = Π 1 0 is the class of arithmetical sets.
We now recall some well known results about the analytical hierarchy.

Proposition 2.6 Let R ⊆ N l for some integer l. Then R is an analytical set iff there is some integer

n ≥ 0 such that R ∈ Σ 1 n or R ∈ Π 1 n .
Theorem 2.7 For each integer n ≥ 1,

(a) Σ 1 n ∪ Π 1 n Σ 1 n+1 ∩ Π 1 n+1 . (b) A set R ⊆ N l is in the class Σ 1 n iff its complement is in the class Π 1 n . (c) Σ 1 n -Π 1 n = ∅ and Π 1 n -Σ 1 n = ∅.
Transformations of prefixes are often used, following the rules given by the next theorem.

Theorem 2.8 For any predicate form with the given prefix, an equivalent predicate form with the new one can be obtained, following the allowed prefix transformations given below :

(a) . . . ∃ 0 ∃ 0 . . . → . . . ∃ 0 . . . , . . . ∀ 0 ∀ 0 . . . → . . . ∀ 0 . . . ; (b) . . . ∃ 1 ∃ 1 . . . → . . . ∃ 1 . . . , . . . ∀ 1 ∀ 1 . . . → . . . ∀ 1 . . . ; (c) . . . ∃ 0 . . . → . . . ∃ 1 . . . , . . . ∀ 0 . . . → . . . ∀ 1 . . . ; (d) . . . ∃ 0 ∀ 1 . . . → . . . ∀ 1 ∃ 0 . . ., . . . ∀ 0 ∃ 1 . . . → . . . ∃ 1 ∀ 0 . . . ;
We now recall the notions of 1-reduction and of Σ 1 n -completeness (respectively, Π 1 n -completeness). Given two sets A, B ⊆ N we say A is 1-reducible to B and write A ≤ 1 B if there exists a total computable injective function

f from N to N with A = f -1 [B]. A set A ⊆ N is said to be Σ 1 n -complete (respectively, Π 1 n -complete) iff A is a Σ 1 n -set (respectively, Π 1 n -set) and for each Σ 1 n -set (respectively, Π 1 n -set) B ⊆ N it holds that B ≤ 1 A.
We now recall an example of a Σ 1 1 -complete decision problem which will be useful in the sequel. Definition 2.9 A non deterministic Turing machine M is a 5-tuple M = (Q, Σ, Γ, δ, q 0 ), where Q is a finite set of states, Σ is a finite input alphabet, Γ is a finite tape alphabet satisfying Σ ⊆ Γ and containing a special blank symbol ∈ Γ \ Σ, q 0 is the initial state, and δ is a mapping from

Q × Γ to subsets of Q × Γ × {L, R, S}.
Harel proved the following result in [START_REF] Harel | Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness[END_REF].

Theorem 2.10 The following problem is Σ 1 1 -complete: Given a Turing machine M z , of index z ∈ N, does M z , when started on a blank tape, admit an infinite computation that reenters infinitely often in the initial state q 0 ? Theorem 3.1 (Post, see [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]) Let Γ be an alphabet having at least two elements. Then it is undecidable to determine, for arbitrary n-tuples (x 1 , x 2 . . . , x n ) and (y 1 , y 2 . . . , y n ) of non-empty words in Γ ⋆ , whether there exists a non-empty sequence of indices i 1 , i 2 . . . , i k such that

x i 1 x i 2 . . . x i k = y i 1 y i 2 . . . y i k .
On the other hand, the infinite Post Correspondence Problem, also called ω-PCP, has been shown to be undecidable by Ruohonen in [START_REF] Ruohonen | Reversible machines and Post's correspondence problem for biprefix morphisms[END_REF] and by Gire in [START_REF] Gire | Two decidability problems for infinite words[END_REF].

Theorem 3.2 Let Γ be an alphabet having at least two elements. Then it is undecidable to determine, for arbitrary n-tuples (x 1 , . . . , x n ) and (y 1 , . . . , y n ) of non-empty words in Γ ⋆ , whether there exists an infinite sequence of indices i 1 , i 2 , . . . , i k . . . such that

x i 1 x i 2 . . . x i k . . . = y i 1 y i 2 . . . y i k . . .
Notice that an instance of the ω-PCP is given by two n-tuples (x 1 , . . . , x n ) and (y 1 , . . . , y n ) of non-empty words in Γ ⋆ , and if there exist some solutions, these ones are infinite words over the alphabet {1, . . . , n}.

We are going to consider now a variant of the infinite Post Correspondence Problem where we restrict solutions to ω-words belonging to a given ωregular language L(A) accepted by a given Büchi automaton A.

An instance of the ω-PCP in a regular ω-language, also denoted ω-PCP(Reg), is given by two n-tuples (x 1 , . . . , x n ) and (y 1 , . . . , y n ) of non-empty words in Γ ⋆ along with a Büchi automaton A accepting words over {1, . . . , n}. A solution of this problem is an infinite sequence of indices i 1 , i 2 , . . . , i k . . . such that i 1 i 2 . . . i k . . . ∈ L(A) and x i 1 x i 2 . . . x i k . . . = y i 1 y i 2 . . . y i k . . .. Notice that one can associate in a recursive and injective way an unique integer z to each Büchi automaton A, this integer being called the index of the automaton A. We denote also A z the Büchi automaton of index z. Then each instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A z ) can be also characterized by an index Ī ∈ N.

We can now state precisely the following result.

Theorem 3.3 It is Σ 1
1 -complete to determine, for a given instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A z ), given by its index Ī, whether there is an infinite sequence of indices i 1 , i 2 , . . . , i k . . . such that i 1 i 2 . . . i k . . . ∈ L(A z ) and

x i 1 x i 2 . . . x i k . . . = y i 1 y i 2 . . . y i k . . ..
Proof. We first prove that this problem is in the class Σ 1 1 . It is easy to see that there is an injective computable function Φ : N → N such that for all Ī ∈ N the Büchi Turing machine M Φ( Ī) of index Φ( Ī), where I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A z ), accepts the set of infinite words i 1 i 2 . . . i k . . . ∈ L(A z ) such that x i 1 x i 2 . . . x i k . . . = y i 1 y i 2 . . . y i k . . .. Then the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A z ) has a solution if and only if the ω-language of the Büchi Turing machine M Φ( Ī) is non-empty. Thus the ω-PCP(Reg) is reduced to the non-emptiness problem of Büchi Turing machines which is known to be in the class Σ 1 1 . Indeed for a given Büchi Turing machine M z reading infinite words over an alphabet Σ we can express L(M z ) = ∅ by the formula "∃x ∈ Σ ω ∃r [r is an accepting run of M z on x ]"; this is a Σ 1 1 -formula because the existential second order quantifications are followed by an arithmetical formula, see [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF][START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF] for related results. Therefore the ω-PCP(Reg) is also in the class Σ 1 1 .

We now prove the completeness part of the theorem. Recall that the following problem (P ) is Σ 1 1 -complete by Theorem 2.10.

(P ): Given a Turing machine M z , of index z ∈ N, does M z , when started on a blank tape, admit an infinite computation that reenters infinitely often in the initial state q 0 ?

We can reduce this problem to the ω-PCP in a regular ω-language in the following way.

Let M = (Q, Σ, Γ, δ, q 0 ) be a Turing machine, where Q is a finite set of states, Σ is a finite input alphabet, Γ is a finite tape alphabet satisfying Σ ⊆ Γ and containing a special blank symbol ∈ Γ \ Σ, q 0 is the initial state, and δ is a mapping from Q × Γ to subsets of Q × Γ × {L, R, S}.

We are going to associate to this Turing machine an instance of the ω-PCP(Reg). First we define the two following lists x = (x i ) 1≤i≤n and y = (y i ) 1≤i≤n of finite words over the alphabet

Σ ∪ Γ ∪ Q ∪ {#}, where # is a symbol not in Σ ∪ Γ ∪ Q. x y # = x 1 #q 0 # = y 1 # # a a for each a ∈ Γ qa q'b if (q ′ , b, S) ∈ δ(q, a) qa bq' if (q ′ , b, R) ∈ δ(q, a) cqa q'cb if (q ′ , b, L) ∈ δ(q, a) q# bq'# if (q ′ , b, R) ∈ δ(q, ) cq# q'cb# if (q ′ , b, L) ∈ δ(q, ) q# q'b# if (q ′ , b, S) ∈ δ(q, )
The integer n is the number of words in the list x and also in the list y. We assume that these two lists are indexed so that x = (x i ) 1≤i≤n and y = (y i ) 1≤i≤n . Let now E ⊆ {1, 2, . . . , n} be the set of integers i such that the initial state q 0 of the Turing machine M appears in the word y i . The ωlanguage L ⊆ {1, 2, . . . , n} ω of infinite words over the alphabet {1, 2, . . . , n} which begin by the letter 1 and have infinitely many letters in E is a regular ω-language and it is accepted by a (deterministic) Büchi automaton A.

We now consider the instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) of the ω-PCP(Reg). It is easy to check that this instance of the ω-PCP(Reg) has a solution i 1 , i 2 , . . . , i k . . . if and only if the Turing machine M, when started on a blank tape, admits an infinite computation that reenters infinitely often in the initial state q 0 .

Thus the Σ 1 1 -complete problem (P ) is reduced to the ω-PCP in a regular ω-language and this latter problem is also Σ 1 1 -complete.

4 Applications to infinitary rational relations

Infinitary rational relations

We now recall the definition of infinitary rational relations, via definition by Büchi transducers:

Definition 4.1 A Büchi transducer is a sextuple T = (K, Σ, Γ, ∆, q 0 , F ), where K is a finite set of states, Σ and Γ are finite sets called the input and the output alphabets, ∆ is a finite subset of K × Σ ⋆ × Γ ⋆ × K called the set of transitions, q 0 is the initial state, and F ⊆ K is the set of accepting states.

A computation C of the transducer T is an infinite sequence of consecutive transitions (q 0 , u 1 , v 1 , q 1 ), (q 1 , u 2 , v 2 , q 2 ), . . . (q i-1 , u i , v i , q i ), (q i , u i+1 , v i+1 , q i+1 ), . . .

The computation is said to be successful iff there exists a final state q f ∈ F and infinitely many integers i ≥ 0 such that q i = q f . The input word and output word of the computation are respectively u = u 1 .u 2 .u 3 . . . and v = v 1 .v 2 .v 3 . . . The input and the output words may be finite or infinite. The infinitary rational relation R(T ) ⊆ Σ ω ×Γ ω accepted by the Büchi transducer T is the set of couples (u, v) ∈ Σ ω × Γ ω such that u and v are the input and the output words of some successful computation C of T . The set of infinitary rational relations will be denoted RAT 2 .

If R(T ) ⊆ Σ ω × Γ ω is an infinitary rational relation recognized by the Büchi transducer T then we denote

Dom(R(T )) = {u ∈ Σ ω | ∃v ∈ Γ ω (u, v) ∈ R(T )}
and

Im(R(T )) = {v ∈ Γ ω | ∃u ∈ Σ ω (u, v) ∈ R(T )}.
It is well known that, for each infinitary rational relation R(T ) ⊆ Σ ω × Γ ω , the sets Dom(R(T )) and Im(R(T )) are regular ω-languages and that one can construct, from the Büchi transducer T , some Büchi automata A and B accepting the ω-languages Dom(R(T )) and Im(R(T )).

To each Büchi transducer T can be associated in an injective and recursive way an index z ∈ N and we shall denote in the sequel T z the Büchi transducer of index z.

We proved in [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF] that many decision problems about infinitary rational relations are highly undecidable. In fact many of them, like the universality problem, the equivalence problem, the inclusion problem, the cofiniteness problem, the unambiguity problem, are Π 1 2 -complete, hence located at the second level of the analytical hierarchy.

We can now use the Σ 1 1 -completeness of the ω-PCP in a regular ω-language to obtain a new result of high undecidability.

Theorem 4.2 It is Π 1 1 -complete to determine whether two given infinitary rational relations are disjoint, i.e. the set

{(z, z ′ ) ∈ N 2 | R(T z ) ∩ R(T z ′ ) = ∅} is Π 1 1 -complete.
Proof. We are going to show that the complement of this set is Σ 1 1 -complete, i.e. that the set

{(z, z ′ ) ∈ N 2 | R(T z ) ∩ R(T z ′ ) = ∅} is Σ 1 1 -complete.
Firstly, it is easy to see that, for two given Büchi transducers T z and T z ′ , one can define a Büchi Turing machine M Φ(z,z ′ ) of index Φ(z, z ′ ) accepting the ω-language R(T z ) ∩ R(T z ′ ). Moreover one can construct the function Φ : N 2 → N as an injective computable function. This shows that the set

{(z, z ′ ) ∈ N 2 | R(T z )∩R(T z ′ ) = ∅} is reduced to the set {z ∈ N | L(M z ) = ∅} which is in the class Σ 1 1 , since the non-emptiness problem for ω-languages of Turing machines is in the class Σ 1 1 . Thus the set {(z, z ′ ) ∈ N 2 | R(T z ) ∩ R(T z ′ ) = ∅} is in the class Σ 1 1 .
Secondly, we have to show the completeness part of the theorem. We are going to reduce the ω-PCP in a regular ω-language to the problem of the non-emptiness of the intersection of two infinitary rational relations. Let then I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) be an instance of the ω-PCP(Reg), where the x i and y i are words over an alphabet Γ. We can then construct Büchi transducers T ψ 1 ( Ī) and T ψ 2 ( Ī) such that the infinitary rational relation R(T ψ 1 ( Ī) ) ⊆ {1, 2, . . . , n} ω × Γ ω is the set of pairs of infinite words in the form (i

1 i 2 i 3 • • • ; x i 1 x i 2 x i 3 • • •) with i 1 i 2 i 3 • • • ∈ L(A).
And similarly R(T ψ 2 ( Ī) ) ⊆ {1, 2, . . . , n} ω × Γ ω is the set of pairs of infinite words in the form (i

1 i 2 i 3 • • • ; y i 1 y i 2 y i 3 • • •) with i 1 i 2 i 3 • • • ∈ L(A). Thus it holds that R(T ψ 1 ( Ī) ) ∩ R(T ψ 2 ( Ī)
) is non-empty iff there is an infinite sequence

i 1 i 2 • • • i k • • • ∈ L(A) such that x i 1 x i 2 • • • x i k • • • = y i 1 y i 2 • • • y i k • • •.
The reduction is now given by the injective computable function Ψ : N → N 2 given by Ψ(z) = (Ψ 1 (z), Ψ 2 (z)).

Continuity of ω-rational functions

Recall that an infinitary rational relation R(T ) ⊆ Σ ω × Γ ω is said to be functional iff it is the graph of a function, i.e. iff

[∀x ∈ Dom(R(T )) ∃!y ∈ Im(R(T )) (x, y) ∈ R(T )].
Then the functional relation R(T ) defines an ω-rational (partial) function

F T : Dom(R(T )) ⊆ Σ ω → Γ ω by: for each u ∈ Dom(R(T )), F T (u) is the unique v ∈ Γ ω such that (u, v) ∈ R(T ).
Recall the following previous decidability result.

Theorem 4.3 ([Gir86]) One can decide whether an infinitary rational relation recognized by a given Büchi transducer T is a functional infinitary rational relation.

One can then associate in a recursive and injective way an index to each Büchi transducer T accepting a functional infinitary rational relation R(T ).

In the sequel we consider only these Büchi transducers and we shall denote T z the Büchi transducer of index z (such that R(T z ) is functional).

It is very natural to consider the notion of continuity for ω-rational functions defined by Büchi transducers.

We assume the reader to be familiar with basic notions of topology which may be found in [Kec95, Tho90, Sta97, PP04]. There is a natural metric on the set Σ ω of infinite words over a finite alphabet Σ which is called the prefix metric and defined as follows. For u, v ∈ Σ ω and u v) where l pref (u,v) is the least integer n such that the (n + 1) th letter of u is different from the (n + 1) th letter of v. This metric induces on Σ ω the usual Cantor topology for which open subsets of Σ ω are in the form W • Σ ω , where W ⊆ Σ ⋆ .

= v let d(u, v) = 2 -l pref (u,
We recall that a function f :

Dom(f ) ⊆ Σ ω → Γ ω , whose domain is Dom(f ), is said to be continuous at point x ∈ Dom(f ) if : ∀n ≥ 1 ∃k ≥ 1 ∀y ∈ Dom(f ) [ d(x, y) < 2 -k ⇒ d(f (x), f (y)) < 2 -n ]
The continuity set C(f ) of the function f is the set of points of continuity of f . The function f is said to be continuous if it is continuous at every point

x ∈ Dom(f ), i. e. if C(f ) = Dom(f ).
Prieur proved the following decidability result.

Theorem 4.4 (Prieur [START_REF] Prieur | How to decide continuity of rational functions on infinite words[END_REF][START_REF] Prieur | How to decide continuity of rational functions on infinite words[END_REF]) One can decide whether a given ω-rational function is continuous.

On the other hand the following undecidability result was proved in [START_REF] Carton | On the continuity set of an omega rational function[END_REF].

Theorem 4.5 (see [START_REF] Carton | On the continuity set of an omega rational function[END_REF]) One cannot decide whether a given ω-rational function f has at least one point of continuity.

We can now give the exact complexity of this undecidable problem.

Theorem 4.6 It is Σ 1 1 -complete to determine whether a given ω-rational function f has at least one point of continuity, i.e. whether the continuity set C(f ) of f is non-empty. In other words the set {z

∈ N | C(F Tz ) = ∅} is Σ 1 1 -complete.
We first prove the following lemma. Proof. Let F be a function from Dom(F ) ⊆ Σ ω into Γ ω . For some integers n, k ≥ 1, we consider the set

X k,n = {x ∈ Dom(F ) | ∀y ∈ Dom(F ) [ d(x, y) < 2 -k ⇒ d(F (x), F (y)) < 2 -n ]} For x ∈ Dom(F ) it holds that: x ∈ C(F ) ⇐⇒ ∀n ≥ 1 ∃k ≥ 1 [ x ∈ X k,n ]
We shall denote X k,n (z) the set X k,n corresponding to the function F Tz defined by the Büchi transducer of index z. Then it holds that:

x ∈ C(F Tz ) ⇐⇒ ∀n ≥ 1 ∃k ≥ 1 [ x ∈ X k,n (z) ]
And we denote R k,n (x, z) the relation given by:

R k,n (x, z) ⇐⇒ [ x ∈ X k,n (z) ]
We now prove that this relation is a Π 0 3 -relation.

For x ∈ Σ ω and k ∈ N, we denote B(x, 2 -k ) the open ball of center x and of radius 2 -k , i.e. the set of y ∈ Σ ω such that d(x, y) < 2 -k . We know, from the definition of the distance d, that for two ω-words x and y over Σ, the inequality d(x, y) < 2 -k simply means that x and y have the same (k + 1) first letters. Thus B(x,

2 -k ) = x[k + 1] • Σ ω . But by definition of X k,n (z) it holds that: x ∈ X k,n (z) ⇐⇒ (x ∈ Dom(F Tz ) and F Tz [B(x, 2 -k ) ∩ Dom(F Tz )] ⊆ B(F Tz (x), 2 -n ))
We claim that there is an algorithm which, given x ∈ Σ ω and z ∈ N, can decide whether

F Tz [B(x, 2 -k ) ∩ Dom(F Tz )] ⊆ w • Γ ω ,
for some finite word w ∈ Γ ⋆ such that |w| = n + 1.

Indeed the ω-language B(x, On the other hand, we have

2 -k ) ∩ Dom(F Tz ) = x[k + 1] • Σ ω ∩ Dom(F Tz
x ∈ X k,n (z) ⇐⇒ (x ∈ Dom(F Tz ) and S(x, k, n, z))
But Dom(F Tz ) is a regular ω-language accepted by a Büchi automaton A which can be constructed effectively from T z and hence from the index z.

And the relation (x ∈ L(A)) is known to be an arithmetical Π 0 3 (and also a Σ 0

3 ) relation, see [START_REF] Lescow | Logical specifications of infinite computations[END_REF]. Thus "x ∈ X k,n (z)" can be expressed also by a Π 0 3 (and also a Σ 0 3 ) formula because the relation S is a ∆ 0 1 relation. Now we have the following equivalences:

C(F Tz ) = ∅ ⇐⇒ ∃x [x ∈ C(F Tz )] ⇐⇒ ∃x [∀n ≥ 1 ∃k ≥ 1 x ∈ X k,n (z)]
Clearly the formula ∃x [∀n ≥ 1 ∃k ≥ 1 x ∈ X k,n (z)] is a Σ 1 1 -formula where there is a second order quantification ∃x followed by an arithmetical Π 0 5 -formula in which the quantifications ∀n ≥ 1 ∃k ≥ 1 are first order quantifications on integers.

End of Proof of Theorem 4.6. To prove the completeness part of the theorem we use some ideas of [START_REF] Carton | On the continuity set of an omega rational function[END_REF] but we shall modify the constructions of [START_REF] Carton | On the continuity set of an omega rational function[END_REF] in order to use the Σ 1 1 -completeness of the ω-PCP(Reg) instead of the undecidability of the PCP. We are now going to reduce the ω-PCP in a regular ω-language to the non-emptiness of the continuity set of an ω-rational function.

Let then I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) be an instance of the ω-PCP(Reg), where the x i and y i are words over an alphabet Γ. We can construct an ωrational function F in the following way.

Firstly, the domain Dom(F ) will be a set of ω-words over the alphabet {1, . . . , n} ∪ {a, b}, where a and b are new letters not in {1, . . . , n}. For x ∈ ({1, . . . , n} ∪ {a, b}) ω we denote x(/{a, b}) the (finite or infinite) word over the alphabet {1, . . . , n} obtained from x when removing every occurrence of the letters a and b. And x(/{1, . . . , n}) is the (finite or infinite) word over the alphabet {a, b} obtained from x when removing every occurrence of the letters 1, . . . , n. Then Dom(F ) is the set of ω-words x over the alphabet {1, . . . , n} ∪ {a, b} such that x(/{a, b}) ∈ L(A) (so in particular x(/{a, b}) is infinite) and x(/{1, . . . , n}) is infinite. It is clear that this domain is a regular ω-language.

Secondly, for x ∈ Dom(F ) such that x(/{a, b})

= i 1 i 2 • • • i k • • • ∈ L(A) we set: • F (x) = x i 1 x i 2 • • • x i k • • • if x(/{1, .
. . , n}) ∈ ({a, b} ⋆ • a) ω , and

• F (x) = y i 1 y i 2 • • • y i k • • • if x(/{1, . . . , n}) ∈ {a, b} ⋆ • b ω .
The ω-language ({a, b} ⋆ .a) ω is the set of ω-words over the alphabet {a, b} having infinitely many letters a. The ω-language {a, b} ⋆ .b ω is the complement in {a, b} ω of the ω-language ({a, b} ⋆ .a) ω : it is the set of ω-words over the alphabet {a, b} containing only finitely many letters a. The two ω-languages ({a, b} ⋆ .a) ω and {a, b} ⋆ .b ω are ω-regular, and one can easily construct Büchi automata accepting them. Then it is easy to see that the function F is ω-rational and that one can construct a Büchi transducer T accepting the graph of the function F . Moreover one can construct an injective computable function ψ : N → N such that T = T ψ( Ī) and so F = F T ψ( Ī) .

We now prove that if x ∈ Dom(F T ψ( Ī) ) is a point of continuity of the function F T ψ( Ī) then the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A)

has a solution i 1 i 2 • • • i k • • •, i.e. an ω-word i 1 i 2 • • • i k • • • ∈ L(A) such that x i 1 x i 2 • • • x i k • • • = y i 1 y i 2 • • • y i k • • •.
To simplify the notations we denote by F the function F T ψ( Ī) . We now distinguish two cases.

First Case. Assume firstly that x(/{1, . . . , n}) ∈ ({a, b} ⋆ • a) ω and that x(/{a, b})

= i 1 i 2 • • • i k • • • ∈ L(A). Then by definition of F it holds that F (x) = x i 1 x i 2 • • • x i k • • •. We denote z = x(/
) = y i 1 y i 2 • • • y i k • • • for every integer p ≥ 1 while F (x) = x i 1 x i 2 • • • x i k • • •. Thus if x is a point of continuity of the function F then it holds that x i 1 x i 2 • • • x i k • • • = y i 1 y i 2 • • • y i k • • • and the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) has a solution i 1 i 2 • • • i k • • •.
Second Case. Assume now that x(/{1, . . . , n}) ∈ {a, b} ⋆ • b ω and that x(/{a, b})

= i 1 i 2 • • • i k • • • ∈ L(A).
Notice that ({a, b} ⋆ .a) ω is also dense in {a, b} ω . Then reasoning as in the first case we can prove that if x is a point of continuity of F then

x i 1 x i 2 • • • x i k • • • = y i 1 y i 2 • • • y i k • • • and the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) has a solution i 1 i 2 • • • i k • • •.
Conversely assume that the ω-PCP in a regular ω-language of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) has a solution i

1 i 2 • • • i k • • •, i.e. an ω-word i 1 i 2 • • • i k • • • ∈ L(A) such that x i 1 x i 2 • • • x i k • • • = y i 1 y i 2 • • • y i k • • •. We now show that each x ∈ Dom(F ) such that x(/{a, b}) = i 1 i 2 • • • i k • • • is a point of continuity of the function F . Consider an infinite sequence (t p ) p≥1 of ele- ments of Dom(F ) such that lim(t p ) = x.
It is easy to see that the sequence (t p (/{a, b})) p≥1 is convergent and that its limit is the ω-word x(/{a, b}

) = i 1 i 2 • • • i k • • •.
This implies easily that the sequence F (t p ) p≥1 is convergent and that its limit is the ω-word F

(x) = x i 1 x i 2 • • • x i k • • • = y i 1 y i 2 • • • y i k • • •.
Thus x is a point of continuity of F and this ends the proof.

We consider now the continuity set of an ω-rational function and its possible complexity. The following undecidability result was proved in [START_REF] Carton | On the continuity set of an omega rational function[END_REF].

Theorem 4.8 (see [START_REF] Carton | On the continuity set of an omega rational function[END_REF]) One cannot decide whether the continuity set of a given ω-rational function f is a regular (respectively, context-free) ω-language.

We can now give the exact complexity of the first above undecidable problem.

Theorem 4.9 It is Π 1 1 -complete to determine whether the continuity set C(f ) of a given ω-rational function f is a regular ω-language. In other words the set {z ∈

N | C(F Tz ) is a regular ω-language} is Π 1 1 -complete.
We first prove the following lemma. Proof. Recall that A z denotes the Büchi automaton of index z. We can express the sentence "C(F Tz ) is a regular ω-language" by the sentence:

∃z ′ C(F Tz ) = L(A z ′ ).
On the other hand we have seen in the proof of Lemma 4.7 that

x ∈ C(F Tz ) ⇐⇒ [∀n ≥ 1 ∃k ≥ 1 x ∈ X k,n (z)
] and then that x ∈ C(F Tz ) can be expressed by an arithmetical Π 0 5 -formula. We can now express C(F Tz ) = L(A z ′ ) by: ∀x [(x ∈ C(F Tz ) and x ∈ L(A z ′ )) or (x / ∈ C(F Tz ) and x / ∈ L(A z ′ ))]

which is a Π 1 1 -formula because there is one universal second order quantification ∀x followed by an arithmetical formula (recall that x ∈ L(A z ′ ) can be expressed by an arithmetical Π 0 3 -formula).

Finally the sentence ∃z ′ C(F Tz ) = L(A z ′ ) can be expressed by a Π 1 1 -formula because the quantification ∃z ′ is a firstorder quantification bearing on integers and the formula C(F Tz ) = L(A z ′ ) can be expressed by a Π 1 1 -formula.

End of Proof of Theorem 4.9. To prove the completeness part of the theorem we reduce the ω-PCP in a regular ω-language to the problem of the non-regularity of the continuity set of an ω-rational function.

As in the proof of the above Theorem 4.8 in [START_REF] Carton | On the continuity set of an omega rational function[END_REF], we shall use a particular instance of Post Correspondence Problem. For two letters c, d, let PCP 1 should be regular (since D = {d 1 , d 2 , d 3 } and {1, . . . , n} ∪ {a, b} are disjoint) and it is not even context-free.

This shows that the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) has a solution if and only if the continuity set C(F ′ ) is not ω-regular. This ends the proof.

It is natural to ask whether the set {z ∈ N | C(F Tz ) is a context-free ω-language} is also Π 1 1 -complete. But one cannot extend directly Lemma 4.10, replacing regular by context-free. If we replace the Büchi automaton A z of index z by the Büchi pushdown automaton B z of index z, we get only that the set {z ∈ N | C(F Tz ) is a context-free ω-language} is in the class Π 1 2 because the "x ∈ L(B z ′ )" can only be expressed by a Σ 1 1 -formula. On the other hand, the second part of the proof of Theorem 4.9 proves in the same way that the set {z ∈ N | C(F Tz ) is a context-free ω-language} is Π 1 1 -hard. Thus we can now state the following result.

Concluding remarks

We have given a complete proof of the Σ 1 1 -completeness of the ω-PCP in a regular ω-language, also denoted ω-PCP(Reg). Then we have applied this result and obtained the exact complexity of several highly undecidable problems about infinitary rational relations and ω-rational functions. In particular, we have showed that there is an amazing gap between two decision problems about ω-rational functions realized by finite state Büchi transducers: it is decidable whether a given ω-rational function is continuous, while it is Σ 1 1 -complete to determine whether a given ω-rational function has at least one point of continuity.

We hope that this paper will attract the reader's attention on a new highly undecidable problem, the ω-PCP(Reg), which could be very useful to study the frontiers between decidable and undecidable problems.

Lemma 4. 7

 7 The set {z ∈ N | C(F Tz ) = ∅} is in the class Σ 1 1 .

  ) is the intersection of two regular ω-languages and one can construct a Büchi automaton accepting it. The graph of the restriction of the function F Tz to the set x[k + 1] • Σ ω ∩ Dom(F Tz ) is also an infinitary rational relation and one can then also find a Büchi automaton B accepting F Tz [x[k + 1] • Σ ω ∩ Dom(F Tz )]. One can then find the set of prefixes of length n + 1 of infinite words in L(B). If there is only one such prefix w then F Tz [B(x, 2 -k )∩ Dom(F Tz )] ⊆ w • Γ ω and otherwise we have F Tz [B(x, 2 -k ) ∩ Dom(F Tz )] w ′ • Γ ω for every word w ′ ∈ Γ ⋆ such that |w ′ | = n + 1. We now write S(x, k, n, z) iff F Tz [B(x, 2 -k ) ∩ Dom(F Tz )] ⊆ w • Γ ω , for some finite word w ∈ Γ ⋆ such that |w| = n + 1. As we have just seen the relation S(x, k, n, z) is computable, i.e. a ∆ 0 1 relation.

  Lemma 4.10 The set {z ∈ N | C(F Tz ) is a regular ω-language} is in the class Π 1 1 .

Theorem 4 .

 4 11 The set {z ∈ N | C(F Tz ) is a context-free ω-language} is Π 1 1 -hard and in the class Π 1 2 \ Σ 1 1 .

  {1, . . . , n}). Notice that there is a sequence of elements z p ∈ {a, b} ⋆ • b ω , p ≥ 1, such that the sequence (z p ) p≥1 is convergent and lim(z p ) = z = x(/{1, . . . , n}). This is due to the fact that {a, b} ⋆ .b ω is dense in {a, b} ω . We call t p the infinite word over the alphabet {1, . . . , n} ∪ {a, b} such that, for each integer i ≥ 1, we have t

p (i) = x(i) if x(i) ∈ {1, . . . , n} and t p (i) = z p (k) if x(i) is the k th letter of z.

Then the sequence (t p ) p≥1 is convergent and lim(t p ) = x. But by definition of F it holds that F (t p

The infinite Post Correspondence ProblemRecall first the well known result about the undecidability of the Post Correspondence Problem, denoted PCP.

be the Post Correspondence Problem of instance ((t 1 , t 2 , t 3 ), (w 1 , w 2 , w 3 )), where t 1 = c 2 , t 2 = t 3 = d and w 1 = w 2 = c, w 3 = d 2 . It is easy to see that its solutions are the sequences of indices in

In particular, this language over the alphabet {1, 2, 3} is not context-free and this will be useful in the sequel.

Let then I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) be an instance of the ω-PCP(Reg), where the x i and y i are words over an alphabet Γ. We can construct an ωrational function F ′ in the following way.

Let D = {d 1 , d 2 , d 3 } such that D and {1, . . . , n} ∪ {a, b} are disjoint. The domain Dom(F ′ ) will be a set of ω-words in D + • Dom(F ), where, as in the proof of Theorem 4.6, Dom(F ) is the set of ω-words x over the alphabet {1, . . . , n} ∪ {a, b} such that x(/{a, b}) ∈ L(A) (so in particular x(/{a, b}) is infinite) and x(/{1, . . . , n}) is infinite. It is clear that the domain Dom(F ′ ) is a regular ω-language.

, and

Then it is easy to see that the function F ′ is ω-rational and that one can construct a Büchi transducer T ′ accepting the graph of the function F ′ . Moreover one can construct an injective computable function Θ : N → N such that T ′ = T Θ( Ī) and so

Reasoning as in the preceding proof we can prove that the function

where y ∈ Dom(F ) , if and only if the the sequence j 1 , . . . , j p is a solution of the Post Correspondence Problem PCP 1 and y(/{a, b}

Thus if the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) has no solution, then the continuity set C(F ′ ) is empty, hence it is ω-regular.

On the other hand assume that the ω-PCP(Reg) of instance I = ((x 1 , . . . , x n ), (y 1 , . . . , y n ), A) has some solutions. In that case the continuity set

and R is a set of infinite words over the alphabet {1, . . . , n} ∪ {a, b}. In that case the continuity set C(F ′ ) can not be ω-regular because otherwise the language T