Dominique Foata

Guo-Niu Han

Dennis Stanton

THE DECREASE VALUE THEOREM WITH AN APPLICATION TO PERMUTATION STATISTICS

Keywords: 2000 Mathematics Subject Classification. Primary 05A15, 05A30, 05E15, 33D15 Decrease value theorem, wreath product, flag-major index, flag-excedance number, flag-descent number, signed permutations, Lyndon factorization, decreases

The decrease value theorem is restated and given a specialization more adapted to Permutation Statistic Calculus. As an application, the computation of a factorial multivariable generating function for the wreath product of the cyclic group of finite order by the symmetric group is given in full detail.

Introduction

In one of our recent papers [START_REF] Foata | Decreases and Descents on Words, Sémin[END_REF] we have derived the decrease value theorem, that makes the calculation of a fundamental multivariable statistical distribution on words possible. The multivariable statistic in question involves the basic notions of decrease and increase, whose definitions are now recalled, together with the classical descent and rise.

Let [0, r] * be the set of all words, whose letters belong to the finite alphabet [0, r] = {0, 1, . . . , r} and let v = y 1 y 2 • • • y n be such a word. An integer i ∈ [1, n] is said to be a descent (or descent place) of v if y i > y i+1 ; it is a decrease of v if y i = y i+1 = • • • = y j > y j+1 for some j such that i ≤ j ≤ n -1. The letter y i is said to be a descent value and a decrease value of v, respectively. The set of all decreases (resp. descents) is denoted by DEC(v) (resp. DES(v)). Each descent is a decrease, so that DES(v) ⊂ DEC(v).

In parallel with the notion of decrease, an integer i ∈ [1, n] is said to be an increase (resp. a rise) of v if y i = y i+1 = • • • = y j < y j+1 for some j such that i ≤ j ≤ n (resp. if y i < y i+1 ). By convention, y n+1 = +∞. The letter y i is said to be an increase value (resp. a rise value) of v. Thus, the rightmost letter y n is always a rise and also an increase value. The set of all increases (resp. rises) of v is denoted by INC(v) (resp. RISE(v)). Each rise is an increase, so that RISE(v) ⊂ INC(v).

Furthermore, a position i (1 ≤ i ≤ n) is said to be a record if y j ≤ y i for all j such that 1 ≤ j ≤ i -1. The letter y i is said to be a record value. The set of all records of v is denoted by REC(v).

The multivariable statistic is now defined by means of six sequences of commuting variables (X i ), (Y i ), (Z i ), (T i ), (Y ′ i ), (T ′ i ) (i = 0, 1, 2, . . . ): for each word v = y 1 y 2 . . . y n from [0, r] * the weight ψ(v) is defined to be

(1.1) ψ(v) := i∈DES X y i i∈RISE\REC Y y i i∈DEC\DES Z y i × i∈(INC\RISE)\REC T y i i∈RISE∩REC Y ′ y i i∈(INC\RISE)∩REC T ′ y i ,
where the argument "(v)" has not been written for typographic reasons. For example, i ∈ RISE \ REC stands for i ∈ RISE(v) \ REC(v).

It is important to note that for each word v = y 1 y 2 • • • y n every integer i ∈ [1, n] belongs to one and only one of the sets DES(v),

(RISE \ REC)(v), (DEC \ DES)(v), ((INC \ RISE) \ REC)(v), (RISE ∩ REC)(v), ((INC \ RISE) ∩ REC)(v).
Example. For the word v = 3 2 4 4 5 5 5 3 1 1 1 4 1 3 5 the sets DES, DEC, INC, RISE, REC of v are indicated by bullets.

w

= 3 2 4 4 5 5 5 3 1 1 1 4 1 3 5

DES = • • • • DEC = • • • • • • RISE = • • • • • • INC = • • • • • • • • • REC = • • • • • • • We have ψ(v) = X 3 Y 2 T ′ 4 Y ′ 4 Z 5 Z 5 X 5 X 3 T 1 T 1 Y 1 X 4 Y 1 Y 3 Y ′ 5 . Now, let C be the (r + 1) × (r + 1) matrix (1.2) C =                    0 X 1 1 -Z 1 X 2 1 -Z 2 • • • X r-1 1 -Z r-1 X r 1 -Z r Y 0 1 -T 0 0 X 2 1 -Z 2 • • • X r-1 1 -Z r-1 X r 1 -Z r Y 0 1 -T 0 Y 1 1 -T 1 0 • • • X r-1 1 -Z r-1 X r 1 -Z r . . . . . . . . . . . . . . . . . . Y 0 1 -T 0 Y 1 1 -T 1 Y 2 1 -T 2 • • • 0 X r 1 -Z r Y 0 1 -T 0 Y 1 1 -T 1
Theorem 1.1 (Decrease Value Theorem). The generating function for the set [0, r] * by the weight ψ is given by

(1.3) w∈[0,r] * ψ(w) = 0≤j≤r 1 + Y ′ j 1 -T ′ j det(I -C) ,
where I is the identity matrix of order (r + 1).

The proof of the Decrease Value Theorem is fully given in our previous paper [START_REF] Foata | Decreases and Descents on Words, Sémin[END_REF], together with its two equivalent formulations:

w∈[0,r] * ψ(w) = 0≤j≤r 1 -Z j 1 -Z j + X j 0≤j≤r 1 -T ′ j 1 -T ′ j + Y ′ j 1 - 0≤k≤r 0≤j≤k-1 1 -Z j 1 -Z j + X j 0≤j≤k-1 1 -T j 1 -T j + Y j X k 1 -Z k + X k , (1.4) w∈[0,r] * ψ(w) = 1≤j≤r 1 -Z j 1 -Z j + X j 0≤j≤r 1 -T ′ j 1 -T ′ j + Y ′ j 1 - 1≤k≤r 1≤j≤k-1 1 -Z j 1 -Z j + X j 0≤j≤k-1 1 -T j 1 -T j + Y j X k 1 -Z k + X k . (1.5)
There is a specialization of (1.5) that deserves a special attention, which is the following. For convenience, introduce three sequences of commuting variables (ξ i ), (η i ), (ζ i ) (i = 0, 1, 2, . . . ) and make the following substitutions:

X i ← ξ i , Z i ← ξ i , Y i ← η i , T i ← η i , Y ′ i ← ζ i , T ′ i ← ζ i , (i = 0, 1, 2, . . . ). The new weight ψ ′ (v) attached to each word v = y 1 y 2 • • • y n is then (1.6) ψ ′ (v) = i∈DEC(v) ξ i i∈(INC\REC)(v) η i i∈(INC∩REC)(v) ζ i ,
and identity (1.5) becomes:

(1.7)

v∈[0,r] * ψ ′ (v) = 1≤j≤r (1 -ξ j ) 0≤j≤r (1 -ζ j ) 1 - 1≤k≤r 1≤j≤k-1 (1 -ξ j ) 0≤j≤k-1 (1 -η j ) ξ k .
The further specializations of (1.6) and (1.7) require the following notations. For each word v = y 1 y 2 • • • y n let λv designate its length (λv = n) and tot v = y 1 + y 2 + • • • + y n the sum of its letters. Next, given a positive integer l, let dec l v be the number of letters of v, which are decrease values and multiple of l; finally, for i = 0, 1, . . . , l -1 let |v| i mod l denote the number of letters of v congruent to i mod l and inrec i v the number of letters of v, congruent to i mod l, which are also increase and record values. Now, let u, s, Y i , Z i (i = 0, 1, 2, . . . ) be a new set of variables and let γ denote the homomorphism defined by the following substitutions of variables:

(1.8) ξ j ← uq j s l Z 0 , if j ≡ 0 mod l; uq j s i Z i , if j ≡ i mod l and 1 ≤ i ≤ l -1;

η j ← uq j s i Z i , if j ≡ i mod l and 0 ≤ i ≤ l -1; ζ j ← uq j s i Y i Z i , if j ≡ i mod l and 0 ≤ i ≤ l -1.
It follows from (1.6) and (1.8) that (1.9)

γ ψ ′ (v) = u λv q tot v s l dec l v 0≤i≤l-1 (s i Z i ) |v| i mod l Y inrec i v i .
For each r ≥ 0 consider the following multivariable generating function for the set [0, r] * :

(1.10) F r (u; q, s,

(Y i ), (Z i )) := v∈[0,r] * u λv q tot v s l dec l v 0≤i≤l-1 (s i Z i ) |v| i mod l Y inrec i v i .
Using the traditional notations for the q-ascending factorials (x; q) n = 1 if n = 0 and (x;

q) n = (1 -x)(1 -qx) • • • (1 -q n-1 x) if n ≥ 1,
the first goal of the paper is to show that F r (u; q, s, (Y i ), (Z i )) can be expressed as an explicit hypergeometric series in the variable u, as stated in the next theorem, where it is assumed that Z l ≡ Z 0 .

Theorem 1.2. For each r ≥ 0 the following evaluation holds:

(1.11) F r (u; q, s, (Y i ), (Z i )) = 1≤i≤l (uq i s i Z i ; q l ) ⌊(r-i)/l⌋+1 0≤i≤l-1 (uq i s i Y i Z i ; q l ) ⌊(r-i)/l⌋+1 Z 0 (1 -q l s l ) × Z 0 -Z 0 q l s l + l i=1 q i s i Z i - l i=1 q i s i Z i (uq l s l Z 0 ; q l ) ⌊(r-i)/l⌋+1 (uZ 0 ; q l ) ⌊(r-i)/l⌋+1 -1
.

The proof of Theorem 1.2 is given in Section 2. It is based on the decrease value theorem and makes use of the traditional techniques of qtelescoping. The above identity on word generating series is next used to show that the infinite series r≥0 t r F r (u; q, s, (Y i ), (Z i )) can be expressed as a factorial series n≥0 A n (s, t, q, (Y i ), (Z i )) u n /(t l ; q l ) n+1 , where each coefficient A n (s, t, q, (Y i ), (Z i )) is a generating polynomial for an algebraic structure by a well-defined multivariable statistic.

