Stéphanie Dib
email: stephania.dib@gmail.com

François Rodier
email: francois.rodier@univ-amu.fr

Error-Correction Capability of Reed-Muller codes

We present an asymptotic limit between correctable and uncorrectable errors on the Reed-Muller codes of any order. This limit is theoretical and does not depend of any decoding algorithm.

Introduction

Let F 2 be the field with 2 elements, and let RM = RM(n, r) be the Reed-Muller code of length 2 n and of order r that is the set of Boolean function with n variables of algebraic degree not more than r.

Building a code is important, but we must think about how many words we can decode. Usually, we content ourselves of the fact that errors of weights less than half of the minimum distance can be corrected in a unique manner. So decoding an error correcting code beyond half of the minimum distance has been a challenge for the one who study error correcting codes. In fact experiments show that a maximum likelihood decoding can decode many more words.

Here we propose a theoretical bound for decoding almost all errors of Reed-Muller code on any order by this method of decoding. Indeed, the decoder will often be able to recover the correct codeword using an algorithm that generates for each received word the closest codeword even if the received word is more distant than half of the minimum distance. On the contrary, when the number of errors exceeds a certain value, the received vector will be rarely closer to the correct codeword than to any other one. Here we give a proof for that.

It is interesting to compare that fact with the phenomenon of concentration of the nonlinearity of Boolean functions which have been studied by several authors ( [START_REF] Dib | Distribution of boolean functions according to the secondorder nonlinearity[END_REF][START_REF] Dib | Distribution de la non-linéarité des fonctions Booléennes[END_REF][START_REF] Litsyn | On the distribution of Boolean function nonlinearity[END_REF][START_REF] Rodier | Sur la non-linéarité des fonctions booléennes[END_REF][START_REF] Rodier | Asymptotic nonlinearity of Boolean functions[END_REF][START_REF] Schmidt | Nonlinearity measures of random Boolean functions[END_REF]. The r-nonlinearity of a Boolean function f denoted NL r (f ) is its Hamming distance to the set of Boolean functions with n variables of algebraic degree not more than r. Claude Carlet [START_REF] Carlet | The complexity of boolean functions from cryptographic viewpoint[END_REF], proved that the density of the set of Boolean functions satisfying

NL r (f ) > 2 n-1 -c 2 n-1 n r log 2
tends to 1 when n tends to infinity, if c > 1. The authors of the present paper proved a concentration of the nonlinearities of almost all Boolean functions around

2 n-1 -2 n-1 n r log 2 (1)
when r ≤ 2 but missed the greater values by lack of knowledge of weight distributions ( [START_REF] Dib | Distribution of boolean functions according to the secondorder nonlinearity[END_REF][START_REF] Dib | Distribution de la non-linéarité des fonctions Booléennes[END_REF][START_REF] Rodier | Sur la non-linéarité des fonctions booléennes[END_REF][START_REF] Rodier | Asymptotic nonlinearity of Boolean functions[END_REF]. Kai-Uwe Schmidt generalized this result for all r thanks to a result of Kaufman, Lovett, and Porat [START_REF] Kaufman | Weight distribution and list-decoding size of Reed-Muller codes[END_REF] helping him to find a better bound for the weights of a RM code [START_REF] Schmidt | Nonlinearity measures of random Boolean functions[END_REF].

On the other hand, Helleseth, Klove and Levenshtein in the paper Error correction capability of binary linear codes [START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF] study order 1 or 2 Reed-Muller codes and they show that almost all the words are decodable up to the same bound as [START_REF] Bollobas | Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability[END_REF] and almost all words are not decodable beyond this bound. For that, they use the monotone structure of correctable and uncorrectable errors. Stéphanie Dib [START_REF] Dib | Distribution de la non-linéarité des fonctions Booléennes[END_REF]Chapter 3] proved by the same method as for the concentration of the nonlinearities of almost all Boolean functions that the bound for correcting most of the values of codewords for 1-order RM codes was given by [START_REF] Bollobas | Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability[END_REF].

We show here that the value given in (1) is also the bound for correcting most of the values of codewords for RM codes for any order. For RM codes, the present work improves the paper by Helleseth et al. [START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF] where they just prove the fact that the codes RM(n, r) are asymptotically optimal for r = 1 (cf. note after inequality (54) of [START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF]) or r = 2 (example 7 of [START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF]).

Presentation

Let d(e, f ) be the Hamming distance between the elements e and f in F 2 n 2 . We denote by wt(e) the weight of an element e in F 2 n 2 . Let C be a linear code of length m, of dimension k. The Reed-Muller code of length 2 n and of order r has dimension r 0 n r and minimum distance 2 n-r .

Correctable and uncorrectable errors

Let F 2 n 2 be the set of all binary vectors of length 2 n . For any vector f ∈ F 2 n 2 , the set

f + C = {f + g | g ∈ C}
is called a coset of C and contains 2 k vectors. One can easily check that two cosets are either disjoint or coincide. This means

f ∈ h + C =⇒ f + C = h + C.
Therefore, the set F 2 n 2 can be partitioned into 2 2 n -k cosets of C:

F 2 n 2 = 2 2 n -k -1 i=0 (f i + C) , f i ∈ F 2 n 2 where (f i + C) ∩ (f j + C) = ∅ for i = j.
If you send a word g and the decoder receive the word h, we will call e = gh the error. Thus, the possible error vectors are the vectors in the coset containing h. In maximum-likelihood decoding, the decoder's strategy is, given h, to choose a minimum weight vector e in h + C, and to decode h as he.

The minimum weight vector in a coset is called the coset leader, and when there is more than one vector of minimum weight in a coset, any one of them can be selected as the coset leader. We denote the set of all coset leaders by E 0 (C) (note that #E 0 (C) = 2 2 n -k ).

The elements of E 0 (C) are called correctable errors, and the elements of

E 1 (C) = F n 2 -E 0 (C) are called uncorrectable errors.
Only coset leaders are correctable errors, which means that 2 2 n -k errors can be corrected with this decoding. A codeword is an unambiguous correctable error if it is a coset leader, and it is the only vector of minimum weight in this coset.

Proposition 1 .

The following statements are equivalent.

1-A codeword e is an unambiguous correctable error;

2-∀e ′ ∈ e + C if e = e ′ then wt(e) < wt(e ′ );

3-∀g ∈ C -{0}, wt(e) < wt(g + e); 4-∀g ∈ C -{0}, d(e, 0) < d(g, e).

Proof

The first assertion implies the second because if e ′ ∈ e + C and e = e ′ then e ′ is not the coset leader, so wt(e) < wt(e ′ ). The second assertion implies the first because if e ′ ∈ e + C and e = e ′ then wt(e) < wt(e ′ ) so e ′ is not the coset leader and e is the only vector of minimum weight in this coset. The other statement are clear.

The probability

We take F 2 n 2 as the probability space. We endow it with the uniform probability P .

The results

Let

λ n = c × 2 n/2 2 n r log 2 and δ = 2 n-1 -λ n /2
where c is a positive real.

We will show that if c > 1 then almost all error of weight smaller than δ are correctable, when n tends to infinity. And that if c < 1 then almost all error of weight higher than δ are uncorrectable, when n tends to infinity. More precisely we will show the following two theorems. when n → ∞.

Proof of the Theorem 1. Decoding a large number of errors

We intend to prove that almost all error of weight smaller than δ for c > 1 are correctable, when n tends to infinity. It is enough to prove P wt(e)≤δ d(e, 0) < d(e, g) for all g ∈ RM(r) -0 → 1 when n → ∞.

We have just to show P wt(e)≤δ δ < d(e, g) for all g ∈ RM(r) -0 → 1 when n → ∞ or P wt(e)≤δ ∃g ∈ RM(r) -0, δ ≥ d(e, g) → 0 when n → ∞ that is

P wt(e)≤δ   g∈RM (r)-0 δ ≥ d(e, g)   → 0 when n → ∞.
It is enough to prove that g∈RM (r)-0

P wt(e)≤δ (δ ≥ d(e, g)) → 0 when n → ∞.
By expressing the conditional probabilities we have to show that g∈RM (r)-0

P d(e, 0) ≤ δ ∩ d(e, g) ≤ δ P d(e, 0) ≤ δ → 0 when n → ∞.
Let B δ (g) be the ball of center g and of radius δ that is the set of e such that d(e, g) ≤ δ. The event B δ (g) is the set of words f in

F 2 n 2 such f ∈ B δ (g), that is d(f, g) ≤ δ.
Hence Theorem 1 is a consequence of the following proposition.

Proposition 2 . If c > 1 then g∈RM (r)-0 P B δ (0) ∩ B δ (g) P (B δ (0)) → 0 when n → ∞
Before the proof of this Proposition we have to evaluate the terms in the sum.

Lemma 1 . For every real s, one has

P B δ (0) ∩ B δ (g) ≤ exp 2s 2 (2 n -wt(g)) -2sλ .
Proof.

Replace δ by its value.

P B δ (0) ∩ B δ (g) = P (wt(f ) ≤ δ) ∩ (wt(f + g) ≤ δ) = P (2 n-1 -wt(f ) ≥ λ/2) ∩ (2 n-1 -wt(f + g) ≥ λ/2)
One knows that

2 n -2wt(f ) = x∈F n 2 (-1) f (x) , 2 n -2wt(f + g) = x∈F n 2 (-1) f (x)+g(x) .
Hence this gives using Markov's inequality:

P B δ (0) ∩ B δ (g) = P     x∈F n 2 (-1) f (x) ≥ λ   ∩   x∈F n 2 (-1) f (x)+g(x) ≥ λ     = P     exp   s x∈F n 2 (-1) f (x)   ≥ exp(sλ)   ∩   exp   s x∈F n 2 (-1) f (x)+g(x)   ≥ exp(sλ)     ≤ E   exp s x∈F n 2 (-1) f (x) exp s x∈F n 2 (-1) f (x)+g(x)   exp(sλ) 2
Since the random values f (x) are independant

P B δ (0) ∩ B δ (g) ≤ E   exp x∈F n 2 s(-1) f (x) 1 + (-1) g(x)   exp(sλ) 2 ≤ x∈F n 2 E exp s(-1) f (x) 1 + (-1) g(x) exp(sλ) 2
Because the random values f (x) takes the values ±1 with probability 1/2, the calculation of the expectation gives

P B δ (0) ∩ B δ (g) ≤ x∈F n 2 cosh s 1 + (-1) g(x) exp(sλ) 2
As cosh(t) ≤ exp(t 2 /2)

P B δ (0) ∩ B δ (g) ≤ x∈F n 2 exp s 2 1 + (-1) g(x) 2 /2 exp(sλ) 2 ≤ exp   s 2 2 n + F n 2 (-1) g(x)   exp(sλ) 2 ≤ exp 2s 2 (2 n -wt(g)) -2sλ .
4.1 Case where the distances are close to 2 n-1 .

We give a bound for P B δ (0) ∩ B δ (g) when the distance to 0 of the center g is rather close to 2 n-1 .

Lemma 2 . If |2 n-1 -d(g, 0)| ≤ 2 n-1 / n r then: P B δ (0) ∩ B δ (g) ≤ 1 2 c 2 2(( n r )-1)
.

Proof.

From lemma 1 we have

P B δ (0) ∩ B δ (g) ≤ exp s 2 2 n + 2 n -2wt(g) exp(sλ) 2 ≤ exp s 2 2 n 1 + 1 n r exp(sλ) 2
We take s = λ/2 n .

P B δ (0) ∩ B δ (g) ≤ exp λ 2 2 -n 1 + 1 n r exp(λ 2 /2 n-1 ) ≤ exp 2c 2 n r log 2 1 + 1 n r exp 4c 2 n r log 2
Simplifying the two members of this fraction by exp 2c 2 n r log 2 you get

P B δ (0) ∩ B δ (g) ≤ exp (2c 2 log 2) exp(2c 2 n r log 2) ≤ 2 2c 2 2 c 2 ×2( n r )
4.2 Case where the distances are away from 2 n-1 .

We use the follwing lemma, which is an application of a result by Kaufman, Lovett, and Porat [START_REF] Kaufman | Weight distribution and list-decoding size of Reed-Muller codes[END_REF].

Lemma 3 . Let α be a strictly positive real number. The number B r,n of functions g in RM(r, n) satisfying

|wt(g) -2 n-1 | ≥ 2 n-1 / n r fulfills B r,n ≤ 2 α( n r ) if n is large enough.
Proof This is shown in the proof of Lemma 3 in K.-U. Schmidt's article [13, relation (6)].

We use this lemma to evaluate Π = P B δ (0) ∩ B δ (g) where the sum is on the nonzero g in RM(n, r) fulfilling

|wt(g) -2 n-1 | ≥ 2 n-1 n r .
Lemma 4 . Let α be a strictly positive real number. Then

Π < 2 α( n r ) 2 -c 2 1-2 -r ( n r )
Proof.

From lemma 1, for all s, we have

P B δ (0) ∩ B δ (g) ≤ exp 2s 2 (2 n -wt(g)) -2sλ Let us take s = λ 2 n+1 -2wt(g)
. We have, expressing the value of λ and noting that wt(g) is not less than the minimum distance 2 n-r of RM(n, r):

P B δ (0) ∩ B δ (g) ≤ exp - λ 2 2 n+1 -2wt(g) ≤ exp   - c 2 × 2 n+1 n r log 2 2 n+1 -2 n-r+1   ≤ 2 - c 2 ×( n r ) 1-2 -r . Therefore Π ≤ B r,n 2 -c 2 1-2 -r ( n r ) ≤ 2 α( n r ) 2 -c 2 1-2 -r ( n r ) .

Evaluation of P (B δ (0))

Proposition 3 . Let r be a fixed integer, δ = 2 n-1c 2 n-1 n r log 2 where c is a positive constant. We have

P (B δ (0)) = 1 2π 2 -c 2 ( n r ) 2c n r log 2 (1 + o(1)) (2)
when n tends to infinity. This is proved in Stéphanie Dib's thesis [START_REF] Dib | Distribution de la non-linéarité des fonctions Booléennes[END_REF]. We recall briefly the proof for completeness.

The following lemma (see [2, lemma 1]) gives well-known asymptotic estimate of the sum of binomial coefficients.

Lemma 5 . Let n be a positive integer and k ≤ n. Then

k i=0 2n i < 2 2n • exp - (n -k) 2 n .
When k is sufficiently close to n, the following lemma (see [6, chapter IX, (9.98)], [START_REF] Feller | An introduction to probability theory and its applications[END_REF]chapter VII]) gives an asymptotic estimation for 2n k :

Lemma 6 . Let n be a positive integer and |n -k| ≤ n 5 8 . Then

2n k = 2 2n √ π • n • exp - (n -k) 2 n • (1 + o(1)) , ( 3
)
where the term o( 1) is independent of the choice of k.

Proof of the Proposition.

The number of Boolean functions whose Hamming distance to 0 is bounded from above by some number δ equals 0≤i≤δ 2 n i . Thus we have 0≤i≤δ

2 n i = 0≤i<2 n-1 -2 (n-1) 5 8 2 n i + 2 n-1 -2 (n-1) 5 8 ≤i≤δ 2 n i .
The first sum on the right hand side is taken care of by lemma 5 which will show that it is negligible with respect of the second sum.

To estimate a lower bound of the second sum (which we denote S), we use

S = 2 2 n √ π 2 n-1 • (1 + o(1)) • 2 n-1 -2 (n-1) 5 8 ≤i≤δ exp - (2 n-1 -i) 2 2 n-1 . (3)
We use that the function in the sum is monotonous to replace the sum by an integral.

S = 2 2 n √ π 2 n-1 • (1 + o(1)) • 2 n-1 -2 (n-1) 5 8 +1≤i≤δ exp - (2 n-1 -i) 2 2 n-1 di. = 2 2 n √ π • (1 + o(1)) • c ( n r ) log 2≤v≤2 n-1 8 -2 1-n 2 exp -v 2 dv.
By [5, chapter VII, Lemma 2] and the fact that

c 2 n r log 2 -2 n-1 8 -2 1-n 2 2 → -∞ which implies that ∞ 2 n-1 8 -2 1-n 2 exp -v 2 dv = o   ∞ c ( n r ) log 2 exp -v 2 dv   the last integral is equivalent to exp -c 2 n r log 2 2c n r log 2 = 2 -c 2 ( n r ) 2c n r log 2 . Thus 0≤i≤δ 2 n i = 2 2 n √ π 2 -c 2 ( n r ) 2c n r log 2 (1 + o(1)).

Proof of Theorem 1

Therefore g∈RM (r)-0

P B δ (0) ∩ B δ (g) P (B δ (0)) ≤ O(n r/2 ) 2 ( n r ) 2 -c 2 2(( n r )-1) 2 c 2 ( n r ) + 2 α( n r ) 2 -c 2 1-2 -r ( n r ) 2 c 2 ( n r ) .
This tends to 0 because the exponent of 2 is, for the left term

n r -c 2 2 n r -1 + c 2 n r = - n r c 2 + 2c 2 → -∞
and for the right term

α n r - c 2 1 -2 -r n r + c 2 n r = n r α - 2 -r c 2 1 -2 -r .
So just take α < 2 -r c 2 1 -2 -r so that this term tends to -∞.

The error correction capability function

Let ǫ C (t) the ratio of the number of correctables errors of weight t to the number of words of weight t. Let us suppose from now on that the lexicographically smallest minimum-weight vectors are chosen as the coset leaders. This involves only the cosets with several minimum weight vectors that is the ambiguous correctable errors. Then an important property of this ratio is that for any t in the range from half the minimum distance to the covering radius, ǫ C (t) decreases with the growing t as the next lemma says.

A corollary of Theorem 1

For Reed-Muller codes of order r, that is to say RM(n, r) we take

t = 2 n-1 -c 2 n-1 n r ln 2. Corollary 1 . If c > 1, then ǫ C (t c ) → 1 when n → ∞.
Proof.

We know that the ratio of the unambiguous correctable errors (hence also the correctable errors) of weight smaller than t c to the words of weight smaller than t c tends to 1 when n tends to infinity. We have to show that the ratio of the correctable errors of weight exactly t c to the words of weight exactly t c tends to 1 when n tends to infinity. For an RM(n, r) code, let

2 2 n √ π 2 -c 2 ( n r ) 2c n r log 2 = A(c).
Let us fix c 1 and suppose that ǫ C (t c 1 ) → 1. Then there exists η < 1 such that ǫ C (t c 1 ) < η for an infinity of n. If c 1 > c 2 > 1, then among the words of weights between t c 1 and t c 2 there is only at most a proportion η of correctable words as the function ǫ C decreases. From Proposition 3 there are about 0≤i≤δ 1

2 n i = A(c 1 )(1 + o(1)).
words of weight in [0, t c 1 ] and

δ 1 ≤i≤δ 2 2 n i = A(c 2 )(1 + o(1)).
words of weight between t c 1 et t c 2 . As A(c 1 ) = o(A(c 2 )) there are at most

A(c 1 )(1 + o(1)) + ηA(c 2 )(1 + o(1)) = ηA(c 2 )(1 + o(1))
correctable words of weights [0, t c 1 ], which shows that it is impossible that almost all words are correctable as says Theorem 1.

Proof of the Theorem 2. An asymptotic decoding upper bound

In the case of RM codes we have a simplification of the proof of the Theorem 3 b in [START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF].

Proposition 4 . If c < 1, then ǫ C (t c ) → 0 when n → ∞.
For every t, one has (cf. Lemma 3 of [START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF])

ǫ C (t) × t i=0 2 n i ≤ t i=0 ǫ C (i) 2 n i = number of correctable errors of weight smaller than t ≤ total number of correctable errors ≤ 2 2 n -k .
We have, from Proposition 3 tc i=0

2 n i = #B tc = 2 2 n -c 2 ( n r ) 2c π n r ln 2 (1 + o(1)). Whence ǫ C (t c ) ≤ 2 2 n -k tc i=0 2 n i = 2c π n r ln 2 2 2 n -c 2 ( n r ) × 2 r i=0 ( n i )-2 n (1 + o(1)) = 2c π n r ln 2 2 r i=0 ( n i ) -c 2 ( n r ) (1 + o(1)).
If c < 1, when n → ∞ then the denominator tends toward infinity, so ǫ C (t c ) → 0.

Remark.

This proposition is still true if we take

t c = 2 n-1 -c √ 2 n-1 k ln 2 with c < 1 if k ≤ 2 (n-1)/4
(to be able to use Proposition 3).

End of the proof of Theorem 2.

Remark that the statement of Theorem 2 does not involves ambiguously correctable errors. So we have the choice of ambiguous correctable errors, and we can choose the lexicographically smallest minimum-weight vectors as the coset leaders as in the beginning of the section 5. Then one has from the last proposition P wt(e)≥δ e is correctable ≤ ǫ(δ) → 0 when n tends to infinity. Therefore P wt(e)≥δ e is unambiguously correctable → 0 which means that Theorem 2 is true. As c 1 and c 2 may be as close to 1 as we wish, we have

Asymptotically optimality of RM codes

2 n -2t C 2 n (ǫ) √ 2 n k log 4 → 1 when n → ∞.

Theorem 1 .

 1 Let c > 1. Then P wt(e)≤δ d(e, 0) < d(e, g) for all g ∈ RM(r) -0 → 1 when n → ∞. and Theorem 2 . Let c < 1. Then P wt(e)≥δ there exists g ∈ RM(r) -0 such that d(e, 0) ≥ d(e, g) → 1

Lemma 7 .

 7 For any [n, k] code C and any t = 0, 1, . . . , n -1ǫ C (t + 1) ≤ ǫ C (t)with strict inequality for t C ≤ t ≤ r C where we set t C = ⌊(d C -1)/2⌋ and denote the covering radius of C by r C .ProofSee Helleseth et al.[START_REF] Helleseth | Levenshtein: Error correction capability of binary linear codes[END_REF] Lemma 2]. This property is due to the fact that the sets of correctable and uncorrectable errors form a monotone structure, (see, for example,[START_REF] Peterson | Error-Correcting Codes[END_REF] p. 58, Theorem 3.11]) and a result of Bollobas about shadows[START_REF] Bollobas | Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability[END_REF] Theorem 3]

