Francis Filbet

Chang Yang

NUMERICAL SIMULATIONS OF KINETIC MODELS FOR CHEMOTAXIS

Keywords: Bacterial chemotaxis, chemical signaling, kinetic theory

We present a new algorithm based on a Cartesian mesh for the numerical approximation of kinetic models for chemosensitive movements set in an arbitrary geometry. We investigate the influence of the geometry on the collective behavior of bacteria described by a kinetic equation interacting with nutrients and chemoattractants. Numerical simulations are performed to verify accuracy and stability of the scheme and its ability to exhibit aggregation of cells and wave propagations. Finally some comparisons with experiments show the robustness and accuracy of such kinetic models.

Introduction

This paper is devoted to the numerical simulation of the process of cellular spatial organization driven by chemotaxis. The effective mechanism by which individual cells undergo directed motion varies among organisms. Here we are particularly interested in bacterial migration, characterized by the smallness of the cells, and their ability to move to several orders of magnitude in the attractant concentration. Several models, depending on the level of description, have been developed mathematically for the collective motion of cells. We refer to [START_REF] Bournaveas | A review of recent existence and blow-up results for kinetic models of chemotaxis[END_REF][START_REF] Perthame | PDE models for chemotactic movements: parabolic, hyperbolic and kinetic[END_REF][START_REF] Perthame | Transport Equations in Biology[END_REF] for a review on parabolic, hyperbolic and kinetic models and to [START_REF] Bouin | Hyperbolic traveling waves driven by growth[END_REF][START_REF] Saragosti | Mathematical Description of Bacterial Traveling Pulses[END_REF][START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF] for traveling waves drivn by growth and chemotaxis. Among them the kinetic model introduced by Othmer, Dunbar and Alt [START_REF] Alt | Biased random walk models for chemotaxis and related diffusion approximations[END_REF][START_REF] Othmer | Models of dispersal in biological systems[END_REF], describes a population of bacteria in motion (for instance the E. Coli) in interactions with a chemoattractant concentration [START_REF] Erban | From individual to collective behavior in bacterial chemotaxis[END_REF]. These cells are so small that they are not able to measure any head-to-tail gradient of the chemical concentration, and to choose directly some preferred direction of motion towards high concentrated regions. Therefore they develop an indirect strategy to select favorable regions, by detecting a sort of time derivative in the concentration along their pathways, and to react accordingly [START_REF] Macnab | The gradient-sensing mechanism in bacterial chemotaxis[END_REF].

More precisely, they undergo a jump process where free runs are followed by a reorientation phenomenon called tumble [START_REF] Webre | Bacterial chemotaxis[END_REF]. For instance it is known that E. Coli increases the time spent in running along a favourable direction [START_REF] Macnab | The gradient-sensing mechanism in bacterial chemotaxis[END_REF]. This jump process can be described by two different informations. First cells switch the rotation of their flagella, from counter-clockwise,

The authors are partially supported by the European Research Council ERC Starting Grant 2009, project 239983-NuSiKiMo. called free runs, to clockwise called reorientation or tumbling phase, and conversely. This decision is the result of a complex chain of reactions inside the cells, driven by the external concentration of the chemoattractant [START_REF] Spiro | A model of excitation and adaptation in bacterial chemotaxis[END_REF][START_REF] Webre | Bacterial chemotaxis[END_REF]. Then bacteria select a new direction, but they are unable to choose directly a favourable direction, so they randomly choose a new orientation. During the "run" phases a bacterium moves with a constant speed in a given direction while during a "tumbling" event it changes direction randomly.

Kinetic models for bacterial chemotaxis

In the simple situation, C. S. Patlak [START_REF] Patlak | Random walk with persistense and external bias[END_REF] and E. F. Keller & L. A. Segel [START_REF] Keller | Traveling bands of chemotactic bacteria: a theoretical analysis[END_REF] considered a density of cells which interacts with two chemical substances. The cells consume nutrients which drive the migration and excrete a chemoattractant that prevents the dispersion of the population. However, this approach is not always sufficiently precise to describe the evolution of bacteria movements. Hence, this phenomenon of run and tumble can be modeled by a stochastic process called the velocity-jump process, and has been introduced by Alt [START_REF] Alt | Biased random walk models for chemotaxis and related diffusion approximations[END_REF] and further developed in [START_REF] Othmer | Models of dispersal in biological systems[END_REF]. A kinetic transport model to describe this velocity jump process consists to study the evolution of the bacterial population by the local density of cells f (t, x, v) ≥ 0 located in position x, at time t and swimming in the direction v ∈ V .

Here the set V of all possible velocities is bounded and symmetric in general. In two dimensions, the modulus of the speed is a constant v 0 , hence V = S(0, v 0 ) circle centred in 0 with a radius v 0 > 0.

A kinetic transport model to describe this velocity-jump process has been introduced by W. Alt [START_REF] Alt | Biased random walk models for chemotaxis and related diffusion approximations[END_REF] inspired by the Boltzmann equation [START_REF] Othmer | Models of dispersal in biological systems[END_REF] where the tumbles appear as scattering events and all the fluxes are explicitly introduced [START_REF] Saragosti | Mathematical Description of Bacterial Traveling Pulses[END_REF]. We consider the Boltzmann type equation

(2.1) ∂f ∂t + v ⋅ ∇ x f = Q(f ) + r f, x ∈ Ω, v ∈ V,
where Q(f ) is the Boltzmann type tumbling operator

Q(f ) = V T (v, v ′ ) f (t, x, v ′ ) dv ′ - V T (v ′ , v) f (t, x, v) dv ′ .
The contribution of the tumbles is introduced with a transition (scattering) kernel T (v, v ′ ) ≥ 0 which stands for the change of velocity from v ′ to v; r is the division rate of the bacteria (r = ln 2 τ 2 where τ 2 is the mean doubling time). This equation is indeed a variant of the Boltzmann equation for gases, where collisions are delocalized via the secretion or consumption of chemical cues. In (2.1), the transition kernel T also depends on the local concentration of chemoattractant S(t, x) and nutrient N (t, x). To estimate the respective contributions on pulse speed of the biais of the run lengths and of preferential reorientation, it is possible to split this transition kernel T (v, v ′ ) in two contributions, one being the tumbling rate λ(v ′ ), and the other one the reorientation effect during tumbles K(v, v ′ ):

(2.2) T (v, v ′ ) = λ(v ′ ) K(v, v ′ ),
with the condition

(2.3) V K(v, v ′ ) dv = 1,
where the function K accounts for the persistence of the trajectories. For simplicity we consider the case of the absence of such an angular persistence, hence the turning kernel T (v, v ′ ) is only proportional to the tumbling rate λ(v ′ ), i.e. K is constant.

For the tumbling rate λ(v ′ ), we assume that bacteria are sensitive to the temporal variations of attractant molecules via a logarithmic sensing mechanism [START_REF] Block | Adaptation kinetics in bacterial chemotaxis[END_REF][START_REF] Kalinin | Logarithmic sensing in Escherichia coli bacterial chemotaxis[END_REF]. Therefore, the tumble frequency only depends on the local gradients of nutrient and attractant, both gradients having independent and additive contributions. This gives

λ(v ′ ) = 1 2 λ N (v ′ ) + λ S (v ′ ) = 1 2 ψ N D log N Dt v ′ + ψ S D log S Dt v ′ = 1 2 ψ N ∂ t log(N ) + v ′ ⋅ ∇ x log(N ) + ψ S ∂ t log(S) + v ′ ⋅ ∇ x log(S) .
The nutrient and chemoattractant response functions ψ N and ψ S are both positive and decreasing, expressing that cells are less likely to tumble (thus perform longer runs) when the external chemical signal increases. These functions are smooth and characterized by their characteristic time δ -1 N and δ -1 S and their tumble frequency χ N and χ S . Here, we have chosen the following analytical form that encompassed these characteristics:

(2.4) ψ α (X) = ψ 0 1 -χ α tanh X δ α , α = {N, S},
where ψ 0 is the mean tumbling frequency, and the parameters χ N and χ S are the modulation of tumble frequency.

In order to define completely the mathematical problem (2.1), suitable boundary conditions on ∂Ω should be applied. Here we consider wall type boundary conditions, for which emerging particles have been reflected elastically at the wall. More precisely, for x ∈ ∂Ω the smooth boundary ∂Ω is assumed to have a unit inward normal n(x) and for v ⋅ n(x) ≥ 0, we assume that at the solid boundary we have

(2.5) f (t, x, v) = R[f (t, x, v)], x ∈ ∂Ω, v ⋅ n(x) ≥ 0, with (2.6) R[f (t, x, v)] = f (t, x, v -2(v ⋅ n(x))n(x)
). This boundary condition (2.5) guarantees the global conservation of mass [START_REF] Cercignani | The Boltzmann equation and its applications[END_REF].

