Fabien Durand

Michel Rigo

MULTIDIMENSIONAL EXTENSION OF THE MORSE-HEDLUND THEOREM

A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence x over a finite alphabet is ultimately periodic if and only if, for some n, the number of different factors of length n appearing in x is less than n + 1. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let d ≥ 2. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z d definable by a first order formula in the Presburger arithmetic Z; <, + . With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse-Hedlund theorem to an arbitrary dimension d and characterize sets of Z d definable in Z; <, + in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.

Introduction

Let d ≥ 1 be an integer. A set M ⊆ Z d is said to be periodic if there exists a non-zero vector p ∈ Z d such that for all x ∈ Z d , x belongs to M if and only if x + p belongs to M . Periodic sets in dimension greater than one have been investigated recently in the spirit of the celebrated Morse-Hedlund theorem.

Theorem 1 (Morse-Hedlund theorem [START_REF] Morse | Symbolic dynamics[END_REF]). Let A be a finite alphabet. Let x ∈ A N . Denote by p x (n) the number of factors of length n appearing in x. Then the following assertions are equivalent:

• x is ultimately periodic;

• there exists n such that p x (n) ≤ n;

• there exist n 0 and C such that p x (n) ≤ C for all n ≥ n 0 .

Observe that this theorem also can be transposed to any subset M of N by considering its characteristic sequence over the alphabet {0, 1}. The ultimate periodicity of this sequence is equivalent, for M , to be a finite union of arithmetic progressions. We are interested in generalizations to higher dimensions, that is, to find conditions on the block counting function forcing (a notion of) periodicity.

Let us briefly mention some interesting works going in that direction. We were first motivated by Nivat's Conjecture [START_REF] Nivat | Invited talk at ICALP[END_REF] stated in 1997, see also [START_REF] Berthé | Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences[END_REF], asserting that if for some pair (n 1 , n 2 ) the number of (n 1 × n 2 )-blocks appearing in M ⊂ Z 2 is less or equal to n 1 n 2 , then M is periodic. With the terminology introduced in [START_REF] Sander | The complexity of functions on lattices[END_REF] it would show that there is a (restricted) Periodicity Principle in Z 2 . This is also strongly related to the Period Conjecture stated in [START_REF] Lagarias | Local complexity of Delone sets and crystallinity[END_REF]. More details on Nivat's conjecture, Period Conjecture and related works can be found in Section 6.

In this paper, we exhibit, thanks to Theorem 2 given below, a complete extension of the Morse-Hedlund theorem to an arbitrary dimension d and characterize sets of Z d definable in Z; <, + in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often. Note that we do not consider "purely" periodic sets in Z 2 or even Z d , with d ≥ 2, i.e., we are not looking at sets M having a vector p acting as "global" period. But instead we study what we consider as a natural extension of the notion of periodicity to a multidimensional setting. Indeed, when A. L. Semenov extended in [START_REF] Semenov | The Presburger nature of predicates that are regular in two number systems[END_REF] the theorem of Cobham [START_REF] Cobham | On the base-dependence of sets of numbers recognizable by finite automata[END_REF] to a multidimensional setting, it turns out that the notion of periodicity he used was not the pure periodicity but sets in Z d defined by a first order formula of the Presburger arithmetic Z; <, + . It is important to observe that the subsets of N which are defined by a first order formula in N; =, + are exactly the ultimately periodic sets (i.e., finite union of arithmetic progressions). As an example, if ϕ(x) := (x = 3) ∨ ((∃y)(x = 2y)) ∨ ((∃y)(x = 5y + 1))

is considered as a formula in N; =, + , then the set [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF]. Except for the scope of the variables, there is no fundamental difference between the structures N; =, + and Z; <, + . Therefore, in this paper, for the sake of simplicity our results are described for the structure Z; <, + . Notice that in N; =, + , the relation x ≤ y can be easily defined by (∃z)(x+z = y) but this is no more true when x, y, z are possibly negative and this is the reason why the order relation < has to be added to the Presburger arithmetic over Z. Note that over Z; <, + the formula x = y can be defined by ¬(x < y) ∧ ¬(y < x) and that x = 0 can be defined by x + x = x.

