Thi Minh

Dung Tran

Alain Y Kibangou
email: alain.kibangou@ujf-grenoble.fr

Distributed Estimation of Graph Laplacian Eigenvalues by the Alternating Direction of Multipliers Method

Keywords: Graph Laplacian, Eigenvalues, Distributed optimization, Alternating Direction of Multipliers Method, Average Consensus

This paper presents a new method for estimating the eigenvalues of the Laplacian matrix associated with the graph describing the network topology of a multi-agent system. Given an approximate value of the average of the initial condition of the network state and some intermediate values of the network state when performing a Laplacian-based average consensus, the estimation of the Laplacian eigenvalues is obtained by solving the factorization of the averaging matrix. For this purpose, in contrast to the state of the art, we formulate a convex optimization problem that is solved in a distributed way by means of the Alternating Direction Method of Multipliers (ADMM). The main variables in the optimization problem are the coefficients of a polynomial whose roots are precisely the inverse of the distinct nonzero Laplacian eigenvalues. The performance of the proposed method is evaluated by means of simulation results.

INTRODUCTION

Investigating the relationship between the structure of a graph and its eigenvalues is the central topic in the field of algebraic graph theory, [START_REF] Merris | Laplacian matrices of a graph: a survey[END_REF]; [START_REF] Chung | Spectral Graph Theory[END_REF]. In particular, the spectrum of the Laplacian matrix has a direct connection to the behavior of several networked dynamical processes. For example, the second smallest eigenvalue of a Laplacian matrix, i.e., the graph algebraic connectivity of the graph, [START_REF] Friedler | Algebraic connectivity of graphs[END_REF], is known to have the main role in the convergence time of various distributed algorithms. It is also a critical parameter that influences on the performance and robustness properties of dynamical systems operating over an information network. From the spectrum of the graph Laplacian matrix, we can also infer bounds on the graph diameter and state the connectedness of the graph, [START_REF] Friedler | Algebraic connectivity of graphs[END_REF]. Moreover, it can be utilized for checking the controllability and observability of the system, [START_REF] Franceschelli | Observability and controllability verification in multi-agent systems through decentralized Laplacian spectrum estimation[END_REF]. A comprehensive survey on properties of Laplacian of undirected graphs can be found in [START_REF] Merris | Laplacian matrices of a graph: a survey[END_REF].

In the recent literature devoted to multi-agent dynamic systems, several issues are formulated as a consensus problem, which is to design a network protocol based on the local information obtained by each agent, such that all agents finally reach an agreement on certain quantities of interest. The network protocol is an interaction rule, which ensures that the whole group can achieve a consensus on the shared data in a distributed manner, i.e. without the coordination of a central authority. In the study of consensus problems, the speed of convergence is usually an important index to evaluate the efficiency of the corresponding protocol. For networks modeled with undirected graphs, when using Laplacian-based consensus matrices, also known as constant edge weights protocol, it has been shown that, for speeding up the convergence in an average consensus problem, the optimal consensus matrix depends on both the largest and the smallest nonzero Laplacian eigenvalues, [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF]. More recently, it has been shown that all the spectrum of the Laplacian matrix can also be used for designing consensus matrices in order to achieve the average consensus in a finite number of steps, [START_REF] Kibangou | Finite-time average consensus based protocol for distributed estimation over AWGN channels[END_REF][START_REF] Kibangou | Graph Laplacian based matrix design for finite-time distributed average consensus[END_REF]. Such a conclusion is based on the fact that the averaging matrix, J N = 1 N 11 T , can be written as a product of Laplacian-based consensus matrices parameterized by the inverse of the Laplacian eigenvalues. Therefore, computing the eigenvalues of the Laplacian matrix is an important issue and solving this problem in a distributed way is particularly challenging.

During the current decade, various studies have been carried out on decentralized algorithms for estimating the Laplacian eigenvalues. For instance, in [START_REF] Yang | Decentralized estimation and control of graph connectivity in mobile sensor networks[END_REF], the second smallest Laplacian eigenvalue was estimated by resorting to a decentralized power iteration method. In [START_REF] Aragues | Distributed algebraic connectivity estimation for adaptive event-triggered consensus[END_REF], the algebraic connectivity was estimated by counting on the distributed computation of the powers of a deflated Laplacian matrix. In [START_REF] Sahai | Hearing the cluster of a graph: A distributed algorithm[END_REF] and [START_REF] Franceschelli | Decentralized estimation of Laplacian eigenvalues in multi-agent systems[END_REF], Fast Fourier Transform (FFT)-based methods were suggested. The main idea in these works is to make the state of each agent oscillate only at frequencies corresponding to the eigenvalues of the Laplacian matrix associated with the network topology. The problem is then mapped into a signal processing one that can be efficiently and independently solved by each agent in applying the Fast Fourier Transform (FFT). The approach in [START_REF] Franceschelli | Decentralized estimation of Laplacian eigenvalues in multi-agent systems[END_REF] involved twice communication burden compared to that in [START_REF] Sahai | Hearing the cluster of a graph: A distributed algorithm[END_REF]. However, both methods inherit the limitations of the FFT-based algorithm. In particular, the resolution of the estimated eigenvalues is strongly dependent on that of the FFT-based method and the accuracy depends on the amount of stored data. In contrast, in [START_REF] Kibangou | Decentralized Laplacian eigenvalues estimation and collaborative network topology identification[END_REF], the authors resort to an algebraic method using observability properties of the network. With this method, the eigenvalues of the network matrix can be recovered by solving a local eigenvalue decomposition on an appropriately constructed matrix of observed data. In addition, this approach also provides multiplicities of Laplacian eigenvalues. However, this method is only applicable to networks having nodes with sufficient storage and computation capabilities. In [START_REF] Tran | Consensus-based distributed estimation of Laplacian eigenvalues of undirected graphs[END_REF], the authors have proposed a method for estimating the distinct nonzero Laplacian eigenvalues by solving the factorization of the averaging matrix as a product of Laplacian-based consensus matrices. Precisely, an equality constrained consensus problem, which turns to be a non-convex optimization problem, was formulated. A gradient backpropagation method was proposed. Despite the efficiency of that method, only convergence towards local minima can in fact be guaranteed. In addition, speed of convergence was particularly slow. It is worth noting that the authors assumed that the number of the distinct nonzero Laplacian eigenvalues was known, which is a strong assumption fulfilled by few families of graphs such as strongly regular graphs (two nonzero distinct Laplacian eigenvalues) and distance regular graph (the number of nonzero distinct Laplacian eigenvalues equals the diameter of the graph), [START_REF] Kibangou | Step-size sequence design for finitetime average consensus in secure wireless sensor networks[END_REF].

In this paper, we propose a novel method to deal with the distributed estimation of the Laplacian eigenvalues. Herein, the number of distinct Laplacian eigenvalues is unknown. Furthermore, the proposed method is shown to be efficient for solving the problem when the exact average value is not known. The proposed solution results on solving a convex optimization problem in a distributed way. The Alternating Direction of Multipliers Method (ADMM), that has received a great attention from the community due to its easy implementation, fast convergence, and good accuracy, is adopted to solve the problem, [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]; [START_REF] Erseghe | Fast consensus by the alternating direction multipliers method[END_REF].

The remainder of this paper is organized as follows: in Section 2, we recall some properties of the graph Laplacian and its connections with the average consensus problem. Then, the proposed method is described in Section 3 for solving a constrained optimization problem. The performance of the proposed method is evaluated in Section 4 by means of simulation results before concluding the paper.

LAPLACIAN SPECTRUM AND AVERAGE CONSENSUS

Average consensus

Consider a network of N agents characterized by local values

x i ∈ ℜ, i = 1, • • • , N.
The interactions between these agents are modeled by means of a connected undirected graph G(V, E), where V and E denote the node set (vertex set) and the link set (edge set) respectively. Average consensus algorithms can be seen as the distributed solution of an optimization algorithm whose goal is the minimization of the disagreement between the nodes in a given network, [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF]. In other words, average consensus resorts to minimizing the cost function

Φ G (x) = x T Lx = 1 2 ∑ (i, j)∈E (x j -x i ) 2 , ( 1
)
where x = [x 1 , x 2 , ..., x N ] T denotes the network state whereas L stands for the Laplacian matrix, which is a double stochastic matrix whose entries are given by l ii = d i , l i j = -1 if (i, j) ∈ E, and l i j = 0 elsewhere, where d i stands for the degree of agent i, i.e. the number of agents that are adjacent to agent i.

Starting from an initial state x i (0) = x i and using a steepest descent method, the following linear iteration scheme is obtained:

x i (t) = x i (t -1) -α ∑ j∈N i (x i (t -1) -x j (t -1)), (2)
where N i = { j ∈ V : (i, j) ∈ E} denotes the neighborhood of node i. In matrix form, we get:

x(t) = (I N -αL)x(t -1),
(3) or equivalently

x(t) = (I N -αL) t x(0) = t ∑ i=0 ( t i ) (-1) i α i q(i), (4)
where q(i) = L i x(0). By appropriately selecting the stepsize α, (0 < α < 1 d max ), with d max = max{d i }, all nodes converge asymptotically to the same value that is the average of the initial ones, [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF]:

lim t→∞ x(t) = x = 1 N 11 T x(0). Let Sp(L) = {λ m 1 1 , λ m 2 2 , • • • , λ m D+1
D+1 } be the Laplacian spectrum (the set of Laplacian eigenvalues), where m i stands for the multiplicity of the i-th eigenvalue,

D+1 ∑ i=1 m i = N, λ 1 = 0, m 1 = 1, and λ 1 < λ 2 < • • • < λ D+1 .
It is well known that the speed of convergence of (3) depends on the smallest nonzero Laplacian eigenvalue λ 2 . In [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF], it was shown that by selecting the step-size α of the average consensus algorithm as 2 λ 2 +λ N , the fastest Laplacian-based consensus algorithm is obtained.