The equations describing the behaviors of nutrients density N and chemottractant S are the same as in [START_REF] Mittal | Motility of Escherichia coli cells in clusters formed by chemotactic aggregation[END_REF]:

(2.7) ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∂S ∂t -D S ∆S = -a S + b V f (t, x, v) dv, x ∈ Ω, ∂N ∂t -D N ∆N = -c N V f (t, x, v) dv, x ∈ Ω,
where a, b and c are respectively the degradation rate of the chemoattractant, its production rate and the consumption rate of the nutrient by the bacteria, whereas D S and D N are the molecular diffusion coefficients. Finally, these equations are completed with homogeneous Neumann boundary conditions, i.e.

(2.8) ∇ x α ⋅ n(x) = 0, α = {N, S}, x ∈ ∂Ω. The purpose of this work is to present a numerical scheme for (2.1)-(2.8) and to investigate numerically the occurrence of cells aggregation, pattern formation or travelling waves when it takes place, and the convergence to equilibrium otherwise for different geometries. Several numerical methods have already been developed to solve the Patlak-Keller-Segel model for chemotaxis using finite element methods [START_REF] Marrocco | 2D simulation of chemotaxis bacteria aggregation[END_REF], finite volume methods [START_REF] Chertock | A second-order positivity preserving central-upwind scheme for chemotaxis and haptotaxis models[END_REF][START_REF] Epshteyn | Fully discrete analysis of a discontinuous finite element method for the Keller-Segel chemotaxis model[END_REF][START_REF] Filbet | A finite volume scheme for the Patlak-Keller-Segel chemotaxis model[END_REF], and the references therein. Other models have also been investigated numerically [START_REF] Filbet | Derivation of hyperbolic models for chemosensitive movement[END_REF][START_REF] Filbet | Approximation of hyperbolic models for chemosensitive movement[END_REF][START_REF] Natalini | Asymptotic high order mass-preserving schemes for a hyperbolic model of chemotaxis[END_REF]. However, it seems that none of the above-mentioned numerical approaches have been studied for kinetic models (2.1)-(2.8). In the present paper we propose a numerical scheme for (2.1)-(2.8) and investigate the influence of the geometry on the collective behavior of bacteria.

We now briefly outline the contents of the paper. In the next section, we introduce the numerical approximation of (2.1) and (2.7) and describe the numerical approximation of the boundary (2.5), (2.6), (2.8). Two points are worth mentioning here. First, we restrict ourselves to the case of specular reflection which seems to be the most appropriate for the study of bacteria. One difficulty in the approximation of kinetic models for chemotaxis, is related to the fact that it can exhibits very different phenomena as finite time blow-up, cell aggregation, wave propagations. At the discrete level, our approximation should also be able to describe a similar property. Secondly, an important step is to discretize appropriately the effect of boundary.

The final section is devoted to numerical simulations performed with the numerical scheme presented in Section 3. We investigate numerically cells aggregation, convergence to equilibrium, and wave propagation in a bounded domain.

Numerical resolution

Numerical resolution of the kinetic model (2.1). We consider a computational domain

[x min , x max ] × [y min , y max ] × V , such that Ω ⊂ [x min , x max ] × [y min , y max ].
The computational domain is covered by an uniform Cartesian mesh X h × V h , where X h , V h are defined by

(3.1) ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ X h ∶= x 0 = (x min , y min ), . . . , x i = (x ix , y iy ), . . . , x (nx,ny) = (x max , y max ) , V h ∶= {v j = v 0 (cos θ j , sin θ j ), θ j = (j + 1 2) ∆v, 0 ≤ j ≤ n v -1} .
The mesh steps are respectively ∆x = (x max -x min ) n x , ∆y = (y max -y min ) n y and ∆v = 2π n v . Let us denote f n i,j an approximation of the distribution function f (t n , x i , v j ). We introduce the following finite difference scheme

(3.2) f n+1 i,j -f n i,j ∆t + v ⋅ ∇ x,h f n i,j = Q h (f n i,j ) + r ⋅ f n i,j ,
where h = (∆t, ∆x, ∆y), v ⋅ ∇ x,h f n i,j is a second-order approximation [START_REF] Van Leer | Towards the ultimate conservative difference scheme II. Monotonicity and conservation combined in a second order scheme[END_REF] of the transport operator v ⋅ ∇ x f , and

Q h (f n i,j
) is an approximation of the Boltzmann type tumbling operator Q(f ). We will now focus on searching the approximation Q h (f n i,j ). By using the trapezoidal rule, we have

Q h (f n i,j ) = ∆v nv-1 =0 (T h ) n+1 2 i,j, f n i, -∆v nv-1 =0 (T h ) n+1 2 i, ,j f n i,j ,
where (T h )

n+1 2 i,j,
is an approximation of the transition kernel T (v, v ′ ). We assume that the nutrient density N and the chemottractant S are known at time t n+1 2 . Moreover with the hypothesis that K is constant, the condition (2.3) implies that K = 1 2π. Thus it remains to search an approximation of the tumbling rate, i.e. λ . We discretize the local gradient of nutrient as follows

(λ N ) n+1 2 i, = 1 N n+1 2 i D h N n+1 2 i + v ⋅ ∇ x,h N n+1 2 i , where D h N n+1 2 i
is a discrete time derivative and will be given in the section 3.2. Moreover we use centred difference approximation for v ′ ⋅ ∇ x N , which yields

v ⋅ ∇ x,h N n+1 2 i = v 0 cos θ N n+1 2 ix+1,iy -N n+1 2 ix-1,iy 2∆x + v 0 sin θ N n+1 2 ix,iy+1 -N n+1 2 ix,iy-1 2∆y .
In summary, the discrete tumbling rate reads

λ n+1 2 i, = 1 2 (λ N ) n+1 2 i, + (λ S ) n+1 2 i,
.

Finally we reduce the tumbling operator as follows

Q h (f n i,j ) = ∆v 2π nv-1 =0 λ n+1 2 i, f n i, -λ n+1 2 i,j
f n i,j .

3.2.

Calculate the chemoattractant S or the nutrient N . The equations (2.7) for nutrient density N and chemottractant S are parabolic equations with source terms depending on the distribution function of density f . We study again the discretization for nutrient density, since the one for chemottractant is similar. The Euler implicit scheme is used for time integration. Hence the scheme for nutrient density N reads

(3.3) D h N n+1 2 i -D N ∆ h N n+1 2 i = -cN n+1 2 i ρ n i ,
where

D h N n+1 2 i
is an approximation of time derivative as follows

(3.4) D h N n+1 2 i = N n+1 2 i -N n-1 2 i ∆t .
Then we use a five points finite difference scheme to discretize ∆N

(3.5) ∆ h N n+1 2 i = N n+1 2 ix+1,iy -2N n+1 2 ix,iy + N n+1 2 ix-1,iy ∆x 2 + N n+1 2 ix,iy+1 -2N n+1 2 ix,iy + N n+1 2 ix,iy-1 ∆y 2 .
Finally, a trapezoidal rule is applied for the integration, i.e.

ρ n i = ∆v nv-1 j=0 f n i,j . 3.
(3.6) R[f ](t, x, v) = f (t, x, v ′ ), with v ⋅ n = -v ′ ⋅ n ⇔ v ′ = v -2(v ⋅ n)n where x ∈ Γ x =
∂Ω is the point at the boundary, n is the interior normal at point x. We note that this specular reflection is just like a mirror. For example, if we follows the characteristic of the flux f (v), its reflected flow is corresponding to the velocity v ′ .

We thus use a mirror procedure to construct f at each ghost point. For instance from the ghost point x g , we can find an inward normal n(x p ), which crosses the boundary at x p (see Figure 1). For velocity v, its reflected velocity with respect to

x p is v ′ = v -2(v ⋅n(x p ))n(x p ).
Thus instead of computing f at the ghost point x g , we compute f at mirror point with respect to the boundary x m = 2x p -x g as follows The last step is to approximate f (x m , v ′ ) using f of interior domain. Let us assume that the values of the distribution function f on the grid points in Ω are given. We first construct a stencil E composed of grid points of Ω for interpolation or extrapolation. For instance as it is shown in Figure 1, the inward normal n(x p ) intersects the grid lines y = y iy , y iy+1 , y iy+2 at points P * 0 , P * 1 , P * 2 . Then we choose the three nearest points of the cross point P * l , l = 0, 1, 2, in each line, i.e. marked by a large circle. From these nine points, we can build a Lagrange polynomial q 2 (x) ∈ Q 2 (R 2 ). Therefore we evaluate the polynomial q 2 (x) at x m , and obtain an approximation of f at the mirror point. We distinguish two cases of mirror points. In the case that mirror point x m is surrounded by interior points, we interpolate f at mirror point x m ; otherwise a WENO type extrapolation can be used to prevent spurious oscillations, which will be detailed below.