M = {x ∈ N | N; =, + |= ϕ(x)} = {0,
To obtain a characterization of sets M in Z d defined by a first order formula of Presburger arithmetic, we estimate the function R M (n) of different blocks of size n occurring infinitely often in M . Collecting several results and observations about Presburger arithmetic and mainly applying the powerful criterion of Muchnik [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF], we derive the following theorem.

Theorem 2. Let M be a subset in Z d . This set is definable in Z; <, + if and

only if R M (n) ∈ O(n d-1
) and every section is definable in Z; <, + .

Hence, we use a different notion of periodicity as the one occurring in Nivat's conjecture and a different complexity function but what we obtain is a necessary and sufficient condition. Note that in many recent papers [START_REF] Lagarias | Local complexity of Delone sets and crystallinity[END_REF][START_REF] Nivat | Invited talk at ICALP[END_REF][START_REF] Quas | Periodicity and local complexity[END_REF][START_REF] Sander | The complexity of functions on lattices[END_REF]

if R M (n) ∈ O(n d-1
) and for all k ∈ {1, . . . , d -1} every (d -k)-dimensional section has a recurrent block complexity in O(n d-k-1 ).

In Section 2, we define the terminology. Section 3 contains several examples of definable and non-definable sets in Z 2 to help the reader to develop some intuition about Presburger arithmetic and complexity. In Section 4 we prove the necessary condition relying mainly on the elimination of quantifiers in Presburger arithmetic.

Observe that for d = 1 our main result corresponds to the Morse-Hedlund theorem: a set M ⊆ Z is periodic, i.e., there exists t such that, for all x ∈ Z, x ∈ M ⇔ x + t ∈ M , if and only if there exists n such that p M (n) ≤ n [START_REF] Morse | Symbolic dynamics[END_REF]. For d = 2 we give, in the first part of Section 5, a direct proof using a lemma already appearing in [START_REF] Epifanio | On a conjecture on bidimensional words[END_REF] and [START_REF] Quas | Periodicity and local complexity[END_REF].

In the second part of Section 5, we treat the general multidimensional case relying on completely different techniques developed by Muchnik in [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF]. In Section 6 we describe some works around the Nivat's Conjecture, the Periodicity Principle and the Period Conjecture. Moreover, under the extra hypothesis of uniform recurrence, we obtain partial answers to these questions for subsets of Z d .

Setting up the framework

Let A be a non-empty finite alphabet and d be a positive integer. Let x = (x 1 , . . . , x d ) ∈ Z d . We consider the norm

||x|| = sup 1≤i≤d |x i |.
Let k > 0. We define the k-neighborhood of size k centered at x by

(2.1) B(x, k) := {y ∈ Z d | ||x -y|| < k}. Let S ∈ A Z d be
N : n → #{S x,n | x ∈ Z d }.
The recurrent block complexity of S is the map R S counting for each n the number of different blocks S x,n appearing infinitely often in S. These blocks are called recurrent blocks. Observe that we do not require to see such blocks in all quadrant.

In other words, this latter function counts only the different blocks B of size n such that for all L ∈ N, there exists x ∈ Z d verifying ||x|| ≥ L and S x,n = B. The following inequalities are obvious

∀n ≥ 1, R S (n) ≤ p S (n) ≤ (#A) n d .
Remark 3. If the alphabet A is binary, say A = {0, 1}, then words in A Z d can be identified with subsets of Z d and the definitions and notation given above can be applied to subsets of Z d . For instance, we can speak of the block complexity and recurrent block complexity of a subset M of Z d . We denote these complexities respectively by p M and R M .

Remark 4. Let M = {0} ⊂ Z d . Then R M (n) = 1 and p M (n) = n d + 1 for all n.
With this example, we stress the fact that it is required to consider R M instead of p M in our main result.

For the sake of completeness, we recall some essential facts about sets definable by first order formulas in the Presburger arithmetic Z; <, + . For more details, we refer the reader to [START_REF] Bès | A survey of arithmetical definability[END_REF][START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF][START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF].

Remark 5. Recall that the subsets of N definable in N; =, + are exactly the ultimately periodic sets in N. When taking a subset M of Z definable in Z; <, + , we can consider the two subsets of N,

M ∩ Z ≥0 and -(M ∩ Z <0 ) = {-x | (x ∈ M ) ∧ (x < 0)}
which are both definable in N; =, + and therefore ultimately periodic. Consequently, if M ⊆ Z is definable in Z; <, + , there exist N, p, q > 0 (which are chosen minimal) such that for x > N , x ∈ M if and only if x + p ∈ M and for x < -N , x ∈ M if and only if x -q ∈ M . Notice that even in dimension one, if p = q or N = 0, then M which is definable in Z; <, + cannot be "purely" periodic. As a trivial example, consider the set M = {0} ⊂ Z. Then, p M (n) = n + 1 for all n ≥ 1.

In this context, Presburger definability can be viewed as a natural extension of ultimate periodicity in dimensions higher than one. Before stating the so-called Muchnik's criterion, we need a few definitions. Definition 6. A set M ⊆ Z d is said to be linear, if there exist x ∈ Z d and a finite set (possibly empty) V ⊂ Z d such that

M = {x} + v∈V Nv.
A finite union of linear sets is a semi-linear set.

Let M ⊆ Z d , i ∈ {1, . . . , d} and c ∈ Z. The section M i,c ⊆ Z d-1 is given by

M i,c = {(x 1 , . . . , x i-1 , x i+1 , . . . , x d ) | (x 1 , . . . , x i-1 , c, x i+1 , . . . , x d ) ∈ M }. Definition 7. Let v ∈ Z d \ {0} and M, X ⊆ Z d . The set M is said to be v-periodic inside X if for any m, m + v ∈ X, m ∈ M ⇔ m + v ∈ M
(i.e., any two points inside X that differ by v either both belong to M or both do not belong to M ). We say v is a local period for X. When V is a subset of Z d , we say

M is V -periodic inside X if M is v-periodic inside X for some v ∈ V . v v X X X v Figure 1
. Three examples of v-periodicity inside X.

As we will see definability in Z; <, + can be expressed in terms of local periodicity as given in [START_REF] Bruyère | Logic and p-recognizable sets of integers[END_REF].

Definition 8. A set M ⊆ Z d is said to be locally periodic if there exists a finite set V ⊂ Z d \ {0} such that for some K > v∈V ||v|| and L ≥ 0, ∀x ∈ Z d , ||x|| ≥ L, ∃v ∈ V : M is v-periodic inside B(x, K).
Figure 2 illustrates this notion: far enough of the origin, the set M is v-periodic inside any K-neigborhood for some v ∈ V .

In [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF] the following alternative definition of local periodicity is given, see also [START_REF] Bès | A survey of arithmetical definability[END_REF][START_REF] Michaux | Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems[END_REF]. Moreover, in [START_REF] Quas | Periodicity and local complexity[END_REF] the authors also defined a related notion of local periodicity.

0 L x K K K x'' x'
∀x ∈ Z d , ||x|| ≥ L, ∃v ∈ V : M is v-periodic inside B(x, K),
then we say that M satisfies Muchnik's condition. A picture similar to the one in Figure 2 should also illustrate this notion.

As shown by the following theorem, these two definitions play similar role to characterize definability. The reader may already notice that the sections of M enter the picture. Theorem 10. [START_REF] Muchnik | The definable criterion for definability in Presburger arithmetic and its applications[END_REF] Let M be a subset of Z d . The following statements are equivalent.

(

) M is definable in Z; <, + , 1
M is semi-linear, (3) every section of M is definable in Z; <, + and M is locally periodic, (4) every section of M is definable in Z; <, + and M satisfies Muchnik's condition.

Remark 11. It is clear in Theorem 10 that condition (4) implies condition (3), i.e., Muchnik's condition implies local periodicity. The converse is not so obvious and as observed in [14, p. 1438], a close inspection of the proof of Theorem 10 reveals that assuming (3) is enough to derive the definability of M and that this definability implies Muchnik's condition.

Let A be a finite alphabet, d ≥ 1 and S ∈ A Z d be a d-dimensional word over A.

For each a ∈ A, we define the set

S -1 (a) := {x ∈ Z d | S x = a}.
Definition 12. The word S is definable in Z; <, + if and only if for all a ∈ A, the sets S -1 (a) are definable in Z; <, + .

We can now recall our main result (stated in the introduction as Theorem 2).

Theorem. Let M be a subset in Z d . This set is definable in Z; <, + if and only if R M (n) ∈ O(n d-1
) and every section is definable in Z; <, + .

The case d = 1 is equivalent to Morse-Hedlund theorem and was already discussed in Remark 5. Notice that the number of recurrent factors occurring in an ultimately periodic word in {0, 1} N is bounded by a constant. The proof of Theorem 2 is given in Section 4 and Section 5. But prior to these developments, let us make a few immediate comments. Theorem 2 has an immediate application.

Corollary 13. Let A be a finite alphabet and

d ≥ 1. A d-dimensional word S ∈ A Z d is definable in Z; <, + if and only if R S (n) ∈ O(n d-1
) and every section is definable in Z; <, + .

Let k ∈ {1, . . . , d -1}. A (d -k)-dimensional section of M ⊆ Z d is a subset of Z d-k
where k components have been fixed to constants. So we define the set

M (i1,...,i k ),(c1,...,c k ) = {x ∈ M | x j = c j , j = 1, . . . , k}
viewed as a subset of Z d-k . If we apply Theorem 2 recursively, we get the following result expressing definability in Presburger arithmetic solely in terms of recurrent block complexity.

Corollary 14. A set M ⊆ Z d is definable in Z; <, + if and only if R M (n) ∈ O(n d-1
) and, for all k ∈ {1, . . . , d -1}, every (d -k)-dimensional section has a recurrent block complexity in O(n d-k-1 ).

Using similar arguments as in Remark 5 we can replace in Theorem 2, Corollary 13 and Corollary 14, Z d by N d and Z; <, + by N; =, + .

Running examples

We briefly give some examples that we hope could be helpful.

Example 15. Consider the set M ⊂ Z 2 represented on the left in Figure 3 and defined by the formula One can show that the block complexity p M satisfies p M (n) ≥ n 2 for n large enough. A simple argument is to observe that the n 2 blocks of size n, (i,

ϕ(x, y) := (x ≥ 0) ∧ (y ≥ 0) ∧ (∃λ)((x, y) = λ(1, 1)) ∧ (∃λ)((x, y) = (0, 1) + λ(1, 0)).
j) + [[0, n -1]] 2 for i, j ∈ [[-n + 1, 0]] are all distinct.
Local periodicity is clear with a set of periods equal to V = {(1, 1), (1, 0)}, and, K = 3 and L = 4. Muchnik's condition is also obvious to check with the same set of periods. The recurrent block complexity is

R M (n) = 3 n.
Example 16. Consider the set M ⊂ Z 2 represented on the right in Figure 3 and defined by the formula

ϕ(x, y) := (x ≥ 0) ∧ (y ≥ 0) ∧ ((∃λ)((x, y) = λ(1, 1)) ∨(∃λ)(∃µ)((x, y) = (4, 3) + λ(1, 0) + µ(1, 2))).
Notice that this set can also be defined with a quantifier-free formula ψ(x, y) =

(x ≥ 0) ∧ (y ≥ 0) ∧ (ψ 1 (x, y) ∨ ψ 2 (x, y) ∨ ψ 3 (x, y)) where (3.1) ψ 1 (x, y) := (y ≥ x) ∧ (2x ≥ y + 5) ∧ (y ≡ 1 mod 2), ψ 2 (x, y) := (y ≥ x) ∧ (x ≥ y), ψ 3 (x, y) := (x ≥ y) ∧ (y ≥ 3) ∧ (y ≡ 1 mod 2). It is not difficult to compute that the recurrent block complexity is R M (n) = 7 n-1 for all n ≥ 1.
The following two examples will be used to see that our main result cannot be improved.

Example 17

(Fibonacci). Let F = (f i ) i≥0 = 0100101001 • • • be the Fibonacci word generated by the morphism h : 0 → 01, 1 → 0. It is well-known that p F (n) = n + 1. Now consider the word G = (g i ) i∈Z
indexed by Z and defined by

g i = g i = f i if i ≥ 0, g i = 1 otherwise g = • • • 11111111.0100101001 • • • . We have p G (n) = 2n. Consider the set G ⊂ Z d defined by x ∈ G if and only if x = (x 1 , . . . , x d ) is such that g x1 = 1. It is clear that G is locally periodic and that R G (n) = p G (n) = 2n
. None of the sections G j,c for j ≥ 2 can be defined in Z; <, + . Indeed, the Fibonacci word is not ultimately periodic (see [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF]) and therefore not definable in N; =, + . Thus, the hypothesis on the sections cannot be remove. It also shows that it is not enough to consider p G instead of R G .

Example 18 (Toeplitz'like set). Consider the set T ⊂ Z 2 depicted in Figure 4 such that (i, j) ∈ T ⇔ (i, j ≥ 0) ∧ (∃n > 0 : i = n 2 j+1 ). Each section is definable in Z; <, + but the set is not locally periodic and does not satisfy Muchnik's condition. It is not difficult to see that R T (n) ≥ n 2 since the patterns represented in Figure 5 appear infinitely often. Thus, the local periodicity property cannot be remove. We call it Toeplitz'like set because, one can obtain the heights of the successive "heaps" as follows. At first step, consider the infinite word (0?) ω = 0?0? • • • , on the second step, replace in order all the "?" symbols with the letters of the infinite word (1?) ω . On the (n + 1)-th step, replace the remaining "?" with the letters of the word (n?) ω . This process generates an infinite word over the alphabet N whose j-th element is the height of the j-th heap.

Complexity of Presburger definable sets

In what follows, as explained in Remark 3, we make no distinction between a subset of Z d and its characteristic word which belongs to {0, 1} Z d . We consider indifferently complexity functions of both subsets of Z d and binary words indexed by Z d . To count the number of different blocks of size n it is convenient to use the following notation:

C(x, n) = {y ∈ Z d | y = x + z, z ∈ [[0, n -1]] d }.
One should avoid the confusion between the neighborhood B(x, n) centered at x given in (2.1) and this set C(x, n) pointed at x.

Proposition 19. If X ⊆ Z d is definable in Z; =, + , then R X (n) ∈ O(n d-1 ).
For a better understanding of the main arguments, we first give the proof for d = 2.

Proof. Let X ⊆ Z 2 be definable in Z; =, + . We can assume [START_REF] Presburger | Über die volständigkeit eines gewissen systems der arithmetik ganzer zahlen[END_REF][START_REF] Presburger | On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation[END_REF] that the formula defining X is a finite boolean combination of formulas of the kind

λ i x + µ i y ≥ ν i , i ∈ {1, . . . , r} or λ i x + µ i y ≡ α i (mod J), i ∈ {1, . . . , s}
where the α i , J, λ i , µ i , ν i 's are integers (for an example, see for instance formula (3.1)). Therefore, except for a neighborhood of the origin, X is made up of finite number of regions bounded by two half (straight) lines. Inside such a region X is periodic (the period being determined with the constant J appearing in the formulas given above). In figure 6, no two lines have the same slope. Let us make this assumption first. Let n > 0. Note that bounded polygonal regions delimited by several lines remain in a finite domain close to the origin. Hence, only infinite regions have to be taken into account to estimate R X . Thus we consider one infinite region bounded by two lines λ i x + µ i y = ν i , i = 1, 2. Since their slopes are different, there exists s(n) such that for any x of norm ||x|| > s(n), C(x, n) intersects at most one line. The number of distinct blocks of size n lying completely in one region R is bounded by a constant r R (due to the periodicity given by a finite number of congruence relations). The number of different blocks of size n intersecting two regions is bounded by C n where the constant C depends on the periods within the two regions and the period on the line. Indeed the number of relative positions of a square of size n with respect to a given line is bounded by 2n (see Figure 7). For each such position, the number of different patterns within the two regions and on the line is bounded respectively by three constants r 1 , r 2 , r 3 (one for each region and one for each line). This gives a number of different blocks bounded by 2r 1 r 2 r 3 n. The conclusion follows from the fact that the number of regions is finite. We have first considered the case where the (infinite) regions were defined by lines having distinct slopes. Now, if several lines defining regions have the same slope as depicted in Figure 8, then one can proceed using the same arguments. Parallel Figure 8. Some regions defined by parallel lines. lines do not increase the linear bound on the complexity. Indeed, the number of relative positions of a square of size n with respect to given parallel lines is bounded by D n, for some D.

Now consider the general case.

Thanks to quantifier elimination in Presburger arithmetic [START_REF] Enderton | A mathematical introduction to logic[END_REF], we can assume that the formula defining X is a finite disjunction of formulas ϕ i (x 1 , . . . , x d ), i = 1, . . . , k, where each such formula is a conjunction of the form (4.1)

ϕ i (x 1 , . . . , x d ) := ℓ j=1 t i,j (x 1 , . . . , x d ) with (4.2) t i,j (x 1 , . . . , x d ) := d k=1 u (i,j) k x k ≥ c i,j or (4.3) t i,j (x 1 , . . . , x d ) := d k=1 u (i,j) k x k ≡ e i,j (mod J)
where all the occurring constants are integers. Notice that we can choose the same constant J in every modular equation occurring in the definition of X. Each ϕ i defines a domain1 of Z d intersected with a pattern2 . The following lemma is obvious.

Lemma 20. The number of distinct blocks of size n for a set X ⊂ Z d defined by a boolean combination of formulas of the kind

d k=1 u k x k ≡ e (mod J) is bounded from above by J d .
Let π i,j be the hyperplane having equation u (i,j) k

x k = c i,j corresponding to (4.2). We define π ′ i,j as the vector subspace having equation u (i,j) k

x k = 0. For the sake of simplicity, let us enumerate all the distinct hyperplanes occurring in the quantifier-free formula as Π = {π 1 , . . . , π t } (with the corresponding vector subspaces denoted by π ′ 1 , . . . , π ′ t ). Let B be a recurrent block of size n, i.e., there exist infinitely many y 1 , y 2 , . . . in

Z d such that B = X y1,n = X y2,n = • • • .
Our aim is to estimate the number of distinct such blocks. Assume that for large enough i, C(y i , n) intersect3 no hyperplane in Π. Then it lies completely in a single domain. We can apply the previous lemma. There are at most J d different such blocks for each domain and the number of domains is finite (and determined by the formula).

In what follows, we may therefore assume that all the blocks X yi,n intersect each of the hyperplanes π 1 , . . . , π j and no other, the y i to the same domain D.

We can do the reasoning for any subset of Π and any domain D (there are at most 2 t subsets of Π). For the sake of simplicity, we have chosen the first j elements in Π. Then, it suffices to prove that there exists a constant C, not depending on n, such that the number of pairwise distinct recurrent blocks X y,n intersecting each of the hyperplanes π 1 , . . . , π j and no other, with y ∈ D, is bounded by Cn d-1 .

Lemma 21. Let B be a block of size n. If there exist infinitely many (different) vectors y 1 , y 2 , . . . ∈ Z d such that, for all i, C(y i , n) intersects each of the hyperplanes π 1 , . . . , π j , then

dim(π ′ 1 ∩ • • • ∩ π ′ j ) ≥ 1.
Proof. Assume to the contrary that the intersection of the vector subspaces π

′ 1 ∩• • •∩ π ′ j is reduced to {0}.
Therefore, for a given n, there are finitely many hypercubes z + [0, n] d of size n intersecting simultaneously π 1 , . . . , π j , with z ∈ Z d .

Now let us assume that

W = π ′ 1 ∩ • • • ∩ π ′ j is
+ • • • + α ℓ b ℓ with α 1 , . . . , α ℓ ∈ Z, C(v + w, n) intersects each of the hyperplanes π 1 , . . . , π j . Furthermore, if v + w ∈ D and C(v + w, n) intersects no other hyperplane, then X v,n = X v+w,n .
Proof. By definition of W , the hypercubes C(v, n) and C(v + w, n) have the same relative position with respect to π 1 , . . . , π j (e.g., consider two intersecting planes in a space of dimension 3 and assume that a cube intersects these two planes, then a translation of w corresponds to a move in the direction of the intersection of the two planes, so the cube still intersects these two planes with a similar relative position of the cube compared with the planes). Moreover, since in each domain the pattern is given by congruence relations modulo J, we conclude thanks to the choice made for the basis (each of the components is a multiple of J).

Remark 23. There exist finitely many vectors of the kind

α 1 b 1 + • • • + α ℓ b ℓ belonging Z d with (α 1 , . . . , α ℓ ) ∈ Q ℓ ∩ [-1, 1] ℓ .
This observation and the periodicity induced by the previous lemma lead to the following fact. Let v ∈ D be such that C(v, n) intersects each of the hyperplanes π 1 , . . . , π j and no other. There exists a constant Q (independent of n) such that the number of pairwise distinct blocks X v+w,n is bounded by Lemma 24. For all i ∈ {1, . . . , d -ℓ}, there exists a constant C i > 0 such that for all C(x, n) intersecting π 1 , . . . , π j at some point y ∈ R d , the following holds:

Q when α 1 , . . . , α ℓ ∈ Q are such that w = α 1 b 1 +• • •+α ℓ b ℓ ∈ Z d , v + w ∈ D and C(v + w, n) intersects
• if C(x + ke i , n) intersects π 1 , . . . , π j , then |k| ≤ C i n, • if |k| > C i n, then C(x + ke i , n) does not intersect π 1 , . . . , π j .
Proof. Without loss of generality, we may assume i = 1. Since e 1 does not belong to W , there exists m ∈ {1, . . . , j} such that e 1 does not belong to the vector subspace π ′ m . In a system of coordinates built on the basis (e 1 , . . . , e d-ℓ , b 1 , . . . , b ℓ ), we may assume π m has an equation of the kind

α (m) 1 x 1 + • • • + α (m) d x d = c
and that y = (a 1 , a 2 , . . . , a d ) belongs to π m . In this case, the equation of the corresponding vector subspace π ′ m is α (m) 1

x 1 + • • • + α (m) d x d =
∃ℓ 2 , . . . , ℓ d ∈ [[-n, n]] : α (m) 1 k + α (m) 2 ℓ 2 + • • • + α (m) d ℓ d = 0. That is, if and only if k = -(α (m) 2 ℓ 2 + • • • + α (m) d ℓ d )/α (m) 1 .
Thus, it suffices to take

C i = sup m d |α (m) i | ||α (m) ||,
where α (m) is the vector whose coordinates are the α (m) i .

We are now able to conclude this part of the proof. There are two kinds of recurrent blocks of size n. Those that do not intersect any hyperplane in Π and those that do. Let us call R 1 X (n) the number of blocks of the first kind and R 2 X (n) the number of blocks of the second kind. Lemma 20 shows that R 1 X (n) is less than the constant 2 t J d . To bound R 2 X (n), we make our reasoning only on the recurrent blocks X yi,n such that y i belongs to a given domain D and C(y i , n) intersects each of the hyperplanes π 1 , . . . , π j and no other (recall that there is only a constant number of such cases to take into account). Thanks to Lemma 22 and Remark 23, moving such a block in any direction parallel to W leads to a number of pairwise distinct blocks bounded by a constant. On the other hand, when moving in a direction spanned by e 1 , . . . , e d-ℓ , Lemma 24 shows that we can have up to O(n d-ℓ ) pairwise distinct blocks of size n. Recall from Lemma 21 that ℓ = dim W belongs to {1, . . . , d -1}. Furthermore, as suggested by the following example, the bound on R 2 X is tight. Consider the hyperplanes having respectively equation x 1 = 0, x 2 = 0, . . . , x d-ℓ = 0 defining 2 d-ℓ regions of the kind

{(x 1 , . . . , x d ) | ∀i ∈ {1, . . . , d -ℓ} : x i i 0} with 1 , . . . , d-ℓ ∈ {≥, <}. Let us define a set X ⊂ Z d such that x = (x 1 , . . . , x d ) ∈ X if and only if x 1 • • • x d-ℓ ≥ 0, i.e.
, if the components of x are non-zero, the fact that x belongs to X depends inly on the parity of the number of negative components amonst the d -ℓ first. Observe that all C(v, n) where v = (v 1 , . . . , v n ) are such that, for all i ∈ {1, . . . , d -ℓ}, -n < v i ≤ 0 give different blocks. Notice also that there is no constraint on v d-ℓ+1 , . . . , v n , modifying any of these components gives the same block and thus such blocks occur infinitely often. Consequently, we get a number of distinct recurrent block equal to n d-ℓ .

Proof of the converse

In what follows, as explained in Remark 3, we make no distinction between a subset of Z d and its characteristic word which belongs to {0, 1} Z d . We consider indifferently complexity functions of both subsets of Z d and binary words indexed by Z d . 5.1. An interesting lemma. The following lemma based on the pigeonhole principle is of particular importance in what follows. It is a first step to provide us with a set of relatively small local periods. The next step is Corollary 26 which is more explicit respectively to our problem. This lemma is proven in [START_REF] Quas | Periodicity and local complexity[END_REF] for d = 2, we simply adapt it to our setting.

Lemma 25. Let M ⊂ Z d and C > 0 be such that R M (n) ≤ Cn d-1 for all n.
Let n ∈ N. There exists m 0 ∈ N such that, for all m satisfying m < n and m d -Cn d-1 ≥ 1, and all z = (z i ) 1≤i≤d , with ||z|| ≥ m 0 + m, there exists a nonzero vector v = (v i ) 1≤i≤d with ||v|| ≤ m, verifying

M z-v,n-m = M z,n-m = M z+v,n-m .
Proof. Far enough from the origin, every block is recurrent. Formally, for all n ∈ N there exists m 0 such that if ||x|| ≥ m 0 , then M x,n is recurrent in M . Let m and z = (z i ) 1≤i≤d be such that m < n, m d -Cn from the fact that M z+y,n = M z+y-v,n and from the overlap of the two blocks.

The following corollary shows that Lemma 25 is "almost" sufficient to complete the proof of Theorem 2.

Corollary 26. Let M ⊆ Z d . Suppose there exists C > 0 such that R M (n) ≤ Cn d-1 for all n. Then, for all large enough K there exists L ≥ 0 such that

∀x ∈ Z d , ||x|| ≥ L, ∃v, ||v|| ≤ (2C) 1 d (5K) d-1 d : M is v-periodic inside B(x, K).
Proof. Suppose d = 1: R M (n) ≤ C for all n. Let x ∈ {0, 1} Z be the characteristic word of M . It suffices to show that there exists three words u, v and w such that

x = • • • uuuwvvv • • • .
We can of course suppose C is an integer. There exists a positive integer n 0 such that all words of length C + 1 appearing in

x + = x n0 x n0+1 • • • and x -= • • • x -n0-1
x -n0 are recurrent (i.e., appear infinitely many times in these sequences). Thus in x + and x -the number of words of length C is less than C. Thus, due to Morse-Hedlund theorem (Theorem 1) both sequences are ultimately periodic:

x + = w + vvv • • • and x -= • • • uuuw -
: n → (1 + Cn d-1 ) 1/d , γ : n → (2C) 1/d n d-1 d and β : n → (n -γ(n))/4. Let n 0 be such that • β is increasing on [n 0 , +∞[; • γ(n) < n for all n ≥ n 0 ; • γ(n) ≤ β(n -1) for all n ≥ n 0 ; • n ≤ 5β(n -1) for all n ≥ n 0 . Let K, n be integers such that K ≥ β(n 0 ), n ≥ n 0 + 1 and β(n -1) ≤ K ≤ β(n).
Let m 0 be given by Lemma 25. Let m be an integer satisfying α(n) ≤ m ≤ γ(n). Notice that m satisfies the assumption of Lemma 25. We set L = m 0 + m + 2K. Let x satisfying ||x|| ≥ L. Let 1 be the vector consisting of ones. From Lemma 25, since ||x -2K1|| ≥ m 0 + m, there exists a vector v, with ||v|| ≤ m such that

M x-2K1,n-m = M x-2K1+v,n-m . But as n -m ≥ n -γ(n) = 4β(n) ≥ 4K, we also have M x-2K1,4K = M x-2K1+v,4K . Thus, M is v-periodic inside B(x, K). Moreover, from the choice of n 0 we obtain that ||v|| ≤ m ≤ (2C) 1/d n d-1 d ≤ (2C) 1/d (5β(n -1)) d-1 d ≤ (2C) 1/d (5K) d-1
d . This completes the proof.

In order to obtain local periodicity as given in Definition 8 leading to a proof of Theorem 2, it would be nice that Corollary 26 implies the existence of a set V ⊂ Z d such that K > v∈V ||v||. This is the case in particular for d = 2 (as presented below). For d ≥ 3 we are not able to give such a direct proof as for d = 2. Nevertheless this corollary is interesting because it provides us with a finite set of quite small local periods. We will use this when d ≥ 3. 5.2. Proof of Theorem 2 for d = 2. The following two lemmata are also true in higher dimensions. The first one is another way to settle down the underlying idea of Lemma 25. Let 1 be the vector consisting of ones.

Lemma 27. Let M ⊂ Z 2 . Suppose M is v-periodic inside B(x, n), for some v = 0, ||v|| < n, and is not w-periodic for any w with ||w|| < ||v||. Then, the ||v|| 2 blocks M x-n1-z,2n+||v|| with z ∈ [[0, ||v|| -1]] 2 are pairwise distinct.

Proof. Suppose there exist two distinct vectors z 1 and

z 2 in [[0, ||v|| -1]] 2 such that M x-n1-z1,2n+||v|| and M x-n1-z2,2n+||v|| are equal. Let w = z 1 -z 2 . Then, ||w|| < ||v|| and M is w-periodic inside B(x, n). Lemma 28. Let n ∈ N, M ⊂ Z 2 and v 1 , . . . , v k , x 1 . . . , x k be vectors of Z 2 such that (1) 0, v 1 , . . . , v k are pairwise distinct; (2) ℓ = max ||v i || ≤ n; (3)
for all i, M is v i -periodic inside B(x i , n) and is not w-periodic inside B(x i , n) for any w with ||w|| < ||v i ||; (4) for all i, M is not v j -periodic inside B(x i , n) for j < i. Then, we have

# M xi-n1-z,2n+ℓ | z ∈ [[0, ||v i || -1]] 2 , 1 ≤ i ≤ k = k i=1 ||v i || 2 .
Proof. Lemma 27, for all i, we have

# M xi-n1-z,2n+||vi|| | z ∈ [[0, ||v i || -1]] 2 = ||v i || 2
and thus, when considering possibly larger blocks, we get

# M xi-n1-z,2n+ℓ | z ∈ [[0, ||v i || -1]] 2 = ||v i || 2 .
Let i, j be such that 1 ≤ j < i ≤ k. It is sufficient to prove that, for all vectors z i ∈ [[0, ||v i || -1]] 2 and z j ∈ [[0, ||v j || -1]] 2 , the blocks M xi-n1-zi,2n+ℓ and M xj-n1-zj ,2n+ℓ are distinct. Indeed, suppose there exist z i and z j such that M xi-n1-zi,2n+ℓ and M xj -n1-zj ,2n+ℓ are equal. Then, since B(x i , n) is included in B(x i -n1z i , 2n + ℓ), M would be v j -periodic inside B(x i , n). This contradicts our assumption (4).

Let us conclude with the proof of Theorem 2 for d = 2. Let M ⊂ Z 2 such that for some C have R M (n) ≤ Cn, for all n, and having all its sections definable in Z; <, + . Thanks to Theorem 10, it suffices to prove that M is locally periodic. Taking in Corollary 26 a large enough K, M satisfies the following property:

(P) there exist two positive integers K and L ′ such that

(1) ∀x ∈ Z 2 , ||x|| ≥ L ′ , ∃v, ||v|| ≤ √ 10CK : M is v-periodic inside B(x, K); (2) √ 10CK ≤ K; (3) 8 log(K) 3 + 3CK log(K) < K. Let L ′′ be such that if ||x|| ≥ L ′′ ,
then the block M x,3K is recurrent. Let L be greater than 2K + L ′′ + L ′ . We need the following lemma.

Let ℓ = max v∈V ||v||. Lemma 29 provides us with vectors x 1 , . . . , x k ∈ Z 2 and a set V = {v 1 , . . . , v k } ⊂ Z 2 fulfilling the hypothesis of Lemma 28. To get local periodicity it remains to show that v∈V ||v|| < K. Applying Lemma 28, we obtain

v∈V ||v|| 2 ≤ R M (2K + ℓ) ≤ C(2K + ℓ).
Using Property (P), we deduce that ℓ ≤ √ 10CK ≤ K. Hence

v∈V ||v|| 2 ≤ 3CK. Let δ n = #{v ∈ V | ||v|| = n}. Then, we have log(K) 2 ⌊ √ 10CK⌋ n=⌊log(K)⌋ δ n ≤ ⌊ √ 10CK⌋ n=1 δ n n 2 = v∈V ||v|| 2 ≤ 3CK.
Consequently, we get

⌊ √ 10CK⌋ n=⌊log(K)⌋ δ n ≤ 3CK log(K) 2 .
Hence, using Cauchy-Schwarz inequality, we deduce that

⌊ √ 10CK⌋ n=⌊log(K)⌋ δ n n = ⌊ √ 10CK⌋ n=⌊log(K)⌋ δ n δ n n ≤   ⌊ √ 10CK⌋ n=⌊log(K)⌋ δ n   1/2   ⌊ √ 10CK⌋ n=⌊log(K)⌋ δ n n 2   1/2 ≤ 3CK log(K) .
Using the fact that, for all n,

δ n ≤ #{v ∈ Z 2 | ||v|| = n} = # n i=-n {(i, n), (i, -n), (n, i), (-n, i)} = 8n, we deduce that v∈V ||v|| = ⌊ √ 10CK⌋ n=1 δ n n ≤ ⌊log(K)⌋-1 n=1 δ n n + 3CK log(K) ≤ 8 ⌊log(K)⌋-1 n=1 n 2 + 3CK log(K) ≤ 8 log(K) 3 + 3CK log(K) < K.
This concludes the proof for d = 2.

Observe that this kind of computation gives nothing in dimension d ≥ 3 because, given some constants a, b, c one should find some sufficiently large K and a function α(K) such that a + bα(K) d+1 + cK d-1 α(K) < K. This is clearly not possible. But, maybe some of the above inequalities could be improved in order to have a direct proof for all d ≥ 3. We leave this as an open question.

In fact, as we did not used the assumption that each section of M is definable, we prove more than what was expected. We have shown that the hypothesis R M (n) ∈ O(n) implies the local periodicity of M . Thus, the definability of the sections is only needed to go from the local periodicity of M to the definability of M . We do not know whether it is true in higher dimensions. This is related to the previous remark.

circles.

The following two lemmata show that it is sufficient to prove that, for some v, the set Bd(M, v) is locally periodic. Bd(A, -v) and a finite number of sections of A, i.e., A can be defined by a formula involving addition, order and unary predicates for the sets Bd(A, v), Bd(A, -v) and for a finite number of sections of A.

The next lemma suggests to proceed by induction on the cardinality of the set of local periods to prove that Bd(M, v) is locally periodic.

Lemma 32. [14, Lemma 1.1] Let A ⊂ Z d . Suppose there exist K, L ≥ 0 and a finite set V ⊂ Z d \ {0} verifying that, for all x ∈ Z d with ||x|| ≥ L, the set A is V -periodic inside B(x, K). Then, for all v ∈ Z d and all x ∈ Z d with ||x|| ≥ L, the set Bd(A, v) is V \ {v, -v}-periodic inside B(x, K).
To complete the proof of Theorem 2 we will proceed by induction on the cardinality of V . We will say that a set M ⊆ Z d satisfies Hyp(k) whenever :

(1) there exists C > 0 such that, for all large enough n ∈ N, R M (n) ≤ Cn d-1 ; 6.1. Delone sets and repetitiveness (or recurrence). Let us recall some terminology in [START_REF] Lagarias | Local complexity of Delone sets and crystallinity[END_REF]. Let X be a subset of R d . We say that X is a (r, R)-Delone set if it has the following two properties:

(1) Uniform Discreteness. Each open ball of radius r in R d contains at most one point of X. (2) Relative density. Each closed ball of radius R in R d contains at least one point of X. Observe that the subsets of Z d are discrete for r = 1/2. The period lattice of a Delone set X is the lattice of translation symmetries given by Λ X = {p ∈ R d |X + p = X}. It is a free abelian group with rank between 0 and d. When the rank of Λ X is equal to d, we say that X is an ideal crystal. Let B(x, t) stands for the open ball centered in x ∈ R d of radius t. The set P X (x, t) = X ∩ B(x, t) is called a t-patch of X. In the sequel we will consider that two t-patches are equal when they are equal up to translation. The Delone set X is repetitive if for each t there is M (t) > 0 such that every closed ball B of radius t contains all t-patches of X (up to translation). It is linearly repetitive if there exists a constant C such that M (t) ≤ Ct for all t > 0. We denote by p X (t) the number (possibly infinite) of different t-patches (up to translation). 6.2. The Period Conjecture. The Period Conjecture is stated in [START_REF] Lagarias | Local complexity of Delone sets and crystallinity[END_REF] for Delone sets in R d .

Period Conjecture. For each integer j = 1, . . . , d, there is a positive constant c j (r, R) such that any (r, R)-Delone set X of R d satisfying p X (t) < c j (r, R)t d-j+1 for all t > t 0 (X), for some t 0 (X), has j linearly independent periods.

Lagarias and Pleasants showed in [START_REF] Lagarias | Local complexity of Delone sets and crystallinity[END_REF] that this conjecture is true for j = n.

Theorem 35. If a (r, R)-Delone set X ⊂ R d has a single value t such that p X (t) < t 2R then X is an ideal crystal.

In [START_REF] Epifanio | On a conjecture on bidimensional words[END_REF] and [START_REF] Quas | Periodicity and local complexity[END_REF] it is also proven for j = 1 and subsets of Z 2 that are not necessarily Delone sets (see Theorem 38 below). In [START_REF] Lenz | Aperiodic linearly repetitive Delone sets are densely repetitive[END_REF], D. Lenz answers positively to a conjecture in [START_REF] Lagarias | Repetitive Delone sets and quasicrystals[END_REF] saying that with the extra hypothesis of linear repetitiveness the Period Conjecture is not far to be true for j = 1.

Theorem 36. Every aperiodic linearly repetitive Delone set X ⊂ R d satisfies lim inf t→∞ p X (t) t d > 0. 6.3. Nivat's Conjecture. Let us recall the Nivat's Conjecture [START_REF] Nivat | Invited talk at ICALP[END_REF] stated in 1997 (see also [START_REF] Berthé | Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences[END_REF]).

Conjecture 37 (M. Nivat). Let M be a subset of Z 2 . If there exist n 1 , n 2 > 0 such that the function p M counting the number of distinct (n 1 × n 2 )-blocks occurring in M is such that p M (n 1 , n 2 ) ≤ n 1 n 2 , then M is periodic.

Nivat's Conjecture cannot be an equivalence because the converse does not hold: there exists a periodic set M in Z 2 such that p M (n 1 , n 2 ) > n 1 n 2 , for all n 1 , n 2 , see [1, p. 49]. Moreover, it cannot be true for dimensions d strictly greater than 2 as shown in [START_REF] Sander | The complexity of functions on lattices[END_REF]. A weaker form of Nivat's Conjecture is the following. Let α < 1. If there exist n 1 , n 2 > 0 such such that p M (n 1 , n 2 ) ≤ αn 1 n 2 , then M is periodic. It was proven for α = 1/144 in [START_REF] Epifanio | On a conjecture on bidimensional words[END_REF] and improved for α = 1/16 in [START_REF] Quas | Periodicity and local complexity[END_REF]. This latter result is a consequence of the following one.

Theorem 38. [START_REF] Quas | Periodicity and local complexity[END_REF] Let M be a subset of Z 2 . If there exist n 1 , n 2 > 0 such that for all (2n 1 × 2n 2 )-blocks B the function counting the maximum number of distinct (n 1 × n 2 )-blocks occurring in B is less or equal to n1n2 16 , then M is periodic. As explained in Section 6.2, this theorem is related to the Period Conjecture. For a survey on the relationships existing between periodicity and block complexity in Z d we refer to [START_REF] Cassaigne | Subword complexity and periodicity in two or more dimensions[END_REF] and [START_REF] Tijdeman | Periodicity and almost-periodicity[END_REF]. We can also mention [START_REF] Sander | The rectangle complexity of functions on two-dimensional lattices[END_REF], see below.

6.4. The Periodicity Principle. Let us recall some terminology introduced in [START_REF] Sander | The complexity of functions on lattices[END_REF]. Let S ∈ {0, 1} Z d . For all finite subset B of Z d we define the B-patterns of S to be the functions S (v) : B → {0, 1} defined by S (v) (x) = S(x + v), v ∈ Z d . The set of all B-patterns is P S (B) = {S (v) |v ∈ Z d }. When B is a cube of size n, then P S (B) is equal to the block complexity p S (n). In [START_REF] Sander | The complexity of functions on lattices[END_REF] the following conjecture is stated .

Periodicity Principle. Let S ∈ {0, 1} Z d and B be a finite subset of Z d . If #P S (B) ≤ #B, then S is periodic.

It is shown in [START_REF] Sander | The complexity of functions on lattices[END_REF] that the Periodicity Principle is true in dimension 1 and turns to be false in higher dimensions without some additional assumptions. If the Nivat's Conjecture holds true, it could be considered as a restricted Periodicity Principle for rectangle blocks. 6.5. Final comments. First, one can show that for subsets M of Z d having all its blocks of size n occurring infinitely many times, definability implies periodicity. Now let us give a corollary of our main result (Theorem 2) in the context of repetitive subsets of Z d , and then comment it relatively to the previously described works.

Theorem 39. Let M be a repetitive subset of Z d . The following statements are equivalent:

(1) R M (n) ∈ O(n d-1 ) and every section is definable in Z; <, + ;

(2) for all k ∈ {1, . . . , d -1} every (d -k)-dimensional section of M has a recurrent block complexity in O(n d-k-1 ); (3) M is an ideal crystal.

Proof. It suffices to use Theorem 10 and to see that when a set is semi-linear and repetitive then it is a ideal crystal (the converse being also true).

Observe that in the above result, assumptions (1) or (2) are much stronger than those of the Period Conjecture. Nevertheless we obtain a necessary and sufficient condition to be an ideal crystal in terms of block complexity. Moreover, for j = 2, the Period Conjecture expects only two linearly independent periods when we obtain an ideal crystal, that is d linearly independent periods. Similar comments are also valid for the Periodicity Principle. Thus, we obtain a restricted Periodicity Principle as it holds for cubic blocks B. But we obtain a much stronger result than just a one dimensional periodicity conclusion. A natural question is whether Theorem 39 remains true for any finite subset B in order to have a Periodicity Principle for repetitive sets. Another question is to ask whether the Periodicity Principle or the Period Conjecture are true for some wellknown families of Delone sets or tilings like those of finite type, linearly repetitive, substitutive, ...

Figure 2 .

 2 Figure 2. Illustration of local periodicity.

Figure 3 .

 3 Figure 3. Examples of sets definable in Presburger arithmetic.

Figure 4 .

 4 Figure 4. Toeplitz'like set.

Figure 5 .

 5 Figure 5. Some blocks of size 3 occurring in T .

Figure 6 .

 6 Figure 6. Regions in dimension 2.

Figure 7 .

 7 Figure 7. Intersection of a square and a line.

  a vector space of dimension ℓ ∈ {1, . . . , d -1}. Let (b 1 , . . . , b ℓ ) be a basis of W . We can suppose the entries of b 1 , . . . , b ℓ are integers and multiples of J. The first idea is to show that a move parallel to W only produces a constant number of distinct blocks. Lemma 22. Suppose C(v, n), v ∈ D, intersects each of the hyperplanes π 1 , . . . , π j and no other. Then for all w = α 1 b 1

  each of the hyperplanes π 1 , . . . , π j and no other.Let e 1 , . . . , e d-ℓ be integer vectors such that (e 1 , . . . , e d-ℓ , b 1 , . . . , b ℓ ) is a basis of the space R d . The idea is now to move in a direction not parallel to W and show that we have d -ℓ degrees of freedom.

  0. The components of e 1 in the basis (e 1 , . . . , e d-ℓ , b 1 , . . . , b ℓ ) are (1, 0, . . . , 0) and they do not satisfy the equation of π ′ m (otherwise, we would get that e 1 ∈ π ′ m ). Therefore, α (m) 1 is non-zero. We can determine the values of k such that (a 1 + k, a 2 + ℓ 2 , . . . , a d + ℓ d ) belongs to π m for some ℓ 2 , . . . , ℓ d ∈ [[-n, n]]. Indeed, this latter point belongs to π m if and only if

Figure 9 .

 9 Figure 9. Sketch of the situation in Lemma 25.

  where u and v are non-empty words. Moreover it is classical to deduce from the proof of Morse-Hedlund theorem that |u| and |v| are both less than C. This achieves the proof. Thus we suppose d ≥ 2. Consider the following maps α

5. 3 .Figure 10 .

 310 Figure 10. Illustration of the border of A in the direction v.

Lemma 30 .

 30 [14, Lemma 1.0] Let A ⊂ Z d and v ∈ Z d . If all sections of A are definable, then all sections of Bd(A, v) are definable. Lemma 31. [14, Lemma 1.2] Let A ⊂ Z d and v ∈ Z d . The set A is definable in terms of Bd(A, v),

We call domain any subset of Z d defined by a conjunction of formulas of the kind (4.2).

We call pattern any subset of Z d defined by a conjunction of formulas of the kind (4.3).

In what follows, when dealing with intersections, one should understand that the underlying hypercube, considered as a convex body in R d , does not intersect any hyperplane.

Acknowledgements. The authors thank the referees for their valuable and relevant comments.

(2) all sections of M are definable;

(3) there exist K, L ≥ 0 and

< K, and, (c) #V = k.

We note that, from Corollary 26, the subsets of

) and having all its sections definable in Z; <, + , satisfy Hyp(k) for some k. Hence, to complete the proof of Theorem 2 it is sufficient to prove that the following assertion P (k) is true for all k.

P (k) :

If M ⊆ Z d satisfies Hyp(k), then it is definable.

If M satisfies Hyp(1) then (3) corresponds to the local periodicity of M . Hence P (1) is true.

Let k ≥ 1 be such that P (1), . . , P (k) are true. Let M be a subset of Z d satisfying Hyp(k + 1). It remains to prove that M is definable. Let C, V , K and L be given by Hyp(k + for M .

Lemma 33. For all v ∈ Z d and ǫ > 0 there exists

Lemma 34. For all v ∈ V the sets Bd(M, v) and Bd(M, -v) satisfy Hyp(k).

Proof. Let w ∈ {v, -v}. From Lemma 33 there exists ǫ > 0 such that (2(C + ǫ))

for all large enough n. From Lemma 30 all sections of Bd(M, w) are definable. We take for Bd(M, w) the constants K, L and the set V of M . With Lemma 32 we know that Bd(M, w) is V \ {v, -v}-periodic inside B(x, K) for all x with ||x|| ≥ L, and, thus satisfies Hyp(k).

We can now conclude the proof of Theorem 2. Let v ∈ V . From Lemma 34, Bd(M, v) and Bd(M, -v) satisfy Hyp(k). BY induction hypothesis both Bd(M, v) and Bd(M, -v) are definable. Hence, by Lemma 31, M is definable.

We recall that for d = 2 we do not need the definability of the sections to deduce the local periodicity. Observe that for dimensions d ≥ 3 it is not the case: We need the definability of the sections to show that the boarders are definable and then, using the induction process and the Muchnik criterion, to conclude the proof.

Related works

In this section we recall some well-known works on the relations between the block complexity and the periodicity for subsets of Z d and R d . We end this section with some comments, related to these works, on our main result with the additional hypothesis of repetitiveness.


Anthony Sigogne
email: asigogne@univ-mlv.fr

Matthieu Constant
email: mconstan@univ-mlv.fr

Real-time unsupervised classification of web documents

This paper adresses the problem of clustering dynamic collections of web documents. We show an iterative algorithm based on a fine-grained keyword extraction (simple, compound words and proper nouns). Each new document inserted in the collection is either assigned to an existing class containing documents of the same topic, or assigned to a new class. After each step, when necessary, classes are refined using statistical techniques. The implementation of this algorithm was successfully integrated in an application used for Information Intelligence.

I. INTRODUCTION

I NFORMATION on the web continously evolves as new documents on new topics are made available everyday. Nevertheless, standard classification algorithms are usually best-suited for static collections of documents and are not optimized for dynamic ones. Indeed, generally, each time a new document arrives, the representations of all classes have to be recalculated. This paper adresses this problem by describing a fine-grained clustering system on dynamic sets of web documents. Its implementation is driven by real industrial needs in Information Intelligence. It requires a real-time classification procedure as thousands of new documents arrive everyday. Classes (or clusters) must correspond to precise events or topics. They are not predefined in advance as news constantly change.

In this paper, we show an iterative algorithm based on a fine-grained keyword extractor taking compound and proper nouns into account. Each new document processed is either assigned to an existing class containing documents of the same topic, or assigned to a new class if no classes match the document topic. After each step, when necessary, the modified classes are refined using statistical techniques by [START_REF] Charu | On using Partial Supervision for Text Categorization[END_REF]. Our method can be compared to [START_REF] Dragomir | A description of the CIDR system as used for TDT-2[END_REF], that was also implemented with strict time efficiency requirements.

Our method is different from standard methods using kmeans algorithm and its extensions, that assum a fixed number (k) of classes and have to recompute classes at each step. Such approach is unappropriate to our problem. Standard agglomerative algorithms are also hardly applicable because in our system all documents are not known initially 1 .

The paper is divided into 4 sections. First, we describe how a document is represented in our system, on the basis of a keyword extraction process. Then, we detail our real-time classification algorithm. Next, we show some implementation details on our system, that is, finally, evaluated.

II. DOCUMENT REPRESENTATION

In the Space Vector Model (SVM) approach, documents are represented as vectors. Each dimension corresponds to a unique term in a collection of documents. For a given document, a dimension is the importance weight of the corresponding term in the document and generally depends on the frequency of the term. For space and speed efficiency reasons, it is often of great interest to limit the number of terms with non-zero weights. In the following, we call these terms keywords. This section is devoted to the extraction and the weigthing of keywords for each web document to be classified.

A. Keyword candidate recognition

Keywords are usually limited to stemmed or lemmatized word-tokens. More and more studies show that the use of more complex forms like named entities (e.g. proper nouns) or word bigrams (trigrams) may improve the system quality. In this paper, we propose to augment the set of standard terms with compound nouns and proper nouns. Compound nouns are recognized by dictionnary look-up and proper nouns by local grammar application. For compounds, we used Unitex large-scale morphological resources [START_REF] Paumier | User Manual[END_REF] available for various languages. These resources were built manually since the 90s by linguists. They also indicate the lemma of each word, so it is possible to lemmatize each compound word: e.g. complex lemma fried patato would stand for compound fried patatoes. Resources also include information on internal structures: this allows for selecting compounds with specific internal structures. Proper nouns are recognized with the use of a local grammar in the form of a finite-state graph [START_REF] Gross | The construction of local grammars[END_REF], [START_REF]Max Silberztein INTEX: An FST Toolbox[END_REF]. The graph roughly represents sequences of capitalized words like John Smith. Sequences like Marne-la-Vallée, Mohammed al Cherif are also recognized. These grammars are contextualized so that utterance In Paris located at the beginning of a sentence, should not be considered as a proper noun. The named entity recognized should be limited to Paris.

B. Keyword filtering and weigthing

In order to improve efficiency, we limited document terms to relevant keywords by filtering candidate terms with a mixed linguistic and statistical approach. First, it is well-known that the main semantic information is contained in nouns, verbs and adjectives of texts. Keywords are even often reduced to nouns. In our case, we applied the morphosyntactic tagger TreeTagger [START_REF] Schmid | Probabilistic Part-of-Speech Tagging Using Decision Trees[END_REF] and kept only the lemmas of the nouns in the document.

This linguistic process is not sufficient and can be combined with a statistical filtering. Usually, each term is given a weight. For each document, the filtering process then keeps only the terms with the best weights. A very well estabished weighting schema is TF.IDF [START_REF] Salton | McGill Introduction to modern information retrieval[END_REF]. For each document j, a term i is assigned a weight w ij :

w ij = T F IDF (i, j) = tf ij • log N N i
where tf ij is the frequency of term i in document j, N is the number of documents in the collection and N i is the number of documents where term i occurs. We applied this term weighting schema by using an external collection of documents, because the entire collection to be classified is not known at the beginning of the process. We used a static collection of web documents randomly extracted from news documents on the web. The main drawback with this collection is that it is independent of the main topic of the processed documents and is limited to general language.

In order to deal with unknown words (words occurring in the document processed, but absent in the external collection), we slightly smoothed the term weight formula like in:

w ij = tf ij • log N + 1 N i + 1
The term frequency tf ij is defined by the number of terms i occurring in document j normalized by the size of document j (number of terms). If a term is not in the external collection, its weight cannot be null in a text where it occurs. Moreover, this enables the weight to be independent of the size of the document processed. This weighting schema was not entirely relevant for compound nouns. Compound nouns can also be reduced to one or some of their components: e.g. green card can be reduced to card. In a text block where green card occurs, an occurrence of card is also potentially a reference to the entity green card. Therefore, it sounds relevant to augment the weight of such a term by the weight of its internal nouns (in the example, card). So the weight w ij of a compound noun i including k nouns (N 1 , N 2 , . . . , N k ) in a document j is

w ij = T F IDF (i, j) + n k=1 T F IDF (N k , j)
Note that this weighting schema is not always relevant. For instance, bank card cannot be reduced to bank. This technique would require refinement by keeping only the head noun. But this is not always accurate or/and sufficient. For instance, French word vin rouge (red wine) can be reduced in rouge (red). Some compounds cannot be reduced at all: porte-parole (spokesman).

The filtering process of simple and compound nouns consists in discarding any of them the weight of which is lower than a threshold. Proper nouns are not filtered. After some experimental tests, we observed that some recurrent nonrelevant words (often, terms in the domain of informatics) were not removed by the filtering process. We then manually formed a stop word list including these words in order to refine the process.

For each document, the filtering process results in a vector each dimension of which corresponds to a unique keyword in the collection. Each dimension is the frequency of the corresponding keyword in the document. Although many systems used TFIDF to measure the weight of keywords, we chose to keep the frequency because the TFIDF would depend on a static external statistics independent of the topic of the subjects processed. In addition, after a strict filtering process, the frequency is a good indicator of the importance of a term.

III. CLASSIFICATION

The classification approach uses a single-pass algorithm. It tries to assign a class (an existing one or a new one) to each new document. If the new document has been included in an existing class, this class might need some refinements: (1) merge with others whether they have become very similar to each others or (2) split whether it has become incoherent.

A. Class projection

A class is defined by the set of documents belonging to it. It is represented in the term space by the centroid of the vectors of all its documents. The dimension c ij corresponding to the importance weight of a term i in a class j is defined by:

c ij = k∈Cj w i k K j
where C j is class j and K j is the number of documents in C j . Like for document representation, it is of great interest to reduce the size of the term space. For instance, there might be many terms in common amongst classes because all documents are of the same general topic. These terms are useless to discriminate classes. As a consequence, they can be removed from the term space. A way to filter such terms is to use a weighting schema ressembling TFIDF, the normalized gini-index introduced in [START_REF] Charu | On using Partial Supervision for Text Categorization[END_REF]. It measures the discriminating value of a term in the set of classes.

Let's assume that the collection of documents can be classified in K classes. Let p i be a function which takes a term as an argument and returns the weight of this term in class i. It is defined as follows:

p i (x) = fi(x) ni K j=1 fj (x) nj
where f i (x) is the number of occurrences of term x in the documents of C i and n i is the total number of terms in the documents of C i . If a term x is considered as noise, p i (x) should be close to 1/K for all classes.

The normalized gini-index of term x is then defined as:

gini(x) = 1 - K i=1 p i (x) 2
For each term x, if gini(x) is lower than a fixed threshold, x is discarded from the term space of all classes.

B. Class assignation

The classification algorithm is a standard single-pass algorithm as in [START_REF] Dragomir | A description of the CIDR system as used for TDT-2[END_REF]. It classifies one document at a time and assigns it to the most similar class. The similarity is measured by the cosine between the document vector and the class centroid. For each class, if the cosine is greater than a manually-fixed threshold, the class is added to the candidate class list sorted by decreasing similarity to the document. Once all classes have been compared with the document, there exist three cases:

1) No class is candidate. This means that the topic of the new document does not match with the topics of the other classes. We therefore create a new class only composed of the document. 2) One class is candidate. We then assign the document to this class. The class centroid is then recomputed. 3) Two or more classes are candidate. A simple solution is to choose the most similar class. But, [START_REF] Charu | On using Partial Supervision for Text Categorization[END_REF] showed that, in the case where the difference of similarities is small, there might exist some similarities between the classes, i.e. they share keywords. To best discriminate classes, it is therefore interesting to compare them without their keywords in common. Our selection process consists in taking the two best candidate classes (two first in the list) and applying the comparison method in [START_REF] Charu | On using Partial Supervision for Text Categorization[END_REF] as it is described below. Once the best class is found, we assign it to the document to be classified and recompute the centroid. Let S 1 and S 2 be the centroids of the two candidate classes. Filtering a class centroid S 1 (S 2 ) consists in nulling the dimensions corresponding to words in common between S 1 and S 2 . The resulting vector is noted S 1 -S 2 (resp. S 2 -S 1 ).

Let's now define a dominance property of a class over another one with respect to a document T . We say that S 1 dominates S 2 if:

• the difference between the similarities of S 1 and S 2 to document T is greater than a manually-fixed threshold T h. • if this difference is lower than T h, the similarity between S 1 -S 2 and T is greater than the one between S 2 -S 1 and T . If S 1 dominates S 2 , the class corresponding to S 1 is assigned to the document. In order to refine our clustering after classifying a new document, we used the method described in [START_REF] Charu | On using Partial Supervision for Text Categorization[END_REF]. We implemented two operations: merging and splitting classes.

C. Class refinements

1) Merge classes: When inserting a new document in an existing class, its centroid is then modified and the class might have become very similar to another class. They should be merged together. In our system, we consider that two classes should be merged if the cosine between their centroids is greater than a manually-fixed threshold. In that case, all documents of the two classes should be gathered in a single class. The merging method is iterative: the modified class c is successively compared with all classes. If they are similar enough, the class c is augmented with the documents of the other class. A class can therefore be merged with several classes. This process is repeated until the set of classes is stable.

2) Split classes: When inserting a new document in a class, the class might become less coherent and should be splitted. The coherency of a class can be calculated with the intra-class value. It is defined by the following formula:

intra(c) = di,

A. Overview

The clustering method described above has been integrated in a real-life application for the French company XERES devoted to Information Intelligence. This company continously receives RSS feeds of web documents on specific topics (around 10,000 documents a day) and is required to discover emergent opinions, trends about this topic. As the number of documents to be examined is very high, they need automatic tools extracting the global meaning of each document and classify them in fine-grained clusters.

Our tool takes RSS feeds and clusters of already classified documents as imput. It produces a new set of document classes. It contains three main modules all written in Python (around 1,500 lines of code) and with shell scripts:

• a module extracting keywords from a web documents (around 1,000 lines of code) • a module classifying web documents (around 500 lines of code) • a module for the graphical user interface written in Python Tkinter (around 500 lines of code) The application also calls programs from the platform Unitex [START_REF] Paumier | User Manual[END_REF] in order to apply large-scale and fine-grained linguistic resources. There exists a global configuration file defining the values of the different parameters of the application like manually-fixed threshold defined in the previous sections. These values were determined after some tests on different collections of web documents.

B. Web document preprocessing

Web documents cannot be processed as is. They need two preprocessing stages: extraction of relevant text blocks and automatic language identification for later lexical ressources application.

1) Web page cleaning:

The process of extracting relevant text blocks in web documents does not only consists in removing HTML tags, because the main textual information is often surrounded by noise. Indeed, the structure of a web page is nowadays more and more complex. Documents often include navigation menus, hyperlinks to other pages coming with a little summary of their content, advertisement, and so on. More and more tools are devoted to this task as it is shown with the organization of the shared task CLEANEVAL (http://cleaneval.sigwac.org.uk/).

Our module, using the SAX parser to easily read the document, is based on simple assumptions. First, the relevant text is a group of long sentences, to the contrary of navigation menus composed of lists of words or short sentences. Secondly, the relevant text has a minimal size in terms of words. Finally, it is formed of sentences relatively close in terms of tag distance. The more there are tags (line break, scripts, ...) between two groups of sentences, the more the second group becomes irrelevant.

For each group of contiguous sentences, if the group is relevant in terms of size and that it is not too far in terms of tag distance from the last relevant group, then it is selected as relevant. This algorithm is quite simple but we will show in the evaluation section that it works fine.

2) Language detection: Our system uses lexical resources depending on the language of the document. A module of language recognition has been implemented in order to detect it automatically. It is based on an algorithm identifying forbidden factors. Intuitively, for each language, there are some forbidden word factor never or rarely occurring. They can be extracted automatically from representative samples of documents for each language.