An k log 4 or c 1 < 2 n

 412 sequence (C m ) m of [m, k] codes where k = o(m) as m → ∞ is called asymptotically optimal if for any fixed ǫ, 0 < ǫ < 1 m -2t Cm (ǫ) ∼ √ mk ln 4where the error correction capability function t C (ǫ) is the maximum t such that ǫ C (t) ≥ ǫ.Theorem 3 . The sequence RM(n, r) n is asymptotically optimal.Proof.Let us take ǫ and try to findt C (ǫ). Let c < 1. If 2t c = 2 nc √ 2 n klog 4 then the words of weight t c are almost all uncorrectable, therefore ǫ C 2 n (t c ) → 0 as n → ∞. And we have ǫ C 2 n (t c ) < ǫ for n big enough (and consequently t c ≥ t C 2 n (ǫ)). As a result t C 2 n (ǫ) ≤ 2 n-1c √ 2 n-1 k log 4. Let now c > 1. If 2t c = 2 n -c √ 2 n k log 4 then the words of weight t c are almost all correctable, therefore ǫ C 2 n (t c ) → 1 as n → ∞. And we have ǫ C 2 n (t c ) > ǫ for n big enough (and consequently t c < t C 2 n(ǫ)). As a result, if c 1 < 1 < c 2 , one has 2 nc 2 2 n k log 4 < 2t C 2 n (ǫ) < 2 nc 1 2 n k log 4 or c 1 2 n k log 4 < 2 n -2t C 2 n (ǫ) < c 2 2 -2t C 2 n (ǫ) √ 2 n k log 4 < c 2 .