(3.7) f (x g , v) = f (x m , v ′ ). x y n(x p ) n ◾ ◾ ◾ • ◾ ◾ • • • x g • • • • • x p P * 0 ◆ • • • • • P * 1 ◆ • • • • • ◆ P * 2 ⊡ i x -2 i x -1 i x i x + 1 i x + 2 i y -2 i y -1 i y i y + 1 i y + 2 ⊡ ⊙ ⊙ x m
Note that in some cases, we can not find a stencil of nine interior points. For instance when the interior domain has small acute angle sharp, the normal n can not have three cross points P * l , l = 0, 1, 2 in interior domain, or we can not have three nearest points of the cross point P * l , l = 0, 1, 2, in each line. In such a case, we alternatively use a first degree polynomial q 1 (x) with a four points stencil or even a zero degree polynomial q 0 (x) with an one point stencil. We can similarly construct the four points stencil or the one point stencil as above. Two-dimensional WENO type extrapolation. A WENO type extrapolation [START_REF] Tan | Inverse Lax-Wendroff procedure for numerical boundary conditions of conservation laws[END_REF] was developed to prevent oscillations and maintain accuracy, which is an extension of WENO scheme [START_REF] Jiang | Efficient implementation of weighted ENO schemes[END_REF]. The key point of WENO type extrapolation is to define smoothness indicators, which is designed to help us choose automatically between the high order accuracy and the low order but more robust extrapolation. Moreover a slightly modified version of the method was given in [START_REF] Filbet | Inverse Lax-Wendroff method for boundary conditions of Boltzmann equations[END_REF], such that the smoothness indicators are invariant with respect to the scaling of f . We now describe this method in 2D case.

The substencils S r , r = 0, 1, 2 for extrapolation are chosen around the inward normal n such that we can construct Lagrange polynomial of degree r. For instance in Figure 1, the three substencils are respectively

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ S 0 = {(x ix , y iy )}, S 1 = {(x ix-1 , y iy ), (x ix , y iy ), (x ix , y iy+1 ), (x ix+1 , y iy+1 )}, S 2 = {(x ix-1 , y iy ), (x ix , y iy ), (x ix+1 , y iy ), (x ix-1 , y iy+1 ), (x ix , y iy+1 ), (x ix+1 , y iy+1 ), (x ix , y iy+2 ), (x ix+1 , y iy+2 ), (x ix+2 , y iy+2 )}.
Once the substencils S r are chosen, we could easily construct the Lagrange polynomials in

Q r (R 2 ) q r (x) = r m=0 r l=0 a l,m x l y m satisfying q r (x) = f (x), x ∈ S r .
Then the WENO extrapolation has the form

(3.8) f (x) = 2 r=0 w r q r (x), x ∈ S r ,
where w r are the nonlinear weights, which are chosen to be

w r = α r ∑ 2 s=0 α s , with α r = d r (ε + β r ) 2 , where ε = 10 -6 , d 0 = ∆x 2 + ∆y 2 , d 1 = ∆x 2 + ∆y 2 , d 2 = 1 -d 0 -d 1 .
The coefficients β r are the smoothness indicators determined by

β 0 = ∆x 2 + ∆y 2 ,
and for r ≥ 1, either we take β r = 0 when f (x) = 0, ∀x ∈ S r , or we choose

β r = 1
∑ x∈Sr f (x) 2 1≤ σ ≤r K K σ -1 (D σ q r (x)) 2 dx, r = 1, 2,
where σ is a multi-index and K = [x p -∆x 2, x p + ∆x 2] × [y p -∆y 2, y p + ∆y 2] and the point x p is given by (x p , y p ).

3.3.2.

Numerical approximation for Neumann boundary condition. In section 3.2, we have seen that discrete Laplace operator (3.5) is the only non-locally in space term in (2.7). In Figure 2, we illustrate an example of a discrete Laplace operator near the boundary. We note that N ix,iy-1 is not known, since x g = (x ix , y iy-1 ) is out of domain. To approximate N at ghost point x g , we have to use the boundary condition (2.8).

In fact, if we denote n ∶= (n x , n y ), then the boundary condition (2.8) reads

n x ∂ x N + n y ∂ y N = 0.
Using a centered difference formula, it yields

n x N (x m ) -N (x g ) x m -x g + n y N (x m ) -N (x g ) y m -y g = 0,
where x g ∶= (x g , y g ), x m ∶= (x m , y m ) is the mirror point of the ghost point x g with respect to the boundary. The previous equation is equivalent to

(3.9) N (x m ) = N (x g ).
Therefore instead of computing N at the ghost point x g , we extrapolate N at the mirror point x m ∶= (x m , y m ). As shown in Figure 2, a nine points stencil S 2 is found, thus we have

(3.10) N ix,iy-1 = N (x m ) = 8 i=0 w i N (x i ), x i ∈ S 2 ,
where w i is weight of extrapolation calculated, for instance, by Lagrange polynomial. Finally by injecting (3.10) into (3.5), we complete the discretization.

Remark 3.1. It is important to emphasize that the numerical scheme for the internal domain is disconnected to the numerical procedure for the treatment of the boundary. Therefore the present method can be applied to any other numerical scheme. The main point is to preserve the order of accuracy and then to eventually increase the stencil outside the domain.

x y n ◾ ◾ ◾ ◾ ◾ ◾ ◾ • x g • • • • • x p • • • • • • • • • • ⊡ i x -2 i x -1 i x i x + 1 i x + 2 i y -2 i y -1 i y i y + 1 i y + 2 ⊙ x m

Numerical examples

In this section, we present a large variety of tests in 2d x and one dimensional in velocity space showing the validation of mathematical model and the effectiveness of our numerical schemes. In Test 1, we consider cell aggregation to study only chemotactic motility [START_REF] Mittal | Motility of Escherichia coli cells in clusters formed by chemotactic aggregation[END_REF]. In Test 2, we consider wave propagation formed by cells reorientation and the presence of nutrients in a disc. In Test 3, we study the interaction of two traveling wave in a U shape. Then in Test 4, we consider again the traveling wave but in a more wide U shape, which is similar like the effectiveness of centrifugal force. Finally in Test 5 we add the effect of cell division for long time behavior using new parameters. 4.1. Test 1 : cell aggregation. Motile bacteria are able to interact with their environment by accumulating in regions of high concentrations of certain chemicals called attractants and avoiding others called repellents. Cell division is not required to generate these multi-cellular structures because they form on a much shorter time scale than the cell-doubling time [START_REF] Mittal | Motility of Escherichia coli cells in clusters formed by chemotactic aggregation[END_REF]. The process leading to formation of multi-cellular clusters can be qualitatively understood as follows: fluctuations in the local cell density produce local gradients of attractants. Cells respond by moving up these concentration gradients thus amplifying the initial spatial nonuniformities in the cell distribution and forming multi-cellular clusters.

We thus use the model of Othmer-Dunbar-Alt [START_REF] Othmer | Models of dispersal in biological systems[END_REF] to mimic the cell aggregation as follows

∂ t f + v ⋅ ∇ x f = v ′ T [S](v, v ′ )f (t, x, v ′ )dv ′ - v ′ T [S](v ′ , v)f (t, x, v)dv ′ ,
where the tumbling kernel

T [S](v ′ , v) describes the frequency of reorientation v ′ → v T [S](v ′ , v) = ψ S ∂ t log(S) + v ′ ⋅ ∇ x log(S) ,
and the chemical signal is secreted by the cells, following the reaction-diffusion equation (2.7). We use a square domain of size [-0.25, 0.25] 2 , which is uniformly divided by a mesh size of n x × n y = 120 × 120. The velocity space belongs to the unit circle S 1 , and is uniformly divided into n v = 64 parts. All the parameters are chosen as in [START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF] and listed in Table 1. The initial chemoattractant S 0 is equal to 0, and the initial distribution function f 0 is independent of the velocity v

f 0 (x, v) = 100m π exp(-100 x 2 ),
where m is the total mass.

The evolution of the cell aggregation is presented in Figure 3. We observe that the initial density is a Gaussian distribution centered at (0, 0). At time t = 0.2 t, the density forms a volcano profile, which disappears soon and is becoming into an exponential function at time t = 1 t. Finally at time t = 10 t, a steady exponential function is formed. The last observation is similar with the sharp boundary of clusters in [START_REF] Mittal | Motility of Escherichia coli cells in clusters formed by chemotactic aggregation[END_REF]. Furthermore, we observe in Figure 4 that with the total mass equal to m = π 100, π 50 and π 25 respectively, the size of clusters is almost the same. This phenomena coincides with the conclusion in [START_REF] Mittal | Motility of Escherichia coli cells in clusters formed by chemotactic aggregation[END_REF] that the steady-state size of clusters is almost independent of the number of cells comprising them. In fact, following [START_REF] Saragosti | Mathematical Description of Bacterial Traveling Pulses[END_REF] the steady density has a form ρ(x) ≃ ρ 0 exp(-λ x ), when x → ∞, where ρ 0 is the maximum density, λ depends on χ S . Notice that the typical size of a cluster, defined as the mean radius given by