This algebraic structure is the following. Let l be a positive integer and consider the wreath product C l ≀ S n of the cyclic group C l of order l by the symmetric group S n of order n (see, e.g., [START_REF] Regev | Statistics on wreath products and generalized binomial-Stirling numbers[END_REF] for a complete description). The elements of C l ≀S n may be viewed as ordered pairs (w, ǫ),

where w = x 1 x 2 • • • x n is a permutation of 12 • • • n and ǫ = ǫ 1 ǫ 2 • • • ǫ n a
word of length n, whose letters belong to {0, 1, . . . , l -1}. Finally, C l ≀ S n is equipped with the total order "<" defined by: (j, i) < (j ′ , i ′ ) if and only if either i > i, ′ or i = i ′ and j < j ′ .

For each argument A let χ(A) = 1 or 0, depending on whether A is true or false and let |ǫ| i denote the number of letters equal to i in ǫ, so that 1

• |ǫ| 1 + 2 • |ǫ| 2 + • • • + (l -1) • |ǫ| l-1 = tot ǫ.
The statistics associated with (w, ǫ) are the following:

exc(w, ǫ) := #{j : 1 ≤ j ≤ n, x j > j, ǫ j = 0}; fexc(w, ǫ) := l • exc(w, ǫ) + tot ǫ; des(w, ǫ) := #{j : 1 ≤ j ≤ n -1, (x j , ǫ j ) > (x j+1 , ǫ j+1 )}; fdes(w, ǫ) := l • des(w, ǫ) + ǫ 1 ; maj(w, ǫ) := 1≤j≤n-1 j χ (x j , ǫ j ) > (x j+1 , ǫ j+1 ) ; fmaj(w, ǫ) := l • maj(w, ǫ) + tot ǫ; fix i (w, ǫ) := #{j : 1 ≤ j ≤ n, (x j , ǫ j ) = (j, i)} (0 ≤ i ≤ l -1).
For each n ≥ 0 consider the generating polynomial for C l ≀ S n :

(1.12)

W n (s, t, q, (Y i ), (Z i )) := (w,ǫ)∈C l ≀S n s fexc(w,ǫ) t fdes(w,ǫ) q fmaj(w,ǫ) 0≤i≤l-1 Z |ǫ| i i Y fix i (w,ǫ) i .
Theorem 1.3. Let F r (u; q, s, (Y i ), (Z i )) be given by (1.11). Then, the following identity holds

(1.13) n≥0 (1 + t + • • • + t l-1 )W n (s, t, q, (Y i ), (Z i )) u n (t l ; q l ) n+1 = r≥0 t r F r (u; q, s, (Y i ), (Z i )).
The proof of Theorem 1.3 is made in two steps. First, the left-hand side of (1.13) is shown to be equal to the generating function for the so-called wreathed permutations, expressed as a series t r G r (u; q, s, (Y i ), (Z i )). This is the content of Section 3. Second, each coefficient of t r in the above series is shown to be equal to the generating series F r (u; q, s, (Y i ), (Z i )), given in (1.10). This is accomplished, in Section 4, by means of a bijection, whose construction is directly inspired by the classical standardization procedure. Finally, we derive several specializations of Theorem 1.3, in particular, the following theorem, which extends MacMahon's classical result of the equidistribution of exceedances and descents on permutations (see [Lo83, Chap. 10]).

Theorem 1.4. The two statistics "fdes" and "fexc" are equidistributed over

C l ≀ S n . Let W (l)
n,k denote the number of elements (w, ǫ) from C l ≀ S n such that fdes(w, ǫ) = k. Then, the following recurrence formula holds

(1.14) W (l) n,k = (k + 1)W (l) n-1,k + W (l) n-1,k-1 + • • • + W (l) n-1,k-(l-1) + (ln -k)W (l) n-1,k-l
for n ≥ 2 and 0 ≤ k ≤ nl -1 and the initial conditions:

W (l) 0,0 = 1, W (l) 0,k = 0 for k = 0; W (l)
1,k = 1 for k = 0, 1, . . . , l -1 and 0 for any other value of k.

Proof of Theorem 1.2

To obtain the right-hand side of (1.11) it suffices to calculate the image under γ of the right-hand side of (1.7). First, remembering that

Z l ≡ Z 0 , γ 1≤j≤r (1 -ξ j ) = γ l i=1 ⌊(r-i)/l⌋ j=0 (1 -ξ jl+i ) = γ l-1 i=1 ⌊(r-i)/l⌋ j=0 (1 -ξ jl+i ) × ⌊(r-l)/l⌋ j=0 (1 -ξ jl+l ) = l-1 i=1 ⌊(r-i)/l⌋ j=0 (1 -uq jl+i s i Z i ) × ⌊(r-l)/l⌋ j=0 (1 -uq jl+l s l Z l ) = l i=1 ⌊(r-i)/l⌋ j=0 (1 -uq i s i Z i (q l ) j ) = l i=1 (uq i s i Z i ; q l ) ⌊(r-i)/l⌋+1 .
In the same manner, γ 0≤j≤r

(1

-ζ j ) = l-1 i=0 (uq i s i Y i Z i ; q l ) ⌊(r-i)/l⌋+1 ; γ 1≤j≤k-1 (1 -ξ j ) = l i=1 (uq i s i Z i ; q l ) ⌊(k-1-i)/l⌋+1 ; γ 0≤j≤k-1 (1 -η j ) = l-1 i=0 (uq i s i Z i ; q l ) ⌊(k-1-i)/l⌋+1 ;
so that the image of (1.7) under γ becomes (2.1)

v∈[0,r] * γψ ′ (v) = l i=1 (uq i s i Z i ; q l ) ⌊(r-i)/l⌋+1 l-1 i=0 (uq i s i Y i Z i ; q l ) ⌊(r-i)/l⌋+1 × (1 -S) -1 ,
where

S = 1≤k≤r (uq l s l Z 0 ; q l ) ⌊(k-1)/l⌋ (uZ 0 ; q l ) ⌊(k-1)/l⌋+1 γ(ξ k ),
which can be rewritten:

S = l i=1 ⌊(r-i)/l⌋ j=0 (uq l s l Z 0 ; q l ) j (uZ 0 ; q l ) j+1 uq lj q i s i Z i . Introduce G(m) = 0≤j≤m (uq l s l Z 0 ; q l ) j (uZ 0 ; q l ) j+1 uq lj , so that S = l i=1 q i s i Z i G(⌊(r -i)/l⌋).
As (uq l s l Z 0 ; q l ) j+1 (uZ 0 ; q l ) j+1 -(uq l s l Z 0 ; q l ) j (uZ 0 ; q l ) j = (uq l s l Z 0 ; q l ) j (uZ 0 ; q l ) j+1 uq lj Z 0 (1q l s l ), we have:

G(m) = 1 Z 0 (1 -q l s l ) (uq l s l Z 0 ; q l ) m+1 (uZ 0 ; q l ) m+1 -1 ,
and then

S = l i=1 q i s i Z i Z 0 (1 -q l s l ) (uq l s l Z 0 ; q l ) ⌊(r-i)/l⌋+1 (uZ 0 ; q l ) ⌊(r-i)/l⌋+1 -1 .
We obtain the righthand side of (1.11) by substituting the above S into (2.1).

Wreathed permutations

The generating polynomial W n (s, t, q, (Y i ), (Z i )) for the group C l ≀ S n has been defined in (1.12). Recall the notation for the q-binomial coefficient n k q := (q; q) n /((q; q) k (q; q) n-k ) for 0 ≤ k ≤ n and the classical identities

1 (t; q) n+1 = r≥0 n + r r q t r ; n + r r q = b∈NIW n (r) q tot b ;
where

NIW n (r) (resp. NIW n ) denotes the set of all words b = b 1 b 2 • • • b n of length n, whose letters are nonnegative integers satisfying r ≥ b 1 ≥ b 2 ≥ • • • b n ≥ 0 (resp. b 1 ≥ b 2 ≥ • • • b n ≥ 0) (see [An76, Chap. 3]).
Using those two identities we have:

1 + t + • • • + t l-1 (t l ; q l ) n+1 = r ′ ≥0 (t lr ′ + t lr ′ +1 + • • • + t lr ′ +l-1 ) n + r ′ r ′ q l = r≥0 t r n + ⌊r/l⌋ ⌊r/l⌋ q l = r≥0 t r b∈NIW n (⌊r/l⌋) q l tot b = r≥0 t r b∈NIW n , lb 1 ≤r q l tot b .
Hence,

(3.1) 1 + t + • • • + t l-1 (t l ; q l ) n+1 W n (s, t, q, (Y i ), (Z i )) = r≥0 t r b∈NIW n , lb 1 ≤r q l tot b (w,ǫ)∈C l ≀S n s fexc(w,ǫ) t fdes(w,ǫ) q fmaj(w,ǫ) 0≤i≤l-1 Y fix i (w,ǫ) i Z |ǫ| i i = r≥0 t r b∈NIW n , (w,ǫ)∈C l ≀S n lb 1 +fdes(w,ǫ)≤r s fexc(w,ǫ) q l tot b+fmaj(w,ǫ) 0≤i≤l-1 Y fix i (w,ǫ) i Z |ǫ| i i .
For each element (w, ǫ)

∈ C l ≀ S n form the word z = z 1 z 2 • • • z n
, where z j is defined to be the number of k such that j ≤ k ≤ n -1 and (x k , ǫ k ) > (x k+1 , ǫ k+1 ) with respect to the order imposed on C l ≀S n . In other words, z j is the number of descents in the right factor (x j , ǫ j )(x j+1 , ǫ j+1 )

• • • (x n , ǫ n ).
The next proposition is easy to verify.

Proposition 3.1. We have: des(w, ǫ) = z 1 , maj(w, ǫ) = tot z.