Marie-Claude Simeone-Senelle

Arabic on the Dahlak islands (Eritrea)

 but none of them has been dedicated particularly to Arabic spoken on the islands. By revising data published previously and by updating them with the new ones collected since, this talk attempts mainly to assess the specific features of Dahalik Arabic compared with the Arabic lingua franca spoken on the African coast of the Red Sea.

. Unique but not recent.

They reflect a time-limited situation before 2007.

Corpus

Based on spontaneous texts, recorded with men and some women and young people who are essentially DHLK and/or Afar native speakers.Very few Arabic native speakers, all are bi-or multilingual. One cannot assess possible differences between native and not native Arabic speakers.

The archipelago and its population

The Dahlak archipelago in Eritrea is lying off the port of Massawa (cf. Maps) Only four islands are permanently inhabited 1) the greatest one, Dahlak Kebir (=D.K.),in the centre of the archipelago.2) Nora [nºra], to the north of D.K., 3) Dehil [deHil], to the north-west and close to the continent. In 2006 the permanent population added up to almost 3.000 islanders, with about 2000 on D.K., 380 on Nora and 600 on Dehil 4) Deseʔ (exclusively Afar).

Sociolinguistic situation

Three languages (Afar, Dahalik, Arabic) are in contact on DK and Nora, and only two on Dehil (Arabic and DHLK). There are distributed as follows:

1) Dahalik. DHLK (Ethio-semitic language ) is the predominant language with 1.680 native speakers on 3.000 islanders. Mother tongue of 56,5% islanders (60% on DK, Nora 60%, Dehil 42% )

2) 'Afar (Cushitic language) is the mother tongue of about 780 islanders (26% of the population: 38% on D.K. and less than 5% on Nora, no Afar on Dehil)

3) Arabic is minority with 521 islanders claiming to have Arabic as mother tongue (17,5%).Their number can be estimated to about 2% on DK, to 35% on Nora and to 58 % on Dehil where they represent a majority. Except some very old women, any adult speaks at least two languages: her/his mother tongue plus a second language, and many people have a passive knowledge of a third or even of a fourth.

The situation varies according to the island and the distribution of the inhabitants speaking different languages within the same village

The school on the three islands being in Arabic, all educated children all know Arabic, in its standard form.

In most villages, the linguistic communities interact on a daily basis. This situation is furthered by the short distances between the villages and the common school gathering children from all communities.

Due to mixed marriages and shared daily life with children from other linguistic communities, many children actually have two first languages. One of the two is always Dahalik.

For the women the situation is different. They are in close contact with their neighbours in their village, but they are not used to travel outside the island. Some Tigre women speak Tigre with their young children but all of them speak Afar or Dahalik, (or Arabic), depending to their husband's mother tongue and the neighbourhood.

For men the situation is more complex. In addition to Dahalik, Arabic, and Afar, they know Tigre and Tigrinya, sometimes Saho, few English words. On Deḥil m any of them know Tigre and are able to speak it fluently.

The oldest know and speak Amharic and have some notions of Italian.

On Dehil there are no Afar, the Arabic native speakers and the Dahalik native speakers live in two distinct but neighbouring districts (see the map : Dahar and ʕAd).

The trade exchanges and the professional and personal relations with the eastern bank of the Red sea, an exclusively Arabic speaking area, are favouring the expansion of Arabic.

Arab presence on the Archipelago

Links between the African and Arabian coasts are attested since Antiquity and are doubtless much older. Many parameters lead to think that Arabic was spoken in the region before the Islamisation. Presently, some islanders who claim to be Arabs because one of their male ancestor came from an Arab country, are presently Dahalik native speakers (ex. 1). On Nora they claim to be there for three or four generations, sometimes more on D.K.

On D.K: Migration from different Arab countries: Egypt, Sudan, but mainly from Yemen (the Tihami coast, Aden area, sometimes Hadramawt), and Saudi Arabia (Farsan island).

On Dehil, in the 19th century the ʕAwāzim (Rashayda) came from Saudi Arabia (about 348 on Deḥil). Cf. the map ʕíla ʕawāzim

Arabic in the state of Eritrea

Only nearly 1% of the citizens have an Arabic language as mother tongue (AbrahaWende, p.c. 2000)

Status of Arabic

Arabic (MSA variety): official status in the state of Eritrea. It is one of the three 'working languages', together with Tigrinya and English. It is taught in school as a second language in the country, and as the medium of instruction and as a subject in primary schools on the northern coast, including the archipelago (see below).

Arabic is also the language of the religion in this area where all people are Muslims.

Religion and social and cultural usefulness confer prestige to Arabic, and usually the parents prefer their children attend the Arabic school (even in the areas where it is not spoken). It is one of the reasons why speakers claim to be Arabs.

Arabic varieties on the islands

1) Modern Standard Arabic: the Eritrean educational policy has been implemented in 1997 before Dahalik has been listed. On the Archipelago the policy has been aligned with that applied to the coast where Arabic is predominant, thus Arabic is the only language of school education.

2) Other Arabic dialects -From Arab countries (Yemen, Sudan, Saudi Arabia, Egypt, Emirates).

• TV programs (movies, varieties broadcast, television quiz shows, news, series of cartoons)

• Relatives in Yemen and Saudi Arabia

• Fishing and trade with Arabic monolingual areas.

-Arabic Lingua franca: During sea navigation in the Red sea and Indian Ocean (essentially Gulf of Aden).

ALF on the African coast gives evidence of contacts with

Arabic dialects, Cushitic languages (Afar and Saho), two Ethio-Semitic languages (Tigre and Tigrinya).

The range of contacts influencing the DHLK Arabic is limited to three languages (Arabic, Afar, Dahālik), one of them is endemic to the islands. I'll discuss the possible impact of Dahalik on Arabic spoken on the islands, using examples different from ALF and collected only with the islanders.

PHONOLOGY AND PHONETICS

1) on Dehil the voiceless emphatic ṭ is clearly pharyngealized under the influence of DHLK spoken on this island.

2) Velar and uvular consonants often overlap but not exactly in the same way as in AFL They waged war and slaughter people

Agreement

The agreement system is more fluctuant than that of AFL. The latter is marked by the contact with the complex concordance system of Afar where the verb usually agrees neither in number (whatever the number of its noun subjects, the verb is in the singular) 3

VOCABULARY

. As for DHLK, the agreement with collective (and occasionally with plural) is very irregular and often unpredictable with respect to feminine or masculine, 3rd person plural or singular. The concordance system in DHLK Arabic appears to be the result of merging both systems.

The counted noun is invariable in both languages.

CONCLUSION

Generally speaking the influence of DHLK on Arabic spoken on the islands is not as significant as it could be expected. DHLK is confined to the domestic life on the islands.

Having no official status, it is depreciated even by many native speakers (some adults and all the young people). The influence of Arabic (AFL) on DHLK is increasing, in return DHLK influences ALF less and less. Both varieties tend to merge into one ALF. In DHLK Arabic few features spotted as being from DHLK language, are indeed just remnants tending to disappear, levelled by the increasing influence of ALF and the very endangerment of DHLK.

As far as Afar, it has neither more nor less impact on this DHLK Arabic variety than on ALF of the coast of the Red Sea. The process of merging both varieties of Arabic into one ALF is irrevocably running.

ABBREVIATIONS Languages:

AFL Arabic Lingua Franca referring only to the varieties spoken along the Red sea coast of the Eritrean mainland -DHLK Dahlik (ADJ.) / Dahālik language -DHLK-Arabic including both varieties (mother-tongue and lingua franca on the islands)

Glosses

CON connector-IPFV imperfective-N noun -PI personal index -PFV perfective -PR pronoun -PTCL participle -SUF suffix, suffixed -V verb