Let Λ = {λ 2 , λ 3 , • • • , λ D+1 } be the set of nonzero distinct Laplacian eigenvalues. It has been shown that the averaging matrix can be factorized as, [START_REF] Kibangou | Graph Laplacian based matrix design for finite-time distributed average consensus[END_REF]:

J = 1 N 11 T = D ∏ t=1 (I -α t L) , α t 1 ̸ = α t 2 if t 1 ̸ = t 2 , 1 α t ∈ Λ,
as a product of D Laplacian-based consensus matrices parameterized by the inverse of a given Laplacian eigenvalue. Therefore, the averaging matrix is a polynomial of the Laplacian matrix:

J = P c (L) = D ∑ t=0 c t L t , with c r = (-1) r ∑ i< j<...<r α i α j . . . α r , r = 0, . . . , D (5)
and specifically c 0 = 1 and c D = (-1) D ∏ D t=1 α t . As a conse- quence, by following the linear iteration scheme x(t) = (Iα t L)x(t -1), with α t given by the inverse of Laplacian eigenvalues, average consensus is achieved in D steps and

x(D) = D ∑ j=0 c t q(t) = Jx(0) = x. (6)
To summarize, a constant step-size α gives rise to an average consensus protocol with asymptotic convergence, which can be accelerated by using min{Λ} and max{Λ}, the smallest and the greatest nonzero Laplacian eigenvalues, whereas all the elements of Λ yield a finite-time average consensus protocol.

Inferring the Laplacian spectrum from average consensus measurements

Equation ( 6) gives some insights on how estimating Laplacian eigenvalues from average consensus measurements. Indeed, assuming that the (D + 1) measurements q(t), t = 0, 1, • • • , D, are stored along with the final value x of a standard average consensus algorithm, the coefficients of the polynomial P c can be retrieved by solving Qc = x, where Q = (q(0) q(1) D+1) . Then the Laplacian eigenvalues can be deduced as the inverse of the roots of the polynomial P c . Obviously, the initial condition q(0) = x(0) should be selected so that Q be full column rank. For instance, the entries of x(0) should not be all equal. Assuming that x(0) is randomly generated from a continuous distribution then one can deduce that almost surely Q is full column rank.

• • • q(D)) ∈ ℜ N×(
In these conditions, a distributed least square algorithm can be devised to solve the problem. However, this presupposes that the following assumptions are fulfilled: D, the number of distinct nonzero Laplacian eigenvalues, is known and the actual average consensus value x is also known. The later assumption means that several iterations of the average consensus protocol have been run prior to the distributed estimation of the Laplacian eigenvalues. Based on these assumptions, in [START_REF] Tran | Consensus-based distributed estimation of Laplacian eigenvalues of undirected graphs[END_REF], the authors proposed to solve the following problem in a distributed way:

min α α α t ∈ℜ N×1 ,t=1,2,...,D 1 2 D ∑ t=1 ∑ i∈V ∑ j∈N i (α t, j -α t,i ) 2 . (7) subject to x(D) = x.
This problem is a constrained consensus one and allows obtaining directly the inverse of the Laplacian eigenvalues. However, as formulated, it is a non-convex optimization problem. Solving this problem with a descent gradient approach suffers slow convergence, strong dependence of convergence with the initialization of the algorithm and no guarantee of convergence to the global minimum. In what follows, we propose an alternative formulation giving rise to a convex optimization problem while relaxing the conditions on the perfect knowledge of D and x.

CONVEX DISTRIBUTED OPTIMIZATION APPROACH FOR LAPLACIAN SPECTRUM ESTIMATION

The only thing we know about the number D is the fact that it is lower bounded by the diameter1 d(G) of the graph and upper bounded by N -1. The lower bound comes from the fact that d(G) characterizes the time necessary for a given information to reach all the agents in the network while the upper bound is derived from the fact that the N × N Laplacian matrix L of a connected graph has at most N eigenvalues including the simple eigenvalue 0. Therefore, the averaging matrix cannot be factored with a number of matrices lower than d(G).

Let us recall the following lemma: Lemma 1. [START_REF] Tran | Consensus-based distributed estimation of Laplacian eigenvalues of undirected graphs[END_REF]). Let λ 2 , • • • , λ D+1 ̸ = 0 be the D distinct nonzero eigenvalues of the graph Laplacian matrix L, then, up to permutation, the sequence

{α i } i=1,••• ,D , with α i = 1 λ i+1 , i = 1, 2, • • • , D, is the
unique sequence, which allows getting the minimal factorization of the averaging matrix as 1

N 11 T = ∏ D i=1 (I N -α i L).
As a consequence, if the factorization of the averaging matrix with h > D factor matrices succeeds then the obtained set of stepsizes includes necessarily the D inverse of Laplacian eigenvalues. Therefore, by taking h = N -1, we intend to find a larger set of values that includes the Laplacian eigenvalues. In subsection 3.2, we describe the way of retrieving the Laplacian eigenvalues from the obtained larger set.

Let us assume that the standard average consensus protocol (2) for obtaining x is stopped after a finite number of iterations M > N. For a sufficiently large value of M, x(M) can be viewed as a reasonable approximation of x. Therefore, the problem under study is:

Consider a network performing the average consensus protocol (3). Given the number of nodes N, the state of the network x(M) at iteration M > N, and the N first consecutive measurements q(t), t = 0, 1, • • • , N -1, estimate the nonzero distinct Laplacian eigenvalues.

Convex optimization problem formulation

Instead of solving the non-convex optimization problem (7) as in [START_REF] Tran | Consensus-based distributed estimation of Laplacian eigenvalues of undirected graphs[END_REF], we first reformulate the problem into a convex one and then solve it in a distributed way.

We know that if {α t } h t=1 contains the D inverses of the nonzero Laplacian eigenvalues, then x

= h ∏ t=1 (I -α t L)x(0) or equiva- lently, x = h ∑ r=0 c r L r x(0) = h ∑ r=0 c r q(r),
Assuming that x(M) is a reasonable approximation of x, our aim is to:

(i)-find the coefficients c r , r = 0, 1, • • • , h, that minimize the quadratic error on the final consensus value:

E(c) = h ∑ r=0 c r q(r) -x(M) 2 ; (8)
(ii)-compute the set S 1 = {α α α t } t=1,••• ,h of the roots of the polynomial with coefficients c r ; (iii)-deduce from S 1 , the set S 2 of inverse of Laplacian eigenvalues.

In order to solve the problem in a distributed way, we first define by c i,r the coefficients of the polynomial of interest as estimated by node i. The optimization problem can be reformulated as follows:

min c i ∈ℜ (h+1) ,i=1,...,N 1 2 N ∑ i=1 ( h ∑ r=0 c i,r q i,r -x i (M)) 2 , ( 9
)
subject to c i,r = c j,r , i = 1, . . . , N; j ∈ N i ; r = 0, . . . , h.

c i = (c i,0 , c i,1 , • • • , c i,h ) T ∈ C i ,
where C i stands for the constrained set with respect to node i defined as

C i = {γ γ γ ∈ ℜ h+1 : Q i γ γ γ = x i (M)1, Q i ∈ ℜ (d i +1)×(h+1) }
where Q i is formed with the rows of Q corresponding to node i and its d i neighbors. This constraint set allows to enforce not only the local coefficients vector c i to be equal in a given neighborhood but also to enforce the scalar product q T i c i to be globally equal, where q T i stands for the row of Q associated with node i.