Now, let b = b 1 b 2 • • • b n ∈ NIW n and (w, ǫ) = (x 1 , ǫ 1 )(x 2 , ǫ 2 ) • • • (x n , ǫ n )∈ C l ≀ S n be given. We define the word c = c 1 c 2 • • • c n by (3.2) c j := l(b j + z j ) + ǫ j (1 ≤ j ≤ n).
As both words b and z are monotonic nonincreasing, we have (b j + z j ) ≥ (b j+1 +z j+1 ) (1 ≤ j ≤ n-1). If the inequality is strict, then c j > c j+1 since 0 ≤ ǫ j+1 ≤ l -1. If b j +z j = b j+1 +z j+1 , then z j = z j+1 and, consequently, (x j , ǫ j ) < (x j+1 , ǫ j+1 ), so that ǫ j ≥ ǫ j+1 . Therefore, c j ≥ c j+1 . The word c is then monotonic nonincreasing. We further have the following properties: (i) c j = c j+1 ⇒ (x j , ǫ j ) < (x j+1 , ǫ j+1 );

(ii) c j ≡ ǫ j (mod l);

(iii) c 1 = l b 1 + fdes(w, ǫ);

(iv) tot c = l tot b + fmaj(w, ǫ). Note that (iii) and (iv) are immediate consequences of Proposition 3.1 and the definition of c.

A triple (c, w, ǫ) such that (w, ǫ)

= (x 1 , ǫ 1 )(x 2 , ǫ 2 ) • • • (x n , ǫ n )∈ C l ≀ S n and c = c 1 c 2 • • • c n ∈ NIW n
and such that properties (i) and (ii) hold is called a wreathed permutation of order n. The set of all wreathed permutations (c, w, ǫ) of order n is denoted by WP n and the subset of WP n of all (c, w, ǫ) such that c 1 ≤ r by WP n (r).

It follows from (3.2) that, for each r ≥ 0 the mapping

(b, w, ǫ) → (c, w, ǫ)
provides a bijection of the set of all triples (b, w, ǫ) such that b ∈ NIW n , (w, ǫ) ∈ C l ≀ S n and l b 1 + fdes(w, ǫ) ≤ r onto WP n (r), having properties (iii) and (iv). By (3.1)

1 + t + • • • + t l-1 (t l ; q l ) n+1 W n (s, t, q, (Y i ), (Z i )) = r≥0 t r (c,w,ǫ)∈WP n (r) s fexc(w,ǫ) q tot c 0≤i≤l-1 Y fix i (w,ǫ) i Z |ǫ| i i ,
so that, if we let

(3.3) G r (u; s, q, (Y i ), (Z i )) := (c,w,ǫ)∈WP(r) u λw s fexc(w,ǫ) q tot c 0≤i≤l-1 Y fix i (w,ǫ) i Z |ǫ| i i ,
we have the identity:

(3.4) n≥0 (1 + t + • • • + t l-1 )W n (s, t, q, (Y i ), (Z i )) u n (t l ; q l ) n+1 = r≥0 t r G r (u; s, q, (Y i ), (Z i )).
Example. With l = 3 the monotonic nonincreasing word c is calculated from the triple (b, w, ǫ):

Id =
1 2 3 4 5 6 7 8 9 10 b = 5 5 4 2 2 2 0 0 0 0 w = 1 8 7 4 10 2 6 9 5 3 ǫ = 0 0 1 1 1 0 2 2 1 0 z = 3 3 2 1 1 1 0 0 0 0 c = 24 24 19 10 10 9 2 2 1 0 Note that des(w, ǫ) = 3 = z 1 ; maj(w, ǫ) = 2 + 3 + 6 = 11; tot b = 20; tot ǫ = 8; fdes(w, ǫ) = 3 • des(w, ǫ) + ǫ 1 = 9;

24 = c 1 = 3 • b 1 + fdes(w, ǫ) = 3 • 5 + 9; fmaj(w, ǫ) = 3 • maj(w, ǫ) + tot ǫ = 3 • 11 + 8 = 41; 101 = tot c = 3 • tot b + fmaj(w, ǫ) = 3 • 20 + 41.

Standardization

By comparison with (1.13) we see that Theorem 1.3 is proved if we show that F r (u; s, q, (Y i ), (Z i )), given by (1.10), is equal to G r (u; s, q, (Y i ), (Z i )), given by (3.3), for all r ≥ 0, that is, if we prove

v∈[0,r] * u λv q tot v s l dec l v 0≤i≤l-1 (s i Z i ) |v| i mod l Y inrec i v i = (c,w,ǫ)∈WP(r) u λw s fexc(w,ǫ) q tot c 0≤i≤l-1 Y fix i (w,ǫ) i Z |ǫ| i i .
To do this, it suffices to construct a bijection v → (c, w, ǫ) of [0, r] n (the set of all words of length n with letters from the alphabet [0, r]) onto WP n (r) having the properties:

(i) tot v = tot c; (ii) dec l v = exc(w, ǫ); (iii) |v| i mod l = |ǫ| i for i = 0, 1, . . . , l -1; (iv) inrec i v = fix i (w, ǫ) for i = 0, 1, . . . , l -1.
For such a bijection the word c is to be the monotonic nonincreasing rearrangement of v, the permutation w an adequate labelling from 1 to n of the n letters of v, and ǫ a word whose letters are the residues of the letters of v mod l. Such a bijection appears to be a standardization of each word by a certain element from C l ≀ S n . Earlier standardizations by the symmetric group S n (resp. the hyperoctahedral group B n ) have been constructed by Gessel and Reutenauer [START_REF] Gessel | Counting permutations with given cycle structure and descent set[END_REF] (resp. in [START_REF] Foata | Signed words and permutations, V; A sextuple distribution[END_REF]). The procedure we now develop proceeds from the same principle.

Recall that a nonempty word v = y 1 y 2 • • • y n is a Lyndon word, if either n = 1, or n ≥ 2 and, with respect to the lexicographic order, the inequality

y 1 y 2 • • • y n > y i y i+1 • • • y n y 1 • • • y i-1 holds for every i such that 2 ≤ i ≤ n.
Let v, v ′ be two nonempty primitive words (none of them can be written as v a 0 for a ≥ 2 and some word v 0 ). We write v v ′ if and only if v a ≤ v ′a with respect to the lexicographic order for an integer a large enough. As shown for instance in [Lo83, Theorem 5.1.5] (also see [Ch58], [START_REF] Schützenberger | On a factorization of free monoids[END_REF]) each nonempty word v can be written uniquely as a product l 1 l 2 • • • l k , called its Lyndon factorization, where each l i is a Lyndon word and l 1 l 2 • • • l k . In the example below the Lyndon factorization of v has been materialized by vertical bars. Now, start with the Lyndon factorization l 1 l 2 • • • l k of a word v from [0, r] n . With such a v associate a permutation σ from S n in the following manner: each letter y i of v belongs to a Lyndon word factor l h , so that

l h = v ′ y i v ′′ . Then, form the infinite word A(y i ) := y i v ′′ v ′ y i v ′′ v ′ • • • If y i and y i ′ are two letters of v, say that y i precedes y i ′ if A(y i ) > A(y i ′ )
for the lexicographic order, or if A(y i ) = A(y i ′ ) and y i is to the right of y i ′ in the word v. This precedence determines a total order on the n letters of v. The letter that precedes all the other ones is given label 1, the next one label 2, and so on. When each letter y i of v is replaced by its label, say, lab(y i ), each Lyndon word factor l j becomes a new word τ j . The essential property is that each τ j starts with its minimum element and those minimum elements read from left to right are in decreasing order. We can then interpret each τ j as the cycle of a permutation and the (juxtaposition) product τ 1 τ 2 • • • τ k as the (functional) product of disjoint cycles. This product, said to be written in canonical form, defines a unique permutation σ from S n ([Lo83], § 10.2).

For example, The labels on the second row are obtained as follows: read the letters equal to 6 (the maximal letter) from left to right and form their associated infinite words: 64213236421

v = 2 | 3 2 1 1 | 3 | 5 | 6 4 2 1 3 2 3 | 6 6 3 1 6 6 2 | 6 σ =
• • •, 66316626631 • • •, 6316621131 • • •, 662663166 • • •, 62663166 • • •, 66666 • • •
Those letters 6 read from left to right will be given the labels 4, 2, 5, 3, 6, 1. We continue the labellings by reading the letters equal to 5, then 4, . . . in the above word v.

No decrease y i in v can be the rightmost letter of a Lyndon word factor l h . We have then

l h = • • • y i y i+1 • • • y j y j+1 • • • with y i ≥ y i+1 ≥ • • • ≥ y j > y j+1
. Consequently, A(y i ) > A(y i+1 ) and lab(y i ) < lab(y i+1 ). Conversely, if lab(y i ) < lab(y i+1 ) and y i , y i+1 belong to the same Lyndon factor, then y i is a decrease in v. To each decrease y i in v there corresponds a unique cycle τ h of σ and a pair lab(y i ) lab(y i+1 ) of successive letters of τ h such that lab(y i ) < lab(y i+1 ) and lab(y i+1 ) = σ(lab(y i )).

Consider the monotonic nonincreasing rearrangement c = c 1 c 2 • • • c n of v and form the three-row matrix

1 2 • • • n c 1 c 2 • • • c n σ(1) σ(2) • • • σ(n)
Then, if y i is a decrease in v, the lab(y i )-th column of the previous matrix is of the form lab(y i )

y i lab(y i+1 ) with lab(y i ) < lab(y i+1 ).
Consequently, y i is a decrease in v if and only if σ(lab(y i )) > lab(y i ). As σ(i) > σ(i + 1) ⇒ c i > c i+1 , the above three-row matrix can be expressed as

Id = 1 • • • m 1 | m 1 +1 • • • m 1 +m 2 | • • • | m 1 +• • •+m k-1 +1 • • • n c = a 1 • • • a 1 | a 2 • • • a 2 | • • • | a k • • • a k σ = σ(1) • • • σ(m 1 ) | σ(m 1 +1) • • • σ(m 1 +m 2 ) | • • • | σ(m 1 +• • •+m k-1 +1) • • • σ(n) where a 1 > a 2 > • • • > a k ≥ 0 and m 1 ≥ 1, m 2 ≥ 1, . . . , m k ≥ 1 and σ(1) < • • • < σ(m 1 ), σ(m 1 + 1) < • • • < σ(m 1 + m 2 ), . . . , σ(m 1 + • • • + m k-1 + 1) < • • • < σ(n).
For each i = 1, . . . , k let a i be the residue of a i mod l and let

