Olivier Finkel
email: finkel@logique.jussieu.fr

Decision Problems for Recognizable Languages of Infinite Pictures

Keywords: Languages of infinite pictures, recognizability by tiling systems, decision problems, unambiguity problem, cardinality problems

 where we gave the exact degree of numerous undecidable problems for Büchi-recognizable languages of infinite pictures, which are actually located at the first or at the second level of the analytical hierarchy, and "highly undecidable". Then we prove here some more (high) undecidability results. We first show that it is Π 1 2 -complete to determine whether a given Büchi-recognizable languages of infinite pictures is unambiguous. Then we investigate cardinality problems. Using recent results of [FL09], we prove that it is D 2 (Σ 1 1 )-complete to determine whether a given Büchi-recognizable language of infinite pictures is countably infinite, and that it is Σ 1 1 -complete to determine whether a given Büchi-recognizable language of infinite pictures is uncountable. Next we consider complements of recognizable languages of infinite pictures. Using some results of Set Theory, we show that the cardinality of the complement of a Büchi-recognizable language of infinite pictures may depend on the model of the axiomatic system ZFC. We prove that the problem to determine whether the complement of a given Büchi-recognizable language of infinite pictures is countable (respectively, uncountable) is in the class Σ 1 3 \ (Π 1 2 ∪ Σ 1 2 ) (respectively, in the class Π 1 3 \ (Π 1 2 ∪ Σ 1 2 )).

1

Introduction

Languages of infinite words accepted by finite automata were first studied by Büchi to prove the decidability of the monadic second order theory of one successor over the integers. Since then regular ω-languages have been much studied and many applications have been found for specification and verification of nonterminating systems, see [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF] for many results and references.

Altenbernd, Thomas and Wöhrle have considered in [START_REF] Altenbernd | Tiling systems over infinite pictures and their acceptance conditions[END_REF] acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. This way they extended both the classical theory of ω-regular languages and the classical theory of recognizable languages of finite pictures, [START_REF] Giammarresi | Two-dimensional languages[END_REF], to the case of infinite pictures.

Many classical decision problems are studied in formal language theory and in automata theory and arise now naturally about recognizable languages of infinite pictures.

In a recent paper, we gave the exact degree of numerous undecidable problems for Büchi-recognizable languages of infinite pictures. In particular, the non-emptiness and the infiniteness problems are Σ 1 1 -complete, and the universality problem, the inclusion problem, the equivalence problem, the complementability problem, and the determinizability problem, are all Π 1 2 -complete. These decision problems are then located at the first or at the second level of the analytical hierarchy, and "highly undecidable". This gave new natural examples of decision problems located at the first or at the second level of the analytical hierarchy.

Here we first review some of these results, and we study new decision problems, obtaining new results of high undecidability.

We first consider the notion of unambiguous Büchi tiling system, and of unambiguous Büchi-recognizable language of infinite pictures. We show that every language of infinite pictures which is accepted by an unambiguous Büchi tiling system is a Borel set. As a corollary this shows the existence of inherently ambiguous Büchi-recognizable language of infinite pictures. Then we use this result to prove that it is Π 1 2 -complete to determine whether a given Büchi-recognizable language of infinite pictures is unambiguous.

Next we study cardinality problems. Using recent results of Finkel and Lecomte in [START_REF] Finkel | Decision problems for Turing machines[END_REF], we first show that it is D 2 (Σ 1 1 )-complete to determine whether a given Büchi-recognizable language of infinite pictures is countably infinite, where D 2 (Σ 1 1 ) is the class of 2-differences of Σ 1 1 -sets, i.e. the class of sets which are intersections of a Σ 1 1 -set and of a Π 1 1 -set. And it is Σ 1 1 -complete to determine whether a given Büchi-recognizable language of infinite pictures is uncountable.

Then we consider the complements of Büchi-recognizable languages of infinite pictures. By using some results of Set Theory, we show that the cardinality of the complement of a Büchi-recognizable language of infinite pictures may depend on the actual model of the axiomatic system ZFC. We prove that one can effectively construct a Büchi tiling system T accepting a language L ⊆ Σ ω,ω , whose complement is L -= Σ ω,ω -L, such that:

1. There is a model V 1 of ZFC in which L -is countable. 2. There is a model V 2 of ZFC in which L -has cardinal 2 ℵ 0 . 3. There is a model V 3 of ZFC in which L -has cardinal ℵ 1 with ℵ 0 < ℵ 1 < 2 ℵ 0 .
Then, using the proof of this result and Schoenfield's Absoluteness Theorem, we prove that the problem to determine whether the complement of a given Büchirecognizable language of infinite pictures is countable (respectively, uncountable) is in the class

Σ 1 3 \ (Π 1 2 ∪ Σ 1 2 ) (respectively, in the class Π 1 3 \ (Π 1 2 ∪ Σ 1 2 ))
. This shows that natural cardinality problems are actually located at the third level of the analytical hierarchy.

The paper is organized as follows. We recall in Section 2 the notions of tiling systems and of recognizable languages of pictures. In section 3, we recall the definition of the analytical hierarchy on subsets of N. The definitions of the Borel hierarchy and of analytical sets of a Cantor space, along with their effective counterparts, are given in Section 4. Some notions of Set Theory, which are useful in the sequel, are exposed in Section 5. We study decision problems in Section 6, proving new results. Some concluding remarks are given in Section 7.

Tiling Systems

We assume 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 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. The length of x is k, denoted by |x|. The empty word has no letter and is denoted by λ; its length is 0. Σ ⋆ 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) for all n ≥ 1 and σ[0] = λ.
The usual concatenation 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 Σ ω .

We now define two-dimensional words, i.e. pictures. Let Σ be a finite alphabet, let # be a letter not in Σ and let

Σ = Σ ∪ {#}. If m and n are two positive integers or if m = n = 0, a picture of size (m, n) over Σ is a function p from {0, 1, . . . , m + 1} × {0, 1, . . . , n + 1} into Σ such that p(i, j) = # if i ∈ {0,
m+1} or j ∈ {0, n+1} and p(i, j) ∈ Σ otherwise. The empty picture is the only picture of size (0, 0) and is denoted by λ. Pictures of size (n, 0) or (0, n), for n > 0, are not defined. Σ ⋆,⋆ is the set of pictures over Σ. A picture language L is a subset of Σ ⋆,⋆ . The research on picture languages was firstly motivated by the problems arising in pattern recognition and image processing, a survey on the theory of picture languages may be found in [START_REF] Giammarresi | Two-dimensional languages[END_REF].

An ω-picture over Σ is a function p from ω ×ω into Σ such that p(i, 0) = p(0, i) = # for all i ≥ 0 and p(i, j) ∈ Σ for i, j > 0. Σ ω,ω is the set of ω-pictures over Σ. An ω-picture language L is a subset of Σ ω,ω . For Σ a finite alphabet we call Σ ω 2 the set of functions from ω × ω into Σ. So the set Σ ω,ω of ω-pictures over Σ is a strict subset of Σω 2 . We shall say that, for each integer j ≥ 1, the j th row of an ω-picture p ∈ Σ ω,ω is the infinite word p(1, j).p(2, j).p(3, j) . . . over Σ and the j th column of p is the infinite word p(j, 1).p(j, 2).p(j, 3) . . . over Σ. As usual, one can imagine that, for integers j > k ≥ 1, the j th column of p is on the right of the k th column of p and that the j th row of p is "above" the k th row of p.

We introduce now (non deterministic) tiling systems as in the paper [START_REF] Altenbernd | Tiling systems over infinite pictures and their acceptance conditions[END_REF]. A tiling system is a tuple A=(Q, Σ, ∆), where Q is a finite set of states, Σ is a finite alphabet, ∆ ⊆ ( Σ × Q) 4 is a finite set of tiles. A Büchi tiling system is a pair (A,F ) where A=(Q, Σ, ∆) is a tiling system and F ⊆ Q is the set of accepting states. A Muller tiling system is a pair (A, F ) where A=(Q, Σ, ∆) is a tiling system and F ⊆ 2 Q is the set of accepting sets of states. Tiles are denoted by (a 3 , q 3 ) (a 4 , q 4 ) (a 1 , q 1 ) (a 2 , q 2 ) with a i ∈ Σ and q i ∈ Q, and in general, over an alphabet Γ, by

b 3 b 4 b 1 b 2 with b i ∈ Γ.
A combination of tiles is defined by:

b 3 b 4 b 1 b 2 • b ′ 3 b ′ 4 b ′ 1 b ′ 2 = (b 3 , b ′ 3 ) (b 4 , b ′ 4 ) (b 1 , b ′ 1 ) (b 2 , b ′ 2 )
A run of a tiling system A=(Q, Σ, ∆) over a (finite) picture p of size (m, n) over Σ is a mapping ρ from {0, 1, . . . , m + 1} × {0, 1, . . . , n + 1} into Q such that for all (i, j) ∈ {0, 1, . . . , m} × {0, 1, . . . , n} with p(i, j) = a i,j and ρ(i, j) = q i,j we have a i,j+1 a i+1,j+1 a i,j a i+1,j • q i,j+1 q i+1,j+1 q i,j q i+1,j ∈ ∆.