C1C2C2e/iC3 -In nominal and verbal sentences Word order: the

  predicative copula in nominal sentence, the verb in the verb sentence: at the end of the sentence. This phenomenon may be enhanced by the contact of DHLK (same word order as Afar: SOV).

	• In the PFV, the 1st and 2nd SG have a regular final -a. This phenomenon is more
	widespread in DHLK Arabic than in ALF.
	6	samaʕta 'I heard, I understand' ; kúnta 'I was / you (SG) were'
	Similarly to DHLK 2	, there is gemination shift
	7 14	ba-ʔaxaberrik 'I'll inform you' and xabbarato 'he informed him' hēdi baladna naħna hiya
		DEM.	PR.PERS.1PL	country.SUF.PR.1PL (PERS.PR.3F.SG)COP
	This one, for us, is country The system of TAM auxiliaries is more reduced than in ALF: except kān aspectual and 15 kān insān yaʕni maʕa ħimar ħaqqo yemši
	temporal marker, DHLK-Arabic does not use auxiliaries. AUX.3M.SG human indeed donkey CON.SUF.PR.3M.SG 3M.SG.IPFV.walk
	• Auxiliary after the verb In fact one human-being was walking with his donkey ba=(particle) clitic to the verb in the IPFV form has a concomitant or prospective
	value 16	ḥarb isáwwū		wu-igeṭṭəʕū	kānū	en-nās
	8	daḥḥin lámma nrūḥ war 3PL.IPFV.do	ba=tšūfu and-3PL.IPFV.slaughter	AUX.PL	ART-people
		now Realizations of etymological consonants in ALF and DHLK Arabic when 1PL.IPFV.go CONC=2PL.see Now when we go there, you will see
	emphatic • participle of some verbs (motion, cognition) has the same value as ba=IPFVVerb: interdentals dento-alveolar palato-alveolars velars. uvulars
	MSA *ṭ ALF (ṭ) t (ṣ),s (ḍ) d, z (θ) *ṣ *ḍ, ð̣ *θ *ð t, s (ð) d, z z, d *z 9 gallaha ana 3M.SG.say.to.SUF.PR.3F.SG PR.PERS.1SG PTCL.SG.go *š *ž (š) s, ss, s̃ j, y, g ɣ, q, *ɣ g rāyaḥ mṣáwaʕ *x *q k (q) g, ɣ, Massawa ʁ,χ, k, ʔ DHLK ṭ, (tt) ṣ, s d, z θ, t, s ð, d, z, z, d š, s, s̃ j, y, g (ɣ) q (x) k q, He told her 'I am going to Massawa' ɣ,(χ), k, g, 10 ʕārif muš (ʔ) PTCP.SG.know INT?
	At the phonetic level, the assimilation of the lateral fricative to the voiced bilabial occlusiveis You know, don't you?
	attested only in the corpus in DHLK Arabic: • baga 'to stay'~ 'and then'. (enunciative particle)
	3 11	bl > bb kébbi 'before me' bága héði		yaʕīdi	jāb	áḥmed saɣīr
		and_then	DEM.PROX		Ya ʕīdi	3M.SG.PFV.give	Ahmed	small
	MORPHO-SYNTAX And then this Ya'idi gave birth to Ahmed Junior
	Verb Conjugation 12 ...bága-l-láḥam	yitṭálləʕu-ho
	and_then-ART-flesh • In the IPFV conjugation, use of the same form for both singular and plural first-person (no 3.PL.IPFV.remove-SUF.PR.3M.SG '... and then the flesh, they removed it.
	number mark). This phenomenon is less rare than suggested in Simeone-Senelle (2000: 166,
	2005: 271). Cf. ex (2) SYNTAX
	4 -In the noun phrase tigrinya	má-naʕref		má-darastö	má-ʕaref
	Tigrinya Genitive construction	NEG-1.IPFV know NEG-learn.PFV.1SG.SUF.PR NEG-1.IPFV know
		I don't know Tigrinya, I didn't learn it, I don't know wálad ḥággi < child/ CON-SUF.PR.1SG> 'my son'.
	But also Another construction attested on the archipelago is not so common in Arabic :
	5 13	əmši ménni awlād< from.SUF.PR.1SG/ children' 'my sons' əmši marbūṭ
		1SG.IPFV.walk	1SG.IPFV.walk hindred.M.SG
		I walk, I walk hindered

2 In DHLK the opposition PFV ~IPFV is marked by gemination of radical C2 : PFV C1aC2aC3a and IPFV PI-

ʕáfar tugūl <3F.SG.IPFV.say>'Afar people

17 náḥna yegūlu kúllanā min hīne 'we say all of us are from here' (verb in the 3PL.) 18 nāskúll -o all people .kúll-oh ṣáyyādin 'all of them are fisherman' 19 say ..', el-

ʕáfar kúlla-ha

  'all the Afar' (Afar is always F.SG in Afar and DHLK)

	23 27		fi-hōri taɣribān kébbi kaman tišti	kam	miya-wu-xamsīn kilo ... ʕam yekkee
			EXIST-hori about	also before.SUF.PR.1SG how 2F.IPFV.want	100-and-50 year	kilo 3M.SG.PFV.happen.INT (Afar)
			There are also hori 4 , you can load 150 kilos, Did that event happen how many years ago approximately before my birth?
	24	•	fi-waħad towards DHLK	kebīr tišta	miyét	kilo
	28		EXIST-one ʔármi		big ʕ́af eš	3F.SG.IPFV.want 100 bilāhu	kilo
			throw.IMP.SG luggage there is a big one, it can load 100 kilos 3M.SG.PFV.say.SUF.PR.3M.SG He told him: 'Throw luggage!'
	(-ata 'to come' in ALF is not attested in my corpus where aga, aja, is usual) 29 ḥurmáti wal... wadaʕat
			wife.SUF.PR.1SG ga...	give_birth.PFV.3F.SG.
	-rāʔe always in the PFV 'see'(as in Tihama), besides šāf in the PFV and IPFV 'see and My wife ha...has given birth.
	look' 30	ballu</bilāhu/ for gallu'he told him'
	25		rēt-u-hum				lámma rēt-u-hum	šāfu-l-juráḥ
	PFV.1SG.see-EP.SUF.PR.3PL when HYPERCORRECTIONS AND REDUNDANCY	cf. first clause	PFV.3PL.see-ART.wound
	I met them, when I met them, they looked at the wound Phonetic variants of the same term within the same sentence :
	-'water' mō (attested only in the corpus from DHLK), mōya 31 keθīr, kesīr, ketīr, ṣaɣīr, ṣaqīr; gárya, qárya;
	-'now' délḥin, déḥḥin tumun qirāṭ núṣṣ-uɣirāṭ , gerāṭ ' one eightof carat, half carat, carat'
	Words of the same meaning -'inside' ben el-fərūm'inside the four' 32 kaman bárdo
	Besides fishery vocabulary many lexemes are etymologically borrowings from Arabic -different words for the same referent
	dialects of the Red sea area (Egypt, Sudan, Saudi Arabia, Yemen) and from other foreign 33 bābur, safīna, markab,
	languages.
	bónsola (<bussola) 'compass'), lamba 'bulb'; fānus 'lighthouse ; lamp'; ítrik(<electric)
	20		tnīn makān 'two places'.
	CODESWITCHING
	21	el-ḥarīm yarqaṣ and in the same text el-ḥarīm yerquṣu 'The women dance' • towards Afar
	26		áh			wáḥad	ʕáfari
			DEICT.ASS (afar)	one	Afar
	əšti (in the IPFV) 'want' This one is Afar
	22		eš tíšti 'What do you want?'
	or in a broader meaning including possibility and eventuality:

'flashlight', dūš 'satellite dish', fībər 'boat made of fibreglass', tan 'ton'; ṭ/tárabeza '(coffee) table'; kínīn 'any pills'; básta 'pasta', bāni 'white bread'; kōkiyan (<conchiglia ? 'seashell') '(Trochus niloticus). Mother-of-pearl, any seashell that produces mother-of-pearl'; šámaṭri 'cinnamon' (< 'from Sumatra').

4

Hori is a small wooden rowing boat for coastal fishing. Its size varies (but there are never more than 4 men on board). The smallest ones (one man on board) can be loaded on a bigger boat (sambuq), the sambuq anchors in open sea and unloads them. The men fish there and every evening or every two days they bring back their fishery produces to the anchored sambuq.

M-Cl. SIMEONE-SENELLE. Arabic on the Dahlak islands (Eritrea) -ArCo 2014 -Naples

Asmara and, partially, by the French Center

The linguistic situation in M.R.'s family (in 2006) M.R. 55 years old -fisherman, trader. born in Melīl (Dahlak Kebir). He has lived in Melīl for 24 years In Melīl : ʕAfar, DHLK & Arabs in contact. He attended Arabic school near Melīl, in Dasqo (exclusively DHLK)

M.R.'s parents

In 2006 his father and mother were living in Jimhile, M.R and his family were living in Dubʕullu.

• The mother (ʕAfar, born in Melīl) speaks : ʕAfar and Arabic with their 9 chidren (her father was of Egyptian origin) Arab and DHLK with her neighbours (women)

The father is born in Jimhile, DHLK mother tongue, speaks Arabic and some ʕAfar He speaks DHLK with M.R.

M.R. his wife was ʕAfar. 10 chidren (7 sons, 3 daughters )

He considers ʕAfar and DHLK as his mother-tongues, and he speaks Arabic very fluently. He knows Tigrinya, Tigre, Amharic (prisoner during DERG). Has notions of Italian, some words in English He spoke ʕAfar with his wife ʕAfar with his daughters (they do not attend school). In 2004, he has realized that her daughters spoke very well DHLK and knew the oral literature.

Arabic with his sons. They speak ʕAfar with their mother. All of them on the island speak DHLK


Marie-Claude Simeone-Senelle

Gender, Number and Agreement in Afar (Cushitic language)

INTRODUCTION

Afar is a Lowland East Cushitic language spoken by more than 1.700.000 people, in Djibouti (ca 310.000), Eritrea (ca 305.000 ) and Ethiopia (ca 1.100.000)

We have collected our data on the field 1 In many languages of the world, agreement is a matter of syntax and of covariance. Reusing Steele's definition of agreement (1978: 610), quoted by Corbett (2006:4) " [...] there is systematic covariance between a semantic or formal property of one element and a formal property of another". In Afar sentence, there is covariance between the subject (personal , with different speakers in Djibouti, in Eritrea and in Ethiopia. Only a few examples were elicited.

SOME PRELIMINARY LINGUISTIC REMARKS

Afar is typically a SOV language, with postpositions.

The canonic order in the noun phrase is determiner/qualifier + determined/qualified In the verb phrase V+ auxiliary; and in the sentence: dependent clause before Matrix clause It is a partially inflected language (only some masculine marked nouns with non-stressed vowel final are concerned). Three cases are marked by apophony of the vowel final (-í) and switching of the stress on the final : : Absolutive vs Nominative / Genitive. There are two genders M., F. and two numbers SG., PL.

The gender is marked on the SG. and PL. nouns. The PL. is marked on the nouns and pronouns. There is a gender opposition for the 3rd SG of the personal pronouns There are three types of verb conjugations: the number is always marked, the gender is marked only in two types of verbs and exclusively for the 3rd SG.

INTRODUCTION 1 The surveys have been carried out with the financial support of LLACAN-INALCO, CEFAS (Sanaa) and ILD (Djibouti). We thank all the Afar native speakers in Djibouti, Eritrea and Ethiopia who have collaborated to this research. We are also indebted to Maki Houmed Gaba for his help to transcribe some texts, in Paris.

pronoun / noun (phrase)), and the verb 2 . Following Givon (1970[START_REF] Hassan Kamil | Resolution rules in Qafar[END_REF]), and Corbett (2006: 4) we can consider that the subject pronoun/noun (phrase) is the controller 3 , and the verb the target 4

• CI: PI+ ASPECTUAL MARK + STEM + (NI)

.

Only the plural personal pronouns and a few nouns referring to sex-differentiated animates require the plural agreement. For the other nouns, covariance usually concerns the gender, characterized by inverse gender between SG and PL, as in many Cushitic and Omotic languages.

Referring to Corbett (2006: 4), it can be said that the 'agreement features' are gender, and eventually number. The predominant situation is that of syntactic agreement, but we shall see that the role of semantics is not insignificant even though it is underlying .

GENDER AND NUMBER MARKS

VERB