w ǫ := σ(1) • • • σ(m 1 ) σ(m 1 +1) • • • σ(m 1 +m 2 ) • • • σ(m 1 +• • •+m k-1 + 1) • • • σ(n) a 1 • • • a 1 a 2 • • • a 2 • • • a k • • • a k
It then follows that (c, w, ǫ) is a wreathed permutation and properties (i), (ii) and (iii) hold. For the proof of (iv) we note that a letter y i of v is an increase and record value if and only if y i is a one-letter factor in the Lyndon factorization of v, that is, if and only if lab y i is a cycle of length 1 of w, or equivalently, a fixed point of w. All the steps previously described are perfectly reversible. This achieves the proof of Theorem 1.3

With the running example take l = 3 we can form the table:

v = 2 | 3 2 1 1 | 3 | 5 | 6 4 2 1 3 2 3 | 6 6 3 1 6 6 2 | 6 σ = 16 |
ǫ = 0 0 0 0 0 0 | 2 | 1 | 0 0 0 0 0 | 2 2 2 2 2 | 1 1 1 1
The word v is given, with its corresponding Lyndon factorization; the word σ is obtained from v by replacing each letter y i by its label lab(y i ) and to be regarded as the product of the cycles duly materialized; c is just the monotonic nonincreasing rearrangement of v; w is the sequence σ(1)σ(2) • • • σ(n); ǫ is derived from c by replacing each c i by its residue mod 3.

The eight decreases of v which are multiple of 3, and the eight excedances of (w, ǫ) have been reproduced in boldface. The four increase and record values of v are reproduced in italic, together with the four one-letter factors of σ, and the four fixed points of w, that is, 16, 10, 7, 1.

Specializations

Let W n (s, t, q) (resp. F r (u; q, s)) be the polynomial W n (s, t, q, (Y i ), (Z i )) (resp. the series F (u; q, s, (Y i ), (Z i )) ), when Y i = Z i = 1 for all i, so that W n (s, t, q) = (w,ǫ)∈C l ≀S n s fexc(w,ǫ) t fdes(w,ǫ) q fmaj(w,ǫ) ; (5.1) F r (u; q, s) = (uq l s l ; q l ) ⌊r/l⌋ (u; q l ) ⌊r/l⌋+1

(1q l s l ) (5.2)

× 1 -q l s l + l i=1 q i s i - l i=1 q i s i (uq l s l ; q l ) ⌊(r-i)/l⌋+1 (u; q l ) ⌊(r-i)/l⌋+1 -1
.

Theorem 1.3 yields the following result.

Theorem 5.1. The generating function for the polynomials W n (s, t, q) reads:

(5.3) n≥0

(1 + t + • • • + t l-1 )W n (s, t, q) u n (t l ; q l ) n+1 = r≥0 t r F r (u; q, s).

When n tends to infinity, remember that 1/(u; q) n tends to the qexponential series e q (u) = n≥0 u n /(q; q) n (see, e.g., [START_REF] Andrews | The theory of partitions[END_REF], chap. 2). Accordingly, when r tends to infinity, F r (u; q, s) tends to F ∞ (u; q, s) = e q l (u) e q l (uq l s l )

(1-q l s l ) 1-q l s l + l i=1 q i s il i=1 q i s i e q l (u) e q l (uq l s l )

-1 = e q l (u) e q l (uq l s l )

(1-q l s l ) (1q l s l ) + qs(1q l s l ) 1qs 1 -e q l (u) e q l (uq l s l ) -1 = e q l (u) e q l (uq l s l )

(1qs) (1qs) + qs 1 -e q l (u) e q l (uq l s l ) -1

=

e q l (u) e q l (uq l s l )

(1qs) 1qs e q l (u) e q l (uq l s l ) -1

=

(1qs)e q l (u) e q l (uq l s l )qse q l (u) .

Theorem 5.2. Let W n (s, 1, q) = (w,ǫ)∈C l ≀S n s fexc(w,ǫ) q fmaj(w,ǫ) .

Then, the following identity holds:

(5.4) n≥0 W n (s, 1, q) u n (q l ; q l ) n = (1qs)e q l (u) e q l (uq l s l )qse q l (u) .

Proof. There suffices to multiply both sides of identity (5.3) by (1t) and let t tend to 1. The right-hand side tends to F ∞ (u; q, s), which has just been calculated.

Let u = (1q l )u and then q → 1 in (5.4). This leads to the identity: The next step is to calculate F r (u; q, 1). First, note that (uq l ; q l ) m (u; q l ) m+1 = 1 1u and (uq l ; q l ) m (u; q l ) m = 1uq ml 1u . Now, let s = 1 in (5.2). We get: F r (u; q, 1) = (uq l ; q l ) ⌊r/l⌋ (u; q l ) ⌊r/l⌋+1

(1

-q l ) × 1 -q l + l i=1 q i - l i=1 q i (uq l ; q l ) ⌊(r-i)/l⌋+1 (u; q l ) ⌊(r-i)/l⌋+1 -1 = 1 -q l 1 -u × 1 -q l + l i=1 q i - l i=1 q i 1 -uq l(⌊(r-i)/l⌋+1) 1 -u -1
(hyperoctahedral group). Theorem 5.3 has several consequences. Write W (l) (1, t, q) := W n (1, t, q) to indicate that the polynomial also depends on l. In particular,

(5.10) W (1) n (1, t, q) = A n (t, q) = σ∈S n t des σ q maj σ , which is precisely the q-Eulerian polynomial introduced by Carlitz [START_REF] Carlitz | q-Bernoulli and Eulerian numbers[END_REF], and also combinatorially interpreted by him [START_REF] Carlitz | A combinatorial property of q-Eulerian numbers[END_REF]. As (5.9) holds for every l, we also have

n≥0 A n (t, q) u n (t; q) n+1 = r≥0 t r 1-u[r+1] q -1 , (5.11) so that W (l)
n (1, t, q) = (t l q l ; q l ) n (t; q) n A n (t, q) (n ≥ 0). (5.12)

In view of (5.12) there is no use working out the other formulas for W (l) (1, t, q) from scratch. We just have to report to Carlitz's original paper [START_REF] Carlitz | q-Bernoulli and Eulerian numbers[END_REF], dealing with the polynomials A n (t, q), and use (5.12). First,

(5.13) (1 -q)W (l) n (1, t, q) = (1 -t l q l )W (l) n-1 (1, t, q) -(-q + tq(1 -q) + • • • + t l-1 q l-1 (1 -q) + t l q l )W (l) n-1 (1, tq, q). Next, let W (l) n (1, t, q) = k W (l)
n,k (q)t k and look for the coefficients of t k on both sides. We get:

(5.14) W (l) n,k (q) = [k + 1] q W (l) n-1,k (q) + q k+1 W (l) n-1,k-1 (q) +q k+2 W (l) n-1,k-2 (q)+• • •+q k+l-1 W (l) n-1,k-(l-1) (q)+q k [nl-k] q W (l) n-1,k-l (q).
With q = 1 in (5.14) we obtain the recurrence formula (1.14) of Theorem 1.4.

Note that for l = 1 identity (1.14) becomes the classical recurrence formula for the Eulerian numbers A n,k := W

(1) n,k A n,k = (k + 1)A n-1,k + (n -k)A n-1,k-1
(see, e.g., [START_REF] Foata | Théorie géométrique des polynômes eulériens[END_REF]), which are the coefficients of the classical Eulerian polynomial A n (t, 1) = k A n,k t k . For q = 1 identity (5.12) becomes:

(5.15)

W (l) n (1, t, 1) = (1 -t l ) n (1 -t) n A n (t, 1).
As the exponential generating function for the Eulerian polynomials (see, e.g., [START_REF] Foata | Théorie géométrique des polynômes eulériens[END_REF]) reads n≥0

A n (t, 1)

u n n! = 1 -t -t + exp(u(t -1)) , (5.16) identity (5.16) implies that n≥0 W (l)
n (1, t, 1)

u n n! = 1 -t -t + exp(u(t l -1))
. (5.17) From identities (5.5) and (5.17) we conclude that (5.18)

W (l) n (t, 1, 1) = W (l) n (1, t, 1) = nl-1 k=0 W (l) n,k t k , the coefficients W (l)
n,k satisfying recurrence (5.15). This proves Theorem 1.4. A good exercise of Combinatorics consists of proving directly that both coefficients W (l,fdes) n,k

:= #{(w, ǫ) ∈ C l ≀S n , fdes(w, ǫ) = k} and W (l,fexc) n,k := #{(w, ǫ) ∈ C l ≀ S n , fexc(w, ǫ) = k} satisfy recurrence formula (1.14). For W (l,fdes) n,k
it suffices to analyze the impact of the insertion of the biletter n i into the n slots of an element from C l ≀ S n-1 . For W (l,fexc) n,k the variation of "fexc" is to be analyzed when the following operation is performed: replace the j-th biletter x j ǫ j of an element w ǫ = x 1 ... x j ... x n-1 ǫ 1 ... ǫ j ... ǫ n-1 from C l ≀ S n-1 by n k , and insert the biletter x j k ′ to the right. We do not reproduce the solution of this exercise!

Concluding remarks

The Decrease Value Theorem, stated and proved in [START_REF] Foata | Decreases and Descents on Words, Sémin[END_REF], was regarded as our Ur-result in our studies on q-calculus of permutation statistics. The motivation of this paper has been to extend its application to another group structure, namely the wreath product C l ≀S n . This theorem makes it possible to have a full control of all decreases in each word. By means of a standardization procedure, the decreases can then be carried over to excedances of the underlying permutations.

As was done in our two papers [START_REF] Foata | Fix-Mahonian Calculus, III: A quadruple distribution[END_REF] and [START_REF] Foata | Signed words and permutations, V; A sextuple distribution[END_REF] dealing with the symmetric, and hyperoctahedral group, respectively, we could as well have made use of the so-called V -word decomposition theorem for words, a theorem directly inspired from a result by Kim-Zeng [START_REF] Kim | A new decomposition of derangements[END_REF] valid for permutations, for deriving Theorem 1.2. The Decrease Value Theorem has the advantage of providing the adequate identity immediately without any further combinatorial construction.