In the literature, there exist several methods dealing with the distributed optimization problem (9), including distributed descent algorithms, [START_REF] Nedic | Constrained consensus and optimization in multi-agent networks[END_REF], dual averaging methods, [START_REF] Duchi | Dual averaging for distributed optimization: Convergence analysis and network scaling[END_REF], and the ADMM, [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]; [START_REF] Erseghe | Fast consensus by the alternating direction multipliers method[END_REF]. However, we make use of the ADMM method, which has become a popular approach for solving convex minimization problems by means of parallelization. The positive features of this method is that it is guaranteed to converge for all tuning parameters [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. ADMM has only one single penalty parameter ρ that can influence on the speed of convergence. ADMM ensures in general very good convergence speed when this parameter is appropriately chosen. There exist some works dealing with penalty parameter selection for accelerating the convergence rate of ADMM [START_REF] Ghadimi | On the optimal step-size selection for the alternating direction method of multipliers[END_REF]; [START_REF] Boley | Local linear convergence of ADMM on quadratic or linear programs[END_REF]; [START_REF] Teixeira | Optimal scaling of the ADMM algorithm for distributed quadratic programming[END_REF]. The convergence analysis is also studied in [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]; [START_REF] Erseghe | Fast consensus by the alternating direction multipliers method[END_REF][START_REF] Boley | Local linear convergence of ADMM on quadratic or linear programs[END_REF]. In what follows, we describe the derivation of the ADMM algorithm for solving problem ( 9) with a constant penalty parameter.

For this purpose, one can note that by introducing the auxiliary variables {z i j }, the following constrained convex optimization problem is absolutely equivalent to problem (9):

min c i ∈ℜ (h+1) ,i=1,...,N 1 2 N ∑ i=1 ( h ∑ r=0 c i,r q i,r -x i (M)) 2 . ( 10
) subject to c i,r = z i j,r , i = 1, . . . , N; j ∈ N i z ji,r = z i j,r , r = 0, . . . , h. ( 11
)
c i ∈ C i .
Since the graph is assumed to be connected, the constraints (11) allow enforcing c i = c j , j ∈ N i . We can then write the associated augmented Lagrangian as:

L ρ (c, z, y) = N ∑ i=1 ( 1 2 h ∑ r=0 (c i,r q i,r -x i (M)) 2 + h ∑ r=0 ∑ j∈N i y i j,r (c i,r -z i j,r ) + ∑ j∈N i ρ 2 ∥c i -z i j ∥ 2 ) . = N ∑ i=1 ( 1 2 (q T i c i -x i (M)) 2 + ∑ j∈N i y T i j (c i -z i j ) + ∑ j∈N i ρ 2 ∥c i -z i j ∥ 2 ) . ( 12
)
The ADMM solution is obtained by solving iteratively three sub-optimization problems. At step k,

given c i [k], z ik [k], and
y i j [k], j ∈ N i , i = 1, • • • , N
, the following problems are to be solved:

• Minimization with respect to the polynomial coefficients

c i , i = 1, • • • , N: c i [k + 1] = Ω C i [argmin L ρ (c i , z i j [k], y i [k])]. (13)
where Ω C i [•] stands for the projection onto the constraints set of the vector in argument.

• Minimization with respect to the auxiliary variables z i j with the constraint z ji = z i j :

z i j = argmin L ρ (c i [k + 1], z i j , y i [k]). (14) • Update of Lagrange multipliers: y i j [k + 1] = y i j [k] + ρ(c i [k + 1] -z i j [k + 1]). (15)
Solving the sub-optimization problem (13) acts in two steps.

First the augmented Lagrangian is minimized with respect to the vector of polynomial coefficients c i :

ĉi [k + 1] = Ψ Ψ Ψ i (x i (M)q i + ρ ∑ j∈N i z i j [k] -∑ j∈N i y i j [k]), (16)
with Ψ Ψ Ψ i = (q i q T i + ρd i I h+1 ) -1 . Then, the obtained solution is projected onto the constraints set:

c i [k + 1] = Ω C i [ĉ i [k + 1]] that yields: c i [k + 1] = Qi xi,M + (I h+1 -Qi Q i )ĉ i [k + 1], ( 17
) with Qi = Q T i (Q i Q T i ) -1 .
This solution is well defined if and only if Q i is a full row rank matrix. One way to guarantee this property is to have a different initial condition at each neighborhood meaning that x i (0) ̸ = x j (0) for any pair (i, j).

One can note that performing this updating task does not need information exchange between neighbors since building matrices Q i is carried out beforehand.

Next, solving the sub-optimization problem ( 14) in the same way yields

z i j [k + 1] = 1 2 (c i [k + 1] + c j [k + 1]) + 1 2ρ (y i j [k] + y ji [k]). (18)
Unlike the previous step, now nodes have to share their local polynomial coefficients vector c i [k + 1] and the Lagrange multipliers y i j [k].

The overall ADMM algorithm for estimating the polynomial coefficient vector or equivalently performing the factorization of the averaging matrix is described in Algorithm 1.

Algorithm 1: ADMM-based distributed factorization of the averaging matrix (1) Given the number of agents N, the intermediate measurements {q i (t)}, t = 0, 1, • • • , h with h = N -1, and the value x i (M) of the state at time M > N, each node forms the vector q i , and the matrices Q i and Qi . (2) Initialization:

• Penalty parameter ρ,

• Random initial values of the coefficients {c i,r }, {z i j,r }, {y i j,r }, r = 0, . . . , h, at each node i, i = 1, . . . , N. 16) and ( 17). (c) Each node i sends a message containing its local polynomial coefficients vector c i [k + 1] and the current Lagrange multipliers y i j [k] to its neighbors j ∈ N i . (d) Compute z i j [k + 1] using (18). (e) Update the Lagrange multipliers y i j [k + 1] using (15). (f) Return to (3a) or stop the iterations if a stopping criterion is reached. (4) Each agent build a polynomial P c,i with the set of coefficients c i,r [k + 1]. (5) Each agent compute the set of the stepsizes {α i,t } as the roots of the polynomial P c,i .