< x > = ∫ x x ρ(x)dx ∫ x ρ(x)dx = 1 λ
is independent of the total mass. This computation shows that the size of a cluster only depends on the model parameters and is entirely independent of the initial mass condition.

4.2.

Test 2 : wave propagation in a disc. Suspended Escherichia coli bacteria swim in convection-free geometries such as capillaries or micro-channels, collectively migrate towards nutrient-rich regions, in the form of propagation concentration waves [START_REF] Adler | Chemotaxis in bacteria[END_REF]. In this test, we are interested in the model (2.1)-(2.8) to study concentration waves attracted by nutrient. Moreover, we consider a disc geometry to verify the numerical discretization of boundary conditions in section 3.3. The computational domain in space is a square domain of size [-3, 3] 2 , which is uniformly divided by a mesh size of n x × n y = 80 × 80. The disc is inside of the square with radius equal to 3. It is clear that the boundary is not located on grids. Thus to achieve interior high order scheme, some artificial values on ghost points behind the boundary are needed. These values are given by using the numerical method presented in section 3.3. Moreover the velocity space belongs to the unit circle S 1 , and is uniformly divided into n v = 64 parts. All the parameters are chosen as in [START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF] and listed in Table 1. The initial distribution function f 0 is given by a Gaussian function

f 0 (x, v) = ρ 0 exp( x 2
), where ρ 0 is constant. The initial chemoattractant S 0 is equal to 0 and the initial nutrient N 0 is homogeneous equal to 1.

The time evolution of concentration wave in a disc is illustrated in Figure 5. In the first row of Figure 5, we observe that the initial Gaussian density is extending and forming a propagating wave. When the circle wave arrives at the boundary, all cell are reflected by the boundary and attracted by nutrient remained in the disc center (see the second row of Figure 5). In the third row of Figure 5, the circle wave contracts back to disc center, and finally the cells concentrates at the disc center. We notice that cell diffusion appears when circle wave goes back to disc center. In fact, this diffusion is due to the stiffness of the response functions in the tumbling kernel [START_REF] Saragosti | Directional persistence of chemotactic bacteria in a traveling concentration wave[END_REF]. 4.3. Test 3 : interaction of traveling waves in a U shape. In this test, we focus on the influence of the reorientation on the shape. The simulations are compared to a particular experiment by courtesy of Axel Buguin, Institut Curie (see the second row of Figure 9). We consider a channel of U shape, with initially homogeneous nutrient injected in the channel. Two clusters of bacteria are then imposed at two extremities of the channel. These two clusters move along the channel and finally meet at the channel center (the top of U shape). We note that these two clusters keep their bar shape till their meeting.

To perform the simulation, we consider a channel of U shape with channel width equal to 1 included in a rectangle computational domain [0, 8] × [0, 6], which is covered by an uniform mesh of size n x ×n y = 80×60. The velocity space belongs to the unit circle S 1 , and is uniformly divided into n v = 64 parts. The numerical parameters used in the simulations are listed in Table 1. The initial distribution function f 0 is given by a constant as follows

f 0 (x, v) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0.25, if 0 ≤ y ≤ 1, 0, else.
The initial chemoattractant S 0 is equal to 0 and the initial nutrient N 0 is homogeneous equal to 1.

The numerical simulations are presented in the first row of Figure 9. In Figure 9(a), we observe that two bar shape clusters form and are moving to the channel center. In Figure 9(b), two clusters go forward along the half-ring channel and keep well their bar shape. Finally in Figure 9(c), two clusters meet at the channel center. We see that the numerical simulations have a good agreement with the experiment. 4.4. Test 4 : one traveling wave in a U shape. In the last test, we consider again traveling wave in a U shape but with a more wide channel than the previous one. The experience is shown in the second row of Figure 7 and Figure 8. Again we inject homogeneous nutrient in the channel, but we consider only one cluster of bacteria at the right extremity of the channel. We observe that at straight part of channel the cluster goes ahead in a bar shape. Once the cluster enters into the half-ring part, the bacteria near interior circle goes faster than the one near the exterior circle. Moreover, bacteria contracts towards the exterior circle. Before the cluster enters into the left straight part of channel, bacteria concentrate almost near the exterior circle. When the cluster goes forward the other extremity, the cluster recovers its original bar shape.

To perform the simulation, we consider a channel of U shape with channel width equal to 3 included in a rectangle computational domain [0, 6.5] × [0, 8], which is covered by an uniform mesh of size n x × n y = 65 × 80. The velocity space belongs to the unit circle S 1 , and is uniformly divided into n v = 64 parts. The numerical parameters used in the simulations are listed in Table 1. The initial condition is the same as in the previous test.

The numerical simulations are presented in the first row of Figure 7 and Figure 8. We can see that the numerical simulations are very similar as the experience one. In fact, this phenomena is due to the directional persistence of chemotactic bacteria in a traveling concentration wave. When bacteria enter into a wide half-ring, they keep going straight and accumulate by the reflection of the exterior circle. It is very similar like the effectiveness of centrifugal force, and can be observed significantly in a wide channel. This test shows that the model (2.1)-(2.8) represents well the chemotactic bacteria behavior and our numerical discretization based on Cartesian mesh approximates well the continuous model.

∂f ∂t + v ⋅ ∇ x f = Q(f ) + rf -γΘ(ρ) Θ(ρ -ρ ∞ ), x ∈ Ω, v ∈ V,
where the division rate is given by [START_REF] Polezhaev | Spatial patterns formed by chemotactic bacteria Escherichia coli[END_REF] r = G 0 N σ + N , it takes into account two experimental facts : the slowing down of the growth rate for low nutrients concentrations and its finite quantity for high concentrations. The third term on the right hand side of (4.1) describes the vegetative cells into anabiotic form due to the increase of the local density. The transition starts when the total cell density reaches the value ρ ∞ and Θ is the Heaviside function. Actually such a source term has been proposed in [START_REF] Polezhaev | Spatial patterns formed by chemotactic bacteria Escherichia coli[END_REF] in the framework of a macroscopic Patlak-Keller-Segel model where the unknown is the total density ρ. Numerical simulations of this macroscopic model have shown pattern formations as the ones observed in experiments [START_REF] Polezhaev | Spatial patterns formed by chemotactic bacteria Escherichia coli[END_REF][START_REF] Budrene | Complex patterns formed by motile cells of Escherichia coli[END_REF]. Here we consider the following initial density f 0 (x, v) ∶= 1 if x ≤ 1, 0 else and the initial nutrient concentration is uniform N 0 = 0.5. In the nutrient and chemoattractant system of equations (2.7) we take the following parameters D S = D N = 1, the production rate of chemoattractant b = 20, the degradation rate of chemoattractant a = 8 and the consumption rate of nutrient c = 0.8, whereas in (4.1), we choose σ = 0.1, ρ ∞ = 15 and for the turning operator (2.2)-(2.4),we have δ = 20, ψ 0 = 1, χ N = 1 2 and χ S = 1 10. The numerical simulations are presented in Fig. 9. We observe that for high initial nutrient concentration, cell density in the expanding ring becomes sufficient both for the break of stability of the uniform cell distribution and for their aggregation. In particular, if after the formation of the successive set of aggregates the expanding ring had time to grasp a certain part of the cells, participating in aggregation, then a radial pattern is formed.

Conclusion

In this paper we present a new algorithm based on a Cartesian mesh for the numerical approximation of kinetic models on an arbitrary geometry boundary modelling chemosensitive movements. We present first a kinetic model for chemotactic bacteria interacting with two chemical substances, i.e. nutrient and chemottractant. Then we give the numerical discretization for this kinetic model and the numerical method for the boundary conditions based on a Cartesian mesh. A large various numerical tests in 2D x × 1D v are shown and compared with biological experiences. We conclude that on the one hand this kinetic model represents well the chemotactic bacteria behaviors and on the other hand our numerical method is accurate and efficient for numerical simulation.

.

  It is also equivalent to search the local gradients of nutrient (λ N ) the local gradients of nutrient (λ N ) n+1 2 i, , since the local gradient of attractant (λ S ) n+1 2 i, has the same expression as (λ N ) n+1 2 i,

Figure 1 .

 1 Figure 1. Spatially two-dimensional Cartesian mesh. • is interior point, ◾ is ghost point, is the point at the boundary, is the point for extrapolation, the dashed line is the boundary.