There is also an extension of Theorem 1.3, where the set {0, 1, . . . , l -1} is split into two subsets I, J such that 0 ∈ I and the total order imposed on C l ≀ S n has the properties: (6.1) (a) (j, i) < (j ′ , i ′ ) when i > i ′ for all j, j ′ ; (b) (1, i) < (2, i) < • • • < (n, i) when i ∈ I; (c) (n, i) < • • • < (2, i) < (1, i) when i ∈ J.

When J = ∅, we recover the total order used in the previous sections. For l = 2, I = {0}, J = {1}, we get the natural order defined on the hyperoctahedral group B n , namely, -n < • • • < -1 < 1 < • • • < n with the convention: -j ≡ (j, 1), j ≡ (j, 0) for all j = 1, 2, . . . , n.

Referring to formula (1.11) let H r (u; q, s, (Z i )) := Z 0 (1q l s l ) × Z 0 -Z 0 q l s l + l i=1 q i s i Z i -l i=1 q i s i Z i (uq l s l Z 0 ; q l ) ⌊(r-i)/l⌋+1 (uZ 0 ; q l ) ⌊(r-i)/l⌋+1 -1

, a series that does not depend on (Y i ). The extension of (1.13) for the total order defined in (6.1) reads: (6.2) n≥0

(1 + t + • • • + t l-1 )W n (s, t, q, (Y i ), (Z i )) u n (t l ; q l ) n+1 = r≥0 t r i∈J (-us i q i Y i Z i ; q l ) ⌊(r-i)/l⌋+1 i∈J (-us i q i Z i ; q l ) ⌊(r-i)/l⌋+1 i∈(I\{0})∪{l} (uq i s i Z i ; q l ) ⌊(r-i)/l⌋+1 i∈I (uq i s i Y i Z i ; q l ) ⌊(r-i)/l⌋+1 × H r (u; q, s, (Z i )).

We do not reproduce the proof of this extension. Note that it fully implies the result we had derived in [START_REF] Foata | Signed words and permutations, V; A sextuple distribution[END_REF] for the hyperoctahedral group. Also note that the first statistical study of the latter group has been made by Reiner [START_REF] Reiner | Signed permutation statistics[END_REF], [START_REF] Reiner | Signed permutation statistics and cycle type[END_REF], [START_REF] Reiner | Upper binomial posets and signed permutation statistics[END_REF], Re95a].

Several papers have recently been published dealing with statistics on wreath products. The first analysis made by Bagno [B04] was followed by Haglund et al. [START_REF] Haglund | Statistics on wreath products, perfect matchings, and signed words[END_REF], who studied another aspect of permutation statistics on wreath products in connection with the theory of perfect matchings and rook placement q-counting. Bernstein [START_REF] Bernstein | Euler-Mahonian polynomials for C a ≀ S n[END_REF] has worked out a theory for the so-called C a ≀ S n q-maj Euler-Mahonian bivariable polynomials and obtained a solid formulary. The definitions he took for his generalized descent and major index do not coincide with the ones presented here. Bagno and Garber [START_REF] Bagno | On the excedance number of colored permutation groups[END_REF] generalize results by

  16 | 12 18 22 21 | 10 | 7 | 4 8 17 20 11 15 9 | 2 5 13 19 3 6 14 | 1

  12 18 22 21 | 10 | 7 | 4 8 17 20 11 15 9 | 2 5 13 19 3 6 14 | 1 Id = 1 2 3 4 5 6 | 7 | 8 | 9 10 11 12 13 | 14 15 16 17 18 | 19 20 21 22 c = 6 6 6 6 6 6 | 5 | 4 | 3 3 3 3 3 | 2 2 2 2 2 | 1 1 1 1 w = 1 5 6 8 13 14 | 7 | 17 | 4 10 15 18 19 | 2 9 16 20 22 | 3 11 12 21

  -s + exp(u(s l -1)) , (5.5) where W n (s, 1, 1) = (w,ǫ)∈C l ≀S n s fexc(w,ǫ) . (5.6)

Ksavrelof and Zeng [KZ03] on the multidistribution of the excedance number associated with the numbers of fixed points and cycles. Some more or less explicit three-variable statistical distributions are derived. Regev and Roichman [RR06] have worked out recurrence formulas of binomial-Stirling type for wreath product statistics related to left minima. Finally, Mendes and Remmel [MR07] have developed a brick-tabloid symmetric function approach for calculating generating functions for statistics for tuples of permutations.

q i 1q l(⌊(r-i)/l⌋+1) 1u

Hence,

(1q lk+s ) = q 1q r 1q .

Consequently, F r (u; q, 1) = 1uuq 1q r 1q

, so that, using the traditional notation for the q-analogs of integers,

(5.7) F r (u; q, 1) = 1u[r + 1] q -1 .

The following theorem has then be proved.

Theorem 5.3. The factorial generating function for the polynomials

.

Several authors ([AR01], [ABR01], [ABR05], [ABR06],

[CHGe07], [HLR05], [START_REF] Foata | Signed words and permutations, V; A sextuple distribution[END_REF]) have derived identity (5.9) in the particular case l = 2


Abdel Belaïd
email: abdel.belaid@loria.fl

Vincent Poulain
email: vincent.poulaindandecy@itesoft.com

D ' Andecy

Hatem Hamza
email: hatem.hamza@itesoft.com

Yolande Belaïd
email: yolande.belaid@loria.fl

Administrative Document Analysis and Structure

This chapter reports our knowledge about the analysis and recognition of scanned administrative documents. Regarding essentially the administrative paper flow with new and continuous arrivals, all the conventional techniques reserved to static databases modeling and recognition are doomed to failure. For this purpose, a new technique based on the experience was investigated giving very promising results. This technique is related to the case-based reasoning already used in data mining and various problems of machine learning. After the presentation of the context related to the administrative document flow and its requirements in a real time processing, we present a case based reasonning for invoice processing. The case corresponds to the co-existence of a problem and its solution. The problem in an invoice corresponds to a local structure such as the keywords of an address or the line patterns in the amounts table, while the solution is related to their content. This problem is then compared to a document case base using graph probing. For this purpose, we proposed an improvement of an already existing neural network called Incremental Growing Neural Gas

Introduction

One could think that paper is something from the past, that documents will all be "electronic" and that our offices and world is becoming paperless. This will be true one day, but it will take several decades or centuries because it is not only a technological mater but a real cultural issue. Even though they all surf and chat over the Internet, our kids still learn how to read with paper books and how to write with pen and paper. Whatever the future, if we just have a look today at our administration services such as public organisations and services (city hall), social security ser-vices (health insurance, family benefits, hospitals, pension funds ), large companies (bank, insurance) etc., they handle each day a large volume of documents from their citizens and customers. On the other hand they face several challenges in order to reduce the charges and increase the customer satisfaction. They do look for processing times reduction; process error reduction and delivery of new services that can share quickly electronic information in an internet or a mobile context.

One solution is to turn the administrative paper flow into an electronic document flow. That means digitize the documents, extract automatically by document analysis techniques some information from the content of these digital images, push the extracted indexes into a business system like an ERP (Enterprise Resource Planning) and finally archive the indexed images into a DMS (Document Management System).

For the last 20 years, several software editors have proposed intelligent systems to automatically read the administrative documents. The current most famous companies are EMC-Captiva, ReadSoft, Top Image System, Kofax, Itesoft, A2IA, AB-BYY, Nuancet, Pegasus, Mitek, Parascript,

The performance of these systems is a good enough fit for some business objectives on few documents such as cheques, invoices, orders or forms but the performance deteriorates quickly when the system faces the complexity and the large variability of administrative document types. Basically an administrative document is a textual document, usually a form. The issue is that the information to extract is very heterogeneous:

• The extracted information can be high level information like a document class (this is an invoice, a complain, a form) or low level information such as fields (invoice number, social security ID, cheque amount) or tables (list of ordered items). • The information can be machine printed (barcodes, characters, symbols, logos), hand-printed (script, marks) in a constraint frame or handwritten (cursive) with no constraint. • The information can be very structured like forms. For one form each field is always located at the same physical position. Notice that there is a vast amount of different administrative document structures. Then if the automation of one form can be quite simple, the automation of hundreds of forms in a single flow becomes a bottleneck. • The information can be semi-structured like bank cheques or invoices. The document looks like a structured document but the field location is floating, respecting only a logical structure. Each supplier prints the document in their own way but respecting (almost) for instance the rule <invoice number is closed to the top of the page beside the keyword "invoice no">. • The information can be unstructured like a free text in a natural language (handwritten mails). • The information can be explicit, directly readable within the document, or implicit, i.e. not directly readable but inferred from readable information, eventually combined with customer context data.

• The information can be isolated and easy to locate (printed or written on a white background) or with overlapping and then hard to segment (printed on a textured background or written over a comb or a printed text, ). • The information can be in color while most of the industrial capture systems produce binary images.

All the proposed systems rely on 2 important kinds of technologies:

• Classifiers to convert the pixels into symbols: OCR (Optical Character Recognition) for machine printed symbols, ICR (Intelligent Character Recognition) for hand-printed characters [START_REF] Grosicki | Results of the RIMES Evaluation Campaign for Handwritten Mail Processing[END_REF], IWR (Intelligent Word Recognition) for handwritten cursive words [START_REF] Bunke | Recognition of cursive Roman handwriting -past, present and future[END_REF] [2], Pattern Matching [START_REF] Llads | Symbol Recognition : Current Advances and Perspectives[END_REF] for some graphic elements, Logo Recognition [START_REF] Chang | Deformed trademark retrieval based on 2d pseudo-hidden markov model[END_REF] [6], etc.

• Segmentation and extraction strategies to locate and interpret the field to extract.

We identify two different techniques: the template matching approach [START_REF] Krishnamoorthy | Syntactic segmentation and labeling of digitalized pages from technical journals[END_REF] [8] and full-text approach [26] [31].