• Set k = 0; (3) Update Process: (a) Set k := k + 1; (b) Compute c i [k + 1] using (

Laplacian eigenvalues retrieving.

At each node, the set S 1 of the step-size obtained by means of Algorithm 1 contains the set S 2 of the inverse of Laplacian eigenvalues. Let xi be the final consensus value reconstructed by node i as xi = h ∑ r=0 c i,r q i,r = P c i ,i (q i ) with the coefficients obtained by means of Algorithm 1. The idea is to reduce, stepby-step, the degree of the polynomial P c i ,i (q i ) by removing one element of S 1 . We know that if the removed element is also an element of S 2 then xi ̸ = Pc i ,i (q i ) where Pc i ,i is the polynomial with reduced degree. Such a simple test allows to conclude if the selected element is an inverse of a Laplacian eigenvalue or not. Algorithm 2 describes the proposed procedure. We can note that it is strictly local.

Algorithm 2: Laplacian eigenvalues retrieving Given the set of step size S 1 , the final consensus value xi , and the measurements vector q i .

(1) Initialization: S 2 = {} and S 3 = S 1 .

(2) while S 3 ̸ = / 0, select an element α j of S 3 . (3) From the set S 3 \{α j } compute the coefficients c i using ( 5) and then form ci . (4) If xi ̸ = cT i q i , include α j in S 2 so that S 2 = S 2 ∪ {α j }, set S 3 = S 3 /{α j }, and return to 2.

(5) If xi = cT i q i , set S 3 = S 3 /{α j }, and return to 2. (6) If S 3 = / 0, deduce the Laplacian eigenvalues as the inverse of the elements in S 2 .

In practice, the test xi = cT i q i is replaced by

( xi -cT i q i ) 2 < ε,
where ε is a sufficiently small positive coefficient.

The overall distributed estimation scheme is summarized in Fig. 1 Average Consensus Protocol Laplacian eigenvalues retrieving λ 1 , . . . , λ D+1

x i (0) α

x i (M ) q i (t), t = 0, . . . , h.

SIMULATION RESULTS

In order to evaluate the performance of the proposed distributed estimation method, we consider a network of 6 nodes modeled as a cycle graph. The performance is evaluated by means of the mean square error (MSE) between the estimated Laplacian eigenvalues λ j,i and the actual ones.

MSE = 1 N N ∑ i=1 D ∑ j=1 (λ j -λ j,i ) 2 . ( 19
)
The Laplacian matrix associated with this graph has 3 distinct nonzero eigenvalues Λ = {1, 3, 4} and, therefore, the corresponding inverse of nonzero distinct eigenvalues are {1, 0.3333, 0.25}.

As depicted in Fig. 1, we first run an average consensus protocol using a constant edge weights consensus protocol with α = 0.2 as a stepsize and x(0) = [0.6179, 0.0702, 0.0693, 0.1360, 0.7889, 0.0924] T as an initial condition. Fig. 2 depicts the trajectory of the state of each node. We can note that a reasonable agreement is obtained Then, the ADMM algorithm for computing the factorization of the averaging matrix was performed for different values for the number of iterations M of the average consensus algorithm.

For instance, Fig. 3 depicts the trajectories of the estimated polynomial coefficients. We can note the good agreement between nodes on the estimation of these polynomial coefficients, which are then used to build a 5th-order polynomial whose roots contain the inverse of the Laplacian eigenvalues. For M ≤ 10, x(M) was too far from x. As a consequence, the obtained polynomial gave rise to negative or complexvalued roots meaning that the coefficients c created from these roots do not satisfy xi = cT i q i in Algorithm 2. For M > 10, Algorithm 2 was successfully performed for retrieving the Laplacian eigenvalues. Fig. 4 depicts the MSE on the estimation of the Laplacian eigenvalues and the corresponding standard deviation. As expected, we can note that the closer x(M) is to x, the higher the precision on the computation of the Laplacian eigenvalues is. In addition, the tight bounds around the MSE inform us about the agreement on the estimated Laplacian eigenvalues.

CONCLUSION

In this paper, we have proposed an improved distributed method to estimate the Laplacian nonzero distinct eigenvalues of a connected undirected graph representing interactions between nodes of a given network. A convex optimization problem has been proposed. It consists in finding the optimal coefficients of a given polynomial whose roots are precisely the stepsizes α t ,t = 1, . . . , D, allowing to factorize the averaging matrix as a product of Laplacian-based average consensus matrices. The stepsizes are the inverse of the Laplacian eigenvalues. To solve this problem in a distributed way, we have devised an ADMM approach that exhibits in general fast convergence. The drawback of the proposed method concerns its scalability. Indeed, for very large graphs the roots of very high degree polynomials are to be computed. Furthermore, the proposed algorithms are implemented perfectly if the average consensus value x is estimated. In stead of solving two tasks, which are average consensus protocol and Laplacian eigenvalues estimation, we can combine them into one problem that simultaneously estimates the average consensus value x and nonzero distinct Laplacian eigenvalues. This problem is still under investigation.

Fig. 1 .

 1 Fig. 1. Block diagram of the proposed distributed Laplacian eigenvalues estimation method.

Fig. 2 .

 2 Fig. 2. Trajectory of the network state during average consensus protocol.from iteration 10.

Fig. 3 .

 3 Fig. 3. Estimation of the polynomial coefficients for (M=15).

Fig. 4 .

 4 Fig. 4. Performance of Laplacian eigenvalues estimation for different values of the number of iterations of the standard average consensus algorithm.

The diameter d(G) of a graph is defined as d(G) = max i, j dist(i, j), where given two vertices i and j, the distance dist(i, j) is the length of the shortest path between i and j.


ENTAM, Italy Giulio Fancello

Márk Szente

László Kocsis

MGI Kornél Szalay

Emmanuel Piron

Anicet Marionneau

New experimental method for measuring the energy efficiency of tyres in real condition on tractors

The ENTAM as the European Network of Testing stations of Agricultural Machines and equipment has settled up a new ENTAM Technical Working Group in order to draft a common methodology to test the agricultural tyre energy efficiency, in close cooperation with one of the biggest tyre manufacturer. The aim was to find a compromise between easiness and representativeness of the measurements, with reproducible records carried out on real agricultural fields, in standardized soil conditions. It is described a proposal for a dimensionless tyre performance index and a way to standardize the test methodology and the test devices.

Aim and scope

The European agriculture is more and more concerned by energy efficiency considerations, for various reasons: the pressure put by the society and the public authorities (eco-labelling…), the economical impact of energy waste, or the farmers' personal commitment toward a "greener" agriculture. Mobile machinery and the pneumatic tyres in particular, play a very significant role in this context. So far, no standard test is existing yet, so as to evaluate the performance of the tyres in this respect. In 2011 according to this new requirement a newest 9th ENTAM Technical Working Group has been established in order to draft a common methodology to test the "Agricultural Tyre Energy Efficiency". [1] This paper proposes a draft for defining such a standard method, encompassing two main field usage conditions, which are the followings: the pulling on field, the carrying on field. We will concentrate first on the case of agricultural tractors. For the field usage conditions, a specification of the reasonable soft soil to be used in the test is proposed, based on soil parameters and the way to control them. The physical signals to be recorded are described, as well as some features of the testing devices.

Proposed material and method of experiments for the future standard test

The worked out "Test Protocol" strictly describes the test conditions. Concerning the soil, it was decided to conduct the study in real, as homogeneous as possible agricultural soil, in open field. The reason for this technically challenging decision is to operate the tyre in convincing usage conditions, as viewed by the farmers. Evidently, the soft soil must not be selected anyhow. So far, 3 criteria must be respected in the Test Protocol: The texture: clay between 5 and 15%, silt between 10 and 30%, sand between 55 and 75% (texture determined according to ISO 25177:2008) [START_REF]Soil quality -Field soil description[END_REF], the moisture content (water mass / dry mass) between 10 and 14% (according to NF ISO 11465) [3], the cone index value (according to ASABE EP542 and ASABE S 313) [4,5] between 0.5 and 0.9 MPa, with optimal value 0.7 MPa. On each test plot 10 individual cone penetration measurements are carried out on each of four 50 metres long zones. During each test conditions, 4 quantities are recorded: The drive torque at wheel centre (T), the Net Traction force (NT), the rotation speed of the wheel (Ω) and the travel speed relative to soil surface (V).

Two dimensionless performance indices can then be computed: The Pull Loss Index (PLI) and the Carry Loss Index (CLI).

Case of pulling (so NT>0) :

Case of self-propelling (so NT=0):

The smaller the indices' values, the better the energy efficiency of the tested tyre. In case of PLI, for instance a value of 55% means that if the implement behind the tractor requires a drawbar power of 100 kW, the tractor (=engine + transmission…) will have to deliver 155 kW to tractor wheel axle. The advantage of this index is that the tyres can be compared on a given delivered basis (the 100 kW in above example, transmitted by drawbar drive direction 1 drive direction 2 "test plot" for a given NT/W to implement), like if they had to "work the same field". However, other indices can also be calculated (like the "tractive efficiency") using the same input quantities (T, NT, Ω and V). In case of CLI, the values are close to the motion resistance ratio, in case the "free rolling" and the "self propelling" modes are very comparable to each other, on the given soil.

Achievement of feasibility tests

According to the preliminary developed method for Agricultural tyres test feasibility tests were performed in 2012, at two testing stations: MGI in Hungary, and IRSTEA in France. One tyre conception was used, of dimension 650/65R38. Tyre settings like tyre vertical load and tyre inflation pressure were varied, so as to produce varied levels of tyre energy efficiency. Tyre dynamic vertical loads were varied from 2500 to 4000 kg. Here, the "dynamic" vertical load is considered, that is to say the load when the tyre is in operation.

Tyre inflation pressures were varied from 60 kPa to 160 kPa. Several levels of tyre traction (NT) were tested, namely 20%, 30%, 40%, 50% and 0% of dynamic vertical load (W). As these preliminary tests were feasibility tests, two different soil preparations were tested.

Tests by Irstea

Irstea used a specific device named "single-wheel-tester" to measure the tyre efficiency. Coupled with a 140 horse-power tractor, and composed by a specific metallic frame avoiding vertical load transfer, it allows to apply a given driving torque on a unique tyre and to measure, using different sensors, all the other parameter (horizontal force, real speed, angular tyre velocity, …). The speed was fixed to 1m.s -1 during all the successive measurement repetitions, each carried out along a series of 50m long zones. The vertical loads applied on the wheel were obtained using different mass.

Evaluation of results from test stations

Fig. 4 shows the Pull Loss Index values, as measured by MGI. The most important point is that depending on the usage condition (NT/W and soil), the PLI may be very big, and even exceed 50%: The tyre has a very significant impact on energy efficiency of the whole tractor, and the present project of standardized test is addressing an important issue.

Beside the impact of net traction coefficient value (NT/W) and soil preparation (variable in this feasibility test), it is interesting to observe that for a given usage condition, the energy loss can be even 1.6 times, depending on the tyre settings (dynamic weight and inflation pressure). So the right choice of tyre setting or the right choice of tyre is key to tractor performance.

Alignment between the two test centres:

Figs 6 and 7 below show that the range of magnitudes of the results obtained in both test centres are very comparable, which is encouraging. However, it can be seen in the graphs (and in other data) that some improvement in test methodology still has to be made, in order to improve tyre comparisons, when the differences between them are small.

Conclusion

The ENTAM network was born in order to define a common methodology for testing of agricultural machines and equipment on the basis of international standard. The ENTAM besides the 8 TWGs established the 9th one, the Eco-technologies TWG inter alia to develop and to test the "Agricultural Tyre Energy Efficiency". According to the developed method two feasibility tests were performed in 2012: One at the MGI in Hungary and one at the French IRSTEA. The results show that there is strong correlation between measured indices. By analysing common tyre settings, we observed that alignment of the two test centres' results has appeared to be acceptable. The next step will be to homogenize the test methodology and test devices, so that the tyre rankings are same too, whatever the test centre is. Some improvements have been suggested and implemented in following tests, especially on soil preparation in order to reduce the natural variability of "soil cone index" measures.

Fig. 1 .

 1 Fig. 1. Spatial repartition of the tests in a field plot.

  [1] Tests by the MGIThe MGI in Hungary carried out the tests by a modified tractor to measure the energy efficiency of tyre with ENTAM and to measure the fuel consumption of the tractor mounted with the above mentioned tyre.

Fig. 2 :

 2 Fig. 2: Modified tractor and the dynamometer vehicle during the tests

Fig. 3 :

 3 Fig. 3: Single-wheel-tester

  Fig 4. Pull loss indices at MGI Fig 5. Pull loss indices at IRSTEA

Fig 6 & 7 :

 7 Fig 6 & 7: Status of the alignment between the two test centres

Acknowledgements

The authors wish to thank Mr Dominique Dessèvre, of Michelin Research and Development Department for supporting the research with data and analysis necessary for the preparation of the paper.


P Djondine

R He

M Ghanes

J-P Barbot

Chaotic behavior study for serial multicellular chopper connected to nonlinear load

In this paper, chaotic behavior investigation of two-cells chopper when it is associated a nonlinear load is considered. The model of such system is described by a continuous time three dimensional non-autonomous system. The route to chaos is studied by using numerical simulations of two-cells chopper model. Moreover phase portraits; Poincaré section and first return map are analyzed to highlight the main characteristic of this particular chaotic behavior.

I. INTRODUCTION

Multicells converters have grown from an attractive theoretical concept to industrial applications, especially for use in higher power applications [START_REF] Erickson | Fundamentals of power electronics[END_REF], [START_REF] Rodriguez | Multilevel inverters: a survey of topologies, controls, and applications[END_REF], [START_REF] Meynard | Electronic device for electrical energy conversion between a voltage source and a current source by means of controllable switching cells[END_REF], [START_REF] Meynard | Multilevel choppers for high voltage applications[END_REF], [START_REF] Meynard | Modeling of multilevel converters[END_REF], [START_REF] Robert | Modélisation en temps discret d'un convertisseur d'énergie électrique. 8th rencontre du non linèaire[END_REF] and they are well suited to packaging of renewable energy sources. Indeed, due to their modular structure, they can be combined easily [START_REF] Meynard | Modeling of multilevel converters[END_REF]. In recent decades, it was discovered that most of static converters were the seat of unknown nonlinear phenomena in power electronics [START_REF] Defay | A predictive control with flying capacitor balancing of a multicell active power filter[END_REF], [START_REF] Ghanes | High gain observer based on z(tn) observability for a 3-cell chopper: Design and experimental results[END_REF], [START_REF] Leon | Simple unified approach to develop a time-domain modulation strategy for singlephase multilevel choppers[END_REF], [START_REF] Bernardo | Chaos in power electronics : An overview[END_REF]. It is for example the case of multicellular choppers that can exhibit unusual and sometimes chaotic behaviors. Obviously this may generate dramatical consequences (see for example the 1MW multicellular chopper [START_REF]LEEIInfos[END_REF]). However, the usual averaged models do not allow to predicting nonlinear phenomena encountered. By nature, these models obscure the essential nonlinearities [START_REF] Tse | Complex behavior of switching power converter[END_REF]. To analyses these strange behaviors, it is necessary to use a nonlinear hybrid dynamical model. The goal of this paper is to highlight the presence of chaotic behavior in the serial multicellular chopper [START_REF] Tse | Complex behavior of switching power converter[END_REF] controlled by classical PWM method. The paper is structured as follows. Section 2 deals with the modeling process. The electronic structure of the multicell converter is addressed and the appropriate mathematical model is derived to describe the dynamics of the chopper. In section 3, the proposed study of two cells chopper is presented. Phase portraits and Poincaré section and first return map are plotted to define the torus breakdown to chaos. Finally, some concluding remarks are reported in section 4.

II. MULTICELLULAR CHOPPER MODELING

Mutilcellular chopper consists of cells, where each one contains two complementary power electronics components and can be controlled by a binary switch (Fig. 1) [START_REF] Davaucens | Etude des convertisseurs multicellulaires parallèles : Analyse du modèle[END_REF], [START_REF] Gateau | De la modélisation à la commande non linéaire des convertisseurs multicellulaires série. application à la fonction hacheur[END_REF], [START_REF] Meynard | Dispositif de conversion d'énergie électrique à semiconducteur[END_REF], [START_REF] Benmansour | Adaptive observer for multi-cell chopper[END_REF], [START_REF] Gateau | Multicell converters: active control and observation of flying-capacitor voltages[END_REF]. The signal is equal to 1 when the cell upper switch is conducting and equal to 0 when the lower one is conducting. These cells are associated to capacitors and the chopper is connected in series with an RL load [START_REF] Bejarano | Observability and observer design for hybrid multicell choppers[END_REF]. Consequently the chopper has p -1 floating voltage capacitors with p refers to cells number. The requested energy balance of the chopper is the following one

(v C k = k E p )
. This condition is necessary in order to guarranty that each cell cut off only E p . In this case output voltage of the chopper takes one of the following values: (0, E p , . . . , (p-1)E p , E). The chopper modeling is: Note that the chopper (Fig. 1), which has a purely dissipative load, can not generate a chaotic behavior. Nevertheless, it is well known since from [START_REF] Bernardo | Bifurcation and chaos in power electronics : an overview in nonlinear dynamics in engineering[END_REF] that power converter when it is connected to nonlinear load may have a chaotic behavior.

                                         dV C 1 dt = u2-u1 C1 i L dV C 2 dt = u3-u2 C2 i L . . . dV C p-1 dt = up-up-1 Cp i L di L dt = u2-u1 L V C1 + u3-u2 L V C2 + . . . + up-1-up L V Cp-1 + up L E -R L i L (1)

III. CHAOTIC BEHAVIOR

A. Modelling

For the sake of simplicity, this investigation is carried out for a two cells chopper (Fig. III-A). A passive load in series with a nonlinear load composes the considered load. Moreover, the nonlinear load is connected with a capacitor in order to keep in mind the nonlinear properties. From equation 1 and taking into account the nonlinearity of the load, the two cells chopper modeling connected to noninear load is given by the following set of equations:

               dv C dt = u2-u1 C i L dv dt = (i L -g(v)) C l di L dt = u2-u1 L v C -1 L v -R L i L + u2 L E (2)
where

g(v) = 1 2 v -(|v + 1| -|v -1|)

B. Chaotic behavior study

In this section, three indicators are used to identify the type of transition leading to chaos [START_REF] Wiggins | Introduction to applied nonlinear dynamics[END_REF] of system (2) : Routes to chaos with phase portraits, Poincaré section and first return map. Chaotic systems are sensitive to initial values. Chaotic behavior of system (2) can be obained only by varying the switching frequency f s of the chopper. To be able to enter the chaotic behavior, the following parameters values of system (2) are chosen and assigned constants in the three indicators:

C = 0.1µF , C l = 40µF , R = 10Ω, L = 50mH, E = 100V .
1) First indicator : routes to chaos: For the sake of simplicity and the leak of space, only the phase portraits of v with respect to I L are given in order to show the route to chaos and express the behaviour of the nonlinear load. The 3 dimentional phase portrait v c with respect to v and i L is given and analysed. As it is expected, a chaotic behaviour appears when the frequency of the converter decreases. As it can be seen from figures [START_REF] Bernardo | Bifurcation and chaos in power electronics : an overview in nonlinear dynamics in engineering[END_REF][START_REF] Bernardo | Chaos in power electronics : An overview[END_REF][START_REF] Davaucens | Etude des convertisseurs multicellulaires parallèles : Analyse du modèle[END_REF][START_REF] Defay | A predictive control with flying capacitor balancing of a multicell active power filter[END_REF][START_REF] Erickson | Fundamentals of power electronics[END_REF][START_REF] Gateau | Multicell converters: active control and observation of flying-capacitor voltages[END_REF][START_REF] Gateau | De la modélisation à la commande non linéaire des convertisseurs multicellulaires série. application à la fonction hacheur[END_REF][START_REF] Ghanes | High gain observer based on z(tn) observability for a 3-cell chopper: Design and experimental results[END_REF], when the frequency is very little (f s = 0.25hz, Fig. 3), iL is a point. As the frequency increase to 1Hz, the chopper get into chaos. And gradually weaken since 30Hz. When the frequency is 100kHz, iL become a point again.