C. Web document processing 1) Keyword extraction task:

The keyword extraction module takes a url as imput. The document is added to the existing document list. If it already exists, it is not processed to avoid useless operations. The document is then cleaned and its language is detected by the preprocessing stage described above. The module loads TF.IDF statistics and lexical resources associated with the corresponding language. By using the method given in section II, it outputs the best keywords for each type of keywords (simple nouns, compound nouns and proper nouns). This module also extracts a little summary composed of 5 key-sentences of the text. This summarization task is based on the weight of the keywords. We make the standard assumption that the more a sentence contains important keywords, the more it brings information on the text content. The weight of a sentence is the sum of the weight of its keywords.

For each processed document, the keyword extraction module produces an HTML page containing the keywords and the little summary.

2) Classification task: Given an existing set of document clusters (initially empty), a new document is either added to an appropriate cluster or assigned to a new one, by using the algorithm given in section III. Note that our program also removes out-of-date clusters, i.e. clusters that have not been modified for a certain amount of time. An HTML page containing all clusters is produced. Each cluster is represented by a list of references to its documents (with keywords and summary) and 12 representative keywords taken from the cluster centroid (the 4 best for each type of keywords).

The various thresholds of the program are manually fixed by users in a configuration file. Users can therefore adjust the clustering precision with respect to the topic of the document collection or to the size of the existing clusters. Determining a threshold value requires a little period of testing with a sample collection of documents belonging to the working topic.