In the template matching approach, the extraction is driven by a mask. The mask defines an accurate physical location (bounding box) for each field to extract within the image. The system interprets the document in applying the classifier (OCR, ICR) to the snippet framed by the bounding box. In the industrial systems, the mask description is usually done by manual settings on a graphical interface. This is easy to handle, very efficient for fixed-structure forms, but is time-consuming when the user has to define many templates. Some researchers have proposed automatic model methods. The system builds itself the template by detecting graphical features: Duygulu [START_REF] Duygulu | A hierarchical representation of form documents for identification and retrieval[END_REF] uses horizontal and vertical lines; Mao [START_REF] Mao | A model-based form processing sub-system[END_REF], Ting [START_REF] Ting | Business form classification using strings[END_REF] use lines, logo, text lines; Hroux [START_REF] Hroux | Etude de mthodes de classification pour l'identification automatique de classes de formulaires[END_REF] uses pixel density; Sako [START_REF] Ishitani | Model based information extraction and its application to document Images[END_REF] uses keywords ; Cesarini [START_REF] Cesarini | Informys : A flexible invoice-like form-reader system[END_REF] uses both keywords and graphical features, Belaïd [START_REF] Belad | Saddok Kebairi: Adaptive Technology for Mail-Order Form Segmentation[END_REF] uses connected component sequences. These features are exploited by a physical structure analysis algorithm which can perform top-down analysis as RLSA based techniques [START_REF] Wahl | Block segmentation and text extraction in mixed text/image documents[END_REF]; bottom-up analysis for example, X-Y cut [START_REF] Nagy | A prototype document image analysis system for technical journals[END_REF] X-Y tree [START_REF] Duygulu | A hierarchical representation of form documents for identification and retrieval[END_REF] [START_REF] Krishnamoorthy | Syntactic segmentation and labeling of digitalized pages from technical journals[END_REF]; and generally said more efficient, hybrid approaches like Pavlidis Split & Merge [START_REF] Pavlidis | Page segmentation and classification[END_REF].

When the document flow contains heterogeneous documents that can not be described by a single template, then a classification step is required to select the adapted model. Some classification techniques rely on the same graphical features as described above. For instance Mao [START_REF] Mao | A model-based form processing sub-system[END_REF] uses also the lines to discriminate the document classes; Heroux [START_REF] Hroux | Etude de mthodes de classification pour l'identification automatique de classes de formulaires[END_REF] uses a vector of pixel density pyramid; Sako [START_REF] Sako | Form reading based on form-type identification and form-data recognition[END_REF] describes a document class with keywords. By extension, text classification strategy with vector of words [START_REF] Laroum | Hybred: An OCR document representation for classification tasks[END_REF] can be used. For instance EMC, Itesoft and A2IA products integrate both graphical and textual classifiers. With these features many categorization algorithms have been explored like decision trees, nearest neighbour [START_REF] Zhong | Efficient online spherical k-means clustering[END_REF] [12], neural networks [START_REF] Vapnik | A note on one class of perceptrons[END_REF] [13], prototype-based methods, support vector machines [START_REF] Bartlett | Generalization performance of support vector machines and other pattern classifiers[END_REF] The automatic model is an interesting method but limited to one or few similar document classes. In fact the features and the document structure analysis hardcode the application domain: invoices [START_REF] Cesarini | Informys : A flexible invoice-like form-reader system[END_REF], orders [START_REF] Belad | Saddok Kebairi: Adaptive Technology for Mail-Order Form Segmentation[END_REF], cheques, forms or tables [START_REF] Mao | A model-based form processing sub-system[END_REF]. Therefore if the method allows a good flexibility in the domain scope, it can not manage heterogeneous flows without an important development invest. The full-text approach answers to this issue.

In the full-text approach, the extraction is driven by the data itself and a set of rules (knowledge base) to find logical labels [START_REF] Kim | Automated labeling in document images[END_REF]. The rules can be parametrized by a user or trained on labeled documents like Cesarini [START_REF] Cesarini | Trainable table location in document images[END_REF] who trains an M-X-Y tree to learn the table structures. Most of the approaches are formal grammar based as in Couasnon [START_REF] Coasnon | a generic document recognition method : application to table structure analysis in a general and in a specific way[END_REF] or Conway [START_REF] Conway | Page grammars and page parsing: A syntatic approach to document layout recognition[END_REF]. Niyogi [START_REF] Niyogi | Knowledge-based derivation of document logical structure[END_REF] presented a system called DeLoS for document logical structure derivation. Dengel [START_REF] Dengel | Computer understanding of document structure[END_REF] described a system (DAVOS) that is capable of both learning and extracting document logical structure. Grammar and tree-representation seem to be a major area of research, the technique can even work for specialized tasks such as table form recognition [START_REF] Sako | Form reading based on form-type identification and form-data recognition[END_REF]. A few systems try to learn the relationship between physical and logical structures [START_REF] Sainz Palmero | A new neuro-fuzzy system for logical labeling of documents[END_REF] that do not focus especially on logical labeling. These systems can outperform classical rule base systems because they use more flexible models, which can tolerate variations of the structure [START_REF] Lebourgeois | Using statistical models in document images understanding[END_REF]. In most recent works, new human brain based approaches have been developed: Rangoni [START_REF] Rangoni | Data Categorization for a Context Return Applied to Logical Document Structure Recognition[END_REF] combines learning and knowledge integration by using a transparent neural network; However all these systems face the same problems:

• Any segmentation and extraction strategies need an expert to describe the documents and "teach" the system. These settings or training are still time consuming and not often final-user friendly. • Only few solutions address the full scope of heterogeneous information.

• The solutions depend on the intrinsic performance of the character classifiers.

These classifiers are very efficient in standard contexts but usually collapse in noisy context.

We proposed in [START_REF] Hamza | Case-Based Reasoning for Invoice Analysis and Recognition[END_REF] a case-based reasoning system to model and train the knowledge for the recognition of administrative documents corresponding to different kind of invoices. They have a typical format that changes depending on the issuing company or administration. It may vary and evolve even within the same company. To cope with these changes, we seek to develop a system able to rely on experience to recognize new samples. The case-based reasoning seems to be a methodology capable of meeting this challenge. We will first describe the methodology, then we will show how we exploit it in the case of invoices. This chapter will be organized as follows. Section 2 provides a general definition of CBR, explaining its various components. Then, Section 3 shows the use of CBR for document analysis. The proposed approach is described in Section 4. Experiments on invoices are detailed in Section 5. Finally, we conclude and give some perspectives of this work in Section 6.

Case-Based Reasoning

The case-based reasoning (CBR) is a reasoning paradigm that uses past experiences to solve new problems [START_REF] Aamodt | Case-based reasoning : Foundational issues, methodological variations, and system approaches[END_REF]. It is applied today in all areas where we need to use or synthesize past experiences to propose new solutions. Early work in CBR has been proposed in 1983 by Kolodner [START_REF] Kolodner | Maintaining organization in a dynamic long-term memory[END_REF], which created a system of questions and answers using a knowledge base already established.

CBR is based on several steps we will detail in this paper. Several models have been proposed to define the CBR (see Fig. 1), but the most common is that of Aamodt and Plaza [START_REF] Aamodt | Case-based reasoning : Foundational issues, methodological variations, and system approaches[END_REF]. It consists of four steps: research, reuse, revision, retention (or learning). A preliminary step, also needed, is the formulation of the problem. In this work, we combined stages for reuse and review a step conventionally called "adaptation". This is also done in most researches in CBR.

CBR Terminology

In CBR, a problem is posed by the user or the system. That is the part to resolve. A case is the set formed by the problem and its solution.

case = {Problem, Solution}

We call "target case" the case to solve and "source case" the case from the case base used to solve the target case. The base case is the core of the system cases. These are either given by the user, or by the system automatically enriched.

Problem elaboration

This phase involves the indices and problem descriptors extraction, and their representation. It can be done either by the user who, based on his data, constitutes the problem to solve, or by the system which knows itself how to elaborate a problem based on available information. For example, in the system FAQFinder [START_REF] Burke | Knowledge-based information retrieval from semistructured text[END_REF], the system input is a question given by the user. The question is then processed by the system which extracts the problem (extraction of the most significant terms, removing the less informative terms). The final problem in FAQFinder is a vector representing the query.

Similar case search

Similar case search is one of the most important parts of CBR. It involves taking into account the representation of cases, a measure of similarity between cases and the choice of one or more close cases. The similarity measure between cases is often limited to a similarity measure between problems. It depends directly on the data representation and complexity. Once the similarity measure appropriate to the problem is chosen, it becomes easy for each new problem, to find similar cases in the case base.

Adaptation

The adaptation is to find a solution to the target problem from a solution given to the source problem . The solution to the source problem should be kept or modified to allow the proposal of a new solution to the target problem. Two major categories of adaptation exist in the literature:

• Structural adjustment: it tries to apply the solution of the source case through some changes, taking into account the differences between source and target problems, on the target problem.

• Derivational adaptation which traces how the source solution has been proposed to produce the solution to target. This is particularly true for planning applications for example.

These two broad categories can be broken down into several types of other adaptations [START_REF] Watson | Case-based reasoning : A review[END_REF]. The simplest, and it's one we'll use is the zero adjustment. It consists, from the solution of the problem source, to "paste" the solution on the target problem. This adaptation, although it is very simple, solves problems as the case of documents for example.

Learning

The role of the learning is to integrate new solved and revised cases in the case base. This process must be designed to avoid filling the database with each new case resolved (redundancy can be dangerous for the system as far as it can slow it down considerably). It allows the system to manage its knowledge. We propose here an interesting solution for classifying the case base. We stand where the case base is constantly fed with new cases resolved as different, and we try to build a system to classify these cases so as to always have quick access to the database.

CBR for Document Image Analysis: CBRDIA

In an administrative Document Image Analysis (DIA) system, it often happens that documents are processed in batches. We call batch a set of similar documents, from the same supplier, the same company or administration. Documents in a batch all have the same characteristics, they are represented in the same manner and only the specific content of each document is different (for example, the cell contents in a form). Currently, in a company, a batch requires a user intervention to model the material on this batch. From the model, it becomes easier for the system to extract the desired information in the document.