In Afar there are three types of conjugations. Whatever the type all the verbs have the number indices suffixed to their stem. There are 3 persons (3 for SG and 3 for PL) with gender opposition (M. vs F). marked for the 3 rd SG only. Types 1 and 2 differ by the position of their personal indices: prefixed for type 1 and suffixed for type 2.

(1) j-a-maːté t-a-maːté j-a-maːté-(e)n(i)

3M-IPFV-come(SG) 3F/2-IPFV-come(SG) 3-IPFV-come-PL(LF)
He comes She comes/You come They come (F/M) Gender is an inherent property of the noun and is always marked morpho-phonologically.

For animates, gender is correlated to sex and is lexical for inanimates.

The feminine noun is marked by a stressed vowel final. This latter may be any vowel He gives honey to a man

NUMBER

Referring to Parker and Hayward (1985: 227) "There are three categories of number in Afar: singular, plural and singulative". It however seems more adequate to consider that there are two numbers organized into two systems. The main system is SG versus PL. Whereby the PL form is derived from SG by the modification of the SG stem: 1) by internal derivation corresponding to the so-called broken plural in Semitic languages, 2) by suffixation of a morpheme (the so-called external plural).

The secondary system is Collective vs Singulative, where SING is derived from COLL by suffix. The general Plural vs SG-PL may be joined to this sub-system,. This system is rare.

Cf. Corbett (2000: 126).

While plural and singulative are marked, singular and collective are not marked as such in the nouns. SG and COLL are lexical. PL. is derived from singular and SING. from COLL.

NUMBER AND GENDER

All forms whatever their number are marked in gender. One of the most remarkable features in some Cushitic languages like 'Afar and Somali (Dubnov, 2003: 27-9) is that the majority of the animate or inanimate nouns, masculine in the singular are feminine in the plural and vice versa. As for the singulative, it may have a different gender from that of the collective if the SING. noun is correlated to sexual animate it can be marked as M. or F.

The inverse gender between singular and plural is a phenomenon common to many Cushitic In some dialects spoken in Djibouti, agábu 'women' is a COLL. without SING. In this dialect, the COLL. is semantically a suppletive plural for barrá (F. SG) 'woman'. Elsewhere ag(a)boytá is SING. of agábu (barrá is not used).

(15) The noun referring to people, tribes, usually marked as M. have no SING.

sinám 'people', mára 'people', ʕafár 'Afar people',

In this category of nouns, some are marked as F. and have SING. with differentiated gender.

Among them are loanwords borrowed from Arabic. When the subject is an independent personal pronoun referring to sexual animate, the agreement of the verb with its controller is complete: it agrees in person, in gender (in the 3 rd SG), and in number (SG vs PL).

When the subject is an explicit personal pronoun, the verb agrees in person, gender, and number with its subject. The only exception in our data concerns a category of boats, borrowed from Arabic. The agreement in gender does not correspond to the morpho-phonological mark. The noun is marked as masculine but the verb is in the 3F.SG.

Here F. is a default gender in the agreement with inanimate controller marked as M. ( 23) doːník ħayyú má geɖ-ɖ-á dhow Obock NEG go-3F-IPFV.SG The dhow doesn't go to Obock (MHK)

In the plural there is not reverse gender, the agreement is F.: dowaː́nik geɖɖa.

In the same semantic field, two other nouns borrowed from Arabic, do not follow the same agreement rules.

(24) huːrí / hawaːrí 'small boat, dinghi', noun is F. in SG. and PL. The agreement is in F. markáb / maraːkíb 'ferry (Dj.)' M. in SG and PL. with the agreement in M.

2.2 When the subject is a collective, it is always marked as M. The rules of agreement depend on the semantic value of the COLL, and on the degree of semantic definiteness.

For a very restricted list

There is alternative in the agreement : the verb agrees with the marked gender of the collective or with the semantic meaning of the COLL.

( People died but the people who have been cured did not die.

When the collective refers to an indefinite set, the word has a low degree of definiteness.

This semantic property explains the syntax of these words thus they cannot be marked as definite by a demonstrative or a restrictive relative clause. Extraction of some elements from the mass is impossible, consequently on the morphological level, these collectives have no derived singulatives.

The collective mára can be determined by a demonstrative á mara 'this people' á marí rabé /rabén (cf. ex. 26 & 27) 'these people died', or by a restrictive relative clause (cf. ex. 32).

The word can be considered semantically as an equivalent of a suppletive plural for num 'man/ human being'.

With sinam/sinaːma none of these constructions is possible Both nouns have different syntactic functioning linked to their different semantic values.

They are not semantically equivalent, contrary to some assertions (example Morin 2012 'sinam= mara'),

The feminine agreement for the marked masculine collective nouns, referring to a mass in which particular elements are not distinguishable, cannot be considered as an agreement in gender, but as an agreement by default. Moreover in Cushitic languages 'Feminine is associated with multiple reference' (Mous 2012).

F. is at the same time a default gender for few inanimate nouns (cf. ex. 23 doːník) and a default number for the COLL referring to animates.

CONJOINED NOUNS

When there are two or more subjects joined by a connective (postclitic =j or the morpheme kee 'and'), the agreement depends the grammatical category of subjects:

1) the subjects of the predicate are personal pronouns in the absolutive case. We and our cars we 'll close the road

3) The subjects are nouns SG, PL, COLL. or SING. marked in gender.

With proper nouns

The verb is at the 3 rd F.SG (36) málko keː ʕábdo gillaːbi-uwwa bej-t-a-ːh Malko and 'Abdo. fishing.GEN-goods take-3F-IPFV-CON Malko and 'Abdo take the fishing equipment and gilláːbi-h geɖ-ɖ-a fishing-to go-3F-IPFV.SG they go to fish (MHK 2004: 137) With nouns referring to animates (37) labhá-ːj agábu-ːj úrru keː idoːlá men-CON women-CON children and old_people

The men, the women, the children and the old people 7 The speaker is a bus driver on strike.

ħaɖá gúba-l tan tree underneath-in 3F.IPFV.be are under the tree. (MHK 2004: 47) Cf. ( 38 (MHK 2004: 128) It is to be noticed that the grammatical subjects, noun or pronoun, are not in nominative case (agábu not agbí, úrru and not urrí)

In these examples, feminine agreement is to be considered as a default agreement (cf. also Corbett 2000: 205). cf. above ex. ***, and it seems to be norm Nevertheless, as for few exceptions with collectives, when controllers refer to animates, there may be syllepsis, and a semantic agreement with the verb in PL. We have some examples only when the subjects refer to humans or animals. For Corbett (2000: 205) 'With noun phrases headed by non-human animates there is a degree of uncertainty about the acceptability of plural agreement' He gives the following example with a question mark before the verb in PL.

wákrii-kee yangúla kudde/ ? kuden jackal.SG.MASC-and / hyena.DG.MASC / ran.away.SG.FEM / ran.away.PL The jackal and the hyena ran away (Corbett 2000: 205 (50)) For our informants in the north-west of the Afar area in Ethiopia both occurrences are valid: kudde (3F.SG) or kuden (3PL) Hayward and [START_REF] Hassan Kamil | Resolution rules in Qafar[END_REF] give some examples with semantic agreement in other contexts: with inanimates and animates, with animates in the nominative case ... No example of this type is attested in our data. The mismatch of the agreement rules may be due to the fact that (Hayward & Corbett 1988: 276) Concerning the collectives marked as M., never not marked in number. The gender agreement depends on semantics of the COLL and its degree of definiteness: the agreement of the verb is not systematically linked to the marked gender of the noun.

A few loanwords marked as masculine have a feminine agreement.

1 COLL.M + V.3M.SG Or (for few words in limited list) COLL.M + V.3PL

2 COLL.M + V.3F.SG COLL type 1 and 2 are not equivalent on the semantic level.

The Collective set can be subdivided into two: those which require a syntactic agreement, gender agreement (verb in M/F. SG), with three exceptions (ex. ( 27), ( 28)) where there is alternative between syntactic and semantic agreement, and the second sub-set requiring a default agreement, the verb is then in F.SG)

With conjoined subjects, usually the feminine singular default agreement is applied, but if the subjects refer to sex-differentiated animates there may be syllepsis and semantic agreement. The verb is then in PL.. If one of the subject is marked as nominative then the agreement is obligatory semantic. Resolution rules applied for conjoined subject nouns are analyzed in detail by [START_REF] Hassan Kamil | Resolution rules in Qafar[END_REF]. It issues from this study that the variability of agreement rules and the alternative between a semantic agreement and an agreement by default concerns more controllers than one could expect.

Considering that Feminine mark refers to a notion of plurality, the agreement in F.SG. with some COLL and with conjoined nouns can be considered as semantic agreement, and not as a syntactic one. Indeed three M. COLL and conjoined nouns referring to sexual animates have an alternative agreement with the target in PL, it is an overtly semantic agreement, overruling the syntactic agreement.

Agreement in F.SG. with some COLL and with conjoined nouns makes obvious that the semantics of the word can play a more important role than the marked gender. There is semantic agreement (notion of plurality to whom F. refers) and not syntactic agreement in this case. With three M. COLL and with conjoined nouns referring to sexual animates the agreement is overtly semantic because /since agreement in number is an alternative to the

( 16 )

 16 ħabʃá 'Ethiopian people' > ħabʃíːta (M.) and ħabʃíːtá (F.) 'Ethiopian man' and 'Ethiopian woman' soːmaːlí 'Somalian people' > soːmaːlíːta (M.SG), soːmaːliːtá (F.SG) faransaːwí 'French people' > faransaːwiːta (M.SG), faransaːwiːtá (F.SG) AGREEMENT CONTROLLER-TARGET The agreement of the verb with its subject depends on the noun category in which the subject belongs. It can be complete or partial. 1. Complete agreement (gender and number).

  had one single Afar speaker as informant and some occurrences have been obviously elicited. CONCLUSION Considering the Gender-polarity in Afar, the agreement rules for the plural marked nouns can be summarized as follows: SG.M + V.3M.SG vs PL.F. + V.3F.SG SG.F + V.3F.SG vs PL.M + V.3M.SG The exceptions concern the nouns which have the same marked gender in SG and in PL, consequently not submitted to reverse gender.

F

  ABBREVIATIONS CI conjugation of type I -CII conjugation of type II -CIII conjugation of type III -COLL collective -CON connective -EF extended form -F. feminine -M. masculine -PI personal index -NI number index -PL. plural -PLUR plurative -S subject -SG singular -SING singulative

  Both nouns together with agábu are exceptions in this system. They may have an agreement in plural but allow for alternatives between syntactic and semantic agreement. There are some examples where the speaker uses syllepsis and the verb is in the plural. It can be said : . refers to a more undifferentiated set from which no unity or group can be extracted.The verb agrees in F. Concerned eare the nouns referring to people, tribes, nationalities, and cattle. We are not aware of any exception from this rule.

	(27) urrí / marí		abalán	/ rabén
		children.S / people.S.	play.IPFV.3PL	/die.PFV.3PL
		Children/People play / died
	(28) agabí	jemeːté	/ jemeːtén
		women.S	come.IPFV.3M /come.PFV.3PL
		Women come
	Only these three three nouns are concerned by this phenomenon (cf. Hayward and Mous
	2012).
	2.2.2 COLL. without SING.
	(29) wadár	t-a-loːlé
		sheep, goats 3F-IPFV-graze.SG
		Sheep/goats graze
	(30) ʕafár Afar people	t-e-meːté 3F-PFV-come.SG
		Afar people came
	(31)	sinám people die.3F.PFV.SG rabté
		People died
	(32) sinám rabté people die.3F.PFV.SG but ímmay dajlisén cure.PFV.3PL people.S NEG-die.PFV.NEG.3SG marí má-rabinna
	)	urrí		abalá
		children.S (boys and girls)	play.IPFV.3SG
		The children play
	(26)	marí	rabé
		people.S die.PFV.3M.SG
		People died