After some tests on the program, we decided to make some practical changes to optimize computation cost. First, the merging class step with two-embedded loops has been simplified to one loop because the process tended to merge all documents in one or very few classes. Then, the splitting class process had to divide them again. Most operations were therefore redundant and drastically increased the computing cost. Secondly, in the theoretical algorithm, the gini-index for each term has to be recalculated each time the set of clusters is modified. This operation being costly, we decided to recalculate the gini-index only after 100 new documents are added in the collection. This does not affect the quality of the system because the insertion of a single document very slightly modifies statistics for the gini-index.

V. EVALUATION

Due to the specificity of the task requirements (e.g. creation of very fine-grained clusters), our system can hardly be evaluated automatically on existing collections used for sharedtasks (e.g. TDT). We therefore asked three independent human evaluators to do this task. None of them were involved in any way in the implementation of the tool. The system was only tested on French documents, except for the language detection module (English, French and Spanish).

A. Preprocessing evaluation

As preprocessing stage is not the central point of our paper, the evaluation of this part is very light and limited to few documents. First, the web document cleaning process was applied on 100 documents from different sources (60% from newspaper sites, 20% from blogs, 20% misc.). The evaluators determined that, among the documents,

• 98% have the totality of the relevant text extracted;

• 99% have all their menu items removed;