The first problem is to try to model documents automatically in a batch and use this model later on the batch. The second problem is more complex. The system must also be able to handle heterogeneous documents. In this case, two configurations are possible:

• The first, and it is the easiest, is the case of the document for which you can find a similar model. This means that documents similar to this document have already been treated before, and it can speed up the processing. Documents in Figure 2 have exactly the same structures. As well the tables as the address structures and payment are similar. It is clear then that knowing the general model of this batch, it becomes very easy to treat all documents belonging to this batch.

• The second is more complex. This is the case of a completely new document, for which no existing model can be associated, and must of course be analyzed. The easiest solution is to appeal to a user who will help to extract the necessary information.

Fig. 2 Two invoices from the same batch. The model of these documents is the same These two problems raised other issues as important:

• how to model documents, what information must be represented in this model,

• how to take advantage of existing templates,

• which approach to take for that user intervention is minimal.

In our application, the system tries to analyze the documents individually, without resorting models of existing documents. The example of invoices in Figure 3 shows two invoices from two different batches. It is clear that both invoices should not (and can in fact not) be treated in the same way. Special treatment should be performed on each of them. The ideal solution would be to try to enjoy the experience of the system, instead of the user. As to treatment, the system accumulates the experience of document analysis. After a while, it is certain that the system has treated so many different documents that the knowledge it gained could be used to analyze any type of documents. We must therefore take advantage of that knowledge. This is the main idea of the solution to the problems mentioned above. We will therefore introduce a system that not only deals with documents, but also learns as you go.

For this reason we chose to use CBR for the proposed system. First, the existing mode of reasoning in CBR is well suited to the needs of a system for document analysis. Indeed, CBR can benefit from previous experiences to offer new solutions to new problems. In the case of our application, a new problem is simply a new document to be analyzed. The fact that this document be in a batch or completely new does not change the fact that we must be able to analyze and interpret. Previous experiences are therefore other than documents previously modeled, analyzed and interpreted.

The proposed approach

Figure 4 shows the block diagram of our approach. It consists of two CBR cycles. For each new document, the problem is first extracted. This is compared with document problems of the case base. • If no similar problem exists in the case base, then we proceed to the next CBR cycle. The structure problems are used. Each structure issue is compared with the problems of the structure case base. The solutions of the closest problems are then applied to the problem of target structure. Through this process we can obtain a complete solution for the document problem. So we can inject this resolved case in the document case base.

Document structures

The document structures constitute in our approach the problems in CBR terminology. The documents that are used in our approach are real world documents taken from a document processing chain. First, they are OCRed thanks to some commercial softwares combined with other local built OCRs. The OCR output is then all the document words with their coordinates in the document. These words have to be organized in a more logical way. For this, we create groups of information given below:

1. Words: which are returned by the OCR. They are given the following attributes: position (top, left, right, bottom), tags (alphabetical, numerical, alphanumerical). 2. Fields: which are groups of neighbor words aligned horizontally. They are given the following attributes: positions and tags. The field tags correspond to the concatenation of the tags of the words composing the field. 3. Horizontal lines: which are groups of neighboring fields. They are given the following attributes: position, pattern. A pattern is the concatenation of the tags of the fields composing the horizontal lines. 4. Vertical blocks: which are groups of fields aligned vertically. They are given the following attributes: position coordinates.

From this physical re-structuring of the document, we extract now the logical structure. We have noticed through our observations on thousands of documents that two kinds of structures exist in invoices:

• The first one is the keywords structures (KWS) that are based on the extraction of some keywords. This extraction uses semantic dictionaries related to the domain of invoice (example: words like Amount, VAT, Total...).

Problem representation

The final document model is a graph of the different structures of the documents. This representation allows us not only to describe a document, but also a whole class of documents. In this way, whenever a document from the class 'X' is presented to the system, it can be directly recognized as belonging to this class. The example in Figure 5 shows clearly how two documents can be represented with the same model. Figure 6 shows a document model. This document is composed of two KWS. It can be clearly seen that the nodes are the document keywords, or the labels of the structures, whereas the edges describe the relative positions between the elements.

Problem solving

Once the document model is extracted, global problem solving starts. It consists of checking if a similar document is available in the document database (using graph probing or edit distance). If it is the case, then the solution of the nearest document is applied on the current document. Otherwise, local solving is used. It consists of finding a solution for every structure (KWS or PS) in the document independent of others. Similarly, as in global solving, the system looks for similar structures in the structure database and tries to apply the solution of the nearest ones on the current structures. Figure 4 shows the flow of this approach. Further details can be found in [START_REF] Hamza | Case-based reasoning for invoice analysis and recognition[END_REF].

Graph matching using graph probing

In CBRDIA, every document is to be matched with the documents of the database. Since our documents are represented by graphs, graph matching techniques have to be used. Many graph similarity measures exist. Edit distance as well as the maximum common subgraph distance can be employed, but time and complexity are factors that lead us to think about a faster similarity measure.

Graph probing distance is a graph dissimilarity measure that was first presented in [START_REF] Lopresti | A fast technique for comparing graph representations with applications to performance evaluation[END_REF]. It is a fast and fairly accurate technique of graph comparison. It has also a direct relation with graph edit distance. Let G1 and G2 be two graphs, then d graphprobing (G1, G2) ≤ 4.d editdistance (G1, G2). Quite often graph probing is a good approximation of graph edit distance. Its principal drawback is the fact that if d graphprobing (G1, G2) = 0, then G1 and G2 are not necessarily isomorphic.

Graph probing is based on the computation of the frequency of each vertex and each edge in its graph. Let A, B, C be the nodes of G1, and B, C, D be the nodes of G2. First, we compute the frequency of A, B, C in G1, and do the same with the nodes of G2. The probe on nodes is then: Pb1 = ∑ | f req(N G1 )f req(N G2 )|, where f req(N G1 ) and f req(N G2 ) are respectively the frequencies of a node N in G1 and G2.

On the other hand, we have to calculate the probe on edges. For every node, we extract its edge structure. If a node N has an edge with the tag (top, left) and another one with the tag (top, right), then the edge structure of N is (top:2, left:1, bottom:0, right:1). This is done for every edge in the graph. The probe over edges is then Pb2 = ∑ | f req(E G1 )f req(E G2 )|, where f req(E G1 ) and f req(E G2 ) are respectively the frequencies of an edge structure E in G1 and G2.

The total probe is then:

Pb = Pb1 + Pb2.
Graph probing is applied in this way to every new document in order to find the most similar document in the database.

Incremental learning in CBRDIA

Now that new cases of documents have to be learnt, incremental learning is adopted. It allows the system to use the solved cases in the future and to avoid the same processing for every similar document. Incremental learning is used as the following: every new case has to be learnt and retained by the case base. Moreover, similar cases have to be grouped together in order to make the comparison between an incoming case and the case base more accurate.

To find an approach of incremental learning, we focused on incremental neural networks. The earliest incremental neural networks were the Growing Cell Structures (GCS [START_REF] Fritzke | Growing cell structuresa self-organizing network for unsupervised and supervised learning[END_REF]), followed by the Growing neural Gas (GNG). Then, many other variations were built on these two networks. The Hierarchical GNG (TreeGNG) is a network that builds classes over the classes given by the GNG. Similarly, the Hierarchical GCS (TreeGCS [START_REF] Hodge | Hierarchical growing cell structures: Treegcs[END_REF]) uses the same principle. Other types of incremental neural networks are those which use self organizing maps. One has to make the difference between incremental neural networks which perform incremental learning (GNG, IGNG) and incremental neural networks which are just incremental because they can add or remove neurons. We will just introduce IGNG in this paper as it is the method we are using.

Incremental Growing Neural Gas

The IGNG is an improvement of the GNG in some aspects (algorithm explained below). As shown in [START_REF] Prudent | A new learning algorithm for incremental self-organizing maps[END_REF], IGNG gives better results for online and in incremental learning. This can be explained by the fact that IGNG creates neurons only when a new datum is very far from the already created neurons, contrary to the GNG which creates neurons periodically. IGNG has also better memory properties. This means that when a new class of data having different properties appears, the IGNG can really adapt its topology without loss of the previous information, whereas the GNG can lose some of its already created neurons.

This neural network IGNG suffers however from the choice of the threshold S. In their original paper, Prudent et al. proposed to initialize S at the standard deviation of the whole database for which classification is done. This is in our opinion contrary to the principles of incremental learning as we do not know apriori which kind data is coming later.

IGNG improvement

The first point on which we worked was to try to be free from the choice of the threshold S. The first constraint is that the only information available at a time T is the information about the already processed data. Moreover, we cannot use the whole previous data to determine the class of the new data. The solution is to use some local information related to each neuron. Let:

• N be the number of IGNG neurons at T. • E be an entry. • m i be the average distance between every element in a class i and its representative neuron n i . σ i the standard deviation of these distances.

It is logical to say that E belongs to a class i if d(E, n i ) < m i . In order to be more flexible, we propose that the threshold S becomes: S = m i + α.σ i , where n i is the nearest neuron to E. By taking into account the mean and standard deviation of this class, we are using intrinsic parameters related to this class, not to the whole data. Two cases typically occur:

• the new data is close enough to the nearest class (meaning d(E, n i ) < m i +α.σ i ), this data will belong to the class i and the neuron n i is updated. • the new data is too far from its nearest class. In this case, a new neuron is created (embryon neuron), and becomes effective in classification only if its age exceeds a neuron max .

Figure 7 shows a typical case where the nearest class is too far from the new data. This new data will then create an embryon neuron.

Node deletion

The second point of interest is the condition of node deletion. In GNG and IGNG, an edge is removed whenever its age exceeds a threshold a edge . Then, if a neuron is not connected to any other neuron, it is removed as well. However, depending on the application, one may not want to remove neurons that are not connected to others, as these single neurons may represent an important information (eventhough it can be very rare). For example, in our application, some rare invoices can be processed from time to time, and can in this way form neurons that are very far from the other neurons. A simple example is shown on Figure 8. The neuron representing the rare data (X) is connected to two other neurons (Y and Z) which have many more data compared to X. Every time a data is attributed to Y or Z, the edges (X-Y) and (X-Z) are incremented. When age(X -Y ) > a edge and age(X -Z) > a edge , these edges are removed. In the classical scheme, X will also be removed. Moreover, its data will be assigned to its nearest neurons in the network (Y and Z). Then, even if Y and Z are not representative of the data associated with X, their data will include new data very different from their original data.