A run of a tiling system A=(Q, Σ, ∆) over an ω-picture p ∈ Σ ω,ω is a mapping ρ from ω × ω into Q such that for all (i, j) ∈ ω × ω with p(i, j) = a i,j and ρ(i, j) = q i,j we have a i,j+1 a i+1,j+1 a i,j a i+1,j • q i,j+1 q i+1,j+1 q i,j q i+1,j ∈ ∆.

We now recall acceptance of finite or infinite pictures by tiling systems:

Definition 2.1 Let A=(Q, Σ, ∆) be a tiling system, F ⊆ Q and F ⊆ 2 Q .

• The picture language recognized by A is the set of pictures p ∈ Σ ⋆,⋆ such that there is some run ρ of A on p.

• The ω-picture language Büchi-recognized by (A,F ) is the set of ω-pictures p ∈ Σ ω,ω such that there is some run ρ of A on p and ρ(v) ∈ F for infinitely many v ∈ ω 2 . It is denoted by L B ((A,F )).

• The ω-picture language Muller-recognized by (A, F ) is the set of ω-pictures p ∈ Σ ω,ω such that there is some run ρ of A on p and Inf (ρ) ∈ F where Inf (ρ) is the set of states occurring infinitely often in ρ. It is denoted by L M ((A,F )).

Notice that an ω-picture language L ⊆ Σ ω,ω is recognized by a Büchi tiling system if and only if it is recognized by a Muller tiling system, [START_REF] Altenbernd | Tiling systems over infinite pictures and their acceptance conditions[END_REF].

We shall denote T S(Σ ω,ω ) the class of languages L ⊆ Σ ω,ω which are recognized by some Büchi (or Muller) tiling system.

Recall of Known Basic Notions

The Analytical Hierarchy

The set of natural numbers is denoted by N and the set of all mappings from N into N will be denoted by F .

We assume the reader to be familiar with the arithmetical hierarchy on subsets of N. We now recall the notions of analytical hierarchy and of complete sets for classes of this hierarchy which may be found in [START_REF] Rogers | Theory of Recursive Functions and Effective Computability[END_REF].

Definition 3.1 Let k, l > 0 be some integers. Φ is a partial recursive function 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 recursive function 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 3.2 Let k, l > 0 be some integers and R ⊆ F k × N l . The relation R is said

to be a recursive relation of k function variables and l number variables if its characteristic function is recursive.

We now define analytical subsets of N l .

Definition 3.3 A subset R of N l is analytical if it is recursive or if there exists a recursive 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.

The levels of the analytical hierarchy are distinguished by considering the number of alternations in the reduced prefix.

Definition 3.4 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 3.5 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 3.6 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 3.7 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 can now define the notion of 1-reduction and of Σ 1 n -complete (respectively, Π 1 n -complete) sets. Notice that we give the definition for subsets of N but one can easily extend this definition to the case of subsets of N l for some integer l.

Definition 3.8 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 such that A = f -1 [B]. Definition 3.9 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.
For each integer n ≥ 1 there exists some

Σ 1 n -complete set E n ⊆ N. The com- plement E - n = N -E n is a Π 1 n -complete set.
These sets are precisely defined in [START_REF] Rogers | Theory of Recursive Functions and Effective Computability[END_REF] or [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF].

Borel Hierarchy and Analytic Sets

We assume now the reader to be familiar with basic notions of topology which may be found in [Mos80, LT94, Kec95, Sta97, PP04].

There is a natural metric on the set Σ ω of infinite words over a finite alphabet Σ containing at least two letters which is called the prefix metric and defined as follows. For u, v ∈ Σ ω and u = v let δ(u, v) = 2 -l pref(u,v) where l pref(u,v) is the first integer n such that the (n + 1) st letter of u is different from the (n + 1) st letter of v. This metric induces on Σ ω the usual Cantor topology for which open subsets of Σ ω are in the form W.Σ ω , where W ⊆ Σ ⋆ . A set L ⊆ Σ ω is a closed set iff its complement Σ ω -L is an open set. Now let define the Borel Hierarchy of subsets of Σ ω : Definition 3.10 For a non-null countable ordinal α, the classes Σ 0 α and Π 0 α of the Borel Hierarchy on the topological space Σ ω are defined as follows: Σ 0 1 is the class of open subsets of Σ ω , Π 0 1 is the class of closed subsets of Σ ω , and for any countable ordinal α ≥ 2:

Σ 0 α is the class of countable unions of subsets of Σ ω in γ<α Π 0 γ . Π 0 α is the class of countable intersections of subsets of Σ ω in γ<α Σ 0 γ . For a countable ordinal α, a subset of Σ ω is a Borel set of rank α iff it is in Σ 0 α ∪Π 0 α but not in γ<α (Σ 0 γ ∪ Π 0 γ ).
There are also some subsets of Σ ω which are not Borel. Indeed there exists another hierarchy beyond the Borel hierarchy, which is called the projective hierarchy and which is obtained from the Borel hierarchy by successive applications of operations of projection and complementation. The first level of the projective hierarchy is formed by the class of analytic sets and the class of co-analytic sets which are complements of analytic sets. In particular the class of Borel subsets of Σ ω is strictly included into the class Σ 1 1 of analytic sets which are obtained by projections of Borel sets.

Definition 3.11 A subset A of Σ ω is in the class Σ 1 1 of analytic sets iff there exist a finite set Y and a Borel subset B of (Σ × Y ) ω such that [x ∈ A ↔ ∃y ∈ Y ω (x, y) ∈ B]
, where (x, y) is the infinite word over the alphabet Σ × Y such that (x, y)(i) = (x(i), y(i)) for each integer i ≥ 1.

We now define completeness with regard to reduction by continuous functions. For a countable ordinal α ≥ 1, a set F ⊆ Σ ω is said to be a Σ 0 α (respectively,

Π 0 α , Σ 1 1 )-complete set iff for any set E ⊆ Y ω (with Y a finite alphabet): E ∈ Σ 0 α (respectively, E ∈ Π 0 α , E ∈ Σ 1 1 ) iff there exists a continuous function f : Y ω → Σ ω such that E = f -1 (F ). Σ 0
n (respectively Π 0 n )-complete sets, with n an integer ≥ 1, are thoroughly characterized in [START_REF] Staiger | Hierarchies of recursive ω-languages[END_REF].

In particular R = (0 ⋆ .1) ω is a well known example of a Π 0 2 -complete subset of {0, 1} ω . It is the set of ω-words over {0, 1} having infinitely many occurrences of the letter 1.

Its complement {0, 1} ω -(0 ⋆ .1) ω is a Σ 0 2 -complete subset of {0, 1} ω .
We recall now the definition of the arithmetical hierarchy of ω-languages which form the effective analogue to the hierarchy of Borel sets of finite ranks. Let X be a finite alphabet. An ω-language L ⊆ X ω belongs to the class Σ n if and only if there exists a recursive relation

R L ⊆ (N) n-1 × X ⋆ such that L = {σ ∈ X ω | ∃a 1 . . . Q n a n (a 1 , . . . , a n-1 , σ[a n + 1]) ∈ R L }
where Q i is one of the quantifiers ∀ or ∃ (not necessarily in an alternating order).

An ω-language L ⊆ X ω belongs to the class Π n if and only if its complement X ω -L belongs to the class Σ n . The inclusion relations that hold between the classes Σ n and Π n are the same as for the corresponding classes of the Borel hierarchy. The classes Σ n and Π n are included in the respective classes Σ 0 n and Σ 0 n of the Borel hierarchy, and cardinality arguments suffice to show that these inclusions are strict.

As in the case of the Borel hierarchy, projections of arithmetical sets (of the second Π-class) lead beyond the arithmetical hierarchy, to the analytical hierarchy of ω-languages. The first class of this hierarchy is the (lightface) class Σ 1 1 of effective analytic sets which are obtained by projection of arithmetical sets. An ω-language L ⊆ X ω belongs to the class Σ 1 1 if and only if there exists a recursive relation R L ⊆ N × {0, 1} ⋆ × X ⋆ such that:

L = {σ ∈ X ω | ∃τ (τ ∈ {0, 1} ω ∧ ∀n∃m((n, τ [m], σ[m]) ∈ R L ))}
Then an ω-language L ⊆ X ω is in the class Σ 1 1 iff it is the projection of an ωlanguage over the alphabet X × {0, 1} which is in the class Π 2 . The (lightface) class Π 1 1 of effective co-analytic sets is simply the class of complements of effective analytic sets. We denote as usual

∆ 1 1 = Σ 1 1 ∩ Π 1 1 . Recall that an ω-language L ⊆ X ω is in the class Σ 1
1 iff it is accepted by a non deterministic Turing machine (reading ω-words) with a Büchi or Muller acceptance condition [START_REF] Cohen | ω-computations on Turing machines[END_REF][START_REF] Staiger | ω-languages[END_REF].

For Γ a finite alphabet having at least two letters, the set Γ ω×ω of functions from ω×ω into Γ is usually equipped with the product topology of the discrete topology on Γ. This topology may be defined by the following distance d. Let x and y in Γ ω×ω such that x = y, then d(x, y) = 1 2 n where n = min{p ≥ 0 | ∃(i, j) x(i, j) = y(i, j) and i + j = p}.