2) Poincaré section analysis: f s = 20Hz:

The Poincaré section is computed for i L = 0 when the frequecy is 20hz and the load voltage is stable in 4V . From figures [START_REF]LEEIInfos[END_REF][START_REF] Leon | Simple unified approach to develop a time-domain modulation strategy for singlephase multilevel choppers[END_REF] it can be seen that the symmetry is arround the nominal voltage capacitor V cn that is 50V . 14) it can be seen that the system is in the chaos between 1Hz and 30Hz. As the frequency increase, the system get into stable. But at the resonance frequency 2253.6Hz, the load current i L get the maximum value of 5A, the system get into unstable aera (figure [START_REF] Meynard | Electronic device for electrical energy conversion between a voltage source and a current source by means of controllable switching cells[END_REF].

IV. CONCLUSION

In this paper, a study of chaotic behaviour in multicellular chopper (mainly 2-cells chopper) connected to a particular nonlinear load is investigated. The main contribution of this work consists to draw the importance of the link between the switching frequency of the chopper and the resonnance frequency of the circuit in chaos generation. The simulated results show that toroidal chaos occurs. Our on going work is first to implement the propored method in experimental 2-cells set up with nonlinear load realization. Then we are planning to extend this investigation to choppers with cell number greater than two.

Fig. 1 .

 1 Fig. 1. p-cells chopper connected to RL load

Fig. 2 . 2 -

 22 Fig. 2. 2-cells chopper connected to a nonlinear load

Fig. 3 .Fig. 5 .

 35 Fig. 3. fs = 0.25. Fig. 4. fs = 1.

Fig. 7 .

 7 Fig. 7. fs = 50.

Fig. 8 .

 8 Fig. 8. fs = 100.

Fig. 9 .

 9 Fig. 9. fs = 500. Fig. 10. fs = 100khz.

Case 1 :

 1 Routes to chaos.

Fig. 11 .

 11 Fig. 11. Poincaré section

Fig. 13 .

 13 Fig. 13. First return map


Mathieu Mangeot
email: mathieu.mangeot@univ-savoie.fr

Antoine Chalvin
email: antoine.chalvin@inalco.fr

Dictionary Building with the Jibiki Platform: the GDEF case

This paper presents the use of the "Jibiki" generic dictionary online development platform in the case of the GDEF Estonian-French bilingual dictionary building project. This platform has been developed mainly by Mathieu Mangeot and Gilles Sérasset based on their research work in the domain. The platform is generic and thus can be used in (almost) any kind of dictionary development project from simple monolingual lexicons to complex multilingual pivot dictionaries as well as terminological resources. The platform is available online, thus it allows entry writers to work and collaborate from any part of the world. It consists in two main modules and data management tools. There is one module for elaborating complex queries on the data and one module for editing entries online. The editing modules generates automatically an interface from the XML structure of the entry.

Introduction

In this paper, we presents the "Jibiki" generic dictionary online development platform used for the GDEF Estonian-French bilingual dictionary building project. This platform has been developped mainly by Mathieu Mangeot and Gilles Sérasset based on their research work in the domain. The platform is generic and thus can be used in (almost) any kind of dictionary development project from simple monolingual lexicons to complex multilingual pivot dictionaries as well as terminological resources. The genericity in the dictionary lookup is obtained thanks to the definition of search criteria based on Xpath strings in the entries structure. For the entry editing, it is obtained thanks to the automatic generation of the editing interface from the XML entry structure. The platform is available online, it allows entry writers to work and collaborate from any part of the world. We begin by presenting an overview of the platform. Then we list 3 projects that are currently using the platform. It consists in two main modules and data management tools. There is one module for elaborating complex queries on the data and one module for editing entries online. The next sections detail the platform usage: first, the dictionary lookup module, then the entry writing module and finally, some task management tools.

Overview of the platform

The Jibiki platform (Sérasset, 2004) is an online 1 generic environment for writing and querying all kinds of dictionaries: terminological glossaries, bilingual dictionaries, multilingual lexical databases, etc. It has been developed mainly by Mathieu Mangeot (Université de Savoie, France) and Gilles Sérasset (Université de Grenoble 1, France), thanks to research driven by the GETA team of the CLIPS laboratory in Grenoble, France (S * † erasset, 1994;Mangeot, 2001).

1 http://jibiki.univ-savoie.fr/jibiki

The platform is implemented in Java, exclusively with open source tools. It is based on Enhydra, a web server of dynamic java objects and Postgres, a relational database. The interface is available in English, Estonian, French, German and Japanese. New languages can be easily added. The snapshots of the Figures 2 and3 were taken with the English interface and the ones of Figures 3 and4 with the French one. Annex tools have been added on various instances of the platform. Some facilitate the communication between communities of users (forums, distribution lists) and others, the work of the lexicographers (tool for managing aligned bilingual corpora).

Projects currently using the platform

The platform is currently used by three lexicographical or terminological projects.

Papillon Project

This project2 (Mangeot et al., 2004), launched in 2001, is at the origin of the building of the platform. Its main goal is the construction of a multilingual lexical database with a pivot structure covering among others the following languages: Chinese, English, French, German, Japanese, Lao, Malay, Thai and Vietnamese. The resulting resources are publicly available and free of rights. The projects is open to all those who are interested in these languages.

GDEF Project

The GDEF (Great Estonian-French Dictionary) project3 (Chalvin and Mangeot, 2006) started in 2003. Its goal is to build a bilingual Estonian-French dictionary of about 80,000 entries, by a team of 8 people made of linguists, as well as Estonian and French translators. The reflections conducted in the GDEF project oriented in a decisive manner, in 2004 and 2005, the development of ´ the platform. A more precise definition of the needs resulting of a professional lexicographic work lead to numerous new functionalities. The tests driven by the GDEF lexicographers strongly contributed to transform an experimental research prototype into a fully functional platform. The GDEF is now the most active project using the Papillon platform. It is supported by the AIF (Intergovernmental Agency for Francophony), Robert Schuman Foundation and the embassy of France in Estonia.

LexALP Project

The European project LexALP 4 (Sérasset, 2005), was launched in 2005. Its goal is to harmonize the terminology of the Alpine Convention four languages (French, German, Italian and Slovenian) so that member states are able to cooperate effectively. For this, the project uses the Jibiki platform in order to build a term bank used to compare the specialized terminology of six different national legal systems in four different language, and to harmonize it, optimizing the understanding between various alpine states in environmental matters at a supranational level. When elaborating a query, the user can interactively add a search criteria by clicking on the "+" button. If the available criteria are not sufficient, it is even possible to define new search criteria when a new resources is added by defining common pointers on searchable information parts. These pointers are defined with XPath strings on the XML entry structure.

Dictionary lookup

In the case where a normal search returned no results, a reverse lookup is also executed. For example, when a user looks for the Estonian translation of a French word but it is not available into French-

• • •
Estonian resources, the system will also lookup into Estonian->French resources and the Estonian entries containing the French word will be displayed. The users can also define their own style sheet for viewing the search results.

Entries Writing

The writing of the entries is done directly online on the platform via a web browser. The writing interface is generated automatically from the description of the structure of the entries (an XML schema), thus allowing the edition of (almost) any type of dictionary entry as long as it is encoded in XML. A preliminary version of this module has been developed by (Mangeot and Thevenin, 2004) from previous research done on plasticity of user interfaces. The actual version of the module was then simplified and rewritten from scratch. The interface is shown in Figure 3. It is built upon an HTML form and can also deal with relatively complex structures thanks to more elaborated interactors that combine the basic HTML ones (text boxes, radio buttons, popup menus). Such example is the list management one that allows the writers to add, delete or reorder elements in a list by simply clicking on a button. These elements can be themselves complex objects containing lists of other objects, etc. A specific module allows the writer to establish links to entries in other resources available on the server. This technique is mainly used for linking an entry to its translation in another language when the translation already exist as a separate entry or for building a pivot acception that links entries in different languages. Every change made in the entry is stored in a history. It is then possible to come back to any previous version of the entry just like the usual "undo" commands. In the GDEF, it is used in order to display some information concerning the French equivalents (gender, irregular forms, etc.). The writing process is divided in several steps depending on the project. The GDEF is the most complete with three steps:

A contributor writes an entry; When the entry is validated, it is integrated into the dictionary and all the users can search it. The reviewers and validators use the reviewing interface for searching entries and editing them (Figure 4).

Tasks Management

In order to manage the different tasks and roles, the platform gives the possibility to define groups and access rights. There are several groups with predefined rights:

If the user is not logged, it can lookup the public re-• sources available on the platform.

When the user is registered and logged, s/he is included de facto in the contributors group and can contribute through the entry writing interface.

The users members of the reviewers group can revise the contributions written by users members of their working group.

The users members of the validators group can validate the previously revised contributions.

The last group is the one of the server administrators. They can manage users and their groups, add new resources on the platform, etc.

In the GDEF project, we added a supplementary constraint: the reviewers are divided into teams of two people: one with Estonian as a mother tongue and the other with French. Each one revise the contributions of the other one. In order to facilitate the construction work of the dictionary and possibly the remuneration of the writers, it is possible to obtain a summary of all the contributions in a given period of time. Figure 5 shows the contributors board of the GDEF dictionary for January and February 2006. Then, in order to facilitate the revision of the entries, the dictionaries can be exported as a whole or by parts, in several formats (text, HTML, XML, PDF, etc.) and printed. After editing or reviewing offline the entries, the data can also be reimported into the database.

Conclusion

We presented here "Jibiki" platform, a generic dictionary online development platform that is used by several dictionary building projects such as the GDEF Estonian-French bilingual dictionary. This platform is based on research work in the domain. It is generic and can be used in (almost) any kind of dictionary development project from simple monolingual lexicons to complex multilingual pivot dictionaries as well as terminological resources. The development of the platform is still an ongoing process. Once a stabilized version is obtained, it is planned to make it available for download freely as an open-source software. As of today, if you would like to use this platform for developing a dictionary free of rights, we invite you to contact us. ´´`

Figure 1 :

 1 Figure 1: Result of the query of the French word "orthographe" in multiple dictionaries

2.Figure 2 :

 2 Figure 2: Advanced Search Interface

Figure 4 :

 4 Figure 4: Reviewing interface for the GDEF Estonian volume

Figure 5 :

 5 Figure 5: Contributors board for the GDEF dictionary

  Gilles Serasset, and Mathieu Lafourcade. 2004. Construction collaborative d'une base lexicale multilingue. Traitement Automatique des Langues, 44(2):151--176, February. Mathieu Mangeot. 2001. Environnements centralises et distribues pour lexicographes et lexicologues en contexte multilingue. These de nouveau doctorat, specialite informatique, Universite Joseph Fourier Grenoble I, Septembre. Gilles Serasset. 1994. Sublim : un systeme universel de bases lexicales multilingues et Nadia : sa specialisation aux bases lexicales interlingues par acceptions. These nouveau doctorat, Universite Joseph Fourier-Grenoble 1, Decembre. Gilles Sérasset. 2004. A generic collaborative platform for multilingual lexical database development. In Gilles Sérasset, editor, COLING 2004 Multilingual Linguistic Resources Workshop, pages 73--79, Geneva, Switzerland, 28 August. Gilles Sérasset. 2005. Multilingual legal terminology on the jibiki platform: The lexalp project. In Mathieu Lafourcade, editor, Proc. of Papillon 2005 Workshop, pages 64--73, Chiang Rai, Thailand, 11-13 December.

	Antoine Chalvin and Mathieu Mangeot. 2006. Méthodes et
	outils pour la lexicographie bilingue en ligne : le cas du
	grand dictionnaire estonien-français. In EURALEX 2006,
	à paraître, Turin, Italie, 6-9 septembre.
	Mathieu Mangeot and David Thevenin. 2004. Online
	generic editing of heterogeneous dictionary entries in pa-
	pillon project. In Proc. of the COLING 2004 conference,
	volume 2, pages 1029--1035, Geneva, Switzerland, 26
	August.
	Mathieu Mangeot,

http://www.papillon-dictionary.org

http://www.estfra.ee


DICTIONARY BUILDING WITH THE JIBIKI PLATFORM Mathieu MANGEOT

Condillac -LISTIC -Université de Savoie

Campus Scientifique F-73376 LE BOURGET DU LAC CEDEX Email : Mathieu.Mangeot@univ-savoie.fr

ABSTRACT

The Jibiki platform is an online generic environment for writing and querying all kinds of dictionaries: terminological glossaries, bilingual dictionaries, multilingual lexical databases, etc. It has been developed mainly by Mathieu Mangeot (Université de Savoie, France) and Gilles Sérasset (Université de Grenoble 1, France), thanks to research driven by the GETA team of the CLIPS laboratory in Grenoble, France. The platform allows one to lookup all the dictionaries available on the server and to display the results in the same window. The advanced query interface offers a combination of multiple search criteria. The writing of the entries is done directly online on the platform via a web browser. The writing interface is generated automatically from the description of the structure of the entries (an XML schema), thus allowing the edition of (almost) any type of dictionary entry.

Dictionary Building with the Jibiki Platform

Overview of the platform

The Jibiki platform is an online generic environment for writing and querying all kinds of dictionaries: terminological glossaries, bilingual dictionaries, multilingual lexical databases, etc. It has been developed mainly by Mathieu Mangeot (Université de Savoie, France) and Gilles Sérasset (Université de Grenoble 1, France), now helped by Francis Brunet-Manquat, thanks to research driven by the GETA team of the CLIPS laboratory in Grenoble, France.

The platform is implemented in Java, exclusively with open source tools. It is based on Enhydra, a web server of dynamic java objects and Postgres, a relational database. The interface is available in English, Estonian, French, German and Japanese. New languages can be easily added.

Annex tools have been added on various instances of the platform. Some facilitate the communication between communities of users (forums, distribution lists) and others, the work of the lexicographers (tool for managing aligned bilingual corpora).

Comparison with existing software

In this section, we will briefly compare our software with two other well known dictionary software: TshwaneLex1 and IDM's Dictionary Publishing Software.

Jibiki platform

Yes

Yes No

Corpus handling

Not included Not included Included

Projects currently using the platform

The platform is currently used by three lexicographical or terminological projects.

Papillon Project

This project 2 , launched in 2001, is at the origin of the building of the platform. Its main goal is the construction of a multilingual lexical database with a pivot structure covering among others the following languages: Chinese, English, French, German, Japanese, Lao, Malay, Thai and

Vietnamese. The resulting resources are publicly available and free of rights. The projects is open to all those who are interested in these languages.

GDEF Project

The GDEF3 (Great Estonian-French Dictionary) started in 2003. Its goal is to build a bilingual Estonian-French dictionary of about 80,000 entries, by a team of 8 people made of linguists, as well as Estonian and French translators.

LexALP Project

The European project LexALP, launched in 2005, use the Papillon platform in order to develop a terminological database of legal and administrative terms in the main Alpine languages (French, German, Italian and Slovene).

Dictionary lookup

The platform allows one to lookup all the dictionaries available on the server and to display the results in the same window. The advanced query interface offers a combination of multiple search criteria on:

• the languages: source, targets, available resources;

• the character string: prefix, suffix, substring;

• the content of the entries: headword, variants, pronunciation, domain, gloss, part-of-speech, translations, examples, etc.

It is even possible to define new search criteria when a new resource is added by defining common pointers on searchable information parts. In the case where a normal search returned no results, a reverse lookup is also executed.

Entries Writing

The writing of the entries is done directly online on the platform via a web browser. The writing interface is generated automatically from the description of the structure of the entries (an XML schema), thus allowing the edition of (almost) any type of dictionary entry.

The interface, built upon an HTML form can also deal with relatively complex structures thanks to more complex interactors that combine the basic HTML ones (text boxes, radio buttons, pop-up menus). Such example is the list management one that allows the writers to add, delete or reorder elements in a list by simply clicking on a button. These elements can be themselves complex objects containing lists of other objects, etc. A specific module allows the writer to establish links to entries in other resources available on the server. This technique is mainly used for linking an entry to its translation in another language when the translation already exist as a separate entry. The writing process is divided in several steps depending on the project. The GDEF is the most complete with three steps:

1) A contributor writes an entry;

2) It is next revised by a reviewer;

3) It is then validated by a validator;

When the entry is validated, it is integrated into the dictionary and all the users can search it.

Tasks Management

In order to manage the different tasks and roles, the platform gives the possibility to define groups and access rights. There are several groups with predefined rights:

• If the user is not logged, it can lookup the public resources available on the platform.

• When the user is registered and logged, s/he is included de facto in the contributors group and can contribute through the entry writing interface.

• The users members of the reviewers group can revise the contributions written by users members of their working group.

• The users members of the validators can validate the previously revised contributions.

• Then, the server administrators manage users and their groups, add new resources, etc.

In order to facilitate the construction work of the dictionary and possibly the remuneration of the writers, it is possible to obtain a summary of all the contributions in a given period of time.

Then, the dictionaries can be exported as a whole or by parts, in several formats (text, HTML, XML, PDF, etc.) and printed.

http://tshwanedje.com/tshwanelex/

http://estfra.ee


Mathieu Mangeot
email: mathieu.mangeot@univ-savoie.fr

Back to the roots: building a French-Japanese dictionary

After four years of life, the Papillon project is dying. In this paper, I summarise the current situation and then give my opinion of the reasons why we did not achieve what we planned four years ago. Then, taking these reasons as a starting point I propose to go back to the original aim of the project, i.e. to build an online bilingual French-Japanese dictionary free of rights. I describe the macro and microstructures, the new methodology and the existing data we could (re)use in order to build at once a bidirectional bilingual dictionary with links that can be directly integrated afterwards in a multilingual pivot database. This (sub)project serves several goals: first, to build the dictionary itself of course, second, to motivate and federate contributors around a project and a platform, third, to advertise the Papillon project, fourth, to test the platform and the methodologies in real conditions and fifth, to build linked data that can be reused in a more long term for the Papillon Multilingual database. Of course, I cannot achieve this alone, so I am looking for support from your part!

Introduction

Let me begin by a warning: the opinions written in this paper come only from my personal point of view and my ideas are probably not shared by everybody. They might shock some sensitive souls. Nevertheless, I have a very good knowledge of the Papillon project [START_REF] Mangeot | Environnements centralisés et distribués pour lexicographes et lexicologues en contexte multilingue[END_REF] (Mangeot et al., 2004) [START_REF] Mangeot | Online generic editing of heterogeneous dictionary entries in papillon project[END_REF]) so I think it is worth to tell them. Furthermore, I also think that it is time to create a new dynamics otherwise, the risk that the project would die is considerable.

I begin by resuming the current situation and by giving what I think are the reasons why we did not achieve the aims previously defined. Then, I take these reasons as a starting point in order to go back to the original aim of the project, that is to build an online bilingual bidirectional French-Japanese dictionary.

2 Current situation

The Meetings

The first Papillon meeting [START_REF] Tomokiyo | Papillon: a project of lexical database for english, french and japanese, using interlingual links[END_REF] took place in Tokyo, in August 2000. since then, we regularly organised a meeting per year. The 2001 meeting took place in July in Grenoble. The 2002 meeting took place in July in Tokyo. The 2003 meeting took place in July in Sapporo. The 2004 meeting took place in August in Geneva. The first two years, we discussed a lot about the dictionary structures we would use and the organisation of the project.

The Data

Concerning the data, we decided to separate it into two layers: the purgatory and the paradise.

The purgatory gathers all the recuperated data in XML but in original structure. In four years, we managed to gather more than 1 million of entries from 14 dictionaries in Chinese, English, French, German, Japanese, Korean, Malay, Thai, and Vietnamese. This data must then be converted into the Papillon structure.

The Paradise gathers the data in Papillon structure. I first converted 613 French entries from the DiCo database [START_REF] Polguère | Towards a theoreticallymotivated general public dictionary of semantic derivations and collocations for french[END_REF]. They were reconverted in more details by Guy Lapalme [START_REF] Lapalme | Batch creation of papillon entries from dico[END_REF] in 2003. Then a few contributors edited a small set of dictionary entries in Papillon XML format. In 2001, Mutsuko Tomokiyo wrote 202 French entries, 183 English entries and 105 Japanese entries; In 2002, Tang Enya Kong and Siti Khaotijah Mohammad wrote 67 Malaysian entries. Unfortunately, few entries are translations the ones from the others. Nevertheless, I could write 41 axies between English, French and Japanese entries and one axie between English, French, Japanese and Malaysian entries. No other entries were created or converted since then. To summarise, today, we have 1,170 lexies in 4 languages and 42 axies.

The Platform

The best progress in Papillon project were realised on the platform. Gilles Sérasset began to write a prototype in Enhydra/Java in 2000. In 2001, I began to co-operate closely with him. I worked almost full time on the development of the platform during three years from 2002 to 2005. We still work on it when time constraints are not too heavy.

In 2003, I began to work on another dictionary construction project: the GDEF project1 about a big Estonian-French dictionary. We had a deadline for the official beginning of the project that was July 2005. Thus, I had to solve as many problems and bugs as possible in order to have a usable version at that time.

In the meantime, more exactly since the beginning of 2005, Gilles began to work on a terminology construction project, the LexAlp project that uses also the platform. He had to show rapidly a usable prototype for June. This is why we both worked hard on the platform in order to deliver a stable version for this summer. Furthermore, we had to take into account the differences of the two projects.

I enriched the platform used by the GDEF project with two important functionalities. In order to facilitate the communication between the platform users, I installed an Open Source online forum in PHP (phpBB2). The second tool I installed is called Uplug2 . It's a GPL software for building and querying online bilingual corpora.

During the test phase of the GDEF project, I received a good feedback from the lexicographers. They built 1,500 entries from scratch. Now, the platform is used everyday by a group of 10 people. They edit entries online. In 10 days, 250 entries were edited and revised without any problem.

The platform can be used as is for building a new dictionary. All the essential functionalities are implemented and work fine. Of course, we will not stop here the development. We would like in particular to redesign some parts and work on specifications in order to build a generic platform easily adaptable for new projects.

3 Identified problems 3.1 Wrong identification of the bottleneck When we began the project, we first thought that the tools we needed to build the dictionary would be the bottleneck. In other words, once the tools would be ready to use, we could start to write Papillon entries. Emmanuel Planas, and Magali Drant (an intern) even started right away a prototype in Java that could create inter-lingual links between entries of two different volumes simply by drawing the link with the mouse. Unfortunately, this prototype has never been used.

In the meantime, Gilles Sérasset started the development of the actual Papillon platform.

Once again, during this development, we strongly thought that once the basic needed functionalities would be implemented, we could begin to write entries on the platform. Four years later, the platform is not only ready but also used daily in two other lexical resources construction projects with success.

We have to admit and two other projects later, the we have to admit that the key problems that forbid us to continue on the project are from another type. My hypothesis is the following: we are not specialists of lexicography, most of us are computer scientists with some knowledge of linguistic. Thus we underestimated the lexicographic aspects of the project.

Very few Japanese collaborators

The project was launched by Emmanuel Planas and François Brown de Colstoun who were working in Japan at that time, and Mutsuko Tomokiyo who was working in France. I spent myself more than two years in Japan to work on the project. Most of the Papillon partners have strong interests in Japanese: Francis Bond and Yves Lepage are still working in Japan; Jim Breen, Ulrich Apel and Jean-Marc Desperrier are directly working on bilingual Japanese dictionary building projects, etc. Despite all our efforts, very few Japanese researchers accepted to join Papillon project: Mutsuko Tomokiyo (researcher in France), Kyo Kageura (ass. prof. at NII) and Kyoko Kuroda (High school teacher).

For this particular problem, making an hypothesis is quite difficult. I'll give two directions:

First, it seems that the needs of a French-Japanese dictionary is not that crucial for Japanese.

Almost every already existing French-Japanese resources were designed for Japanese. For example, the missing kana or counters are not an issue for them. Furthermore, although they are not free, some of them are relatively complete with a good quality (like Shogakukan-Robert f(íÙüë with about 120,000 entries and 250,000 examples).

Second, once again, the researchers we know in Japan are not lexicographers or researchers in lexicography. The people interested were generally very busy and wanted to see a more advanced concrete project before joining. We should build some core data in order to demonstrate the viability of the project as well as look into other directions.

Macrostructure too abstract

The pivot macrostructure that links monolingual volumes with inter-lingual links through a pivot volume seems to be difficult to understand by the majority of the people, even the domain experts. Most people believe that we try to build a semantic inter-lingua. For most of the people, it is impossible to imagine how these links can be built.

We may not have explained clearly this pivot structure and the way we build it. Furthermore, we do not have yet any example set to show (I believe that a good example is better than a long even detailed explanation).

I would like to go a step farther by saying that the reason why we did not explain the pivot structure clearly is it properly because even ourselves have not a clear idea of this structure. Another illustration of this is that in four years, despite very promising ideas (like semantic vectors), we were not able to build any example set (even very small).

Something we might consider in order to build an example set would be to recuperate data of the PARAX pivot database built by Étienne Blanc [START_REF] Blanc | Designing an acception-based multilingual lexical data base under hypercard: Parax[END_REF] [START_REF] Blanc | Une maquette de base lexicale multilingue à pivot lexical : Parax[END_REF] if it is still technically possible.

Wrong entry unit

I think that the idea to directly use the lexies as the basic entry unit is wrong. I list here four reasons why: Some data is shared between lexies of the same vocable (transcriptions, pronunciation, grammatical features, etc.), thus if we manage the lexies separately, it increases the risk of inconsistencies.

The ranking (mostly by frequency) between the lexies of the same vocable is very important when someone wants to translate a word into another language. For the moment, we have no way to indicate this ranking.

Another problem is the difficulty to distinguish between lexies of a same vocable and lexies of homograph vocables. For the moment, the lexies are displayed alphabetically but not gathered in vocables.

The latest reason is that the majority of the people are used to the traditional "vocable" entry unit. We should follow their entry unit representation in order to facilitate the adhesion of the contributors.

Microstructure too complex

The Papillon microstructure is based on the Explanatory and Combinatorial Lexicography (ECL) [START_REF] Mel'čuk | Introduction à la lexicologie explicative et combinatoire. Universites francophones et champs linguistiques[END_REF], part of the Meaning Text Theory. It is an XML'ized version of the DiCo database designed by Alain Polguère, Igor Mel'čuk and their colleagues of Université de Montréal in Canada.

This structure may be very interesting and convenient scientifically but the learning curve is by far too long to think that any contributor will be able to understand it (even parts of it) in a glance.

Furthermore, I think that the idea that the users will contribute at their level of knowledge and that ECL specialists will complete the structure is wrong because in order to contribute correctly on even the most easily understandable part of the entry structure, peo-ple need to understand at least the main lines of the ECL and this is already too much to ask.

Eyes bigger than stomach

Instead of building a first core of data by hands, we imagined that we could first build a skeleton of data from existing one by using various techniques in order to build (semi)automatically inter-lingual links. We tried to use for example the angular distance between semantic vectors in order to evaluate the semantic distance between two lexies.

Of course, this direction must be followed, but we should not put all our eggs in one basket. While we are waiting for this core, people are forgetting the project. Thus it is slowly dying.

In the meantime, we should also start to build data "by hands" from what we have now. This experiment is necessary to know if the chosen structures are adequate. Furthermore, The data can then be used for various experiments and bootstrap for automatic linking mechanisms. It would also help to establish a community of contributors around the project, and thus to increase the visibility of the project.

I think that instead of willing to build automatically all at once, we should increment the complexity step by step: building data by hands and then automatically; building first a bilingual dictionary and then a multilingual pivot database, etc. The next section tries to follow this principle.

Building a French-Japanese dictionary

In this section, I use the previous analysis of what I identified as problems in Papillon project in order to propose a more realistic direction to the project that would be a first step in the building of a multilingual pivot database. It consists in building "by hands" a relatively simple bilingual bidirectional French-Japanese dictionary. This was also in fact the very first aim of Papillon project.

Structures

4.1.1 Macrostructure I propose to keep a pivot macrostructure with inter-lingual links (axies) between lex-ies. But the inter-lingual linking mechanism is hidden. The linking interface shows only two languages, so that the contributors build only bilingual links between French and Japanese.

Entry unit

The entry unit is a traditional "vocable" made of one grammar block per part-of-speech. Each grammar block contains one or more lexie blocks sorted by frequency order.

Microstructure

The microstructure should tend to the ECL in order to reuse this data in a future Papillon database but must be much more simple:

• For every vocable: headword, homograph number, variants, pronunciation in IPA.

• For French vocables: kana transcription, inhaled h (h aspiré).

• For Japanese vocables: yomigana, romaji transcription, quantifiers.

• For every grammar blocks: the part-ofspeech.

• For French grammar blocks: gender, number, irregular plural and feminine for substantives; conjugation table and "être" auxiliary for verbs.

• For every lexie : the government pattern for predicative lexies, a free text definition, the domain, the language levels, a list of examples, a list of idioms, a translation link to the other language.

Methodology 4.2.1 Linking process

My hypothesis that drives the linking process is the following: every translation from one language to another is bidirectional, i.e. if there is a non null frequency for a vocable V1 to be translated into another language by a vocable V2, there is also a non null frequency for the vocable V2 to be translated into the vocable V1. The only difference between the two translations is located in the frequencies.

For example, the most frequent Japanese translation of the French vocable "tabouret" is the vocable P DY (isu); but the most frequent French translation of the Japanese vocable P is "chaise". Nevertheless, there are less frequent cases when P is translated into "tabouret".

The translation links can be only established in a lexie block. Furthermore, a lexie block cannot contain more than one translation link. Thus, when a user wants to create a translation link for the vocable V1 of language lang1, s/he must add a new lexie L1 in the vocable V1.

Then, when a translation link from vocable V1 of lang1 to vocable V2 of lang2 is established, a new lexie L2 is added to the vocable V2 and another link from lang2 to lang1 is also established. The lexie L2 is added at the end of the lexies block list and is labelled "to be reviewed".

When the vocable V2 is reviewed, the lexie L2 cannot be deleted. Only the order of the lexies can be modified in order to reflect the frequency of the translations of V2 into lang1 (Note to the developers: the interface have to be modified to allow the modification of a list order).

Following our example, the Japanese vocable P would have at least two lexies: the first one with a translation link to the French vocable "chaise" and the second one to the French vocable "tabouret".

When a vocable cannot be translated directly into another vocable, the translation link is done with the head of the translating expression and the whole expression is taken as a definition for the newly created lexie L2. For example, the Japanese vocable À [dv " (setsubun) is translated in French by the following expression: "jour précédent le printemps où l'on jette des graines de soja pour éloigner la malchance". In that case, a new lexie block is created into the French vocable "jour" and the definition of the lexie is the expression itself.

Writing protocol

The writing protocol involves four types of users:

• Users not logged can look-up existing validated data

• Logged users can create contributions

• Couples of 2 users (A and B): 1 French and 1 Japanese, pertaining to the group "specialist";

• A small group of validators (user V) who validate the reviewed contributions, pertaining to the group "validator";

It follows four steps:

1. creation of a contribution by user A, status "not finished" 2. end of contribution writing by user A, status "finished"

3. revision of the contribution by user B, status "reviewed" 4. validation of the contribution by validator V, status "validated"

Once the contribution is validated, it is added into the volume and can be queried by all the users.

Available Data

Monolingual Data

We think that the best way is to build a first word list for both languages by reusing existing monolingual data as a starting point.

• WaDokuJiTen is a big Japanese-German dictionary construction project led by Ulrich Apel. The data is available for Papillon project. The In our opinion, the Japanese part of the WaDokuJiTen is the most complete Japanese data available freely. It has more than 214,000 Japanese entries.

Bilingual Data

We propose to reuse only French-Japanese bilingual data and not other bilingual data like Japanese-English one because what people do is to translate the English into French without understanding the Japanese.

• Dico-F-J Project led by Jean-Marc Desperrier [START_REF] Desperrier | Analyzis of the results of a collaborative project for the creation of a japanese-french dictionary[END_REF]; 10,000 entries. Structure common with the JMDict project.

• FJocean Terminological French-Japanese lexicon of 3,328 French entries translated into Japanese about the ocean vocabulary available online 4 . The Japanese part have to be parsed in order to identify the translations.

• Maniette French translations of the meaning of 2,066 kanji by Yves Maniette for his book "Les kanjis dans la tête" (translation of the English book "Remembering the kanji" by James W. Heisig).

• Armement Small terminological lexicon about armament given by the French embassy in Tokyo, Japan with 1,116 terms. The terms are very specifics, it may not be usable for a dictionary of general domain.

Conclusion

This paper is mainly the result of my four years of work on Papillon project but also a summary of all the comments I listened every time I presented the project to newbies. I must admit that I was intentionally a little bit provocative. Things may not be that dramatic. Anyway, my aim here is first to give my opinion freely and second to shake the people consciousness about Papillon project. I am waiting for your comments. I think that if we do not react quickly, Papillon project will soon be dying. Already many people lost interest in following the project. This sub-project is a proposal to add a new dynamics in Papillon. I need your comments on the feasibility of such a project.

Then, if we decide to follow my proposal, I will need to find groups of validators and specialists; and more specifically Japanese contributors.

http://www.estfra.ee

http://stp.ling.uu.se/cgi-bin/joerg/Uplug

http://actarus.atilf.fr/morphalou