Figure 2 .

 2 Figure 2. Illustration of discretization of Laplace operator near the boundary on two-dimensional Cartesian mesh. • is interior point, ◾ is ghost point,is the point at the boundary, is the point for extrapolation, the dashed line is the boundary.

Table 1 .

 1 Summary of the values used in the simulation Parameter Value run speed v 0 = 25µm ⋅ s -1 mean tumbling frequency ψ 0 = 3s -1 modulation of tumbling frequency of nutrient χ N = 60% modulation of tumbling frequency of chemoattractant χ S = 20% stiffness of the response functions 1 δ N = 1 δ N ≈ 20s space scale x = 1mm time scale t = 40s doubling time τ 2 = ln 2 r ≈ 2h degradation rate of the chemoattractant a = 5 ⋅ 10 -3 mol ⋅ s -1 production rate of the chemoattractant b = 4 ⋅ 10 5 cell -1 s -1 consumption rate of the nutrient by the bacteria c = 2 ⋅ 10 -7 cell -1 s -1 diffusion coefficient of the nutrient molecules D N = 8 ⋅ 10 -6 cm 2 ⋅ s-1 diffusion coefficient of the chemoattractant molecules D S = 8 ⋅ 10 -6 cm 2 ⋅ s-1

Figure 3 . 1 :

 31 Figure 3. Test 1 : Time evolution of the cell aggregation: (a) cell density in domain, (b) section plot of cell density, (c) section plot in log-scale of cell density.

Figure 4 . 1 :

 41 Figure 4. Test 1 : The steady-state size of clusters comparison for different total masses at time t = 10 t: (a) section plot of cell density, (b) section plot in log-scale of cell density.

Figure 5 . 2 :

 52 Figure 5. Test 2 : Time evolution of the cell density at different time.

Figure 6 .

 6 Figure 6. Test 3 : Time evolution of the cell density (a) t= 0.65 sec. (b) t = 2.65 sec. (c) t = 4.53 sec. At the top numerical results and at the bottom experiments on Escherichia coli (courtesy of Axel Buguin, Institut Curie).

Figure 7 . 4 . 5 .

 745 Figure 7. Test 4 : Numerical simulations (top) and experiments on Escherichia coli (bottom) : time evolution of the cell density (a) t = 7.5 t (b) t = 18.5 t (c) t = 23 t in sec.

Figure 8 .

 8 Figure 8. Test 4 : Numerical simulations (top) and experiments on Escherichia coli (bottom) : time evolution of the cell density (d) t = 28 t (e) t = 34.5 t (f ) t = 46.5 t in sec.

Figure 9 .

 9 Figure 9. Test 5 : Time evolution of the cell density (a) t = 0 t (b) t = 15 t (c) t = 25 t (d) t = 35 t (e) t = 45 t and (f ) t = 55 t in sec.


Mohammed-Amine Abchir

Isis Truck

TOWARDS AN EXTENSION OF THE 2-TUPLE LIN-GUISTIC MODEL TO DEAL WITH UNBALANCED LIN-GUISTIC TERM SETS

In the domain of Computing with words (CW), fuzzy linguistic approaches are known to be relevant in many decision-making problems. Indeed, they allow us to model the human reasoning in replacing words, assessments, preferences, choices, wishes. . . by ad hoc variables, such as fuzzy sets or more sophisticated variables.

This paper focuses on a particular model: Herrera & Martínez' 2-tuple linguistic model and their approach to deal with unbalanced linguistic term sets. It is interesting since the computations are accomplished without loss of information while the results of the decision-making processes always refer to the initial linguistic term set. They propose a fuzzy partition which distributes data on the axis by using linguistic hierarchies to manage the non-uniformity. However, the required input (especially the density around the terms) taken by their fuzzy partition algorithm may be considered as too much demanding in a real-world application, since density is not always easy to determine. Moreover, in some limit cases (especially when two terms are very closed semantically to each other), the partition doesn't comply with the data themselves, it isn't close to the reality. Therefore we propose to modify the required input, in order to offer a simpler and more faithful partition. We have added an extension to the package jFuzzyLogic and to the corresponding script language FCL. This extension supports both 2-tuple models: Herrera & Martínez' and ours. In addition to the partition algorithm, we present two aggregation algorithms: the arithmetic means and the addition. We also discuss these kinds of 2-tuple models.

INTRODUCTION

Decision making is one of the most central human activities. The need of choosing between solutions in our complex world implies setting priorities on them considering multiple criteria such as benefits, risk, feasibility. . . The interest shown by scientists to Multi Criteria Decision Making (MCDM) problems, as the survey of Bana e Costa shows [START_REF] Bana | Multiple criteria decision aid: An overview[END_REF], has led to the development of many MCDM approaches such as the Utility Theory, Bayesian Theory, Outranking Methods and the Analytic Hierarchy Process (AHP). But the main lack of these approaches is that they represent the preferences of the decision maker about a real-world problem in a crisp mathematical model. As we are dealing with human reasoning and preference modeling, qualitative data and linguistic variables may be more suitable to represent linguistic preferences and their underlying aspects [START_REF] Châtel | LCP-nets: A linguistic approach for non-functional preferences in a semantic SOA environment[END_REF]. Martínez et al. have presented in [START_REF] Martínez | Computing with words in decision support systems: An overview on models and applications[END_REF] a wide list of applications to show the usability and the advantages that the linguistic information (using various linguistic computational models) produce in decision making. The preference extraction can be done thanks to elicitation strategies performed through User Interfaces (UIs) [4] and Natural Language Processing (NLP) [3] in a stimulusresponse application for instance.

In the literature, many approaches allow to model the linguistic preferences and the interpretation made of it such as the classical fuzzy approach from Zadeh [START_REF] Lotfi | The Concept of a Linguistic Variable and Its Application to Approximate Reasoning, I, II and III[END_REF]. Zadeh has introduced the notions of linguistic variable and granule [START_REF] Lotfi | Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[END_REF] as basic concepts that underlie human cognition. In [START_REF] Herrera | Computing with words in decision making: foundations, trends and prospects[END_REF], the authors review the computing with words in Decision Making and explain that a granule "which is the denotation of a word (. . . ) is viewed as a fuzzy constraint on a variable".

Among the existing models, there is one that permits to deal with granularity and with linguistic assessments in a fuzzy way with a simple and regular representation: the fuzzy linguistic 2-tuples introduced by Herrera and Martínez [START_REF] Herrera | A 2-tuple fuzzy linguistic representation model for computing with words[END_REF]. Moreover, this model enables the representation of unbalanced linguistic data (i.e. the fuzzy sets representing the terms are not symetrically and uniformly distributed on their axis). However, in practice, the resulting fuzzy sets do not match exactly with human preferences. Now we know how crucial the selection of the membership functions is to determine the validity of a CW approach [START_REF] Martínez | Computing with words in decision support systems: An overview on models and applications[END_REF]. That is why an intermediate representation model is needed when we are dealing with data that are "very unbalanced" on the axis.

The aim of this paper is to introduce another kind of fuzzy partition for unbalanced term sets, based on the fuzzy linguistic 2-tuple model. Using the levels of linguistic hierarchies, a new algorithm is presented to improve the matching of the fuzzy partitioning.

This paper is structured as follows. First, we shortly recall the fuzzy linguistic approach and the 2-tuple fuzzy linguistic representation model by Herrera & Martínez. In Section 3 we introduce a variant version of fuzzy linguistic 2-tuples and the corresponding partitioning algorithm before presenting aggregation operators (Section 4). Then in Section 5 another extension of the model and a prospective application of this new kind of 2-tuples are discussed. We finally conclude with some remarks.

THE 2-TUPLE FUZZY LINGUISTIC REPRESENTATION MODEL

In this section we remind readers of the fuzzy linguistic approach, the 2-tuple fuzzy linguistic representation model and some related works. We also review some studies on the use of natural language processing in human computer interfaces.

2-tuples linguistic model and fuzzy partition

Among the various fuzzy linguistic representation models, the approach that fits our needs the most is the representation that has been introduced by Herrera and Martínez in [START_REF] Herrera | A 2-tuple fuzzy linguistic representation model for computing with words[END_REF]. This model represents linguistic information by means of a pair (s, α), where s is a label representing the linguistic term and α is the value of the symbolic translation. The membership function of s is a triangular fuzzy set.

Let us note that in this paper we call a linguistic term a word (e.g. tall) and a label a symbol on the axis (i.e. an s).