COLL

With vocalic extension, there is always a final epenthetic vowel. In some nouns, the mid-vowel is lenghtened.

There is neither gender nor aspectual opposition in the conjugation of this type of verb


Marek Kurdej

Julien Moras

Véronique Cherfaoui

Philippe Bonnifait

Map-aided Evidential Grids for Driving Scene Understanding †

Keywords: dynamic fusion, geo-referenced maps, mobile perception, prior knowledge, evidential occupancy grid, autonomous vehicle

Evidential grids have recently shown interesting properties for mobile object perception since the Dempster-Shafer framework allow them to handle efficiently partial information which is a frequent situation when driving in complex urban areas. This article deals with a lidar perception scheme that is enhanced by geo-referenced maps used as an additional source of information in a multi-grid fusion framework. The paper presents the key stages of such a data fusion process. An adaptation of the conjunctive combination rule is presented to refine the analysis of the conflicting information. The method relies on temporal accumulation to make the distinction between stationary and moving objects, and applies contextual discounting for modelling information obsolescence. As a result, the method is able to better characterise the state of the occupied cells by differentiating moving objects, parked cars, urban infrastructure and buildings. Another output of this approach is the capability to separate the navigable space from the non-navigable one. Experiments carried out on real traffic conditions with an equipped car illustrate the performance of such an approach.

I. INTRODUCTION

Autonomous driving has been an important challenge in recent years. Navigation and precise localisation aside, perception of nearby environment is an important characteristic of a self-drivable vehicle. The level of difficulty in autonomous driving increases in urban environments, where a good scene understanding makes the perception crucial. On the one hand, there are several reasons that make cities a demanding environment. Poor satellite visibility deteriorates the precision of GPS positioning. Objects' trajectories are hard to predict due to high variation in speed and direction. Also, the sheer number of mobile objects poses computational problems, e.g. for tracking algorithms.

On the other hand, more and more detailed and precise geographic databases become available. This source of information has not been well examined yet, hence our approach of incorporating prior knowledge from digital maps in order to improve perception scheme. A substantial amount of research has focused on the mapping problem for autonomous vehicles, e.g. Simultaneous Localisation and Mapping (SLAM) approach [START_REF] Thrun | Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)[END_REF], but the use of maps for perception is still understudied.

In this article, we propose a new perception scheme for intelligent vehicle navigation. The information fusion method is based on Dempster-Shafer theory of evidence [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The principal innovation of the method is the use of meta-knowledge obtained from a digital map. The map is considered as an additional source of information on a par with other sources, e.g. sensors. We study the advantage of including prior knowledge into an embedded perception system of an autonomous car. To model the vehicle environment, our approach uses multiple 2D occupancy grids [START_REF] Elfes | Using Occupancy Grids for Mobile Robot Perception and Navigation[END_REF], or precisely their evidential version adaptation [START_REF] Pagac | An evidential approach to map-building for autonomous vehicles[END_REF].

Digital maps have been used as prior knowledge for already a few years [START_REF] Oh | Map-based Priors for Localization[END_REF]. The use of navigable road maps for localisation [START_REF] Fouque | Enhancement of Global Vehicle Localization using Navigable Road Maps and Dead-Reckoning[END_REF], [START_REF] Moosmann | Interlacing Self-Localization, Moving Object Tracking and Mapping for 3D Range Sensors[END_REF], perception [START_REF] Moras | Drivable Space Characterization Using Automotive Lidar and Georeferenced Map Information[END_REF], navigation and driving [START_REF] Wei | Towards a Viable Autonomous Driving Research Platform[END_REF] was proved to be of high value. Not only highly accurate and precised specialised maps, but also those which are open-sourced have been successfully employed, e.g., Open-StreetMap [START_REF] Irie | Road Recognition from a Single Image using Prior Information[END_REF], [12]. A considerable amount of research works have contributed to the map updating problem [START_REF] Xiao | Change detection of trees in urban areas using multi-temporal airborne lidar point clouds[END_REF].

Our method aims to capture complex and dynamic vehicle environments, so that they can be used as world representations for safe navigation. In particular, it is important to make the vehicle able to distinguish static objects attached to infrastructure (e.g. road sign) from mobile road users (e.g. cars, cyclist, pedestrian). In this last category (called "movable" in the following), the perception mechanism can be enhanced in order to make the difference between stopped and moving objects. Indeed, if a movable object has been detected on the side of the carriageway, it can be a pedestrian and the vehicle may reduce its speed in anticipation of a possible collision. Another objective of the proposed scheme is to characterize the free space nearby the vehicle by using exteroceptive sensors and refine this information by highlighting, thanks to a map of the area, the navigable space on which the vehicle can plan a safe path.

This paper describes a unified approach to a variety of problems in spatial representation using the Dempster-Shafer theory of evidence. The theory of evidence was not combined with occupancy grids until recently to build environment maps for robot perception [START_REF] Pagac | An evidential approach to map-building for autonomous vehicles[END_REF]. Only recent works take advantage of the theory of evidence in the context of mobile perception [START_REF] Moras | Credibilist Occupancy Grids for Vehicle Perception in Dynamic Environments[END_REF]. There is also some research on efficient probabilistic and 3-dimensional occupancy grids [START_REF] Wurm | OctoMap: A Probabilistic, Flexible, and Compact 3D Map Representation for Robotic Systems[END_REF]. Some authors have also used a laser range scanner as an exteroceptive source of information [START_REF] Moras | Credibilist Occupancy Grids for Vehicle Perception in Dynamic Environments[END_REF]. Some works use 3D city model as a source of prior knowledge for localisation and vision-based perception [START_REF] Dawood | Vehicle geo-localization based on IMM-UKF data fusion using a GPS receiver, a video camera and a 3D city model[END_REF], whereas our method uses maps for scene understanding. Geodata are also successfully used for mobile navigation [START_REF] Hentschel | Autonomous Robot Navigation Based on OpenStreetMap Geodata[END_REF]. This article is organised as follows. Section II gives necessary theoretical background of the Dempster-Shafer theory of evidence. In section III, we describe the details of the proposed method, starting with the description of needed data and the purpose of each grid. Further, details on the information fusion are given. Data-dependent computation which are not in the heart of the method are described in section IV-A. Sections IV-B and IV-C present the results obtained with real-world data. Finally, section V concludes the paper and presents ideas for future work.

II. DEMPSTER-SHAFER THEORY OF EVIDENCE

The Dempster-Shafer Theory (DST) is a mathematical theory specially adapted to model the uncertainty and the lack of information introduced by Dempster and further developed by Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. DST generalises the theory of probability, the theory of possibilities and the theory of fuzzy sets. In the Dempster-Shafer Theory (DST), a set Ω = ω 1 , . . . , ω n of mutually exclusive propositions is called the frame of discernment (FOD). In case of closed-world hypothesis, the FOD presents also an exhaustive set. Main difference in comparison to the theory of probability is the fact that the mass of evidence is attributed not only to single hypotheses (singletons), but to any subset of the FOD, including an empty set.

As stated in the previous paragraph, beliefs about some piece of evidence are modelled by the attribution of mass to the corresponding set. This attribution of mass, called a basic belief assignment (bba), or a mass function, is defined as a mapping:

m(•) : 2 Ω → [0, 1] (1)
A⊆Ω

m(A) = 1 (2)
m(∅) = 0 (3)
In order to combine various information sources in the DST, there are several rules of combination. Combined mass functions have to be defined on the same FOD Ω or transform to a common frame using refining functions. A refining is defined as a one-to-many mapping from

Ω 1 to Ω 2 . r : 2 Ω1 → 2 Ω2 \ ∅ (4) r(ω) = ∅ ∀ω ∈ Ω 1 (5) ω∈Ω1 r(ω) = Ω 2 (6) r(A) = ω∈A r(ω) (7)
The frame of discernment Ω 2 is then called the refinement of Ω 1 , and Ω 1 is the coarsening of the Ω 2 .

When combined pieces of evidence expressed by bbas are independent and both are reliable, then the conjunctive rule and Dempster's combination rule are commonly used.

In the following, let us suppose that m 1 , m 2 are bbas defined on some finite frame of discernment Ω. Then, the conjunctive rule of combination denoted by ∩ is defined as follows:

∅ a b Ω = {a,
(m 1 ∩ m 2 )(A) = A=B∩C m 1 (B) • m 2 (C) (8)
The combination using the conjunctive rule can generate the mass on the empty set m(∅). This mass can be interpreted as the conflict measure between the combined sources. Therefore, a normalised version of conjunctive rule, called Dempster's rule and noted ⊕ was defined:

K = (m 1 ∩ m 2 )(∅) (9)
(m 1 ⊕ m 2 )(A) = (m 1 ∩ m 2 )(A) 1 -K (10)
(m 1 ⊕ m 2 )(∅) = 0 (11)
In the DST, a discounting operation is used in order to, e.g. model information ageing. Discounting in its basic form requires to set a discounting factor α and is defined as:

α m(A) = (1 -α) • m(A) ∀A Ω (12) α m(Ω) = (1 -α) • m(Ω) + α (13)
Decision making in DST creates sometimes a necessity of transforming a mass function into a probability function [START_REF] Smets | Decision Making in the TBM: the Necessity of the Pignistic Transformation[END_REF]. Smets and Kennes proposed so called pignistic transformation in [START_REF]What is Dempster-Shafer's model?[END_REF]. Pignistic probability betP has been defined as:

betP(B) = A∈Ω m(A) • |B ∩ A| |A| ( 14
)
where |A| is the cardinality of the set A. Table I presents an example of different combination rules, pignistic transform and discounting operation. The Dempster-Shafer theory will serve as in further sections as the main modelling and information fusion tool in the perception system.

III. MULTI-GRID FUSION APPROACH

This section presents the proposed perception scheme). We use three evidential occupancy grids to model prior information, sensor acquisition and perception result. The grid construction method is described in section III-B. We detail all data processing steps in section III-D. Figure 1 presents a general functional overview of our approach. Following sections correspond to different blocks of this diagram.

A. Heterogeneous data sources

There are three sources in our perception system: vehicle pose, exteroceptive acquisition data and vector maps. Figure 1 illustrates all system inputs. The proposed approach is based on the hypothesis that all these information sources are available. Other hypotheses on the input data are done. Firstly, a globally referenced vehicle pose is needed to situate the system in the environment. The pose provided by a proprioceptive sensor has to be reliable and as precise as possible. It is assumed that the pose reflects closely the real state of the vehicle. Secondly, an exteroceptive sensor supplies a partial view of the environment. This sensor ought to be able to at least distinguish free and occupied space, and model it in 2D x, y or 3D x, y, z coordinates. The coordinates can be globally referenced or relative to the vehicle. A typical exteroceptive sensor capable of satisfying this assumption is a Lidar (laser range scanner), radar, or a stereo camera system. Lastly, our method tries to exploit at large the information contained in vector maps, so we assume that the maps are sufficiently rich and contain valuable accurate data. Typically, map data should contain information on the location of buildings and the model of road surface.

B. Occupancy grids

An occupancy grid models the world using a tessellated representation of spatial information. In general, it is a multidimensional spatial lattice with cells storing some stochastic information. In our case, each cell representing a box (a part of environment) X × Y where X = [x -, x + ], Y = [y -, y + ] stores a mass function.

1) SensorGrid (SG): In order to process the exteroceptive sensor data, an evidential occupancy grid is computed when a new acquisition arrives, this grid is called SensorGrid. Each cell of this grid stores a mass function on the FOD Ω SG = {F, O}, where: F free space, O occupied space.