Then the topological space Γ ω×ω is homeomorphic to the topological space Γ ω , equipped with the Cantor topology. Borel subsets of Γ ω×ω are defined from open subsets as in the case of the topological space Γ ω . Analytic subsets of Γ ω×ω are obtained as projections on Γ ω×ω of Borel subsets of the product space Γ ω×ω × Γ ω . The set Σ ω,ω of ω-pictures over Σ, considered a topological subspace of Σω×ω , is easily seen to be homeomorphic to the topological space Σ ω×ω , via the mapping ϕ : Σ ω,ω → Σ ω×ω defined by ϕ(p)(i, j) = p(i + 1, j + 1) for all p ∈ Σ ω,ω and i, j ∈ ω.

Some Results of Set Theory

We now recall some basic notions of set theory which will be useful in the sequel, and which are exposed in any textbook on set theory, like [START_REF] Jech | Set theory[END_REF].

The usual axiomatic system ZFC is Zermelo-Fraenkel system ZF plus the axiom of choice AC. A model (V, ∈) of the axiomatic system ZFC is a collection V of sets, equipped with the membership relation ∈, where "x ∈ y" means that the set x is an element of the set y, which satisfies the axioms of ZFC. We shall often say " the model V" instead of "the model (V, ∈)".

The axioms of ZFC express some natural facts that we consider to hold in the universe of sets. For instance a natural fact is that two sets x and y are equal iff they have the same elements. This is expressed by the Axiom of Extensionality.

Another natural axiom is the Pairing Axiom which states that for all sets x and y there exists a set z = {x, y} whose elements are x and y. Similarly the Powerset Axiom states the existence of the set of subsets of a set x. We refer the reader to any textbook on set theory, like [START_REF] Jech | Set theory[END_REF], for an exposition of the other axioms of ZFC.

The infinite cardinals are usually denoted by ℵ 0 , ℵ 1 , ℵ 2 , . . . , ℵ α , . . . The cardinal ℵ α is also denoted by ω α , as usual when it is considered an ordinal.

The continuum hypothesis CH says that the first uncountable cardinal ℵ 1 is equal to 2 ℵ 0 which is the cardinal of the continuum. Gödel and Cohen proved that the continuum hypothesis CH is independent from the axiomatic system ZFC: providing ZFC is consistent, there exist some models of ZFC + CH and also some models of ZFC + ¬ CH, where ¬ CH denotes the negation of the continuum hypothesis, [START_REF] Jech | Set theory[END_REF].

Let ON be the class of all ordinals. Recall that an ordinal α is said to be a successor ordinal iff there exists an ordinal β such that α = β + 1; otherwise the ordinal α is said to be a limit ordinal and in that case α = sup{β ∈ ON | β < α}.

The class L of constructible sets in a model V of ZF is defined by

L = α∈ON L(α)
where the sets L(α) are constructed by induction as follows:

1. L(0) = ∅ 2. L(α) = β<α L(β), for α a limit ordinal, and 3. L(α + 1) is the set of subsets of L(α) which are definable from a finite number of elements of L(α) by a first-order formula relativized to L(α).

If V is a model of ZF and L is the class of constructible sets of V, then the class L forms a model of ZFC + CH. Notice that the axiom (V=L) means "every set is constructible" and that it is consistent with ZFC.

Consider now a model V of the axiomatic system ZFC and the class of constructible sets L ⊆ V which forms another model of ZFC. It is known that the ordinals of L are also the ordinals of V. But the cardinals in V may be different from the cardinals in L.

In particular, the first uncountable cardinal in L is denoted

ℵ L 1 . It is in fact an ordinal of V which is denoted ω L 1 .
It is known that this ordinal satisfies the inequality ω L 1 ≤ ω 1 . In a model V of the axiomatic system ZFC + V=L the equality ω L 1 = ω 1 holds. But in some other models of ZFC the inequality may be strict and then ω L 1 < ω 1 . This is explained in [Jec02, page 202]: one can start from a model V of ZFC + V=L and construct by forcing a generic extension V[G] in which the cardinals ω and ω 1 are collapsed; in this extension the inequality ω L 1 < ω 1 holds.

We now recall the notion of a perfect set.

Definition 3.12 Let P ⊆ Σ ω , where Σ is a finite alphabet having at least two letters. The set P is said to be a perfect subset of Σ ω if and only if :

(1) P is a non-empty closed set, and

(2) for every x ∈ P and every open set U containing x there is an element y ∈ P ∩ U such that x = y.

So a perfect subset of Σ ω is a non-empty closed set which has no isolated points. It is well known that a perfect subset of Σ ω has cardinality 2 ℵ 0 , see [START_REF] Moschovakis | Descriptive set theory[END_REF]page 66].

We now recall the notion of thin subset of Σ ω . Definition 3.13 A set X ⊆ Σ ω is said to be thin iff it contains no perfect subset.

The following important result was proved by Kechris [START_REF] Kechris | The theory of countable analytical sets[END_REF] and independently by Guaspari [START_REF] Guaspari | Thin and well ordered analytical sets[END_REF] and Sacks [START_REF] Sacks | Countable admissible ordinals and hyperdegrees[END_REF].

Theorem 3.14 (see [Mos80] page 247) (ZFC) Let Σ be a finite alphabet having at least two letters. There exists a thin

Π 1 1 -set C 1 (Σ ω ) ⊆ Σ ω which contains every thin, Π 1 1 -subset of Σ ω . It is called the largest thin Π 1 1 -set in Σ ω .
An important fact is that the cardinality of the largest thin Π 1 1 -set in Σ ω depends on the model of ZFC. The following result on the cardinality of C 1 (Σ ω ), was proved by Kechris and independently by Guaspari and Sacks, see also [START_REF] Kanamori | The Higher Infinite[END_REF]page 171].

Theorem 3.15 (ZFC) The cardinal of the largest thin

Π 1 1 -set in Σ ω is equal to the cardinal of ω L 1 .
This means that in a given model V of ZFC the cardinal of the largest thin Π 1 1 -set in Σ ω is equal to the cardinal in V of the ordinal ω L 1 which plays the role of the cardinal ℵ 1 in the inner model L of constructible sets of V.

We can now state the following result which will be useful in the sequel.

Corollary 3.16

(a) There is a model V 1 of ZFC in which the largest thin Π 1 1 -set in Σ ω has cardinal ℵ 1 , where ℵ 1 = 2 ℵ 0 . (b) There is a model V 2 of ZFC in which the largest thin Π 1 1 -set in Σ ω has cardinal ℵ 0 , i.e. is countably infinite. (c) There is a model V 3 of ZFC in which the largest thin Π 1 1 -set in Σ ω has cardinal ℵ 1 , where ℵ 0 < ℵ 1 < 2 ℵ 0 .
Proof. (a). In the model L, the cardinal of the largest thin Π 1 1 -set in Σ ω is equal to the cardinal of ω 1 . Moreover the continuum hypothesis is satisfied thus

2 ℵ 0 = ℵ 1 . Thus the largest thin Π 1 1 -set in Σ ω has the cardinality 2 ℵ 0 = ℵ 1 . (b). Let V be a model of (ZFC + ω L 1 < ω 1 ). In this model ω 1 is the first un- countable ordinal. Thus ω L 1 < ω 1 implies that ω L 1 is a countable ordinal in V.
Its cardinal is ℵ 0 and it is also the cardinal of the largest thin Π 1 1 -set in Σ ω .

(c). It suffices to show that there is a model V 3 of ZFC in which ω L 1 = ω 1 and ℵ 1 < 2 ℵ 0 . Such a model can be constructed by Cohen's forcing. We can start from a model V of ZFC + V=L (in which ω L 1 = ω 1 ) and construct by forcing a generic extension V[G] in which ℵ 2 subsets of ω are added. Notice that the cardinals are preserved under this extension (see [START_REF] Jech | Set theory[END_REF]page 219]) and that the constructible sets of V[G] are also the constructible sets of V. Thus in the new model

V[G] we still have ω L 1 = ω 1 but now ℵ 1 < 2 ℵ 0 .

Decision Problems

We now study decision problems for recognizable languages of infinite pictures. We gave in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF] the exact degree of several natural decision problems. We first recall some of these results.

Castro and Cucker proved in [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF] that the non-emptiness problem and the infiniteness problem for ω-languages of Turing machines are both Σ 1 1 -complete. We easily inferred from this result a similar result for recognizable languages of infinite pictures.

From now on we shall denote by T z the non deterministic tiling system of index z, (accepting pictures over Σ = {a, b}), equipped with a Büchi acceptance condition.

Theorem 4.1 ([Fin09b])

The non-emptiness problem and the infiniteness problem for Büchi-recognizable languages of infinite pictures are Σ 1 1 -complete, i.e. :

1. {z ∈ N | L B (T z ) = ∅} is Σ 1 1 -complete. 2. {z ∈ N | L B (T z ) is infinite } is Σ 1 1 -complete.
In a similar way, the universality problem and the inclusion and the equivalence problems, for ω-languages of Turing machines, have been proved to be Π 1 2 -complete by Castro and Cucker in [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF], and we used these results to prove the following results in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF].

Theorem 4.2 ([Fin09b])

The universality problem for Büchi-recognizable languages of infinite pictures is Π 1 2 -complete, i.e. :

{z ∈ N | L B (T z ) = Σ ω,ω } is Π 1 2 -complete.

Theorem 4.3 ([Fin09b])

The inclusion and the equivalence problems for Büchirecognizable languages of infinite pictures are Π 1 2 -complete, i.e. :