The computational model developed for this representation one includes comparison, negation and aggregation operators. By default, all triangular fuzzy sets are uniformly distributed on the axis, but the targeted aspects are not usually uniform. In such cases, the representation should be enhanced with tools such as unbalanced linguistic term sets which are not uniformly distributed on the axis [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF]. To support the non-uniformity of the terms (we recall that the term set shall be unbalanced), the authors have chosen to change the scale granularity, instead of modifying the shape of the fuzzy sets. The key element that manages multigranular linguistic information is the level of a linguistic hierarchy, composed of an odd number of triangular fuzzy sets of the same shape, equally distributed on the axis, as a fuzzy partition in Ruspini's sense [START_REF] Ruspini | A New Approach to Clustering[END_REF].

A linguistic hierarchy (LH) is composed of several label sets of different levels (i.e., with different granularities). Each level of the hierarchy is denoted l(t, n(t)) where t is the level number and n(t) the number of labels (see Figure 1). Thus, a linguistic label set S n(t) belonging to a level t of a linguistic hierarchy LH can be denoted S n(t) = {s n(t) 0 , . . . , s n(t) n(t)-1 }. In Figure 1, it should be noted that s 2 5 (bottom, plain and dotted line) is a bridge unbalanced label because it is not symmetric. Actually each label has two sides: the upside (left side) that is denoted s i and the downside (right side) that is denoted s i . Between two levels there are jumps so we have to bridge the unbalanced term to obtain a fuzzy partition. Both sides of a bridge unbalanced label belong to two different levels of hierarchy.

Linguistic hierarchies are unions of levels and assume the following properties [START_REF] Herrera | A model based on linguistic 2-tuples for dealing with multigranularity hierarchical linguistic contexts in multiexpert decision making[END_REF]:

• levels are ordered according to their granularity;

• the linguistic label sets have an odd number n(t);

• the membership functions of the labels are all triangular;

• labels are uniformly and symmetrically distributed on [0, 1];

• the first level is l(1, 3), the second is l(2, 5), the third is l(3, 9), etc.

Using the hierarchies, Herrera and Martínez have developed an algorithm that permits to partition data in a convenient way.

This algorithm needs two inputs: the linguistic term set S1 (composed by the medium term denoted S C , the set of terms on its left denoted S L and the set of terms on its right denoted S R ) and the density of term distribution on each side. The density can be middle or extreme according to the user's choice. For example the description of S = {A, B, C, D, E, F, G, H, I} is {(2, extreme), 1, (6, extreme)} with S L = {A, B}, S C = {C} and S R = {D, E, F, G, H, I}.

Drawbacks of the 2-tuple linguistic model fuzzy partition in our context

First, the main problem of this algorithm is the density. Since the user is not an expert, how could he manage to give the density? First, he should be able to understand notions of granularity and unbalanced scales. Second, it is compulsory to have an odd number of terms (cf. n(t)) in order to define a middle term (cf. S C ). But it may happen that the parity shall not be fulfilled. For example, when talking about a GPS battery we can consider four levels: full, medium, low and empty.

Last, the final result may be quite different from what was initially expected because only a "small unbalance" is allowed. It means that even if the extreme density is chosen, it doesn't guarantee the obtention of a very thin granularity. Only two levels of density are allowed (middle or extreme) which can be a problem when considering distances such as: arrived, very closed, closed, out of reach. "Out of reach" needs a level of granularity quite different from the level for terms "arrived", "very closed" and "closed".

As the fuzzy partition obtained by this approach does not always fit with the reality, we proposed in [1] a draft of approach to overcome this problem. This is further described in [2] where we mainly focus on the industrial context (geolocation) and the underlying problems addressed by our specific constraints.

The implementations and tests made for this work are based on the jFuzzyLogic library. It is the most used fuzzy logic package by Java developers. It implements Fuzzy Control Language (FCL) specification (IEC 61131-7) and is available under the Lesser GNU Public Licence (LGPL).

Even if it is not the main point of this paper, one part of our work is to provide an interactive tool in the form of a natural language dialogue interface. This dialogue, through an elicitation strategy, helps to extract the human preferences. We use NLP techniques to represent the grammatical, syntactical and semantic relations between the words used during the interaction part. Moreover, to be able to interpret these words, the NLP is associated to fuzzy linguistic techniques. Thus, fuzzy semantics are associated to each word which is supported by the interactive tool (especially adjectives such as "long", "short", "low", "high", etc.) and can be used at the interpretation time. This NLP-Fuzzy Linguistic association also enables to assign different semantics to the same word depending on the user's criteria (business domain, context, etc.). It allows then to unify the words used in the dialogue interface for different use cases by only switching between their different semantics.

Another interesting aspect of this NLP-fuzzy linguistic association lies in the possibility of an automatic semantic generation in a sort of autocompletion mode.

For example, in a geolocation application, if the question is "When do you want to be notified? ", a user's answer can be "I want to be notified when the GPS battery level is low ". Here the user says low, so we propose a semantic distribution of the labels of the term set according to the number of the synonyms of this term. Indeed, the semantic relations between words introduced by NLP (synonyms, homonyms, opposites, etc.) can be used to highlight words associated with the term low semantically and then to construct a linguistic label set around it. The more relevant words found for a term, the higher the density of labels is around it. In comparison with the 2-tuple fuzzy linguistic model introduced by Herrera & al., this amounts to deduce the density (in Herrera & Martínez' sense) according to the number of synonyms of a term. In practice, thanks to a synonym dictionary it is possible to compute a semantic distance between each term given by the geolocation expert. If two terms are considered as synonymous they will share the same LH. Moreover, a word with few (or no) synonyms will be represented in a coarse-grained hierarchy while a word with many synonyms will be represented in a fine-grained hierarchy.

We can see here how much the unbalanced linguistic label sets can be relevant in many situations. To couple NLP techniques and fuzzy linguistic models seems very promising.

TOWARDS ANOTHER KIND OF 2-TUPLES LINGUISTIC MODEL

Starting from a running example, we now present our proposal that aims at avoiding the drawbacks mentioned above.

Running example

Herrera & Martínez' methodology needs a term set S and an associated description with two densities. For instance, when considering the blood alcohol concentration (BAC in percentage) in the USA, we can focus on five main values: 0% means no alcohol, .05% is the legal limit for drivers under 21, .065% is an intermediate value (illegal for young drivers but legal for the others), .08% is the legal limit for drivers older than 21 and .3% is considered as the BAC level where risk of death is possible. In particular, the ideal partition should comply with the data and with the gap between values (see Figure 2 that simply proposes triangular fuzzy sets without any real semantics, obtained directly from the input values). But this prevents us from using the advantages of Herrera & Martínez' method, that are mainly to keep the original semantics of the terms, i.e. to keep the same terms from the original linguistic term set. The question is how to express linguistically the results of the computations if the partition doesn't fulfill "good" properties such as those from the 2-tuple linguistic model? 2 where we notice that the label unbalance is not really respected). We recall that each label s i has two sides. For instance, the label s i associated to NoAlcohol has a downside and no upside while the term s j associated to RiskOfDeath has an upside and no downside. Two problems appear: the use of densities is not always obvious for final users, and the gaps between values (especially between LegalLimit and RiskOfDeath) are not respected.

Extension of jFuzzyLogic and preliminary definitions

To avoid the use of the densities that can be hard to obtain from the user (e.g., see the specific geolocation industrial context explained in [2]), we have evoked in [1] a tentative approach which offers a simpler way to retrieve unbalanced linguistic terms. The aim was to accept any kind of description of the terms coming from the user. That is why we propose an extension of jFuzzyLogic to handle linguistic 2-tuples in addition to an enrichment of the FCL language specification. Consequently, we suggest another way to define a TERM with a new type of variable called LING (see the example below).

VAR_INPUT BloodAlcoholConcentration : LING; END_VAR FUZZIFY BloodAlcoholConcentration

TERM S := ling (NoAlcohol,0.0) (YoungLegalLimit,0.05) (Intermediate,0.065) (LegalLimit,0.08) (RiskOfDeath,0.3); END_FUZZIFY It should be noted that the linguistic values are composed by a pair (s, v) where s is a linguistic term (e.g., LegalLimit) and v is a number giving the position of s on the axis (e.g., 0.08). Thus several definitions can now be given. Definition 3.1. Let S be an unbalanced ordered linguistic term set and U be the numerical universe where the terms are projected. Each linguistic value is defined by a unique pair (s, v) ∈ S × U . The numerical distance between s i and s i+1 is denoted by

d i with d i = v i+1 -v i .
Definition 3.2. Let S = {s 0 , . . . , s p } be an unbalanced linguistic label set and (s i , α) be a linguistic 2-tuple. To support the unbalance, S is extended to several balanced linguistic label sets, each one denoted S n(t) = {s n(t) 0 , . . . , s n(t) n(t)-1 } (obtained from the algorithm of [START_REF] Herrera | A model based on linguistic 2-tuples for dealing with multigranularity hierarchical linguistic contexts in multiexpert decision making[END_REF]) defined in the level t of a linguistic hierarchy LH with n(t) labels. There is a unique way to go from S (Definition 3.1) to S, according to Algorithm 1. Definition 3.3. Let l(t, n(t)) be a level from a linguistic hierarchy. The grain g of l(t, n(t)) is defined as the distance between two 2-tuples (s n(t) i , α).