• 99% have all information on connected documents removed. Although this evaluation is partial, it shows that the cleaning process is effective.

We also evaluated the language detection module by applying it on 300 documents, 100 for each language. The percentage of documents the language of which was correctly detected, reached 99% for French, 94% for English and 92% for Spanish. The incorrect detections come from web documents with no or very short texts, like YouTube ones.

B. Classification evaluation

We made two types of evaluations to measure the quality of our classification process: (1) the quality of the description of the classes (keyword list); (2) the quality of the document class assignement. The evaluation corpus was composed of 173 documents all speaking of the French political party UMP and divided by the system into 88 clusters. For the first evaluation, we asked the evaluators to indicate the quality of the description of each class obtained after inserting all documents. They had to assign each of them to one of the three following categories: not or little understandable (NU), understandable (U), immediate understanding (IU). Results are gathered in table II.

For the second evaluation, the evaluators had to indicate for each document, whether it has been assigned to a correct class by the system. The system reached a score of 85% of documents assigned the correct class. There exist two main types of errors. First, the document was inserted in a class with a low intra-class value but not low enough to be splitted during the class refinement process. Secondly, it was assigned to a singleton class that should has been merged to another one.

The results obtained are good. Nevertheless, it is very difficult to evaluate the system because the number of classes is high (i.e. very fine-grained classes). In practice, the system has been tested and is successfully used in the company XERES.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, we described a real-time unsupervised classification system dealing with dynamic sets of web documents. It is based on a single-pass algorithm assigning a new document either to an existing class or to a new one. It has been shown that the classifications obtained are precise enough to be sucessfully used in the domain of Information intelligence. This tool, nevertheless, requires some improvements, especially time efficiency optimizations. The evaluation also needs larger experiments and has to be compared with other systems.