1. {(y, z) ∈ N 2 | L B (T y ) ⊆ L B (T z )} is Π 1 2 -complete. 2. {(y, z) ∈ N 2 | L B (T y ) = L B (T z )} is Π 1 2 -complete.
The class of Büchi-recognizable languages of infinite pictures is not closed under complement [START_REF] Altenbernd | Tiling systems over infinite pictures and their acceptance conditions[END_REF]. Thus the following question naturally arises: "can we decide whether the complement of a Büchi-recognizable language of infinite pictures is Büchi-recognizable?". And what is the exact complexity of this decision problem, called the complementability problem.

Another classical problem is the determinizability problem: "can we decide whether a given recognizable language of infinite pictures is recognized by a deterministic tiling system?". Recall that a tiling system is called deterministic if on any picture it allows at most one tile covering the origin, the state assigned to position (i + 1, j + 1) is uniquely determined by the states at positions (i, j), (i + 1, j), (i, j + 1) and the states at the border positions (0, j + 1) and (i + 1, 0) are determined by the state (0, j), respectively (i, 0), [START_REF] Altenbernd | Tiling systems over infinite pictures and their acceptance conditions[END_REF]. As remarked in [START_REF] Altenbernd | Tiling systems over infinite pictures and their acceptance conditions[END_REF], the hierarchy proofs of the classical Landweber hierarchy defined using deterministic ω-automata "carry over without essential changes to pictures". In particular, a language of ω-pictures which is Büchi-recognized by a deterministic tiling system is a Π 0 2 -set and a language of ω-pictures which is Muller-recognized by a deterministic tiling system is a boolean combination of Π 0 2 -sets, hence a ∆ 0 3 -set.

These topological properties have been used in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF], along with a dichotomy property, to prove the following results.

Theorem 4.4 ([Fin09b])

The determinizability problem and the complementability problem for Büchi-recognizable languages of infinite pictures are Π 1 2 -complete, i.e. :

1. {z ∈ N | L B (T z ) is Büchi-recognizable by a deterministic tiling system} is Π 1 2 -complete. 2. {z ∈ N | L B (T z ) is Muller-recognizable by a deterministic tiling system } is Π 1 2 -complete. 3. {z ∈ N | ∃y Σ ω,ω -L B (T z ) = L B (T y )} is Π 1 2 -complete.
We already mentioned that we used some results of Castro and Cucker in the proof of the above results. Castro and Cucker studied degrees of decision problems for ω-languages accepted by Turing machines and proved that many of them are highly undecidable, [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF]. We are going to use again some of their results to prove here new results about Büchi-recognizable languages of infinite pictures.

We firstly recall the notion of acceptance of infinite words by Turing machines considered by Castro and Cucker in [START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF].

Definition 4.5 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 Σ ⊆ Γ, q 0 is the initial state, and δ is a mapping from Q × Γ to subsets of Q×Γ×{L, R, S}. A configuration of M is a 3-tuple (q, σ, i), where q ∈ Q, σ ∈ Γ ω and i ∈ N. An infinite sequence of configurations r = (q i , α i , j i ) i≥1 is called a run of M on w ∈ Σ ω iff:

(a) (q 1 , α 1 , j 1 ) = (q 0 , w, 1), and (b) for each i ≥ 1, (q i , α i , j i ) ⊢ (q i+1 , α i+1 , j i+1 ),

where ⊢ is the transition relation of M defined as usual. The run r is said to be complete if the limsup of the head positions is infinity, i.e. if (∀n ≥ 1)(∃k ≥ 1)(j k ≥ n). The run r is said to be oscillating if the liminf of the head positions is bounded, i.e. if (∃k ≥ 1)(∀n ≥ 1)(∃m ≥ n)(j m = k).

Definition 4.6 Let M = (Q, Σ, Γ, δ, q 0 ) be a non deterministic Turing machine and F ⊆ Q. The ω-language accepted by (M, F ) is the set of ω-words σ ∈ Σ ω such that there exists a complete non oscillating run r = (q i , α i , j i ) i≥1 of M on σ such that, for all i, q i ∈ F.

The above acceptance condition is denoted 1 ′ -acceptance in [START_REF] Cohen | ω-computations on Turing machines[END_REF]. Another usual acceptance condition is the now called Büchi acceptance condition which is also denoted 2-acceptance in [START_REF] Cohen | ω-computations on Turing machines[END_REF]. We now recall its definition.

Definition 4.7 Let M = (Q, Σ, Γ, δ, q 0 ) be a non deterministic Turing machine and F ⊆ Q. The ω-language Büchi accepted by (M, F ) is the set of ω-words σ ∈ Σ ω such that there exists a complete non oscillating run r = (q i , α i , j i ) i≥1 of M on σ and infinitely many integers i such that q i ∈ F.

Recall that Cohen and Gold proved in [CG78, Theorem 8.6] that one can effectively construct, from a given non deterministic Turing machine, another equivalent non deterministic Turing machine, equipped with the same kind of acceptance condition, and in which every run is complete non oscillating. Cohen and Gold proved also in [CG78, Theorem 8.2] that an ω-language is accepted by a non deterministic Turing machine with 1 ′ -acceptance condition iff it is accepted by a non deterministic Turing machine with Büchi acceptance condition.

From now on, we shall denote M z the non deterministic Turing machine of index z, (accepting words over Σ = {a, b}), equipped with a 1 ′ -acceptance condition.

An important notion in automata theory is the notion of ambiguity. It can be defined also in the context of acceptance by tiling systems, see [START_REF] Anselmo | Unambiguous recognizable two-dimensional languages[END_REF] for the case of finite pictures.

Definition 4.8 Let A=(Q, Σ, ∆) be a tiling system, and F ⊆ Q. The Büchi tiling system (A, F ) is unambiguous iff every ω-picture p ∈ Σ ω,ω has at most an accepting run by (A, F ).

Definition 4.9 A Büchi recognizable language L ⊆ Σ ω,ω is unambiguous iff there exists an unambiguous Büchi tiling system (A, F ) such that L = L(A, F ). Otherwise the language L is said to be inherently ambiguous.

We can now prove the following result, which is very similar to a corresponding result for recognizable tree languages proved in [START_REF] Finkel | On recognizable tree languages beyond the Borel hierarchy[END_REF].

Proposition 4.10 Let L ⊆ Σ ω,ω be an unambiguous Büchi recognizable language of infinite pictures. Then L is a Borel subset of Σ ω,ω .

Proof. Let L ⊆ Σ ω,ω be a language accepted by an unambiguous Büchi tiling system (A, F ), where A=(Q, Σ, ∆), and let R ⊆ ( Σ × Q) ω×ω be defined by: R = {(p, ρ) | p ∈ Σ ω,ω and ρ ∈ is an accepting run of (A, F ) on the picture p}.

The set R is easily seen to be a Π 0 2 -subset of ( Σ × Q) ω×ω . Proof. The result follows directly from the above proposition because we know that there exist some Büchi-recognizable languages of infinite pictures which are not Borel sets, see [START_REF] Finkel | On recognizable languages of infinite pictures[END_REF][START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF].

Consider now the projection PROJ

Σω×ω : Σω×ω × Q ω×ω → Σω×ω defined by PROJ Σω×ω ((p, ρ)) = p for all (p, ρ) ∈ Σω×ω × Q ω×ω .
We can now state that the unambiguity problem for recognizable language of infinite pictures is Π 1 2 -complete.

Theorem 4.12 The unambiguity problem for recognizable languages of infinite pictures is Π 1 2 -complete, i.e. :

{z ∈ N | L B (T z ) is non ambiguous } is Π 1 2 -complete.
Proof. To prove that the unambiguity problem for recognizable language of infinite pictures is in the class Π 1 2 , we reason as in the case of the unambiguity problem for ω-languages accepted by 1-counter or 2-tape automata, see [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF].

Notice first, as in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF], that, using a recursive bijection b : (N -{0}) 2 → N-{0}, one can associate with each ω-word σ ∈ Σ ω a unique ω-picture p σ ∈ Σ ω,ω which is simply defined by p σ (i, j) = σ(b(i, j)) for all integers i, j ≥ 1. And we can identify a run ρ ∈ Q ω×ω with an element of Q ω and finally with a coding of this element over the alphabet {0, 1}. So the run ρ can be identified with its code ρ ∈ {0, 1} ω . If a tiling system A=(Q, Σ, ∆) is equipped with a set of accepting states F ⊆ Q, then for σ ∈ Σ ω and ρ ∈ {0, 1} ω , "ρ is a Büchi accepting run of (A, F ) over the ω-picture p σ " can be expressed by an arithmetical formula, see [ATW03, Section 2.4] and [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF].

We can now first express "T z is non ambiguous" by : "∀σ ∈ Σ ω ∀ρ, ρ ′ ∈ {0, 1} ω [(ρ and ρ ′ are accepting runs of T z on p σ ) → ρ = ρ ′ ]" which is a Π 1 1 -formula. Then " L B (T z ) is non ambiguous" can be expressed by the following formula: "∃y[L B (T z ) = L B (T y ) and T y is non ambiguous]". This is a Π 1 2 -formula because L B (T z ) = L B (T y ) can be expressed by a Π 1 2 -formula, and the quantification ∃y is of type 0. Thus the set {z ∈ N | L B (T z ) is non ambiguous } is a Π 1 2 -set.

To prove the completeness part of the theorem, we shall use the following dichotomy result proved in [Fin09b, proof of Theorem 5.11].

There exists an injective computable function H • θ from N into N such that:

First case: If L(M z ) = Σ ω then L B (T H•θ(z) ) = Σ ω,ω . Second case: If L(M z ) = Σ ω then L B (T H•θ(z)
) is not a Borel set.

In the first case L B (T H•θ(z) ) = Σ ω,ω is obviously an unambiguous language. And in the second case the language L B (T H•θ(z) ) cannot be unambiguous because it is not a Borel subset of Σ ω,ω . Thus, using the reduction H • θ, we see that : Notice that the same dichotomy result above with the reduction H • θ was used in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF] to prove that topological properties of recognizable languages of infinite pictures are actually highly undecidable. Theorem 4.13 ([Fin09b]) Let α be a non-null countable ordinal. Then

1. {z ∈ N | L B (T z ) is in the Borel class Σ 0 α } is Π 1 2 -hard. 2. {z ∈ N | L B (T z ) is in the Borel class Π 0 α } is Π 1 2 -hard. 3. {z ∈ N | L B (T z ) is a Borel set } is Π 1 2 -hard.
A natural question is to study similar problems by replacing Borel classes by the effective classes of the arithmetical hierarchy. This was not studied in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF], but a similar problem was solved in [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF] for ω-languages accepted by 1counter or 2-tape Büchi automata. We can reason in a similar way for the case of recognizable languages of infinite pictures, and state the following result.

  {z ∈ N | L(M z ) = Σ ω } ≤ 1 {z ∈ N | L B (T z ) is non ambiguous }and the result follows from the Π 1 2 -completeness of the universality problem for ω-languages of Turing machines proved by Castro and Cucker in[START_REF] Castro | Nondeterministic ω-computations and the analytical hierarchy[END_REF].

  This projection is a continuous function and it is injective on the Borel set R because the Büchi tiling system (A, F ) is unambiguous. Hence, by a Theorem of Lusin and Souslin, see [Kec95, Theorem 15.1 page 89], the injective image of R by the continuous function PROJ Σω×ω is Borel. Thus the language L = PROJ Σω×ω (R) is a Borel subset of Σω×ω . But Σ ω,ω is a closed subset of Σω×ω and L ⊆ Σ ω,ω . Thus L is also a Borel subset of Σ ω,ω .

	Corollary 4.11 There exist some inherently ambiguous Büchi-recognizable lan-
	guages of infinite pictures.

We are now looking at complements of recognizable languages of infinite pictures. We first state the following result which shows that actually the cardinality of the complement of a recognizable language of infinite pictures may depend on the models of set theory. We denote L B (T ) -the complement Σ ω,ω -L B (T ) of a Büchi-recognizable language L B (T ) ⊆ Σ ω,ω .

Theorem 4.14 Let n ≥ 1 be an integer. Then

We do not give the complete proof here. It is actually very similar to the case of ω-languages accepted by 1-counter or 2-tape Büchi automata in [START_REF] Finkel | Highly undecidable problems for infinite computations[END_REF]. A key argument, to prove that {z ∈ N | L B (T z ) is in the arithmetical class Σ n } (respectively, {z ∈ N | L B (T z ) is in the arithmetical class Π n }) is a Π 1 2 -set, is the existence of a universal set U Σn ⊆ N × Σ ω,ω (respectively, U Πn ⊆ N × Σ ω,ω ) for the class of Σ n -subsets of Σ ω,ω , (respectively, Π n -subsets of Σ ω,ω ), [START_REF] Moschovakis | Descriptive set theory[END_REF]p. 172]. Notice also that the completeness part follows easily from the dichotomy result obtained with the reduction H • θ.

We now come to cardinality problems. We already know that it is Σ 1 1 -complete to determine whether a given recognizable language of infinite pictures is empty (respectively, infinite). Recall that every recognizable language of infinite pictures is an analytic set. On the other hand, every analytic set is either countable or has the cardinality 2 ℵ 0 of the continuum. Then some questions naturally arise. What are the complexities of the following decision problems: "Is a given recognizable language of infinite pictures countable? Is it countably infinite? Is it uncountable?". Notice that similar questions were asked by Castro and Cucker in the case of ω-languages of Turing machines and have been solved very recently by Finkel and Lecomte in [START_REF] Finkel | Decision problems for Turing machines[END_REF]. We can now state the following result for recognizable languages of infinite pictures. Below D 2 (Σ 1 1 ) denotes the class of 2-differences of Σ 1 1 -sets, i.e. the class of sets which are intersections of a Σ 1 1 -set and of a Π 1 1 -set.

Theorem 4.15

Proof.

(1). We can first prove that {z ∈ N | L B (T z ) is countable} is in the class Π 1 1 in the same way as in the case of ω-languages of Turing machines in [START_REF] Finkel | Decision problems for Turing machines[END_REF]. We know that a recognizable language of infinite pictures

for more details.

To prove the completeness part of Item (1), we shall use the following two lemmas proved in previous papers.

For σ ∈ Σ ω = {a, b} ω we denote σ a the ω-picture whose first row is the ω-word σ and whose other rows are labelled with the letter a. For an ω-language L ⊆ Σ ω = {a, b} ω we denote L a the language of infinite pictures {σ a | σ ∈ L}.

Lemma 4.16 ([Fin04]

) If L ⊆ Σ ω is accepted by some Turing machine (in which every run is complete non oscillating) with a Büchi acceptance condition, then L a is Büchi recognizable by a finite tiling system.

Lemma 4.17 ([Fin09b])

There is an injective computable function K from N into N satisfying the following property. If M z is the non deterministic Turing machine (equipped with a 1 ′ -acceptance condition) of index z, and if T K(z) is the tiling system (equipped with a Büchi acceptance condition) of index K(z), then

On the other hand, we can easily see that the cardinality of the ω-language L(M z ) is equal to the cardinality of the ω-picture language L(M z ) a . Thus using the reduction K given in the above lemma we see that:

(2). The proof of Item (2) follows directly from Item (1).

(3). We already know that the set

. Using again the reduction K we see that:

Theorem 4. 18 The cardinality of the complement of a Büchi-recognizable language of infinite pictures is not determined by the axiomatic system ZFC. Indeed there is a Büchi tiling system T such that:

Recall that one can construct, from the Σ 1 1 -formula ψ defining C 1 (Σ ω ) -, a Büchi Turing machine M accepting the ω-language C 1 (Σ ω ) -.

On the other hand it is easy to see that the language Σ ω,ω -(Σ ω ) a of ω-pictures is Büchi recognizable. But the class T S(Σ ω,ω ) is closed under finite union, so we get the following result.

Lemma 4.19 ([Fin09b]

) If L ⊆ Σ ω is accepted by some Turing machine with a Büchi acceptance condition, then L a ∪ [Σ ω,ω -(Σ ω ) a ] is Büchi recognizable by a finite tiling system.

Notice that the constructions are effective and that they can be achieved in an injective way. Thus we can construct, from the Büchi Turing machine M accepting the ω-language C 1 (Σ ω ) -, a Büchi tiling system T such that

It is then easy to see that:

Thus the cardinality of L B (T ) -is equal to the cardinality of the ω-language C 1 (Σ ω ), and then we can infer the results of the theorem from previous Corollary 3.16.

We can now use the proof of the above result to prove the following result which shows that natural cardinality problems are actually located at the third level of the analytical hierarchy.

Theorem 4.20

Proof. Item (1) was proved in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF].