Proposition 3.4. The grain g of a level l(t, n(t)) is obtained as: g l(t,n(t)) = 1/(n(t)-1). P r o o f . g is defined as the distance between (s n(t) i , α) and (s n(t) i+1 , α), i.e., between two kernels of the associated triangular fuzzy sets because α equals 0. Since the hierarchy is normalized on [0, 1], this distance is easy to compute using ∆ -1 operator from [START_REF] Herrera | A model based on linguistic 2-tuples for dealing with multigranularity hierarchical linguistic contexts in multiexpert decision making[END_REF] where ∆ -1 (s

n(t) i , α) = i n(t)-1 + α = i n(t)-1 . As a result, g l(t,n(t)) = (i+1) n(t)-1 -i n(t)-1 = 1/(n(t) -1
). For instance, the grain of the second level is g l(2,5) = .25.

Proposition 3.5. The grain g of a level l(t -1, n(t -1)) is twice the grain of the level l(t, n(t): g l(t-1,n(t-1)) = 2g l(t,n(t)) P r o o f . This comes from the following property of the linguistic hierarchies. Let l(t, n(t)) be a level. Its successor is defined as: l(t + 1, 2n(t) -1) (see [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF]).

Algorithm 1 Partitioning algorithm Require: (s 0 , v 0 ), . . . , (s p-1 , v p-1 ) are p pairs of S × U ; t, t 0 , . . . , t p-1 are levels of hierarchies 1: scale the linguistic hierarchies on [0, v max ], with v max the maximum v value 2: precompute η levels and their grain g (η ≥ 6) 3: for k = 0 to p -1 do 4:

d k ← v k+1 -v k 5:
for t = η to 1 do

for i = 0 to n(t k ) -1 do 12: if tmp > |∆ -1 (s n(t k ) i , 0) -v k | then 13: tmp = |∆ -1 (s n(t k ) i , 0) -v k | 14: j ← i 15: end if 16: end for 17: s n(t k ) k ← s n(t k ) j ; s n(t k ) k+1 ← s n(t k ) j+1 18:
depending on the level, , α p-1 )}

α k = v k -∆ -1 (s n(t k ) j , 0) or α k+1 = v k+1 + ∆ -1 (s n(t k ) j+1 ,

A new partitioning

The aim of the partitioning is to assign a label s n(t) i (indeed one or two) to each term s k . The selection of s n(t) i depends on both the distance d k and the numerical value v k . We look for the nearest level -they are all known in advance, see Table 1 in [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF] -i.e., for the level with the closest grain from d k . Then the right s n(t) i is chosen to match v k with the best accuracy. i has to minimize the quantity min i |∆ -1 (s

n(t k ) i , 0) -v k |.
By default, the linguistic hierarchies are distributed on [0, 1], so a scaling is needed in order that they match the universe U .

The detail of these different steps is given in Algorithm 1. We notice that there is no condition on the parity of the number of terms. Besides, the function returns a set of bridge unbalanced linguistic 2-tuples with a level of granularity that may not be the same for the upside than for the downside.

Herrera & Martínez' partitioning does not follow exactly the user wishes because it transforms them into a model with many properties, such as Ruspini condi-tions [START_REF] Ruspini | A New Approach to Clustering[END_REF]. As for us, we try to match the wishes as best as possible by adding lateral translations α to the labels s n(t) i

. From this, it results a possible non-fulfillment of the previous properties. For instance, what we obtain is not a fuzzy partition. But we assume to do without these conditions since the goal is to totally cover the universe. This is guaranteed by the minimal covering property.

Proposition 3.6. The 2-tuples (s n(t) i , α) (from several levels l(t, n(t))) obtained from our partitioning algorithm are triangular fuzzy sets that cover the entire universe U .

Actually, the distance between any pair (s

n(t) k , α k ), (s n(t)
k+1 , α k+1 ) is always strictly greater than twice the grain of the corresponding level. P r o o f . By definition and construction, d k is used to choose the convenient level t for this pair. We recall that when t decreases, g l(t,n(t)) increases. As a result, we have:

g l(t,n(t)) ≤ d k < g l(t-1,n(t-1)) (1)
After having applied the steps of the assignation process we obtain two linguistic

k+1 , α k+1 ) representing the downside and upside of labels s n(t) k and s n(t) k+1 respectively. Thanks to the symbolic translations α, the distance between the kernel of these two 2-tuples is d k . Then, according to Proposition 3.5 and to Equation 1 we conclude that:

d k < 2g l(t,n(t)) (2)
which means that, for each value in U , this fuzzy partition has a minimum membership value ε strictly greater than 0. Considering µ s n(t) i the membership function associated with a label s

n(t) i
, this property is denoted:

∀u ∈ U, µ s n(t 0 ) 0 (u) ∨ • • • ∨ µ s n(t i ) i (u) ∨ • • • ∨ µ s n(t p-1 ) p-1 (u) ≥ ε > 0 (3)
To illustrate this work, we take the running example concerning the BAC. The set of pairs (s, v) is the following: {(NoAlcohol, .0), (YoungLegalLimit, .05) (Intermediate, .065) (LegalLimit, .08) (RiskOfDeath, .3)}.

It should be noted that our algorithm implies to add another level of hierarchy: l(0, 2).

We denote by L and R the upside and downside of labels respectively. Table 1 shows the results, with α values not normalized. To normalize them, it is easy to see that they have to be multiplied by 1/.3 because v max = .3.

See Figure 4 for a graphical representation of the fuzzy partition.

AGGREGATION WITH OUR 2-TUPLES

Arithmetic mean

As our representation model is based on the 2-tuple fuzzy linguistic one, we can use the aggregation operators (weighted average, arithmetic mean, etc.) of the unbalanced linguistic computational model introduced in [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF]. The functions ∆, ∆ -1 , LH and LH -1 used in our aggregation are derived from the same functions in Herrera & Martínez' computational model. In the aggregation process, linguistic terms (s k , v k ) belonging to a linguistic term set S have to be dealt with. After the assignation process, these terms are associated to one or two 2-tuples (s n(t) i , α i ) (remember the upside and downside of a label) of a level from a linguistic hierarchy LH. We recall two definitions taken from [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF].

Definition 4.1. LH -1 is the transformation function that associates with each linguistic 2-tuple expressed in LH its respective unbalanced linguistic 2-tuple.

Addition

As we are using an absolute scale on the axis for our linguistic terms, the approach for other operators is the same as the one described above for the arithmetic means aggregation. We first apply the operator to the v values of the linguistic terms and then we use the ∆ and the LH -1 functions successively to express the result in the original term set.

If we consider for instance that, this time, we need to add the two following terms: (YoungLegalLimit, .05) and (LegalLimit, .08), we denote (YoungLegalLimit, .05) ⊕ (LegalLimit, .08) and proceed as follows:

• We add the two v values .05 and .08 to obtain β = .13.

• We then apply the ∆ function to express β in LH, ∆(0.13) = (s 33 14 , -.001).

• Finally, we apply the LH -1 function to obtain the result expressed in the initial linguistic term set S : LH -1 ((s 33 14 , -.001)) = (LegalLimit, .05).

This ⊕ addition looks like a fuzzy addition operator (see e.g. [START_REF] Herrera | A 2-tuple fuzzy linguistic representation model for computing with words[END_REF]) used as a basis for many aggregation processes (combine experts' preferences, etc.). Actually, ⊕ operator can be seen as an extension (in the sense of Zadeh's principle extension) of the addition for our 2-tuples.

The same approach can be applied to other operators. It will be further explored in our future works.

DISCUSSIONS

Towards a fully linguistic model

When dealing with linguistic tools, the aim is to avoid the user to supply precise numbers, since he's not always able to give them. Thus, in the pair (s, v) that describes the data, it may happen that the user doesn't know exactly the position v.

For instance, considering five grades (A, B, C, D, E), the user knows that (i) D and E are fail grades, (ii) A is the best one, (iii) B is not far away, (iv) C is in the middle. If we replace v by a linguistic term, that is a stretch factor, the five pairs in the previous example could be: (A, VeryStuck); (B, Far); (C, Stuck); (D, ModeratelyStuck); (E,N/A) (see Figure 5). (A, VeryStuck) means that A is very stuck to its next label. (E,N/A) means that E is the last label (v value is not applicable).

This improvement permits to ask the user for:

• either the pairs (s, v), with v a linguistic term (stretch factor);