1

 1 When a document is assigned to an existing class, this may cause two types of side-effects:[START_REF] Charu | On using Partial Supervision for Text Categorization[END_REF] a class can become very Algorithm Merging a cluster c with similar clusters in clusterSet with threshold T repeat for cluster x ∈ clusterSet do if similarity(x,c) > T or c ⊂ x then remove x from clusterSet c = c ∪ x end if end for add c in clusterSet until clusterSets is modified similar to another one and it might be useful to merge them together; (2) a class can become incoherent and it might be useful to split it. Standard clustering algorithms like K-means takes this phenomenon into account: they iteratively refine the initial clustering until a certain stability in the cohesion of the clusters is reached.

  If this value is lower than a manuallyfixed threshold (T ic ), the class have to be divided into several sub-classes that would be added to the global set of classes. Splitting a cluster c in several clusters to be inserted in a set of clusters clusterSet, given two threshold T ic and T sim Require: T sim greater than threshold used in section III-B

	All documents of this class has to be reassigned to various sub-class by using the method described in subsection III-B. At the initialization stage, an empty set of classes newC is created. Then, we assign each document to the most similar class in newC if their similarity is greater than a manually-fixed threshold T if intra(c) < T ic then newC = {} {empty set of clusters} for document d ∈ c do bestc ← findClass(d,newC,T sim ) if bestc is empty then bestc ← {d} else bestc ← bestc ∪ {d} end if end for clusterSet ← clusterSet ∪ newC -{c} end if IV. IMPLEMENTATION

dj ∈c;di =dj cos(d i , d j ) n where d i and d j are documents in class c and n is the number of documents in c. sim . T sim is required to be greater than the one in subsection III-B. If no classes are found for a document, it is added in a new class which is inserted in newC.

The detailed algorithm is given in figure

2

.

Algorithm 2

TABLE II QUALITY

 II OF THE DESCRIPTION OF CLASSES (KEYWORD LIST)

	Quality rate	NU	U	IU
	Score	4.5%	20.5 %	75 %

Note though the experiments in[START_REF] Elmore | Real-Time Document Cluster Analysis for Dynamic Data Sets[END_REF] on the use of agglomerative algorithm for real-time clustering.

This work was partly funded by the company Xeres.


Anthony Sigogne
email: sigogne@univ-mlv.fr

Matthieu Constant
email: mconstan@univ-mlv.fr

Éric Laporte
email: laporte@univ-mlv.fr

French parsing enhanced with a word clustering method based on a syntactic lexicon

.

Introduction

Syntactic lexicons are rich language resources that may contain useful data for parsers like subcategorisation frames, as it provides, for each lexical entry, information about its syntactic behaviors. Many works on probabilistic parsing studied the use of a syntactic lexicon. We can cite Lexical-Functional Grammar [LFG] [START_REF] O'donovan | Large-Scale induction and evaluation of lexical resources from the Penn-II and Penn-III Treebanks[END_REF][START_REF] Schluter | Treebank-Based Acquisition of LFG Parsing Resources for French[END_REF], Head-Driven Phrase Structure Grammar [HPSG] [START_REF] Carroll | The automatic acquisition of verb subcategorisations and their impact on the performance of an HPSG parser[END_REF] and Probabilistic Context-Free Grammars [PCFG] [START_REF] Briscoe | Automatic extraction of subcategorization from corpora[END_REF][START_REF] Deoskar | Re-estimation of lexical parameters for treebank PCFGs[END_REF]. The latter has incorporated valence features of verbs to PCFGs and observe slight improvements on global performances. However, the incorporation of syntactic data on part-of-speech tags increases the effect of data sparseness, especially when the PCFG grammar is extracted from a small treebank 1 . [START_REF] Deoskar | Re-estimation of lexical parameters for treebank PCFGs[END_REF] was forced to reestimate parameters of his grammar with an unsupervised algorithm applied on a large raw corpus. In the case of French, this observation 1 Data sparseness implies the difficulty of estimating probabilities of rare rules extracted from the corpus. can be linked to experiments described in [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du franc ¸ais[END_REF] where POS tags are augmented with some syntactic functions2 . Results have shown a huge decrease on performances. The problem of data sparseness for PCFG is also lexical. The richer the morphology of a language, the sparser the lexicons built from a treebank will be for that language. Nevertheless, the effect of lexical data sparseness can be reduced by word clustering algorithms. Inspired by the clustering method of [START_REF] Koo | Simple semi-supervised dependency parsing[END_REF], [START_REF] Candito | Improving generative statistical parsing with semi-supervised word clustering[END_REF]Candito et al., 2010) have shown that by replacing each word of the corpus by automatically obtained clusters of words, they can improve a PCFG parser on French. They also created two other clustering methods. A first method consists in a step of desinflection that removes some inflexional marks of words which are considered less important for parsing. Another method consists in replacing each word by the combination of its POS tag and lemma. Both methods improve significantly performances. In this article, we propose a clustering method based on data extracted from a syntactic lexicon, the Lexicon-Grammar. This lexicon offers a classification of lexical items into tables, each table being identifiable by its unique identifier. A lexical item is a lemmatized form which can be present in one or more tables depending on its meaning and its syntactic behaviors. The clustering method consists in replacing a verb by the combination of its POS tag and its tables identifiers. The goal of this article is to show that a syntactic lexicon, like the Lexicon-Grammar, which is not originally developed for parsing algorithms, is able to improve performances of a probabilistic parser. In section 2 and 3, we describe the probabilistic parser and the treebank, namely the French Treebank, used in our experiments. In section 4, we describe more precisely previous work on clustering methods. Section 5 introduces the Lexicon-Grammar. We detail information contained in this lexicon that can be used in the parsing process. Then, in section 6, we present methods to integrate this information into parsers and, in section 7, we describe our experiments and discuss the obtained results.

Non-lexicalized PCFG parser

The probabilistic parser, used into our experiments, is the Berkeley Parser3 (called BKY thereafter) [START_REF] Petrov | Learning accurate, compact, and interpretable tree annotation[END_REF]. This parser is based on a PCFG model which is non-lexicalized. The main problem of non-lexicalized context-free grammars is that nonterminal symbols encode too general information which weakly discriminates syntactic ambiguities. The benefit of BKY is to try to solve the problem by generating a grammar containing complex symbols. It follows the principle of latent annotations introduced by [START_REF] Matsuzaki | Probabilistic CFG with latent annotations[END_REF]. It consists in iteratively creating several grammars, which have a tagset increasingly complex. For each iteration, a symbol of the grammar is splitted in several symbols according to the different syntactic behaviors of the symbol that occur into a treebank. Parameters of the latent grammar are estimated with an algorithm based on Expectation-Maximisation (EM). In the case of French, [START_REF] Seddah | Adaptation de parsers statistiques lexicalisés pour le franc ¸ais : Une évaluation complète sur corpus arborés[END_REF] have shown that BKY produces state-of-the-art performances.

French Treebank

For our experiments, we used the French Treebank4 (Abeillé et al., 2003) [FTB]. It is composed of articles from the newspaper Le Monde where each sentence is annotated with a constituent tree. Currently, most of papers about parsing of French use a specific variant of the FTB, namely the FTB-UC described for the first time in [START_REF] Candito | Improving generative statistical parsing with semi-supervised word clustering[END_REF]. It is a partially corrected version of the FTB which contains 12351 sentences and 350931 tokens. This version is smaller5 and has specific characteristics. First, the tagset takes into account the rich original annotation containing morphological and syntactic information. It results in a tagset of 28 part-ofspeech tags. Some compounds with regular syntax schemas are undone into phrases containing simple words. Remaining compounds are merged into a single token, whose components are separated with an underscore.

Previous work on word clustering

Numerous works used clustering methods in order to reduce the size of the corpus lexicon and therefore reducing the impact of lexical data sparseness on treebank grammars. A method, described in [START_REF] Candito | Parsing word clusters[END_REF] and called CatLemma, consists in replacing a word by the combination of its POS tag and its lemma. In the case of a raw text to analyze (notably during evaluations), they used a statistical tagger in order to assign to each word both POS tag and lemma6 . Instead of reducing each word to the lemmatized form, [START_REF] Candito | Improving generative statistical parsing with semi-supervised word clustering[END_REF][START_REF] Candito | Parsing word clusters[END_REF] have done a morphological clustering, called desinflection [DFL], which consists in removing morphological marks that are less important for determining syntactic projections in constituents. The mood of verbs is, for example, very helpful. On the other hand, some marks, like gender or number for nouns or the person of verbs, are not so crucial. Moreover, original ambiguities on words are kept in order to delegate the task of POS tags desambiguation to the parser. This algorithm is done with the help of a morpho-syntactic lexicon. The last clustering method, called Clust, consists in replacing each word by a cluster id. Cluster ids are automatically obtained thanks to an unsupervi-sed statistical algorithm [START_REF] Brown | Class-based n-gram models of natural language[END_REF] applied on a large raw corpus. They are computed by taking account of co-occurrence information of words. The main advantage of this method is the possibility of combining it to DFL or CatLemma. First, the raw corpus is preprocessed with one of these two methods and then, clusters are computed on this modified corpus. Currently, this method permits to obtain the best results on the FTB-UC.