To prove Item (2), we first show that {z

As in [START_REF] Finkel | Highly undecidable problems about recognizability by tiling systems[END_REF], using a recursive bijection b : (N -{0}) 2 → N -{0}, we can consider an infinite word σ ∈ Σ ω as a countably infinite family of infinite words over Σ : the family of ω-words (σ i ) such that for each i ≥ 1, σ i is defined by σ i (j) = σ(b(i, j)) for each j ≥ 1. And one can associate with each ω-word σ ∈ Σ ω a unique ω-picture p σ ∈ Σ ω,ω which is simply defined by p σ (i, j) = σ(b(i, j)) for all integers i, j ≥ 1.

We can now express "L B (T z ) -is countable " by the formula:

This is a Σ 1 3 -formula because "p ∈ L B (T z )", and hence also "[(p ∈ L B (T z )) or (∃i ∈ N p = p σ i )]", is expressed by a Σ 1 1 -formula.

We can now prove that {z ∈ N | L B (T z ) -is countable } is neither in the class Σ 1 2 nor in the class Π 1 2 , by using Shoenfield's Absoluteness Theorem from Set Theory.

Let T be the Büchi tiling system obtained in Theorem 4.18 and let z 0 be its index so that T = T z 0 .

Assume now that V is a model of (ZFC + ω L 1 < ω 1 ). In the model V, by the proofs of Theorem 4.18 and of Corollary 3.16, the integer z 0 belongs to the set {z

But, by the proofs of Theorem 4.18 and of Corollary 3.16, in the inner model L ⊆ V, the language L B (T z 0 ) -has cardinality 2 ℵ 0 . Thus the integer z 0 does not belong to the set {z ∈ N | L B (T z ) -is countable }.

On the other hand, Schoenfield's Absoluteness Theorem implies that every Σ 1 2 -set (respectively, Π 1 2 -set) is absolute for all inner models of (ZFC), see [Jec02, page 490]. In particular, if the set {z ∈ N | L B (T z ) -is countable } was a Σ 1 2 -set or a Π 1 2 -set then it could not be a different subset of N in the models V and L considered above. Therefore, the set {z ∈ N | L B (T z ) -is countable } is neither a Σ 1 2 -set nor a Π 1 2 -set.

Item (3) follows directly from Item (2).

Concluding Remarks

Using the notion of largest effective coanalytic set, we have proved in another paper that the topological complexity of a recognizable language of infinite pictures is not determined by the axiomatic system ZFC. In particular, there is a Büchi tiling system S and models V 1 and V 2 of ZFC such that: the ω-picture language L(S) id Borel in V 1 but not in V 2 , [START_REF] Finkel | The complexity of infinite computations in models of set theory[END_REF].

We have proved in this paper that {z ∈

It remains open whether this set is actually Σ 1 3 -complete.


L Leguen

F Huchet

P Tamagny

Drying and Heating Modelling of Granular Flow: Application to the Mix-Asphalt Processes

Keywords: Asphalt mix plant, Rotary drum dryer, Granular flow, Heat and mass transfer, Modeling

Concrete asphalt is a hydrocarbon material that includes a mix of mineral components along with a bituminous binder. Prior to mixing, its production protocol requires drying and heating the aggregates. Generally performed in a rotary drum, these drying and heating steps within mix asphalt processes have never been studied from a physical perspective. We are thus proposing in the present paper to analyze the drying and heating mechanisms when granular materials and hot gases are involved in a co-current flow. This process step accounts for a large proportion of the overall energy consumed during hot-mix asphalt manufacturing. In the present context, the high energy cost associated with this step has encouraged developing new strategies specifically for the drying process. Applying new asphalt techniques so that an amount of moisture can be preserved in the asphalt concrete appears fundamental to such new strategies. This low-energy asphalt, also referred to as the "warm technique", depends heavily on a relevant prediction of the actual moisture content inside asphalt concrete during the mixing step. The purpose of this paper is to present a physical model dedicated to the evolution in temperature and moisture of granular solids throughout the drying and heating steps carried out inside a rotary drum. An initial experimental campaign to visualize inside a drum at the pilot scale (i.e. 1/3 scale) has been carried out in order to describe the granular flow and establish the necessary physical assumptions for the drying and heating model. Energy and mass balance equations are solved by implementing an adequate heat and mass transfer coupling, yielding a 1D model from several parameters that in turn drives the physical modeling steps. Moreover, model results will be analyzed and compared to several measurements performed in an actual asphalt mix plant at the industrial scale (i.e. full scale).

Thermal diffusion coefficient (m².s 1 ) Thermal conductivity (W.m -1 .K -1 ) Dynamic viscosity (m.s.kg -1 ) Kinematic viscosity (m².s -1 ) Density (kg.m -3 ) Rotation velocity (rad.s-1)

INTRODUCTION

Hot-mix asphalt production offers a significant research challenge in terms of energy consumption and CO 2 emissions reduction within the road sector (U.S. Environmental Protection Agency 2004). This process basically consists of mixing stones (mineral aggregate) and bitumen binder to produce the asphalt mix, which is also called "asphalt concrete". However, the aggregates must be dried and heated prior to mixing in order to obtain satisfactory fluidity (handling) of the concrete, hence the origin of the term "hot-mix asphalt". Among a wide array of current drying technologies (e.g. tunnel dryer, furnace, disk dryer, atomization, flash dryer, fluidized bed), the rotary dryer is favored in mix asphalt production for its ability to remove moisture from the aggregates.

Hot asphalt mixing is by far the main process involved in road and pavement construction. A large proportion of the energy consumed is due to the drying and heating of aggregates before coating with the bitumen binder. Recent estimations for example cite up to 3 TWh/year in consumption, which accounts for 800,000 TeqCO 2 /year in France. In addition to this permanent challenge of reducing energy consumption [START_REF] Mujumdar | An overview of innovation in industrial drying: current status and R&D needs[END_REF], with respect to the environmental impacts of this process, French concrete asphalt production represents approx. 42 million tons of hot-mix asphalt per year, from roughly 600 asphalt mix plants inventoried.

The rotary drum dryer features a long rotating cylindrical shell slightly inclined to the horizontal. In a direct heat rotary dryer, hot gas is supplied by a burner operating in turbulent flow regime through the dryer. These hot combustion gases in turn provide the heat required for vaporization of the water and heating of the aggregates. At the end of the drying and heating steps, the aggregates are in an appropriate condition to be successfully mixed with bitumen until reaching a temperature of roughly 440°K.

Recently, new techniques have been developed that involve a drop in aggregate temperature. This lowtemperature technique is also referred to as "warm asphalt" (i.e. at temperatures above 373°-383° Kelvin); included herein is the LEA technique [START_REF] Romier | Low-Energy Asphalt with performance of hot-mix asphalt[END_REF] or "half-warm asphalt" (between 313° and 373°K), which is currently being marketed and considered as a new sustainable process in terms of energy cost savings and greenhouse gas reduction (Krisjantdottr 2007). The warm asphalt technique requires only limited water content inside the aggregates prior to mixing with bitumen. Knowledge of the actual water content and temperature of aggregates just before mixing is thus of paramount importance in controlling these warm techniques. The rotary drum dryer offers a complete operation that entails thermal drying and heating, depending on particle motion in the dryer. The mixing of solids plays a critical role in the various transfer phenomena (momentum, heat and mass).

Several authors have studied the distribution of granular solids (aggregates) to characterize the different types of granular flow regimes inside rotary baffles during the drying process [START_REF] Iguaz | Mathematical modelling and simulation for the drying process of vegetable wholesale by-products in a rotary dryer[END_REF][START_REF] Lisboa | A study of particle motion in rotary dryer[END_REF]. These baffles or "flights" are inserted into the rotary drum wall. The most direct form of heat dryers used in the hot-mix asphalt process contains such flights, set in parallel along the length of the shell; the flights serve to lift solids so that they fall across the dryer cross-section as a way of initiating gas-solid contact. The transport of solids through the drum takes place by the action of solids cascading from these flights. Each cascade, comprising the lifting cycle on a given flight design, is essential to stimulating the gas-solid contact required for rapid and homogeneous drying.

Drying inside rotary drum flights is a very recent research topic: either the agitated solids are treated as a purely granular flow in the mix [START_REF] Huang | Experimental study on fluidization of fine powders in rotating drums with various wall friction and baffled rotating drums[END_REF] or the mass transfer is included within a global model [START_REF] Sheehan | A model for solids transport in flighted rotary dryers based on physical considerations[END_REF] . A f e w s t u d i e s c a r r i e d o u t w i t h complex processes have focused on the stirred mixing of complex systems with: momentum [START_REF] Zhu | Pneumatic conveying of granular solids in horizontal and inclined pipes[END_REF], heat [START_REF] Chaudhuri | Modelling of heat transfer in granular flow in rotating vessels[END_REF][START_REF] Chen | Heat transfer enhancement in dense suspensions of agitated so lid s . P a rt I : T h eo ry[END_REF], or mass transfer coupling [START_REF] Heydenrich | Mass transfer in rolling rotary kilns: a novel approach[END_REF] . T h e D E M ( D i s c r e t e Element Modeling) Bertrand 2005) a n d C F D (Computational Fluid Dynamics) [START_REF] Ristow | Flow properties of granular materials in 3D geometries[END_REF] methods are currently being used as modeling tools for the dispersed and continuous phases, respectively. This paper presents a drying and heating model capable of predicting the temperature and moisture evolution of aggregates inside a co-current rotary drum. At first, the assumptions relative to granular transport will be derived from results of experiments conducted at a pilot scale (i.e. 1/3). The evolution in granular media distribution within the rotary drum cross-section will be discussed in Section 2. Section 3 will then display the one-dimensional model, based on mass and energy balance, in order to predict evolution in aggregate temperature and moisture along the rotary dryer axis.

As determined by the granular transport regime, each area of exchange between gas flow and granular medium will be evaluated. In addition, each parameter involved in the model will be identified and quantified based on model results. Section 4 will compare these model results to output from an experimental campaign built around temperature measurements and performed inside an instrumented asphalt mixing plant (i.e. fullscale). Several experimental campaigns have been undertaken to provide gas temperature profiles inside the drum during a permanent production run. The model will be validated by means of the measured gas temperature. The production parameters presented in this paper correspond to the given asphalt technique (i.e. hot-and warm-mix asphalt).

GRANULAR TRANSPORT AND PHYSICAL ASSUMPTIONS

Experimental Visualization at the Pilot Scale

The granular regime in a rotary drum without baffles has been studied on several occasions. Such regimes have been observed and classified by both Henein et al. (1993) and Mellman (2001). The various granular solid motions, including slipping, rolling, avalanching, cataracting and centrifuging, have all been correlated with drum rotation velocity. The granular solid motion is classified mainly by the Froude number (Fr=R 2 /g). Table 1 lists the various motions as a function of Froude number. The drum configuration used in the asphalt mixing plant is quite atypical however due to the positioning and shape of the baffles (or flights) along the drum. Experimental campaigns at the pilot scale of an industrial unit have been carried out in order to observe aggregate distribution within the drum cross-section, in the absence of gas flow.

Table 1 Froude number for each of the different modes [START_REF] Henein | Experimental study of transverse bed motion in rotary kilns[END_REF] Mode Fr 1. Slipping Fr < 1.0×10 -5 2. Slumping 1.0×10 -5 < Fr <0.3×10 -3 3. Rolling 0.5×10 -3 < Fr < 0.2×10 -1 4. Cascading 0.4×10 -1 < Fr < 0.8×10 -1 5. Cataracting 0.9×10 1 < Fr < 1.0 6. Centrifuging

Fr > 1.0

The first objective of this visualization step is intended to establish the physical basis of the transfer phenomena taking place inside the drum from knowledge of the granular media in the mix. These flights actually influence the transport of solids, as was mentioned by [START_REF] Huang | Experimental study on fluidization of fine powders in rotating drums with various wall friction and baffled rotating drums[END_REF]. The motions recorded in a smooth drum are delayed at lower Froude numbers; moreover, moisture content can influence the granular flow regime and consequently the gas flow distribution. A good knowledge of the granular flow is therefore essential to setting correct assumptions for the heat and mass transfer modeling process.

A time-resolved camera is used to capture instantaneous images; this system features a DALSA FA-20-01M1H camera (100 Hz, with a resolution of 1400 × 1024 pixels). Spherical glass beads are introduced as the seeding particles; their average diameter equals 2 mm and their density is close to 2.5. Dry (X s =0%) and wet (X s =8%) aggregates with a mean diameter of 6 mm have also been tested. A dedicated processor, the STEMMER IMAGING device, serves to acquire data and therefore processes each image.

The 2D experiments have been carried out on a pilotscale device with an inclination angle equal to 3 degrees. The rotary drum diameter D=552 mm (see Fig. 1). The drum is stirred by 20 baffles, each of length 50 mm and width 25 mm.

The experiments were conducted at a rotational speed of N=18 rpm. The Froude number thus equals 0.01, and the granular flow regime corresponds to rolling in a smooth drum. The working area of the drum (1.22 m in length) is composed of five sections: one (200 mm long) is dedicated to the inlet area for materials, while each of the other four is 255 mm long. The pilot is not set at the feeding rate; its scale ratio is equal to 1/3, in comparison with an industrial drum. Regardless of the materials introduced, the fill rate is fixed at 15% over the first section of the drum. The frequency of the highspeed camera is adjusted to 25 Hz in order to strike a compromise between spatial resolution and temporal accuracy. The flights are loaded in the bottom part of the drum.

Once the flight rotation angle reaches a given level ( /2), the overloaded flight is discharged (t=3.5 s and 4.36 s). When the flight is under-loaded (t=17.24 s), it exhibits areas where materials drop, while other parts allow for passage of the gas flow. A certain proportion of the aggregate remains at the bottom of the drum so as to form a granular bed. A second campaign was carried out using aggregates with two distinct water contents: dry (X s =0%) and moist (X s =8%) aggregates with a mean diameter equal to 6 mm were introduced. The time series in Fig. 3 represents flow patterns associated with dry aggregate motion. The motions observed correspond quite well to findings from the experimental campaign conducted with spherical glass beads. From the recorded flow pattern, no variation in granular flow regime is detected across the various aggregate moisture fractions tested.

Physical Assumptions

Cross Flow Description in a Rotary Drum

Within the framework of building a relevant model, visualization at the pilot scale based on a range of experimental conditions leads to suggesting a two-part granular solid distribution. The majority of the granular flow pattern exhibits a dispersed phase in descending from the top of the drum, while the remaining part constitutes a granular bed at the bottom. These observations are in good agreement with the classification of granular flow regimes inside a rotary drum according to the Froude number [START_REF] Boateng | Rotary kilns Transport phenomena and Transport processes[END_REF]).

In the present case, the granular flow regime in the drum is of the avalanche type [START_REF] Ding | Granular motion in rotating drums bed turnover time and slumping-rolling transition[END_REF]; such a regime gives rise to a homogenization of both the aggregate temperature and moisture in the crosssection, which in turn leads to defining T s (x,t) (aggregate temperature at position x along the drum axis at time t) and X s (x,t) (aggregate water content at the same position and same time).

As indicated in the previous section for aggregate temperature and water content, each model variable or parameter is assumed to be uniform on any slice taken of the drum. It would therefore seem relevant to build a one-dimensional model that depends solely on time t and position x along the drum axis.

Exchange Areas for Heat / Mass Transfer

The aggregates are assumed to be spherical particles. The diagram in Fig. 4 summarizes the main exchange areas for heat and mass transfer during both drying and heating. The exchange areas between the gas and the drum environment, S ge , and between the granular bed and the environment, S se , depend on aggregate distribution within the cross-section. The S gs exchange area, which is related to the transfer between gases and solids, depends on the particle and gas motions defined by their respective mean velocities, V s and V g (Fig. 5). As a rough approximation, it can be considered that V s <<V g and that the relative velocity is negligible. The particle size (d > 2 mm) leads to a Gas phase : Tg(x,t) ; Xg(x,t)

particle Reynolds number ( Re p gas s gas Vd ) much higher than the critical value of 1,000; hence, the flow regime is assumed to be Newtonian. The value of S gs takes into account the entire surface area of the sphere.

The particle-particle interaction, emission and radiation of the gases have all been neglected, and the gas velocity is assumed to be the driving force for transfer phenomena in the dispersed phase, during which forced convection becomes the most important mechanism. Since gas flow in the granular bed is much less than in the free part of the drum, no exchange between particles a n d g a s i n t h e g r a n u l a r b e d n e e d s t o b e t a k e n i n account. The heat transfer between gases and the granular bed is therefore restricted to the surface of the granular bed, S gs2 . Moreover, this transfer depends on a characteristic length, L, which we have chosen as being the width of the granular bed surface.

Definition of a Source Term for Evaporation

The mass flow rate of water vapor between aggregates and hot air, m , depends on both the temperature and moisture of the aggregates contributing to the heat and mass transfer coupling. This mass flow rate of water vapor also depends on the temperature of the solid particle; the induced mass transfer of water vapor can be evaluated by Fick's Law, as follows: where k gs i s t h e m a s s t r a n s f e r c o e f f i c i e n t f o r t h e dispersed phase, and k gs2 the mass transfer coefficient for the granular bed. The evaluation of these coefficients will be described in the next section. In addition, for both heat and mass transfer, water vapor is considered as a pure element and a perfect gas. The entire amount of water corresponding to the moisture content of an aggregate is assumed to lie on the surface of the solid particle (Fig. 5). (5)

where m s and m g represent respectively the linear solid mass density and the linear gas mass density, while Cp s and Cp g denote respectively the specific heat capacity of solids and gases at constant pressure. Cp vap is the specific heat capacity of water vapor at constant pressure, Lv the latent heat of vaporization for water, h gs the heat transfer coefficient between gas and solid, h gs2 the heat transfer coefficient between gas and the surface of the granular bed, h se the heat transfer coefficient between the granular bed and the drum environment, and lastly h ge the heat transfer coefficient between gas and the drum environment. All these heat transfer coefficients will be defined in the following section.

The term on the left-hand side of Eq. 4 is the energy rate required to increase the temperature of aggregates with linear mass density m s .

Several terms are redundant between Eqs. 4 and 5. H T S ( . . () gs gs g s S hTT ) is the heat transfer around solid particles. Since the particle is present within the gas flow, HTS is driven by convective heat transfer, which accounts for its form.

HTSB ( 22 . . () g s g sgs

Sh TT ) is the heat transfer on the solid bed. HTSB results from convective heat transfer between the solid bed area and gases, which explains its form.

TLSB ( .. se se s se

S hTT )) is the thermal loss around the solid bed. Since the temperature of solids differs from the outside temperature, thermal losses occur at this spot. This thermal loss consists of the conductive heat transfer through the drum wall, yet the transfer between wall drum and the outside is a mixed convective heat transfer. The equivalent heat transfer coefficient therefore depends on the coefficients of each heat transfer.