The basic belief assignment reflects the sensor model.

2) PerceptionGrid (PG):

To store the results of information fusion, an occupancy grid PG has been introduced with a FOD Ω P G = {N, W, I, U, S, M }. The choice of such a FOD is directly coupled with the objectives that we try to achieve. Respective classes represent: N free navigable space, W free non-navigable space, I mapped infrastructure (buildings), U unmapped infrastructure, S temporarily stopped objects, M mobile moving objects. Ω P G is a common frame used for scene understanding. By using PG as a cumulative information storage, we are not obliged to store preceding SensorGrids.

3) GISGrid (GG): This grid allows the system to perform a contextual information fusion incorporating the metaknowledge about the environment. GISGrid uses frame of discernment Ω GG = {B, R, T }. This FOD represents: B buildings, R roads, T intermediate space (e.g. pavements). The grid can be obtained, for instance, by projection of map data, buildings and roads, onto a 2D grid with global coordinates (see Figure 5 for an example). However, the exact method of creating GG depends on available GIS information. Section IV-A.2 presents how GG is constructed.

Figure 2 demonstrates how the above grids fit together in the general scheme. It names the input sources involved at each step and shows necessary grid transformations.

C. Combining prior knowledge

In our method, prior information contained in maps serves to ameliorate the perception scheme. We have chosen to combine the prior knowledge with the sensor data of SensorGrid. However, the Dempster-Shafer Theory does not allow to combine sources with different frames of discernment. The frame of discernment Ω SG is distinct from Ω GG used in GISGrid. Hence, one needs to find a common frame for both sources. In order to enable the fusion of SensorGrid (SG) and GISGrid (GG), we define refining r SG to transform SensorGrid:

r SG : 2 Ω SG → 2 Ω P G (15) r SG ({F }) = {N, W } (16) r SG ({O}) = {I, U, S, M } (17) r SG (A) = θ∈A r SG (θ) (18)
and refining r GG to transform GISGrid:

r GG : 2 Ω GG → 2 Ω P G (19) r GG ({B}) = {I} (20) r GG ({R}) = {N, W, S, M } (21) r GG ({T }) = {N, W, S, M, U } (22) r GG (A) = θ∈A r GG (θ) (23)
Above defined refinings allows us to combine prior knowledge included in GISGrid with instantaneous grid obtained from sensor(s). The refined mass function can be expressed as:

m Ω P G SG (r SG (A)) = m Ω SG SG (A) ∀A ⊆ Ω SG (24)
m

Ω P G GG (r GG (A)) = m Ω GG GG (A) ∀A ⊆ Ω GG (25)
Then, Dempster's rule described in section II is applied to each cell in order to exploit the prior information included in GG:

m Ω P G SG, t = m Ω P G SG, t ⊕ m Ω P G GG ( 26
)
We have chosen to use the Dempster's rule of combination, since the GIS data and the sensor data are independent. Besides, we suppose that both sources are reliable, even if errors are possible. In the end of this stage, we obtain a grid being a combination of the sensor data, SensorGrid, with the prior knowledge from GISGrid.

D. Temporal fusion

The role of the fusion operation is to combine current sensor acquisition with preceding perception result. The sensor acquisition input is already combined with prior information as described in preceding paragraphs. We propose to exploit dynamic characteristics of the scene by analysing produced conflict masses. As the preceding perception result PerceptionGrid is partially out-of-date at the moment of fusion, the contextual discounting operation is employed to model this phenomena [START_REF] Kurdej | Conservative, Proportional and Optimistic Contextual Discounting in the Belief Functions Theory[END_REF]. Moreover, an accumulator of occupancy is introduced and a mass function specialisation is performed to distinguish mobile, but temporarily stopped objects.

1) Computing conflict masses: To distinguish between two types of conflict which arise from the fact that the environment is dynamic, the idea from [START_REF] Moras | Moving Objects Detection by Conflict Analysis in Evidential Grids[END_REF] is used. ∅ F O denotes the conflict induced when a free cell in PG is fused with an occupied cell in SG. Similarly, ∅ OF indicates the conflicted mass caused by an occupied cell in PG fused with a free cell in SG.

Conflict masses are calculated using the formulas:

m P G, t (∅ OF ) = m P G, t-1 (O) • m SG, t (F ) (27) m P G, t (∅ F O ) = m P G, t-1 (F ) • m SG, t (O) (28)
where m(O) = A⊆{I, U, S, M } m(A) and m(F ) = A⊆{N, W } m(A). In an error-free case, these conflicts represent, respectively, the disappearance and the appearance of an object in a given cell.

2) PerceptionGrid specialisation using an accumulator: Mobile object detection is an important issue in dynamic environments. We propose the introduction of an accumulator ζ in each cell in order to include temporal information on the cell occupancy. For this purpose, incrementation and decrementation steps δ inc ∈ [0, 1], δ dec ∈ [0, 1], as well as threshold values γ O , γ ∅ have been defined. Using ζ values, we impose a specialisation of mass functions in PG using the equation:

ζ (t) = min 1, ζ (t-1) + δ inc (29) if m P G (O) ≥ γ O and m P G (∅ F O ) + m P G (∅ OF ) ≤ γ ∅ ζ (t) = max 0, ζ (t-1) -δ dec (30) if m P G (∅ F O ) + m P G (∅ OF ) > γ ∅ ζ (t) = ζ (t-1) (31) otherwise (32)
m P G, t (A) = S(A, B) • m P G, t (B) (33)
where specialisation matrix S(•, •) is defined as:

S(A\ {M } , A) = ζ ∀A ⊆ Ω P G and {M } ∈ A S(A, A) = 1 -ζ ∀A ⊆ Ω P G and {M } ∈ A S(A, A) = 1 ∀A ⊆ Ω P G and {M } / ∈ A S(•, •) = 0 otherwise ( 34
)
The idea behind the specialisation matrix and the accumulator is that the mass attributed to set N, S, M or S, M is transferred to set N, S or S, respectively. The transferred mass value is proportional to the time that the cell stayed occupied. In this way, moving objects are differentiated from static or stopped objects.

3) Fusion rule: An important part of the method consists in performing the fusion operation of a discounted and specialized PerceptionGrid from preceding epoch α m P G, t-1 with a SG combined with prior knowledge from current epoch m SG, t . The discounting operation is presented in section II and the specialisation is described in the preceding paragraph. In the section III-C, combination of prior knowledge with SensorGrid is demonstrated.

m P G, t = α m P G, t-1 m SG, t (35)
The fusion rule is a modified conjunctive rule adapted to mobile object detection. There are of course many different rules that could be used, but in order to distinguish between moving and stationary objects some modifications had to be performed. These modifications consist in transferring the mass corresponding to a newly appeared object ∅ F O to the class of moving objects M as described by the equation 36. Please remind that ∩ denotes the conjunctive fusion rule.

(m 1 m 2 ) (A) = (m 1 ∩ m 2 ) (A) ∀A Ω ∧ A = M (m 1 m 2 ) (M ) = (m 1 ∩ m 2 ) (M ) + (m 1 ∩ m 2 ) (∅ F O ) (m 1 m 2 ) (Ω) = (m 1 ∩ m 2 ) (Ω) + (m 1 ∩ m 2 ) (∅ OF ) (m 1 m 2 ) (∅ F O ) = 0 (m 1 m 2 ) (∅ OF ) = 0 (36)
All the above steps allow the construction of a PG containing reach information on the environment state, including the knowledge on mobile and static objects.

E. Fusion rule behaviour

Proposed fusion scheme behaves differently depending on the context. In this section, we describe briefly the behaviour of the fusion rule. For an in-depth analysis, the reader is invited to read [START_REF] Kurdej | Controlling Remanence in Evidential Grids Using Geodata for Dynamic Scene Perception[END_REF]. Context stands for prior knowledge information contained in GISGrid. To demonstrate the effect of the fusion operator, we have chosen two particular cases, which clearly represent different contexts.

Building context: In the building context, the fusion rule behaves as Yager's rule, which consists in transferring the conflict mass to unknown class Ω [START_REF] Yager | On the Dempster-Shafer framework and new combination rules[END_REF]. This behaviour is relevant, since it is assumed that no mobile obstacles are present in this context. Therefore, only free space and infrastructure are to be distinguished.

Road and intermediate space: The conflict management adapted to the perception scheme directs mass attribution to moving obstacles (class M ). The introduction of occupied space counter and PerceptionGrid specialisation (see section III-D.2) permits to transfer a part of the mass from "moving or other" class to "other", where other is contextdependent.

F. Illustrative examples

This section aims to present the behaviour of our perception system on a pedagogical example. The example is composed of three 1D-grids (for simplification, here) evolving in time, and so the scenario has to be read from top to bottom, line by line. Colours are determined by the mass function of the cell according to the legend. Please note that a mass function can contain more than one focal element so the effective colour is a mix of corresponding classes.

In the scene (see Figure 3), there are 3 pedestrians: one crossing the road, one staying on the road and one staying on the pavement. GISGrid represents our prior knowledge obtained from the digital map. Both sides are known to be pavement (intermediate space T ) and the middle is supposed to be the road surface R. SensorGrid is a representation of current sensor data. The sensor provides in this situation only free/occupied information. PerceptionGrid is the step-by-step result of the perception system. Its initial state is a complete ignorance (all mass attributed to unknown Ω). As the moving pedestrian walks, the movement is detected in different grid cells. Behind the pedestrian, previously occupied cells become gradually free. Free, navigable and non-navigable, cells have their masses increased as the sensor confirms the same information. The information relative to the two stopped pedestrians is processed differently thanks to the map information. The one on the road is considered as a movable M S object at first, since initially the cell was unknown. Then, as time evolves, it is considered as stopped, which illustrates how the accumulator and the specialisation work. This change is visible as the colour changes from purple to blue. The other pedestrians on the pavement are seen as moving or stopped or unmapped obstacle M SU at the beginning. At the end, the one staying on the pavement is detected as a stopped obstacle or as unmapped infrastructure SU . Indeed, it is impossible to distinguish between a stopped pedestrian and, for instance, a light post. The pedestrian crossing the road is quickly detected as moving M .