• or only the labels s while placing them on a visual scale (i.e., the stretch factors are automatically computed to obtain the pairs (s, v));

• or the pairs (s, v), with v a numerical value, as proposed above. end if 9: end for 10: return the set of linguistic 2-tuples, one per node 6. CONCLUDING REMARKS In this paper, we have formally introduced and discussed an approach to deal with unbalanced linguistic term sets. Our approach is inspired by the 2-tuple fuzzy linguistic representation model from Herrera and Martínez, but we fully take advantage of the symbolic translations α that become a very important element to generate the data set.

The 2-tuples of our linguistic model are twofold. Indeed, except the first one and the last one of the partition that have a shape of right-angled triangles, they all are composed of two half 2-tuples: an upside and a downside 2-tuple. The upside and downside of the 2-tuple are not necessary expressed in the same hierarchy nor level. Regarding the partitioning phase, there is no need to have all the symbolic translations equal to zero. This permits to express the non-uniformity of the data much better.

Despite the changes we made, the minimal cover property is fulfilled and proved. Moreover, the aggregation operators that we redefine give consistent and satisfactory results. Next steps in future work will be to study other operators, such as comparison, negation, aggregation, implication, etc.

ACKNOWLEDGEMENT

This work is partially funded by the French National Research Agency (ANR) under grant number ANR-09-SEGI-012. In International Conference on Automated Software Engineering, page 36, Los Alamitos, CA, USA, 1997. IEEE Computer Society.

[4] Paul Booth. An Introduction to Human-Computer Interaction. Lawrence Erlbaum Associates, Publishers, New Jersey, USA, 1989.

Fig. 1 .

 1 Fig. 1. Unbalanced linguistic term sets: example of a 3 level-partition

Fig. 2 .

 2 Fig. 2. The ideal fuzzy partition for the BAC example.

  With Herrera & Martínez' method, we have S = {NoAlcohol, YoungLegalLimit, Intermediate, LegalLimit, RiskOfDeath} and its description is {(3, extreme), 1, (1, extreme)} with S L = {NoAlcohol, YoungLegalLimit, Intermediate}, S C = {LegalLimit} and S R = {RiskOfDeath}. jFuzzyLogic extension (we have added the management of Herrera & Martínez' 2tuple linguistic model) helps modeling this information and we obtain the following FCL script: VAR_INPUT BloodAlcoholConcentration : LING; END_VAR FUZZIFY BloodAlcoholConcentration TERM S := ling NoAlcohol YoungLegalLimit Intermediate | LegalLimit | RiskOfDeath, extreme extreme; END_FUZZIFY The resulting fuzzy partition is quite different from what was initially expected (see Figure 3 compared to Figure

Fig. 3 .

 3 Fig. 3. Fuzzy partition generated by Herrera & Martínez' approach.

Fig. 4 .

 4 Fig. 4. Fuzzy partition generated by our algorithm for the BAC example.

(

  Received 2011/07/31) R E F E R E N C E S [1] Mohammed-Amine Abchir. A jFuzzyLogic Extension to Deal With Unbalanced Linguistic Term Sets. Book of Abstracts, pages 53-54, 2011.[2] Mohammed-Amine Abchir and Isis Truck. Towards a New Fuzzy Linguistic Preference Modeling Approach for Geolocation Applications. In Proc. of the EUROFUSE Workshop on Fuzzy Methods for Knowledge-Based Systems, pages 413-424, 2011.

Fig. 6 .

 6 Fig. 6. Example of the simplification of a binary tree

Table 1 .

 1 The 2-tuple set for the BAC example.

  Algorithm 2 Simplification algorithm Require: o is a node, T is a binary tree, o is the root node of T 1: o ← (s 3 0 , 0) 2: for each node o ∈ T, o = o do

	3:	let (s j i , k) be the parent node of o
	4:	if o is a left child then
	5:	o ← (s 2j-1 2i-1 , 0)
	6:	else
	7:	o ← (s 2j-1 2i+1 , 0)

8:

When talking about linguistic terms, S (calligraphic font) is used, otherwise S (normal font) is used.

Definition 4.2. Let S = {s 0 , . . . , s g } be a linguistic label set and β ∈ [0, g] a value supporting the result of a symbolic aggregation operation. Then the linguistic 2tuple that expresses the equivalent information to β is obtained with the function ∆ : [0, g] -→ S × [-.5, .5), such that

where s i has the closest index label to β and α is the value of the symbolic translation.

Thus the aggregation process (arithmetic mean) can be summarized by the three following steps:

1. Apply the aggregation operator to the v values of the linguistic terms. Let β be the result of this aggregation.

2. Use the ∆ function to obtain the (s r q , α q ) 2-tuple of LH corresponding to β.

3. In order to express the resulting 2-tuple in the initial linguistic term set S, we use the LH -1 function as defined in [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF] to obtain the linguistic pair (s l , v l ).

To illustrate the aggregation process, we suppose that we want to aggregate two terms (two pairs (s, v)) of our running example concerning the BAC: (YoungLegal-Limit, .05) and (LegalLimit, .08). In this example we use the arithmetic mean as aggregation operator.

Using our representation algorithm, the term (YoungLegalLimit, .05) is associated to (s 9 1 , .125) and (s 33 5 , .003) and (LegalLimit, .08) is associated to (s 17 4 , .005) and (s 3 1 , -.07). First, we apply the arithmetic means to the v value of the two terms. As these values are in absolute scale, it simplifies the computations. The result of the aggregation is β = .065.

The second step is to represent the linguistic information of aggregation β by a linguistic label expressed in LH. For the representation we choose the level associated to the two labels with the finest grain. In our example it is l(5, 33) (fifth level of LH with n(t) = 33). Then we apply the ∆ function on β to obtain the result: ∆(.065) = (s 33 7 , -.001). Finally, in order to express the above result in the initial linguistic term set S, we apply the LH -1 function. It associates to a linguistic 2-tuple in LH its corresponding linguistic term in S. Thus, we obtain the final result LH -1 ((s 33 7 , -.001)) = (YoungLegalLimit, .005).

Given that countries have different rules concerning the BAC for drivers, the aggregation of such linguistic information can be relevant to calculate an average value of allowed and prohibited blood alcohol concentration levels for a set of countries (Europe, Africa, etc.). It should be noted that the first case ensures to deal with fully linguistic pairs (s, v). It should also be noted that our stretch factor looks like Herrera & Martínez' densities, but in our case, it permits to construct a more accurate representation of the terms.

Towards a simplification of binary trees

The linguistic 2-tuple model that uses the pair (s n(t) i , α) and its corresponding level of linguistic hierarchy can be seen as another way to express the various nodes of a tree. There is a parallel to draw between the node depth and the level of the linguistic hierarchy. Indeed, let us consider a binary tree, to simplify. The root node belongs to the first level, that is l(1, 3) according to [START_REF] Herrera | A model based on linguistic 2-tuples for dealing with multigranularity hierarchical linguistic contexts in multiexpert decision making[END_REF]. Then its children belong to the second one (l(2, 5)), knowing that the next level is obtained from its predecessor: l(n+1, 2n(t)-1). And so on, for each node, until there is no node left. In the simple case of a binary tree (i.e., a node has two children or no child), it is easy to give the position -the 2-tuple (s n(t) i , α) -of each node: this position is unique, left child is on the left of its parent in the next level (resp. right for the right child).

The algorithm that permits to simplify a binary tree in a linguistic 2-tuple set is now given (see Algorithm 2). If we consider the graphical example of Figure 6, the linguistic 2-tuple set we obtain is the following (ordered by level): {(s 3 1 , 0), (s 5 1 , 0), (s 5 3 , 0), (s 9 5 , 0), (s 9 7 , 0), (s 17 9 , 0), (s 17 11 , 0)}, where a ← (s 3 1 , 0), b ← (s 5 1 , 0), c ← (s 5 3 , 0), d ← (s 9 5 , 0), e ← (s 9 7 , 0), f ← (s 17 9 , 0) and g ← (s 17 11 , 0). The last graph of the figure shows the semantics obtained, using the representation algorithm described in [START_REF] Herrera | A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[END_REF].

In a way, this algorithm permits to flatten a binary tree into a 2-tuple set which can be useful to express distances between nodes. The opposite is also true: a linguistic term set can be expressed through a binary tree. One of the advantages to perform this flattening is to consider a new dimension in the data of a given problem. This new dimension is the distance between the possible outcomes (the nodes that can be decisions, choices, preferences, etc.) of the problem and this would allow for a ranking of the outcomes, as if we had a B-tree. The fact that the level of the linguistic hierarchy is not the same, depending on the node depth, is interesting since it gives a different granularity level, and, as with Zadeh's granules, it permits to connect a position in the tree and a precision level.