TLG ( . . () ge ge g e S hTT

) is a thermal loss relative to gas. TLG corresponds to the convective heat transfer between the gas and the outside.

Water mass transfer gives rise to two equations for the solid and gaseous phases:

.

ss s X dX mV t dx (6) . gg g X dX mV t dx (7)
where V s and V g are respectively the solid velocity and the gas velocity.

The five main model unknowns can then be computed using the set of five Eqs. ( 1) and ( 4) through (7). The granular bed is in contact with the rotary drum wall, while a thermal loss exists between the granular bed and the outside. h se is quantified by means of the following relationship:

Definition of Heat and Mass Transfer Coefficients

h
ext wd se h e h 1 1 (12)
where h ext is the heat transfer coefficient between the external wall of the rotary dryer and the outside. The rotary drum is in fact non-insulated, and the wall temperature, which equals 400°K, remains constant along the drum. For h ge , the reflection pattern is the same, except that h gs is taken into consideration when assessing h ge :

1 11 ge gs wd ext e h hh ( 13
)
The evaporation energy is provided by the aggregates, while the energy for heating water vapor is provided by the gas [START_REF] Messai | Etude expérimentale du séchage convectif à haute température d'un milieu granulaire[END_REF].

The aggregate distribution in a given cross-section implies two areas for mass transfer: one around the solid particle, the other on the granular bed surface. k gs is correlated with the Sherwood number, i.e.:

.

Final Version of the 1D Model

In reality however, the drying step operates in a steady regime. This assumption supposes that the permutation from a temporal dimension to a spatial dimension is valid. Hence, the temperatures of solids and gases are solely dependent on the x-axis position.

Equations ( 4) and ( 5) are therefore modified into the following equations:

MODEL TESTING

Sensitivity of the Calculation Step