IV. EXPERIMENTAL RESULTS

A. Experimental setup 1) Dataset:

The data set used for experiments was acquired in the 12th district of Paris using our vehicular platform Carmen (see figure 4). The overall length of the Vehicle Carmen with Alaska XT lidar embedded in the front bumper.

trajectory was about 9 kilometres. The vehicle pose comes from a system based on a NovAtel SPAN-CPT inertial measurement unit (IMU). The system provides precise positioning with high confidence. Our main source of information about the environment is an IBEO Alaska XT lidar able to provide a cloud of about 800 points 10 times per second. The digital maps that we use were provided by the French National Geographic Institute (IGN) and contain 3D building models as well as the road surface. We also performed successful tests with freely available OpenStreetMap project 2D maps [12], but here we limited the use to building data. We assume the maps to be accurate and up-to-date.

2) GISGrid construction: The map data can be represented by two sets of polygons defining the 2D position of buildings and road surface by, respectively,

B = b i = x 1 x 2 . . . x mi y 1 y 2 . . . y mi , i ∈ [0, n B ] (37)
R = r i = x 1 x 2 . . . x mi y 1 y 2 . . . y mi , i ∈ [0, n R ] (38)
Our dataset satisfies the condition: B∩R = ∅. An example of GISGrid is presented in Figure 5 juxtaposed with an aerial photo with 3D building models. Classes B, R, T characterise the meta-information inferred from geographic maps. Set A denotes then all other strict subsets of Ω. For instance, on the road surface R, we encourage the existence of free navigable space N as well as stopped S and moving M objects. Analogically, building information B fosters mass transfer to I. Lastly, T denotes the intermediate area, e.g. pavements, where mobile and stationary objects as well as small urban infrastructure can be present. T can contain free non-navigable space W as well. Please note that neither buildings nor roads are present, so the existence of mapped infrastructure I can be excluded, but the presence of the other classes cannot. Also, a level of confidence β is defined for each map source, possibly different for each context (in our case:

β B = β R = β T = β). Let m GG {X, Y } be the mass function in the cell at coordinates {X, Y } = {[x -, x + ], [y -, y + ]} and x = x-+x+ 2 , ỹ = y-+y+ 2 , then: m GG {X, Y }(B) = β B if (x, ỹ) ∈ b i 0 otherwise (39) ∀i ∈ [0, n B ] m GG {X, Y }(R) = β R if (x, ỹ) ∈ r i 0 otherwise (40) ∀i ∈ [0, n R ]
m GG {X, Y }(T ) = 0 if (x, ỹ) ∈ b i ∨ (x, ỹ) ∈ r j β T otherwise (41) ∀i ∈ [0, n B ], ∀j ∈ [0, n R ] m GG {X, Y }(Ω) =      1 -β B if (x, ỹ) ∈ b i 1 -β R if (x, ỹ) ∈ r i 1 -β T otherwise (42) ∀i ∈ [0, n B ], ∀j ∈ [0, n R ] m GG {X, Y }(A) = 0 (43) ∀A Ω and A / ∈ {B, R, T }
3) Sensor model: This section describes the way in which the data obtained from the lidar are transformed into SensorGrid. If another exteroceptive sensor is used, one has to define an appropriate model. The model used in the presented method is based on the one described in [START_REF] Moras | Credibilist Occupancy Grids for Vehicle Perception in Dynamic Environments[END_REF] which takes into account the measurement uncertainties and occlusions. As demonstrated in Figure 2, the sensor provides a polar grid. This grid undergoes several transformation before being fused into PerceptionGrid. Our lidar model uses frame of discernment Ω SG with two classes: free F and occupied O. Each scan point (lidar impact) results in a grid cell being set with high value of occupied mass. All the cells before the first cell in each angular sector have their main part of the mass attributed to free. Small portion of the mass is set to Ω in order to take into account sensor resolution and grid discretisation errors. The state of other cells, those between obstacles and behind obstacles, cannot be determined and so all the mass goes to the unknown Ω.

4) Parameters: The size of the grid cell in the occupancy grids was set to 0.5 m, which is sufficient to model a complex environment with mobile objects. We have defined the map confidence factor β by ourselves, but ideally, it should be given by the map provider. β describes data currentness (age), errors introduced by geometry simplification and spatial discretisation. β can also be used to depict the localisation accuracy. In our case, β = 0.005, since we suppose our maps precise and accurate. Other parameters, such as counter steps δ inc , δ dec and thresholds γ O , γ ∅ used for mobile object detection determine the sensitiveness of mobile object detection and were set by manual tuning.

B. Results of obstacle detection

The results for a particular instant of the approach tested on real data are presented on Figures 6 and7. The reported scenes were recorded while the vehicle was moving to illustrate the performance in real urban traffic conditions, typically at the speed of 40 km/h.

Topmost images show camera captures, middle images present PerceptionGrid in a fixed Cartesian frame, zoomed in around the vehicle location. The visualisation of PG has been obtained by attributing to each class a colour proportional to the pignistic probability betP and calculating the mean colour. Images containing grids contain some markers to show the vehicle position (small red cross) and vehicle speed vector (black arrow). Light dashed white lines show the approximate camera's field of view limits in order to link the image with the grid. Please notice that the field of view of the lidar is wider than the one of the camera and is not shown for clarity. Bottommost images reflect the result of a decision rule done by thresholding pignistic probabilities (see Equation 14). The different thresholds were set to 0.5 except for class S for which the threshold was 0.35, since we wanted to magnify the effect of detection of obstacles stopped for a short moment.

Figure 6 presents quite a complex scene with multiple moving vehicles and a few stopped ones. The two moving motorcycles and the moving car on the opposite lane are clearly detected as shown by red cells on the bottom figures. Behind these moving cells, the state of the space is unknown, which is consistent with the lidar capabilities. The car in front, waiting at a traffic light, has been detected as stopped (see the blue cells right in the direction of the arrow). Similarly, cars parked on the left side road are detected as stopped (blue cells in the bottom right of the grids). One can notice that even if these vehicles are hardly visible on the camera images, they have been detected by the perception system. When the size of the objects become small, the lidar can miss them. This can induce some artefacts in the perception scheme making for instance posts of traffic signs oscillating between moving and stopped. This explains the isolated red/blue cells in the grid.

Figure 7 presents another complex scene containing three cars moving in the opposite direction (visible only in some photos), one parked car, one parked bus and a motorcycle going in the same direction as the equipped vehicle. Moving cars (in red) are well-distinguished in the bottom images. Navigable (green) and non-navigable (white) spaces are well characterised and clearly separated. The partially visible bus and the car parked on the left (blue) are well detected as well.

The additional information provided by the map clearly enhances the driving scene understanding. The system is able to make a clear difference between moving (red cells) and stopped (blue) objects. Also, we have noticed on other sequences that stopped objects are perceived distinctly from infrastructure when prior map information is available. In addition, thanks to the prior knowledge, stationary objects such as infrastructure are distinguished from stopped objects on the road. This is a behaviour similar to one of Capelle et al. system that uses 3D city models [START_REF] Cappelle | Virtual 3D City Model for Navigation in Urban Areas[END_REF].

Finally, the effect of discounting is noticeable particularly behind the vehicle, as the information about the environment is being forgotten with different rates thanks to the map. The grid cells get discounted, so the mass on the different classes diminishes gradually. The thresholded plots show that the stopped information is more remanent as some blue cells are left behind.

C. Results of free space detection

Figure 8 is the result of cumulating subsequent grids for navigable and non-navigable free spaces after having executed the pignistic decision rule. These figures show all the cells that were detected as free either on the road or on the pavement at least at one moment of the test sequence. These cells are shown in green for navigable space and in white for non-navigable space. In violet, we superposed the prior map information about road surface from GISGrid. In such a way, one can identify areas that the vehicle perceived during the test. More interestingly, one can clearly recognise on Figure 8(b) the places where cars or other vehicles were parked. On the other hand, the non-navigable free space on Figure 8(a) (in white) exhibits zones that are normally useless for navigation but that could be useful for safety manoeuvres like the avoidance of a pedestrian collision.

V. CONCLUSION AND PERSPECTIVES

A new mobile perception scheme based on prior map knowledge has been introduced. Geographic information is exploited to reduce the number of possible hypotheses delivered by an exteroceptive source. A modified fusion rule taking into account the existence of mobile objects has been defined. Furthermore, the variation in information lifetime has been modelled by the introduction of contextual discounting.

In the future, we anticipate removing the hypothesis that the map is accurate. This approach will entail considerable work on creating appropriate error models for the data source. This will be a step towards the use of our approach in autonomous navigation. Another perspective is the use of reference data to validate the results, choose the most appropriate fusion rule and learn algorithm parameters. We envision using map information to predict object movements. It rests also a future work to exploit fully the 3D map information.

Fig. 1 .

 1 Fig. 1. Method overview.

Fig. 2 .

 2 Fig. 2. Illustration of grid transformations.

Fig. 3 .

 3 Fig. 3. Example with three pedestrians. T represents the intermediate space and R -road surface.

Fig. 4 .

 4 Fig. 4.Vehicle Carmen with Alaska XT lidar embedded in the front bumper.

Fig. 5 .

 5 Fig. 5. Paris 12th district cityhall. Left: GISGrid constructed using our dataset. Right: 3D view of the area, source: Google Earth. Buildings in blue, roads in khaki, intermediate space in gray.

Fig. 6 .

 6 Fig. 6. Scene 1 evolution: time goes from left to right. From top to bottom: (a) scene capture, (b) PerceptionGrid pignistic probability, (c) simple decision rule to detect free space, moving and stopped obstacles, Colour code for figures (3): green -navigable free space, white -non-navigable free space, red -moving objects, blue -stopped objects, black -unknown. Infrastructure (classes U and I) has not been visualised in the bottom figures.

Fig. 7 .

 7 Fig. 7. Scene 2 evolution. Same display as Figure 6.

  (a) Whole test sequence area. (b) Zoom on navigable space N .

Fig. 8 .

 8 Fig. 8. Free spaces N (in green) and non-navigable (in white) cumulated over the complete test sequence. Road surface from maps in violet. Both axes in meters.

† This article is an elaborated version of[START_REF] Kurdej | Enhancing Mobile Object Classification Using Geo-referenced Maps and Evidential Grids[END_REF], which was presented in the 5th Workshop on Planning, Perception and Navigation for Intelligent Vehicles at IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, Japan, 2013.* UMR CNRS 7253 Heudiasyc, University of Technology of Compiègne, France. E-mail: firstname.surname@hds.utc.frONERA. E-mail: firstname.surname@onera.fr

ACKNOWLEDGEMENTS

This work was supported by the French Ministry of Defence DGA (Direction Générale de l'Armement), with a Ph.D. grant delivered to Marek Kurdej.