Lexicon-Grammar

The Lexicon-Grammar [LG] is the richest source of syntactic and lexical information for French 7 that focuses not only on verbs but also on verbal nouns, adjectives, adverbs and frozen (or fixed) sentences. Its development started in the 70's by Maurice Gross and his team [START_REF] Gross | Constructing Lexicon-grammars[END_REF]. It is a syntactic lexicon represented in the form of tables. Each table encodes lexical items of a particular category sharing several syntactic properties (e.g. subcategorization information). A lexical item is a lemmatized form which can be present in one or more tables depending on its meaning and its syntactic properties. Each table row corresponds to a lexical item and a column corresponds to a property (e.g. syntactic constructions, argument distribution, and so on). A cell encodes whether a lexical item accepts a given property. Figure 1 shows a sample of verb table 12. In this table, we can see that the verb chérir (to cherish) accepts a human subject (pointed out by a + in the property N0 = : Nhum) but this verb cannot be intransitive (pointed out by ain the property N0 V). Recently, these tables have been made consistent and explicit (Tolone, 2011) in order to be exploitable for NLP. They also have been transformed in a XML-structured format [START_REF] Constant | A generic tool to generate a lexicon for nlp from lexicon-grammar tables[END_REF] 8 . Each lexical entry is associated with its table identifier, its possible arguments and its syntactic constructions. For the verbs, we manually constructed a hierarchy of the tables on several levels. Each level contains classes which group LG tables which may not share all their defining properties but have a relatively similar syntactic behavior. Figure 2 shows a sample of 7 We can also cite lexicons like LVF [START_REF] Dubois | Les verbes franc ¸ais[END_REF], Dicovalence [START_REF] Eynde | La valence : l'approche pronominale et son application au lexique verbal[END_REF] and Lefff [START_REF] Sagot | The Lefff, a freely available, accurate and large-coverage lexicon for French[END_REF] ristics of each level are given in the Table 1 (level 0 represents the set of tables of the LG). We can state that there are 5,923 distinct verbal forms for 13,862 resulting entries in tables of verbs9 . The column #classes specifies the number of distinct classes. The columns AVG 1 and AVG 2 respectively indicate the average number of entries per class and the average number of classes per distinct verbal form. The hierarchy of tables has the advantage of reducing the number of classes associated with each verb of the tables. We will see that this ambiguity reduction is crucial in our experiments.

Word clustering based on the Lexicon-Grammar

The LG contains a lot of useful information that could be used into the parsing process. But such information is not easily manipulable. We will focus on table identifiers of the verb entries which are important hints about their syntactic behaviors. For example, the table 31R indicates that all verbs belonging to this table are intransitive. Therefore, we followed the principle of the clustering method Cat-Lemma, except that here, we replace each verb of a text by the combination of its POS tag and its table ids associated with this verb in the LG tables 10 . We will call this experiment TableClust thereafter. For instance, the verb chérir (to cherish) belongs to the table 12. Therefore, the induced word is #tag 12, where #tag is the POS tag associated with the verb. For an ambiguous verb like sanctionner (to punish), belonging to two tables 6 and 12, the induced word is #tag 6 12. Then, we have done variants of the previous experiment by taking the hierarchy of verb tables into account. This hierarchy is used to obtain clusters of verbs increasingly coarse as the hierarchy level increases, and at the same time, the size of the corpus lexicon is also increasingly reduced. Identifiers combined to the tag depend on the verb and the specific level in the hierarchy. For example, the verb sanctionner, belonging to tables 6 and 12, is replaced by #tag QTD2 at level 1. In the case of ambiguous verbs, for a given level in the hierarchy, identifiers are all classes the verb belongs to. This experiment will be called LexClust thereafter. As for clustering method CatLemma, we need a Part-Of-Speech tagger in order to assign a tag and a lemma to each verb of a text (table ids can be determined from the lemma). We made the choice to use MElt [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-theart pos tagging with less human effort[END_REF] which is one of the best taggers for French. Lemmatization process is done with a French dictionary, the Dela [START_REF] Courtois | Dictionnaires électroniques du franc ¸ais. Présentation[END_REF], and some heuristics in the case of ambiguities.

10 Verbs that are not in the LG remain unchanged.

Experiments and results

Evaluation metrics

As the FTB-UC is a small corpus, we used a cross-validation procedure for evaluations. This method consists in splitting the corpus into p equal parts, then we compute training on p-1 parts and evaluations on the remaining part. We can iterate this process p times. This allows us to calculate an average score for a sample as large as the initial corpus. In our case, we set the parameter p to 10. Results on evaluation parts are reported using the standard protocol called PARSEVAL [START_REF] Black | A procedure for quantitatively comparing the syntactic coverage of english grammars[END_REF] for all sentences. The labeled F-Measure [F1] takes into account the bracketing and labeling of nodes. We also use the unlabeled and labeled attachement scores [UAS, LAS] which evaluate the quality of unlabeled and labeled dependencies between words of the sentence11 . Punctuation tokens are ignored in all metrics.

Berkeley parser settings

We used a modified version of BKY enhanced for tagging unknown and rare French words [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du franc ¸ais[END_REF] 12 . We can notice that BKY uses two sets of sentences at training, a learning set and a validation set for optimizing the grammar parameters. As in (Candito et al., 2010), we used 2% of each training part as a validation set and the remaining 98% as a learning set. The number of split and merge cycles was set to 5.

Clustering methods

We have evaluated the impact of clustering methods TableClust and LexClust on the FTB-UC. For both methods, verbal forms of each training part are replaced by the corresponding cluster and, in order to do it on the evaluation part, we use Melt and some heuristics. So as to compare our results with previous work on word clustering, we have reported results of two clustering methods described in section 4, DFL and DFL+Clust (Clust is applied on a text that contains desinf lected words).

Evaluations

The experimental results are shown in the We observed a gap of almost 0.5% for both tagging and F1. For instance, on the first evaluation part, Melt has high but not perfect scores, with a precision of 98.2% and a recall of 97.2%, for a total of 165 errors 14 . About lemmatization, we have a perfect score of 100%.

13 All experiments have a tagging accuracy of about 97%. 14 We can compute precision and recall scores because sometimes Melt wrongly identifies a word as a verb or miss a verb.

Our approach is based on the combination of tags and table ids contained in the syntactic lexicon. In order to validate this approach, we have done two other experiments. A first one, called Tag, consists in replacing each verbal lemma by its verbal tag only. The second one, called TagLemma, consists in the combination of the tag and the lemma. Results are reported in the Table 2. As for TableClust and Lex-Clust, we replace only verbal forms that are present in the LG tables. We can see that Tag has equal performances to TableClust. Therefore, original table ids combined with tags are useless. Maybe, the number of clusters is too high and consequently, the size of the corpus lexicon is still too large. However, Lex-Clust is better than Tag. About TagLemma, results are almost identical to the baseline. According to these observations, we can say that verbal clusters created with our method LexClust are relevant and useful for a parser like BKY. We have indicated in Table 3, the top most F1 absolute gains according to phrase labels, for our best clustering method LexClust with level 2 of the hierarchy. For each phrase, the column called Gain indicates the average F1 absolute gain in comparison to the baseline F1 for this phrase, and prop. is the proportion of the phrase in the whole corpus. We can see that three of the five best corrected phrases relate to verbal phrases (plus one if we consider that AdP is linked to a verbal phrase). Therefore, the integration of syntactic data into a clustering algorithm of verbs improves the recognition of verbal phrases.

Conclusion and future work

In this article, we have shown that by using information on verbs from a syntactic lexicon, like the Lexicon-Grammar, we are able to improve performances of a statistical parser based on a PCFG grammar. In the near future, we plan to reproduce experiments with other grammatical categories.

  FIG. 2: Sample of the hierarchy of verb tables.

  ).

	8 These	resources	are	freely	available	at
	http ://infolingu.univ-mlv.fr/

FIG. 1: Sample of verb table 12.

  Table213 . The column #lexicon represents the size of the FTB-UC lexicon according to word clustering methods. In the case of the method LexClust, we varied the level of the verbs hierarchy used. The TableClust slightly improves performances compared with the baseline. Nevertheless, using levels of the hierarchy of verb tables through Lex-Clust increases results while considerably reducing the size of the corpus lexicon. We obtain the best results with the level 2 of the hierarchy. These performances are almost identical to those of DFL, despite the fact that we only modify verbal forms while DFL alters all inflected forms regardless of grammatical categories. However, DFL+Clust has high scores and is significantly better than LexClust. As of this writing, we tried some combination of methods LexClust and Clust but we observed that both methods are not easily mergeable. The impact of TableClust and LexClust on a new text is strongly influenced by the quality of the tagging produced by Melt. For evaluating this impact, we computed Gold experiments for both clustering method. Each verb of evaluation parts, present in the LG tables, is replaced by correct tag and table ids.

	Method	#lexicon F1	UAS	LAS	F1<40
	Baseline	27,143	83.82 89.43 85.85 86.12
	DFL	20,127	84.57 89.91 86.36 86.80
	DFL+Clust 1,987	85.22 90.26 86.70 87.39
	TableClust	24,743	84.11 89.67 86.10 86.53
	LexClust 1 22,318	84.33 89.77 86.22 86.62
	LexClust 2 21,833	84.44 89.87 86.32 86.76
	LexClust 3 20,556	84.26 89.64 86.10 86.57
	Tag	20478	84.11 89.58 86.00 86.40
	TagLemma 24722	83.87 89.51 85.91 86.26
	TAB. 2: Results from cross-validation evaluation accor-
	ding to clustering methods.

method

There were 28 original POS tags and each can be combined with one of the 8 syntactic functions.

The Berkeley Parser is freely available at http ://code.google.com/p/berkeleyparser/

The French Treebank is freely available under licence at http ://www.llf.cnrs.fr/Gens/Abeille/French-Treebank-fr.php

The original FTB contains 20,648 sentences and 580,945 tokens.

They used the tagger MORFETTE[START_REF] Chrupala | Learning morphology with Morfette[END_REF][START_REF] Seddah | Lemmatization and statistical lexicalized parsing of morphologically-rich languages[END_REF] which is based on two statistical models, one for tagging and the other for lemmatization. Both models were trained thanks to the Average Sequence Perceptron algorithm.

Note that 3,121 verb forms (3,195 entries) are unambiguous. This means that all their entries occur in a single table.

These scores are computed by automatically converting constituent trees into dependency trees. The conversion procedure is made with the Bonsaï software, available at http ://alpage.inria.fr/statgram/frdep/fr stat dep parsing.

html. 12 Available in the Bonsaï package.