Physical resolution is achieved through use of a secondorder Runge-Kutta numerical method. The number of calculation steps n ( n=L/ x) ranges between 500 and 50,000 (where x controls the accuracy of the set-up, i.e. x is the size of the 1D subdivision cells).

Solids m s =38,89kg.s -1 (Re p =1600) X s (x=0)=4% T s (x=0)=323K Gas m g =5,23kg;s -1 (Re g =4864) X g (x=0)=0% T g (x=0)=1073K
Figure 6 below displays the numerical results obtained. The initial conditions are explained in the figure caption, and the solid particle diameter equals 20 mm. The Reynolds number for solid particles is 1,600, meaning that the Newtonian regime has been achieved.

Gas temperature decreases, whereas solid temperature i n c r e a s e s a l o n g t h e m a i n a x i s o f t h e d r u m , w h i c h corresponds to the actual rotary dryer at the industrial plant (12 m long).

Both of these temperatures reach an identical value at the drum outlet. Some numerical assessments have demonstrated the independence of this phenomenon (in terms of both variations and final value) relative to the size n of the numerical scheme, as long as n exceeds 1,000.

Dependence of the dimensionless numbers on temperature

As revealed by many of the authors presented in the introduction, granular transport exerts a strong impact on transfer phenomena (heat and mass). The Reynolds number for gases offers some information on both aggregate and air transport. The initial model conditions implemented are mentioned in the legend in Figure 7.

The solid particle size here is 20 mm, and the Reynolds number for solid particles equals 1,600, which once again indicates that the Newtonian regime has been obtained. The Reynolds number is defined from the air velocity; this number also varies with the mass flow r a t e o f t h e g r a n u l a r m e d i a . I n t u r n , t h i s f l o w r a t e induces a variation in the cross-section for gas flow passage. The corresponding results are presented in Fig. 7. Given that the flow of air volume is highly dependent on T g and that air velocity is one of the parameters used to calculate the Reynolds number (when T g decreases), air velocity decreases, which causes the Reynolds number to drop as well. For a fixed value of m s , as m g is increasing, the Reynolds number also rises.

The cross-section of the air passage remains fixed, hence air velocity rises as well. Since the other dimensionless numbers (Nu, Sh) depend on the Reynolds number via the correlations previously exposed, these other numbers decrease to the same extent, as observed through the Reynolds number with an increasing abscissa. Moreover, the temperature difference between gases and solids decreases, meaning that the transfer amount is smaller in order to obtain a similar temperature for solids and gases.

Energy transfer evaluation

An assessment of the relative weight of each term in Eqs. ( 4) and ( 5) is now proposed so as to compare each transfer and validate assumptions along the drum. The initial conditions are presented in T a b l e 2 w i t h a calculation step equal to 2,000.

Figure 8 displays the distribution of energy transfer, for the purpose of evaluating the evolution in each energy transfer along half the drum length. These initial conditions have been included on the legend in Fig. 8. The primary energy transfer is correlated with water evaporation and water vapor heating at the drum inlet. This transfer occurs along the first 50 cm.

The vapor flow rate is in fact the difference in vapor mass concentration between gases and solids. Nevertheless, the vapor mass concentration on solids is tied to saturation temperature. The vapor flow rate is therefore independent of the moisture content found on the solids.

The mass transfer however is switched off when moisture content of the solids equals zero, which explains the sudden interruption of transfer. These energy transfers represent the drying step for aggregates. It can be observed up until the outlet that the main energy transfer pertains to aggregate heating.

MODELING VS. EXPERIMENTATION AT THE INDUSTRIAL SCALE

An industrial mix-asphalt processing unit has been monitored. Eight temperature probe supports were implemented in the longitudinal axis along a drum (12 meters long), in order to measure gas temperature. for the support and hence temperature measurement deviation. K-thermocouples were chosen due to a temperature range varying between 400°K and 1500°K. The actual process was monitored at the same time so as to record the parameters required by the model, including: solid feed rate and initial moisture content, gas temperature, and mix-asphalt temperature.These recorded parameters are necessary to implement the model in a way that compares calculated output with measurement results. The four application cases studied are detailed in Table 2.

The various tests conducted account for several productions using different techniques. The classical hot-mix asphalt and the warm-asphalt technique differ in terms of asphalt concrete temperature at the plant outlet.

The gas temperatures for these four cases have been compared at the same location as for the probes.

Figure 10 presents a comparison between measured and calculated temperatures.

The trends are identical between the measured and calculated values: the mean deviation is approximately 17% over the entire dataset, and the maximum deviation equals 41%.

A better estimation of both the transfer coefficients and exchange areas could improve the model. For the time being however, the transfer coefficients are being estimated from the standard correlation.

The local influence of a granular flow composed of several material classes on the gas phase is essential to a good evaluation of the momentum transfer. A similar study is necessary of the exchange area, through improving the pilot-scale measurements.

CONCLUSION

Experimental measurements at both the pilot scale (1/3) and industrial scale (full-scale) of a co-current rotary drum have been performed in order to build a drying and heating model applicable to mix-asphalt processes. The first experimental stage was conducted using different materials (glass spheres, then moist and dry aggregates) without any flow gases to allow characterizing the granular flow regime. This visualization tool proved relevant to the construction of a physical model based on two transfer areas. One of these areas contained a dispersed phase, while the second was a granular bed located in the bottom part of the drum. From this physical consideration, a 1D model was developed using the energy and mass balance equation, along with a suitable coupling between heat and mass transfer at the aggregate scale. The system of equations was solved for various initial conditions and demonstrated applicability beyond 1,000 iterations. The strong dependence of the Reynolds number on the temperature gradient in the flow direction (x-axis) reveals that both the exchange area and transfer coefficients for heat and mass transfers must be taken into account and validated in order to proceed with the next step of this research. Measurements using infrared tomography at the drum shell are currently underway.

The second work step has consisted of measuring gas temperatures in an industrial rotary drum. The model was validated with respect to gas temperature values, since a suitable evolution was obtained with the two approaches for different techniques (hot-and warmasphalt techniques). Nevertheless, a complete validation still needs to be performed on the entire set of parameters.

Fig. 1 .

 1 Fig. 1. Description of pilot scale device

  Figure2shows an example of pictures captured among the many experimental sets, performed by placing spherical glass beads inside the rotary drum. Four flow patterns have been chosen to describe the initial startup at t=0 s as well as the evolution in mixed materials during a 17-second period.

Fig. 3 .

 3 Fig. 3. Transversal motion of dry granular inside a rotary scale dryer.

Fig. 4 .

 4 Fig. 4. Areas of exchange in a cross-section of the rotary drum in a slice

Fig. 5 .

 5 Fig. 5. Scheme representing the settling velocity and area of exchange at the solid scale in the gas flow disturbance Water vapor saturation is thus anticipated around each solid particle. The saturation state is determined by the saturation pressure and depends on aggregate temperature, according to Clapeyron's formula, i.e.: 2 00 . 11 l n . ()

Fig. 6 .Fig. 7 .

 67 Fig. 6. Calculation step variation of numerical model

Fig. 8 .

 8 Fig. 8. Assessment of the energetic transfers

Fig. 9 .

 9 Fig. 9. probes support in the rotary drum and probe

Figure 9 Fig. 10 .

 910 Fig. 10. Comparison between measured and calculated gases temperature

  gs is derived from the Nusselt number, as calculated at the solid particle scale, i.e.:.

	Nu	gs			gs hd							(8)
							g
	In this case, the Nusselt number is estimated from the
	Ranz-Marshall correlation, after particle drying
	(Boateng 2008):
	Nu	gs			0.5 2 0.58.Re .Pr	0.33	(9)
	On the other hand, h gs2 is derived from the Nusselt
	number at the granular bed scale, i.e.:
	Nu		gs	2	2 hL . gs							(10)
								g
	The Nusselt number originates from a flat-plate
	correlation given that the transfer configuration lies on
	a flat plate (the solid bed area) (Schlichting 1960):
	Nu	gs	2	0	.	. 023	Re	0	8 .	.	Pr	. 0	33	(11)

Table 2

 2 Initial conditions for the tests

		c a s e	m s	V s	S gs	Sgs2	Sse	X s(x=0) C ps (Hewitt 1997)	d
		1	42,82 0,08 11,10 1,54.10 -8 0,019	1,3	920	0,01
		2	41,53 0,08 10,74 1,52.10 -8 0,019	1,3	920	0,01
		3	45,54 0,08 11,82 1,57.10-8 0,019	1,3	920	0,01
		4	44,38 0,08 11,52 1,56.10 -8 0,019	1,3	920	0,01
	c a s e	m g	V g	T g(x=0)	S ge	Cpg	(T=373) (Hewitt 1997)	(T=373) (Hewitt 1997)	Text
	1	10,47 4,92 1032 0,124 1100		0,94	2,17.10 -5	19,3
	2	10,47 4,92 1035 0,124 1100		0,94	2,17.10 -5	13,2
	3	9,08	4,27	878	0,124 1100		0,94	2,17.10 -5	21,3
	4	10,31 4,84	923	0,124 1100		0,04	2,17.10 -5	9,9

ACKNOWLEDGEMENTS

The authors would like to express their thanks to Ermont-Fayat Group for the pilot scale device lending. T h e a u t h o r s a r e g r a t e f u l t o t h e S E M R / C E T E Normandie-Centre department for the monitoring of the industrial mix-asphalt processing unit.