We propose in this case to examine the distance between X and its nearest neuron, let this distance be d(X,Y). If d(X,Y ) > β • ((m y + α.σ y ) + (m x + α.σ x )), then this X has to be kept in the network, even if it has no connection with the other neurons. Otherwise, this neuron can be removed and its data can be assigned to the other neurons. The β factor can be chosen by the user, depending on the application. Fig. 8 A neuron that should not be deleted, even if it is not connected to any other neuron From now on, the Improved Incremental Growing Neural Gas will be noted I2GNG.

Adaptation to the case of graph classification

In [START_REF] Gunter | Self-organizing map for clustering in the graph domain[END_REF], Gunter and al. proposed a method of adapting Self Organizing Maps (SOM) to graph classification. This method was used to digit classification and was based on the computation of the edit distance between graphs. Every formula in the SOM algorithm was then adapted based on the edit path between any two graphs. Here is a simple explanation of the idea: let G1 and G2 be two graphs. Let d(G1,G2) be the edit distance between G1 and G2. This distance corresponds to the cost of some additions, deletions or substitutions of nodes or/and edges which transform G1 into G2.

d(G1, G2) = ∑ cost(editing)
In the vector domain, when the distance between a vector X and vector Y is d(X,Y), it is easy to transform X by ε(X,Y ), ε being a real quantity. The same operation in the graph domain means that G1 has to be modified by β = ε •d(G1, G2) (equivalent to Neuron = ε b .(Neuron nearestentry)). Modifying G1 by β means that we have to apply only β edit operations on G1. As we already know the edit path that allowed us to compute the distance between G1 and G2, β corresponds just to a part of this edit path. Modifying G1 becomes in this way an easy task as we just have to find the edit operations which cost approaches β as much as possible. More elaborate details can be found in [START_REF] Gunter | Self-organizing map for clustering in the graph domain[END_REF].

Adapting the I2GNG formula using the principles cited above allows us now to classify graphs or trees using I2GNG.

Experiments

The first part of these experiments shows the results of the whole CBRDIA system. The second experiments are only related to incremental learning using administrative documents.

Experiments on CBRDIA

CBRDIA was tested on 950 invoice documents taken from invoice processing chain of ITESOFT. They are divided in 2 groups:

• the first one contains 150 documents where each one has a similar case in the document database: this is used to test global solving. The document database contains 10 different cases; • the second one contains 800 documents for which no associated case exists in the document database. Hence, local solving will be applied on these documents.

The results are described thanks to three different measures as in 1. In this equation, X can be a document, a KWS or a PS.

R X = | f ound solutions | |solutions in ground truth X| . (1)
Global solving produced 85.29% of good results whereas local solving produced 76.33%. More detailed results can be found in [START_REF] Hamza | Case-based reasoning for invoice analysis and recognition[END_REF].

Experiments on administrative documents

Our experiments were performed on a dataset of real documents (invoices) taken from a real invoice processing chain. Every invoice was modeled with its graph and then submitted to the I2GNG. The complexity of these documents is variable. Whereas some documents are very clean and have almost no OCR errors, others can be degraded and have very few key-words to be identified.

The dataset was divided in two parts: a learning set (324 documents) and a testing set (169 documents). 8 classes of invoices were used for this purpose. We chose this strategy of I2GNG evaluation as the learning procedure helps in knowing about the incremental capabilities of the modified I2GNG applied to graphs, whereas the testing phase helps knowing about its classification properties.

We performed two different series of tests. The first one is concerned with the influence of α, the second one concerns the influence of the threshold age of neurons (above which neurons become mature). Table 1 The results show that the number of neurons is always greater than the number of classes [START_REF] Yamashita | A model based layout understanding method for the document recognition system[END_REF]. This is due to the variations found in these classes. Representing one class with several neurons is not a problem as far as a neuron is not shared by two classes. In the training process, we tag manually the obtained neurons (by giving them the name of the class they represent).

The obtained results are very encouraging. They mean that the I2GNG with our improvements is working well. As shown in table 1, the bigger α is, the more neurons we obtain. This can be explained as the following:

• when α is big, the threshold (m + α.σ ) for each neuron is also big. A new class is created if and only if it is outside the range of an existing neuron. Neurons are then not close to each others. Their ages increase quickly and they become mature quickly too. • on the other hand, when α is small, neurons are very close to each other. One class can be represented by high number of neurons, few of which become mature because of the high competition among classes.

Conclusion

In this paper, we presented the different steps composing the system CBRDIA. This system and its incremental learning part have been implemented and tested on real data. An existing neural network was improved and extended to graph classification. The obtained results are satisfying, but some work still needs to be done in order to improve the performance of the I2GNG. Two studies are being done. The first one concerns the automation of the choice of the maximum ages of edges and neurons. These parameters have an influence on the final results. The second study concerns α the choice of which can be done using some characteristics of the studied neuron. For example, we can use the density of a class, its entropy or other descriptors to get an adaptive α.

We have demonstrated that the Case-Based Reasoning approach is natively adapted to heterogeneous document flows because each document is a case. The aim of the system is to organize and retrieve the different cases from an incremental knowledge base and moreover to adapt the previous knowledge to cope with a new document. The major concept of the adaptation approach comes from the observation that, specifically in the invoicing domain, the data (address, invoice date, amount) are often presented in few similar ways, in spite of each supplier editing and printing the invoices by its own feeling. Therefore, the 2-scales reasoning Global and Local approach demonstrates how it is possible to benefit from the redundancy of local structures to automatically model a whole new document.

This adaptation feature should reduce the time spent on modeling, which is one of the most important issues of Administration Documents Processing systems in the face of a large heterogeneous document flow.

In addition to invoices, this system can be applied directly to a very large majority of administrative documents in all domains: insurance, health, banking. We should recall that document processing targets the extraction of a finite set of indexes. These indexes are framed by business definitions obviously shared by the writer and the reader, otherwise there is no communication. Each writer can be free to organize the information set within a document and then introduce a large variety of documents. But the various ways to represent an index may converge, depending the accuracy of the business definition. Very formalized indexes will be very redundant (social security number for instance) and, on the other hand, indexes explained in a natural language text will support a batch of representation (that cannot be modeled by a structure).

Another perspective is to generalize the multi-scale CBR approach to manage the document flow structure. So far we have dealt only with documents, and supposed that the system input is the document. This supposition is true from a functional point of view. The end user handles each document separately and may define a data-extraction scope for each document. This is why all document analysis systems use the document scale as the system input scale. In fact the document is not the input scale but the output scale. The real input of the system is the result of the capture process: single page images. Using a fax machine or a desktop scanner, the user can digitize documents one by one. This makes sense when the user digitizes one or two documents, it makes no sense when production scanners which capture 1 000 to 10 000 pages per hour are used. Here the paper documents are turned into a flat sequence of page images. The challenge is then to segment the flat sequence into a structured document flow. The easiest solution is to introduce document separators (white sheets for instance) when preparing the batches to capture. This takes time and is paper-consuming. The other solution is document analysis to identify certain master documents in order to trigger the flow segmentation. For instance, a document starts at each page nb. 1 of an invoice or at each cheque. This solution supposes modeling of the flow sequence and the ability to identify before segmenting. To complete the complexity we should note here that the flow structure can be a multi-level tree: for instance the end users payment business document is a complex document composed of two more natural documents that are one (multi-page) invoice plus one cheque. We believe that we can expand the multi-scale CBR system in adding new CBR cycles to model the whole flow. We expect in this very global system to take advantage of redundancy in the documents and sub-structures at each level of the tree to enlarge the system scope and minimize the end users conception efforts.

Introducing the Case-Based Reasoning combined with Optical Character Recognition and Document Structure representation is a new step from Vision to Artificial Intelligence. For the last 40 years, the biggest challenge was to interpret the pixel into more symbolic information: characters, words, tables introducing more and more language models and semantic information to drive recognition. This pure recognition challenge is far from being solved, but the solution has reached a good enough level of quality to move slowly away from the document analysis scope towards a more ambitious document understanding scope. We now do not just ask the computer to read information and follow a fixed analysis process, defined by a grammar or a technical template. We can now ask the future system to simply learn from samples, to build its own rules, to infer new knowledge and to memorize enough of it so that human assistance is no longer needed.

If you will allow us the following comparison: the document reader system was yesterday a little boy able to recognize some patterns. He can today re-use part of his experience and learn himself from read documents in order to infer all this information onto new documents. On our side we will continue to raise our little boy and we wish you to conceive many brothers.

Fig. 1

 1 Fig. 1 CBR paradigm

Fig. 3

 3 Fig. 3 Two invoices from different batches.

Fig. 4

 4 Fig. 4 CBRDIA flow

Fig. 5

 5 Fig. 5 Two documents from the same class

Fig. 6

 6 Fig. 6 A document model

Fig. 7 A

 7 Fig. 7 A new data creates an embryon neuron

•

  The second type of structures is tables which are very important structures in administrative documents. As tables correspond generally to a repetition of a pattern, these structures are called pattern structures (PS). Once these two types of structures are extracted, the document model takes them into account as well as their relative positions (top, left, bottom, right). Further details about our document model extraction, and especially on table extraction can be found in[START_REF] Hamza | Case-based reasoning for invoice analysis and recognition[END_REF].

Table 1

 1 gives these results. influence of α and a edge

	a edge neurons rec	α	neurons rec
	10 14	99.40% 0.5	10	98.22%
	20 18	97.63% 1	15	98.22%
	30 18	97.63% 1.5	12	98.81%
	40 16	98.22% 2	14	98.81%
	50 16	98.22% 2.5	12	99.40%
	60 16	98.22% 3	18	97.63%