Stavros Meskos
email: stameskos@imbm.bas.bg

Stefan Stefanov
email: stefanov@imbm.bas.bg

Knudsen

A Marie-Curie-ITN within H2020 ISTEGIM 2019-285175 DECOMPOSITION OF GASEOUS MIXTURE INTO BALLISTIC AND COLLISION PART: MATHEMATICAL FORMULATION AND APPLICATION WITH DSMC METHOD

In this work, the method of decomposition of a gaseous flow refers to the process of investigating the flow by separating the gas particles into two groups, namely the "ballistic" one, composed of particles that have arrived at a defined space having performed free movement, with their last collision to be with a boundary wall and the "collision" one, for the particles group that arrived at the same space having previously experienced at least one intermolecular collision. The mathematical formulation of the decomposition method for gas mixtures is presented. Next, the method is incorporated into the Direct Simulation Monte Carlo method and used to model and simulate the flow and the process of gas mixing of two gases inside a simple two-dimensional configuration of a micro-mixer.

INTRODUCTION

In general, a kinetic solution at some point in a flow domain consists of two parts, namely the ballistic and the collision parts. The former one is due to particles arriving at this point from the boundaries with no collisions, while the latter one is due to particles arriving at this point after an arbitrary number of collisions (at least one). From the Boltzmann equation, the dimensionless velocity distribution function , xy may collide other particles in their movement after that point. This novel approach of modeling a gas flow was conceptualized and presented by the group of Vargas, Tatsios, Valougeorgis and Stefanov in order to investigate a thermally induced rarefied single gas flow in a rectangular enclosure with non-isothermal walls [START_REF] Vargas | Rarefied gas flow in a rectangular enclosure induced by non-isothermal walls[END_REF]. The same year, the same approach was used to predict the Knudsen minimum and provide a quantitative measurement that verified the previously reported qualitative physical arguments of the Knudsen "paradox" [START_REF] Tatsios | Predicting the Knudsen paradox in long capillaries by decomposing the flow into ballistic and collision parts[END_REF]. The readers are referred for a detailed reasoning and the derivation of the equations for the decomposition of a single gas flow in [START_REF] Tatsios | Predicting the Knudsen paradox in long capillaries by decomposing the flow into ballistic and collision parts[END_REF][START_REF] Tatsios | Advanced deterministic and stochastickinetic modeling of gaseous microscaletransport phenomena[END_REF]. Here, following from the latter works the solution is extended to cover the more general case of gas mixtures. In the following sections, the mathematical formulation of the decomposition method for gas mixtures is presented, focusing on the derivation of the macroscopic density, velocity and temperature. Furthermore, the decomposition is implemented in the DSMC method and it is employed to analyze the flow properties of two gases during the mixing process inside a micro-mixer.

MATHEMATICAL FORMULATION

For the general case of gas mixtures, the following variables are defined: the macroscopic density is equal to the sum of the individual species densities 1 ()

Nsp pp p m n nm  = ==  , ( 1
)
where Nsp is the total number of species, p m and p n the species mass and number density respectively and n the mixture's number density. The mass average velocity is defined by

( ) 0 1 1 / Nsp p p p p c m n c mc m  = ==  (2)
The peculiar or thermal velocity c of each molecule is measured relative to 0 c , that is 0 c c c  =-, and the mean thermal velocity of species p is

0 pp c c c  =- (3)
This quantity is called the diffusion velocity and is denoted by p C . The species translational temperature is calculated as follows ( )

2 2 2 2 ,, 3 1 1 or 2 2 2 3 p B tr p p p p p tr p p p B m k T m c m C T c C k   = + = + (4)
The number density the velocity and the temperature of species p are decomposed according to

( ) ( ) bc p p p n n n =+ , ( 6
) ( ) ( ) , , , bc p p p u u u    =+, (7)
( ) ( ) , , , , , , bc tr p tr p tr p T T T    =+, (8)
where the superscripts () b and () c denote the ballistic and collision parts respectively and ,,

x

DIRECT SIMULATION MONTE CARLO IMPLEMENTATION

The prescribed decomposition of the particle distribution in a given cell of the computational grid with center point ( ) As a result, the total number of all particles accumulated in a cell is divided into two groups

,
( ) ( ) bc T N N N =+
and the macroscopic quantities are sampled into the two corresponding parts. From equations ( 7), ( 8) and ( 9) the corresponding number densities, velocities and translational temperatures per species are formed as

( ) ( ) ( ) ( ) , bc pp bc pp cc NN nn SV SV == (9)   ( ) ( ) ( ) ( ) , , , , 1 1 1 1 11 1 ( ) ( ), ( ) ( ) kk N t N t SS bc p i k i k p i k i k k i k i TT u I t u I t t NN      = = = = = - =     (10) and ( ) ( ) ( ) ( ) ( ) ( ) () 22 ()
,0 11

() 22 () ,0 11 1 1, 1 k k Nt S b p pi k p i p p ki Tp Nt S c p pi k p i p p ki Tp T I t u c N T I t u u c N   = - - + -     = - + -     (11)
where S is the total number of samples, c V is the volume of the current cell, () k Nt is the total number of particles inside the cell at time k t and

TEST CASE: Application of the decomposition method to a gas micro-mixer

The decomposition method was implemented as described above in an in-house developed DSMC code. The test case is based on one of our previous published work [START_REF] Meskos | Gas mixing and final mixture composition control in simple geometry micro-mixers via DSMC analysis[END_REF] and refers to a simple 2-dimensional configuration composed by two parallel plates of length L , positioned in 0 y = and yH = respectively. A splitter plate with length equal to /4

L is positioned at /2 yH = and in parallel with the other two, forming in that way two inlets. Two pure gases enter the domain from the upper and lower inlet respectively and they start mixing after the end of the splitter plate and the area defined at /4 L x L  is considered as the main mixing zone. The flow is induced by a pressure difference. A fixed pressure is applied equally at both inlets at 0 x = , while at xL = vacuum condition is set in order to prevent backflow. In [5] the value relative density difference , pj  is defined per species p at a column of cells j , and it provides a homogeneity index, in the ideal case where , 0 pj  → the species p at column j is considered perfectly homogeneous.

In this work  since the majority of the particles will perform ballistic movement. In contrast, for large inlet pressures, where 0.001 Kn  , the evolution of , pj  across the length of the mixer will coincide to () , c pj  since the majority of the particles will perform collisional movement. The evolutions of relative density differences for two cases corresponding to inlet pressures 1(a) and (b) respectively. The working gases are CO entering from the upper inlet and N2 entering from the lower inlet. The relative density differences [START_REF] Meskos | Gas mixing and final mixture composition control in simple geometry micro-mixers via DSMC analysis[END_REF] "rdd 1", "rdd 2", "rddfm 1", "rddfm 2", "rddc 1" and "rddc 2" correspond to  in (b), are both evolving separately and do not coincide with the rest. This behavior is expected, since in DSMC there is a probability that a very small number of particles will perform intermolecular collisions in a highly rarefied flow (a) and similarly a number of particles will perform ballistic movement, most probably only at the cells adjacent to the wall boundaries, in near continuum flow (b). However, since in both cases this number is very small, their contribution to the mixture's macroscopic flow values is equivalently very small. For demonstration purposes, in Fig. 3

CONCLUSION

The decomposition method has been applied to gaseous mixtures. The derivation of the mathematical formulas of ballistic and collision parts as well as the extraction of macroscopic values have been presented. A test case of mixing two gases in a simple micro-mixer is presented in order to validate the implementation in a DSMC code and illustrate the analysis of a mixture problem. The decomposition of the flow at a micro scale into ballistic and collision part could be interpreted as a result of transport process due to diffusion and advection respectively in macro-physics and -engineering. For the case of a slip flow regime, the final result is provided by simple addition of ballistic and collision part in micro-scale corresponding to a convection in macro-scale which is the combination of advective and diffusive transport.

  and collision parts of the distribution function respectively. It is noted that particles contributing to the ballistic part of the solution at point ( )

2 A

 2 Proceedings of the International Symposium onThermal Effects in Gas flows In Microscale October24-25, 2019 -Ettlingen, Germany Marie-Curie-ITN within H2020

  where B k is the Boltzmann's constant and p c is the single species thermal velocity measured relative to the average velocity p c of the species, that is p p p c c c  =-[START_REF] Bird | Molecular gas dynamics and the direct simulation of gas flows[END_REF]. The total translational temperature is given by

3 Awith indicators 1 jI

 31 xy can be implemented in the basic DSMC algorithm by making some additions in the indexing stage. More specifically, all model particles 1, , T jN = taking place in the simulation are tagged by introducing the indicator j I , which has the value of 0 or 1 indicating if a particle contributes to the ballistic or the collision part of the distribution respectively. A particle passes into the ballistic part when it is Proceedings of the International Symposium on Thermal Effects in Gas flows In Microscale October24-25, 2019 -Ettlingen, Germany Marie-Curie-ITN within H2020reflected from a wall and goes into the collision part when interacts with another particle. The indicator is set to 0 each time that a particle is reflected from the bounding walls, while in the stage of particle free motion the indicators are not changed. In the stage of binary collisions the indicators ( ) ji I ,I of any pair of particles ( ) , ji involved in a collision are set to 1. During the simulation process the particle indicators may change their values all the time. In the sampling stage of the macroscopic properties at given time k are considered belonging to the ballistic part of the particle distribution and all particles = to the collision part.

  the molecular velocity and the averaged molecular velocity of species p respectively. The terms ( ) squared single species thermal velocity and to the squared diffusion velocity respectively, as shown in Eq.(5).

 4 A

 4 are calculated as well, corresponding to the density differences of the fraction of particles p that belong to ballistic and collision part respectively. A simple test to validate the implementation of decomposition is to investigate the two extreme cases in terms of inlet pressure. For very small inlet pressures, where 1 Kn  it is expected that the evolution of , pj  across the length of the mixerProceedings of the International Symposium onThermal Effects in Gas flows In Microscale October24-25, 2019 -Ettlingen, Germany

  Fig.1(a) and (b) respectively. The working gases are CO entering from the upper inlet and N2 entering from the lower inlet. The relative density differences[START_REF] Meskos | Gas mixing and final mixture composition control in simple geometry micro-mixers via DSMC analysis[END_REF] "rdd 1", "rdd 2", "rddfm 1", "rddfm 2", "rddc 1" and "rddc 2" correspond to

  both cases the expected outcome is retrieved. It is worth noting the collision part of()

2 inFigure 1 .

 21 Figure 1. Relative density difference evolutions over the main mixing zone for the cases: (a) inlet pressure equal to 0.001 atm and (b) inlet pressure equal to 2 atm.

5 AFigure 2 .

 52 Proceedings of the International Symposium onThermal Effects in Gas flows In Microscale October24-25, 2019 -Ettlingen, Germany Density contours of (a) mixture's total, (b) collision part and (c) ballistic part for the case with inlet pressure equal to 2 atm.

Acknowledgementsa

This project has received funding from the European Union's Framework Programme for Research and Innovation Horizon 2020 (2014-2020) under the Marie Sklodowska-Curie Grant Agreement No. 643095. Also the second author S.S. would like to acknowledge the partial support provided by the Bulgarian NSF under grand DN 02/7 -2016.


Stavros Meskos
email: stameskos@imbm.bas.bg

Stefan Stefanov
email: stefanov@imbm.bas.bg

A Direct Simulation Monte Carlo Approach on the Riemann Problem for Gas Mixtures

The Direct Simulation Monte Carlo method is employed to solve the "1D -Sod-Shock tube problem", a special case of Riemann problems, for gas mixtures. Initially, two different gas species are distributed separately in the high and low pressure sides of the tube without interacting with each other. For time greater than zero the species start mixing and shock and rarefaction waves are formed moving in opposite directions. In this work, the mixing process between different kinds of gas species was investigated by observing differences in waves' formation. The influence of the mass and diameter ratio between the species was studied in detail. It was found that greater mass differences had very strong effect on the mixing process, while the effects due to diameter differences were relatively small. Finally, it is shown that in case of single species the interaction molecular models of hard sphere, variable hard sphere and variable soft sphere gave the same results, while for gas mixtures the variable hard sphere and variable soft sphere models gave slightly different results.

INTRODUCTION

Gas flows in micro-scale have received increasing attention in the past two decades. Advances in micro and nano-fabrication technology have opened the road for Micro-Electro-Mechanical-Systems (MEMS) and Nano-Electro-Mechanical-Systems (NEMS) [1][START_REF] Chaudhuri | Recent Advances in Technologies[END_REF][START_REF] Nguyen | Mixing in Microscale[END_REF][START_REF] López Quesada | [END_REF]. Such devices, depending on the application, can operate with certain kind of fluids. Very common working fluids are gases and so far single gas flows in micro scale have been extensively studied [5][6][7][8][9][10][11][12]. However, only recently the focus has shifted to gas mixtures and the process of gas mixing that are frequently met in real applications [13][14][15][16][17][18][19][20]. MEMS refer to devices with characteristic lengths starting as low as 1μm up to 1mm, therefore very often the characteristic length of the problem in study is critically small, comparable to the mean free path of the gas molecules. In such cases, the continuum assumption of the fluid is no longer valid and the classical Navier-Stokes equations cannot describe accurately the flow field. Similar conditions at higher Knudsen numbers are also met in large-scale spaces when the pressure is very low. For both cases mentioned above, where the flow depart from continuum regime, other approaches have been employed and amongst them, the most common are the deterministic Discrete Velocity (DVM) [START_REF] Sharipov | Discrete Velocity Method[END_REF] and Lattice Boltzmann (LBM) [START_REF] Mcnamara | [END_REF] methods that solve the Boltzmann equation and the Direct Simulation Monte Carlo (DSMC), a stochastic particle-based method [START_REF] Bird | Molecular Gas Dynamics and the Direct Simulation of Gas Flows[END_REF]. In this work, the DSMC method is employed to investigate the gas mixing process at the Sod-Shock tube problem, which is a form of the well-known Riemann problem in continuum mechanics with existing analytical solution in the case of single gas [START_REF] Sod | [END_REF]. Although the Riemann problems have been extensively studied and there is a plethora of published work, there are only a few papers that investigate the same problems with numerical methods employed in slip and rarefied regimes [25][26][27][28]. To the authors best knowledge it is the first time that a Riemann problem for gas mixtures is solved with the DSMC method.

PROBLEM STATEMENT

The Riemann problem in gas dynamics refers to a specific initial value problem defined in space [0,1] with conditions given by  

, for 0.5 ,,

, for x 0.5

L L L R R R u p x up up          (1)
A mechanical realization of the Riemann problem is a shock tube. Such tube consists of a long tube with a diaphragm in the middle. Initially, the volume to the left is filled with gas having density and pressure L  and L p respectively, while volume to the right of the diaphragm is filled with gas having density and pressure R  and R p respectively. The corresponding bulk velocities at the areas right and left of the diaphragm L u and R u respectively, can be both or individually greater, less or equal to zero. The particular configuration that is investigated in this work is the Sod shock tube problem, originally studied by Gary A. [START_REF] Sod | [END_REF] [START_REF] Sod | [END_REF] with specific initial values defined as

 

1 0 1 for 0.5 ,, 0.125 0 0.1, for x 0.5

x up        (2)
A schematic diagram of the initial condition before the diaphragm is removed is provided in Fig. 1. Figure 2 depicts a quality plot of pressure at time t equal to zero, where numbers 1 and 5 correspond to the initial high and low pressure areas respectively. At time 0 t  the diaphragm is suddenly removed and there is an initial discontinuity in the contact surface. Immediately after that a shock and a rarefaction waves are formed, where the shock is traveling from high to low pressure area, while the rarefaction wave is traveling on the opposite direction. For 0 t  the states of the flow can be described in five different areas as depicted in Fig. 3. Zones 1 and 5 correspond to the undisturbed high and low density states keeping their values from the initial condition. The head and foot of the rarefaction and shock wave are located at the interfaces between zones 1 and 2 and zones 2 and 3 and respectively between zones 4 and 5 and 3 and 2. Finally, the contact surface, which also travels towards the low pressure area, following the shock head lies inside the shock wave and it is located at the interface between the zones 3 and 4. Density and temperature are discontinuous within the zones surrounding the contact surface while pressure and velocity are constant. The process in zone 2 is isentropic and the flow properties gradually change.

NUMERICAL METHOD AND CODE VALIDATION

Flow regimes and mathematical formulation

In general, the gas flow is characterized by the Knudsen number, which is defined as ratio of mean free path to characteristic length of the problem and reads as follows

Kn L   (3)
where the mean free path  is given by

2 1 2 dn    , (4)
d is the diameter of the molecule and n is the number density, related to mass density  and molecular mass m by nm

  . ( 5
)
The equation of state is given by . The gas flows with Knudsen numbers in the range of 31 10 10 Kn   are considered to be in slip regime, a moderate rarefied area, where velocity slip and temperature jump at wall strongly influences heat transfer [29]. Finally, for Knudsen numbers

B p nk T  , (6)
a n C n  , (7)
where

2 1 nn      . ( 8
)
The Direct Simulation Monte Carlo method

The DSMC is a particle-based stochastic method that can simulate gas flows in the whole spectrum of the Knudsen regime. It is worth noting that it is extremely efficient for flows in slip and rarefied regimes but becomes computationally very expensive in continuum regime. The main principle of the method is the decoupling of the motion and collision processes of the particles within each time step of the numerical simulation. The computational domain is divided into cells. The simulated number of particles is a fraction of the real number; a weighted number density is defined as

w w n n F  (9)
where w F is the weight factor. Initially, particles are randomly distributed in cells with molecular velocities sampled from the Maxwellian distribution. Next, within a time step the particles are moved through the cells proportionally to their velocity, then collisions only between particles within the same cell are realized stochastically by using collision probability distribution and finally, macroscopic gas properties such as average flow velocity and number densities are sampled at each cell. This process is repeated each time step and the simulation continues in time until steady-state conditions are reached. There are two possibilities for averaging. The first employs time averaging of accumulated data over a time interval of finite number of time steps k dt  that corresponds to one sample step. This averaging method is usually sufficient when only the steady-state solution is of interest. However, in order to derive accurate results for the transient period as well, an ensemble averaging method is employed along with the time averaging method, where many independent simulations are performed and results are additionally averaged at the same sample steps by ensemble averaging over all simulations. The collision scheme, employed in this work is the No-Time-Counter and particles are modeled as hard spheres [START_REF] Bird | Molecular Gas Dynamics and the Direct Simulation of Gas Flows[END_REF]. An in-house DSMC code was developed and employed in this work, which combines both time and ensemble averaging methods.

Code Validation

The classical 1D Sod-Shock tube problem is considered. Before proceeding to the actual gas mixing problem the correctness of the code was verified by replicating a case of a single gas as presented by Tiwari et al. [25] and comparing the results with both theirs as well as with the analytical solution. The following parameters have been used. The gas is chosen as Argon with molecular mass sec. This particular configuration as described above will be referred to as the "base configuration". In Fig. 4 the mass density evolution is plotted over the length of the tube, with the dashed line corresponding to the current work, while with dotted and solid lines to the Tiwari and analytical solutions respectively. The results of this works are in very good agreement with the others. It is important to notice, that the perfect sharp discontinuities as calculated by the analytical solution are impossible to retrieve with the numerical methods. Instead the interfaces between the otherwise distinctive zones are smooth transitions from one flow state to another. Finally, with the analytical solution the exact positions of those states are measured as follows, the head and foot of the rarefaction at 0.29

From continuum to rarefied regime

For the next test case, the base configuration was used. However the mass densities in both sides were reduced each time by a factor of ten while keeping the same ratio between them. The evolution of mass densities was compared between flows in continuum, slip and rarefied regimes. In the following sections the results for gas mixtures are presented and organized as follows: In the first part the comparison is conducted over pairs between four noble gases. Next, follows a series of tests to investigate the mass ratio and diameter ratio influence to the mixing process independently. Finally, the impact of the three most commonly employed phenomenological molecular models, namely the hard sphere, the variable hard sphere and the variable soft sphere is investigated on a single gas, as well as, on a gas mixture case.

RESULTS

Mixing of noble gases

Following the base configuration as described in the previous section, simulations with different gas species were conducted by letting on the left side of the diaphragm, where the high density area lies, the gas Argon, as was before, while replacing it, on the right side, the low density area, with Neon, Helium, and Xenon respectively. The cases that are tabulated in Table 1 were chosen in purpose in order to cover a wide range of mass and diameter ratios. The corresponding mass density profiles are depicted in Fig. 6. It was immediately noticed that the profiles were very different from each other. With a more careful observation two differences were noticed. The value of density between the foot of the shock wave and the contact surface, marked in the previous section as zone [START_REF] Nguyen | Mixing in Microscale[END_REF], is increased when the gas in the right side is lighter and with smaller diameter e.g. Ne, He, while it is decreased for the case of the heavier Xe. The second observation refers to the contact surface and more generally to the formation of all five zones. While for the cases of Ar-Ar and Ar-Ne all zones were visible, for the much heavier Xe the contact surface is almost nonexistent, which means that there were no longer discontinuities in the corresponding zones, and for the case of the much lighter He the shock and rarefaction waves have exchanged positions and the mixture is moving in the opposite direction. Although the above cases have already provided with a first insight in the mixing behavior, they were not adequate to provide specific pattern behavior so that safe conclusions to be drawn. For that reason two series of simulations were conducted. A gas species having all the properties of the monatomic noble gases was defined with mass m and considered as hard sphere. This gas will be referred to as the reference gas. For the first series of simulations the base configuration was investigated were the reference gas was positioned in both sides of the diaphragm and in each simulation the mass ratio was different while the diameter remained fixed. For the second series of simulations, following the same logic, the mass was fixed, while the diameter ratio varied. In that way, it was possible to investigate the mass and diameter influence unaffected from each other.

Influence of the mass ratio

The results below correspond to the base configuration with the reference gas having fixed diameter in all cases while the corresponding mass ratios between the species in the left and right side of the diaphragm are depicted in the legends of the Figures [7][8][9][10][11]. The solution corresponds to time sec. The exact mass ratios are the 1:1 corresponding to single gas case, 1:2, 1:3, 1:5 and 1:10 where the light gas is on the high density (left) side, and 2:1, 3:1, 5:1 and 10:1 where the light gas is on the low density (right) side. In Fig. 7 the mass density profiles provide the first set of results. For the cases with the solid lines when the mass on the right side is increased the standard downward step corresponding to the third zone, as observed in the classic Sod problem is gradually replaced with an upward step, this is firstly noticed in the case of 1:5 and it becomes clear in the case of 1:10. For the rest of the cases with opposite mass ratios it is interesting that the same behavior as in Fig. 6 with Ar-He is retrieved, firstly noticed at the case of 5:1 and became clearer at 10:1.

In Fig. 8 the molar fraction of the left species is depicted, when it is equal to one, the area is filled with pure left gas, while when equal to zero the area is filled with the right gas only. Focusing first on the solid lines it is seen that up until the position at 0.6 x  m the molar fraction is 1

Left C  which indicates that the mixing has not started yet, however, for the same position looking at Fig. 7 the mixture's density has been greatly reduced. This suggested that the mixing process did not start immediately after the diaphragm was removed neither did it happen at the middle position at 0.5 x  m, in contrast, the light species initially diffused from the high to low pressure area without mixing rather pushing or rather compressing the heavier species further to the right. This behavior explained the increase in density that was observed for the cases 1:5 and 1:10 in Fig. 7 at the area   0.6, 0.7 x 

. For the other set of cases with the dashed lines, the situation appears to be the opposite. The mixing process has started immediately and the greater the mass ratio the further had the light gas diffused from the low density area into the high density area with the heavy gas. In Fig. 9 where the temperature profiles are presented, is worth noticing that for the mass ratios of 1:3, 1:5 and 1:10 the corresponding temperatures at the right end are higher than the fixed value in the initial undisturbed areas, the reason for this behavior is that for these cases and for the chosen solution time the heads of the shock waves had already reached the right boundary and had reflected backwards. The higher the temperature the further the shock had traveled in the opposite direction. Next, the velocity profiles in Fig. 10 shed more light into what happened with the cases of 5:1 and 10:1. It is seen especially for the latter ratio that there are regions that the mixture's velocity is negative explaining the high peek in density profiles approximately at   0.3, 0.4 x  .

Influence of diameter ratio

Following the above logic as with the mass ratio results, the same base configuration is employed with the same reference gas, however, this time the species mass was fixed at both sides while their diameters were varying. In order to match the most common diameter differences met in real gases the ratios were chosen as 1:1 for the same species case, 1:1.25, 1:1.5, 1:1.75 and 1:2 when the smaller diameter species is on the (left) high density side and 1.25:1, 1.5:1, 1.75:1, 2:1 when the smaller diameter species is on the (right) low density side. A first observation on the figures suggested that diameter difference between species did influence the process of mixing, however in a much smaller scale than due to mass difference. In Fig. 12 , which corresponds to the area from the foot of the rarefaction to the contact discontinuity, the flow's transition was much smoother in (a) than in (b). However, at the other half of the shock wave, that is, the area approximately at   0.63, 0.85 x  , that is the area from the contact discontinuity until the head of the shock wave, the transition is much smoother in (b) than in (a). The above indicates that the wave formation and the distinction between the regions as seen in the analytical solution are replicated better with larger diameter particles than with smaller. In Fig. 13(a) and (b) the molar fraction of the left species is depicted for the smaller and larger diameter species respectively. The importance of these plots is twofold. First, they are almost identical, which indicates that the mixing process is affected in the same way regardless of the differences in diameter ratios between the two figures. Second, in both figures the molar fraction was reduced at the location of the diaphragm, which means that the mixing started immediately after the removal of the diaphragm, contrary to the case as shown before between the heavier and lighter species.

Finally, in Fig. 13(a) and (b) the velocity profiles are depicted for the two sets of diameter ratios respectively. Here, symmetry appears between the two figures covering the area between the regions 3 and 4. That is regions 3 and 4 of Fig. 13

Influence of the molecular model

In DSMC the most prevalent molecular models are the Hard Sphere (HS), the Variable Hard Sphere (VHS) and the Variable Soft Sphere (VSS). The HS model is the most simplistic one, physically it means that two particles cannot be closer than their diameter and when they are separated their interaction force is zero. However, it fails to provide the correct diameter of the species at different temperatures. The VHS model, introduce a hard sphere molecule but with a diameter that is a function of the translational molecular velocity, in that way it allows for the diameter to be corrected at each cell and time step [30]. A next step further from the VHS model is given by the VSS model in which the diameter varies in the same way as with the VHS model, however a scattering parameter is provided that corrects the deflection angle value to better match that of real gas values [31]. Due to its simplicity and low computational overhead the HS model is widely used especially in cases of single gas flows as well as of isothermal problems or at least in problems with very small temperature gradients.

In this section of results the application of the HS, VHS and VSS molecular models is presented for the cases of a single species and of a mixture in Fig. 14

CONCLUSION

In this work the Sod-shock tube problem for gas mixtures was solved with the DSMC method. The goal was to investigate how the differences in masses and diameters between different species influence in general the mixing process and the formation of the waves. For that reason, two groups of tests were conducted, the first one that involved a series of simulations of gasses with different masses but fixed diameters and the second one another series of simulations that involved gasses with different diameters but fixed masses. Results showed that the mass difference was much more influential than diameter difference; in fact, the greater mass ratio is the higher is the effect on the flow formation. Finally, a comparison between the HS, VHS and VSS molecular models showed that for a single species case all models give the same results, while for mixtures the VHS and VSS gave slightly different results between the critical zones of the rarefaction and shock waves.

Figure 1 .

 1 Figure 1. Schematic diagram of the initial condition of the Sod-shock tube problem.

Figure 2 .

 2 Figure 2. Quality plot of pressure before the diaphragm is removed.

Figure 3 .

 3 Figure 3. Quality plot of pressure after removing the diaphragm.

  is defined up to free molecular flow. In this work, it is also important for a gas mixture to define the molar fraction of species  by

  a

4 6

 4 given initially at both sides of the tube is kept fixed approximately at 273 and right area respectively. The characteristic length 1 L  m, is the total length of the tube, while the diaphragm position is at 0.5 x  m. Total collision cells where 1200 and the sampling was performed from the averaged values of every 6 neighboring cells. The solution corresponds to time

Figure 5 10 

 510 depicts density profiles of the three cases corresponding to Knudsen numbers in the left side at , with solid, dotted and dashed lines respectively. It is obvious from the plots that the classical Riemann problem is valid only in continuum regime and in the slip regime the discontinuities are vanished.

Figure 4 .

 4 Figure 4. Mass density profiles referring to the validation case. The results of this work are depicted with the dashed line. With doted are the results of Tiwari et al. and with the solid line the analytical solution.

Figure 5 .

 5 Figure 5. Dimensionless density profiles for different Knudsen numbers, covering flows from continuum up to slip and rarefied regimes.

Figure 7 .

 7 Figure 7. Mass density profiles for different mass ratios.

Figure 8 .

 8 Figure 8. Molar fraction profiles for different mass ratios.

Figure 9 .Figure 10 .

 910 Figure 9. Temperature profiles for different mass ratios.Figure10. Velocity profiles for different mass ratios.

  (a) and (b) the mass density plots are depicted for the cases when the smaller diameter species is on the high density side (a) and on the low density side (b) respectively. The main differences are spotted at regions 3 and 4 corresponding to the shock wave body. In specific, by focusing on the area approximately at   0.46, 0.63 x 

Figure 11 .Figure 12 .Figure 13 .

 111213 Figure 11. Mass density profiles for different diameter ratios when (a) the species with the smaller diameter is at the high density side and (b) when the species with the smaller diameter is at the lower density side.

  (a) and (b) respectively. The tests confirm that for the simple gas case in Fig.14(a) the results of all models coincide, while for the case of Ar-Ne in Fig14(b) the VHS and VSS models give slightly different results in the most critical zones covering the area between the foot of the rarefaction wave until the head of the shock.

Figure 14 .

 14 Figure 14. Comparison of mass density profiles corresponding to HS, VHS and VSS molecular models, for the single gas case of Argon.

Figure 15 .

 15 Figure 15. Comparison of mass density profiles corresponding to HS, VHS and VSS molecular models, for the case of Ar -Ne.

Table 1 .

 1 Cases simulated with noble gases Mass density profiles for different pairs of noble gases at fixed Knudsen number equal to 0.001 as measured at the left side of the tube before the diaphragm is removed.

	Gas pairs Mass ratio Diameter ratio
	Ar -Ar	1.00	1.00
	Ar -Ne	1.98	1.33
	Ar -He	9.96	1.58
	Ar -Xe	0.30	0.64
			Figure 6.

ACKNOWLEDGMENTS

This project has received funding from the European Union's Framework Programme for Research and Innovation Horizon 2020 (2014-2020) under the Marie Sklodowska-Curie Grant Agreement No. 643095. Also the second author S.S. would like to acknowledge the partial support provided by the Bulgarian NSF under grand DN 02/7 -2016.


Yves Lepage
email: yves.lepage@waseda.jp

Jean Lieber
email: jean.lieber@loria.fr

An approach to case-based reasoning based on local enrichment of the case base

Keywords: analogical reasoning, case base enrichment, case-based machine translation, case-based reasoning

This paper describes an approach to case-based reasoning by which the case base is enriched at reasoning time. Enrichment results from the local application of variations to seed cases: new hypothetical cases are created which get closer and closer to the target problem. The creation of these hypothetical cases is based on structures associated to the problem and solution spaces, called variation spaces, that enable to define a language of adaptation rules. Ultimately reaching the target problem (exactly or nearly) allows the system to deliver a solution. A realistic application of the proposed approach to machine translation between French and English shows behind state-of-the-art, but promising results.

Introduction

In machine learning, some techniques are used to enrich the training set in order to improve the accuracy of a learning system. This is called data augmentation. It can be done using general transformations (e.g., flipping, rotating, etc. images when this does not affect the class in image classification, see for example [START_REF] Kim | Star-galaxy classification using deep convolutional neural networks[END_REF] or [START_REF] Taylor | Improving deep learning using generic data augmentation[END_REF]), adding some controlled noise (like Gaussian noise on images [START_REF] Hussain | Differential data augmentation techniques for medical imaging classification tasks[END_REF]), or by analogical reasoning (see, e.g. [START_REF] Couceiro | Analogy-preserving functions: a way to extend Boolean samples[END_REF]).

While case-based reasoning (CBR [START_REF] Richter | Case-based reasoning: a textbook[END_REF]) is usually less greedy than most current machine learning techniques, the enrichment of the case base can be useful. In this paper, we propose to perform the enrichment of the case base in a "casebased way": the case base is enriched with new source cases that are "around" the target problem. This constitutes a local enrichment of the case base, computed on-line, at the time of problem-solving. The case base is enriched with the help of learned adaptation rules: given a source case, another source case closer to the target problem is generated thanks to such a rule. The process can be repeated, though each application of a rule may degrade the generated case, in the sense that it is less and less likely to be a licit case.

To deal with this issue, the notion of penalized case is introduced: this is a hypothetical case, whose likelihood to be licit is characterized by a number that penalizes the re-usability of the case. Therefore, the enriched case base is a set of penalized cases: the cases to be reused are the ones which offer the best compromise between the similarity to the target problem (e.g., in the sense of a distance function) and their penalties.

This paper is organized as follows. Section 2 presents general definitions, notations and assumptions. The notions of penalized cases and penalized case bases, mentioned above, are presented with details in Section 3. The notions of variations between problems and between solutions, and some related notions useful for presenting the approach, are defined in Section 4, with some strong assumptions that make the general ideas easier to understand. Section 5 is the core of the paper: it presents the approach for local enrichment of the case base. Two applications are presented in Section 6, where the strong assumptions mentioned above about the representation of variations do not necessary hold. However, the principle of the approach still holds. These applications show how case-based translation [START_REF] Lepage | Case-Based Translation: First Steps from a Knowledge-Light Approach Based on Analogy to a Knowledge-Intensive One[END_REF] can be actually performed thanks to the approach of local enrichment of the case base. The results are demonstrative and promising.

Preliminaries

This section presents some general notions and assumptions about case-based reasoning and analogies, with the notations used throughout the paper.

Notations and assumptions on case-based reasoning

Let P and S be two given sets, called the problem space and the solution space. A problem is by definition an element x of P and a solution, an element y of S. A relation on P × S is assumed to exist and x y is read "x has for solution y" or "y is a solution to x". A case is a pair (x, y) ∈ P × S such that x y. The case base CB is a finite and nonempty set of cases. A source case is an element (x s , y s ) of CB. Case-based reasoning (CBR) aims at solving a new problem x t called the target problem with the help of the case base. It usually consists in the following steps:

-Retrieval (aka "retrieve" in [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]) selects a subset of CB; -Adaptation (aka "reuse") proposes a plausible solution y t to x t , using the retrieved source cases; -Learning (aka as "revise" and "retain") consists in validating/correcting y t (for example, with the help of a human expert) and in storing the newly formed case (x t , y t ) in the case base, if this storage is judged appropriate.

It is worth noting that, for many applications, y t is only a plausible solution: CBR often appears as a hypothetical reasoning whose use is motivated by the incompleteness of the knowledge of the relation . The term "hypothetical case" stands for any pair (x, y) ∈ P × S, though this notion is generally used when a solution y to x is plausibly inferred. In some applications, other knowledge containers are used [START_REF] Richter | Case-based reasoning: a textbook[END_REF]: the domain knowledge (DK, aka domain ontology), the retrieval knowledge (RK), and the adaptation knowledge (AK). These four knowledge containers (CB, DK, RK and AK) are interrelated. In particular, there are studies on learning AK using CB presented further.

Analogies

An analogy is a quaternary relation on a set U denoted by A : B :: A ratio is an expression of the form P : Q ("P is to Q"), the relation :: ("as") is called conformity. Thus, analogy is a conformity of ratios.

C : D for (A, B, C, D) ∈ U 4 , that is to be read "A is to B as C is to D". It
Classical examples of analogies are as follows:

(geometrical analogy) Here the ratio is division, conformity is equality, and

U = R \ {0}.
This analogy is defined by A : B ::

C : D if A B = C D .
(arithmetic analogy) Here the ratio is subtraction, conformity is equality, and U = R. This analogy is defined by A : B ::

C : D if A -B = C -D.
(analogy on tuples) If an analogy is defined on each set U i (1 ≤ i ≤ n) and U = U 1 × U 2 × . . . × U n then the following analogy can be defined on U: A : B :: C : D if for every i, A i : B i :: C i : D i . (analogies on strings) Let dist be the LCS distance. 2 The Parikh vector of a string is the tuple of the number of occurrences of each character in the string.

A ratio P : Q between two strings P and Q can be defined as the difference of their Parikh vectors (arithmetic analogies on tuples) plus the LCS distance between them. However, this ratio does not entail the exchange of the means because dist(A, B) = dist(C, D) does not imply dist(A, C) = dist(B, D) in general. To define an analogy it is necessary to state: A : B ::

C : D if A : B = C : D and A : C = B : D.
An analogical equation is an expression of the form A : B :: C : y, where y is the unknown. Solving it amounts to find the set of y such that the analogy holds.

It may have 0, 1 or several solutions, depending on the type of analogies: for geometrical analogies on R \ {0} and arithmetic analogies on R, every analogical equation has exactly one solution. By contrast, with the analogy on strings defined above, an analogical equation may have 0, 1 or several solutions.

Penalized cases and penalized case bases

The enrichment of the case base presented in this paper is based on a hypothetical reasoning: it generates hypothetical cases (x, y), which means that the assertion "x y" is uncertain. Thus, a hypothetical case is less trustworthy than a licit case (such as a source case), and thus, the former has to be penalized in the reasoning, in comparison to the latter. Two hypothetical cases should have different penalties if one of them is more uncertain than the other. The notion of penalty as a way to model uncertainty is introduced for this purpose. The penalties are associated to hypothetical inferences: the more uncertain is the inference, the higher is the inference cost, that is the additional penalty associated with the inference. Finally, the notion of penalized case is introduced: they are triples (x, y, π) where x ∈ P, y ∈ S and π is a penalty. An enriched case base is actually a set of penalized cases, i.e., a penalized case base.

Uncertainty and Penalties

A hypothetical reasoning leads to an uncertain result. In this paper, uncertainty of an event is measured by an uncertainty penalty (or, simply, a penalty) π ∈ [0, ∞] such that the higher π is, the less certain the event is. The penalty of an event that is certain is π = 0. The penalty of an impossible event is π = ∞. 3Remark 1: If two penalties π 1 and π 2 are associated to the same event, with π 1 < π 2 , the lower penalty -associated to the higher certainty-is kept. In other words, if π is associated to an event e, then every π ≥ π can also be associated to e.

Cost associated to a hypothetical inference

Let ϕ 0 be a piece of knowledge whose uncertainty (to be consistent with the real world) has an uncertainty penalty π 0 . From ϕ 0 , a new piece of knowledge ϕ 1 can be produced by a hypothetical inference hypo. Since hypo is hypothetical, it adds some uncertainty, thus an uncertainty penalty π 1 associated to ϕ 1 can be computed as π 1 = π 0 + c where c > 0 measures the additional uncertainty of hypo. c is assumed to be computed on the basis on hypo by a function called cost: c = cost(hypo). 4 In summary: if π 0 is an uncertainty penalty associated to ϕ 0 and ϕ 1 is inferred from ϕ 0 by the hypothetical inference hypo then π 1 = π 0 + cost(hypo) is an uncertainty penalty associated to ϕ 1

(1) Now, if ϕ 0 , ϕ 1 , . . . , ϕ n are pieces of knowledge, ϕ 0 being certain (it can be associated to an uncertainty penalty π 0 = 0) and ϕ i being produced by a hypothetical inference hypo i (1 ≤ i ≤ n), then, according to (1), the uncertainty

penalty π n = n i=1 cost(hypo i ) can be associated to ϕ n .
In particular, let us consider the simple approach to CBR consisting in retrieving a source case (x s , y s ) and in reusing (without modification) y s as a plausible solution to the target problem x t (y t = y s ). If retrieval is based on a distance function dist, then the higher dist(x s , x t ) is, the more the assertion x t y t is uncertain, and the higher the cost of this inference has to be. For this reason, dist(x s , x t ) can be used to measure the cost of this inference: this is how the distance function is interpreted and used in the rest of the paper.

Penalized cases

In this paper, every hypothetical case (x, y) ∈ P × S is either a licit case (x y) or not (x y): there is no gradual distinction between licit and illicit cases. By contrast, a hypothetical case is more or less certain to be a licit case. So, a hypothetical case should be preferred to another one on the basis of their respective chances of being licit. A penalized case is a triple (x, y, π) with (x, y), a hypothetical case and π, a penalty measuring the uncertainty that x y is licit. The estimation of π is made on the basis of an inference that has conducted to the hypothetical case (x, y). If π = 0, then (x, y, π) = (x, y, 0) is assimilated to the case (x, y).

A penalized case base PCB is a finite set of penalized cases (x s , y s , π s ) ∈ P × S × [0, ∞]. In particular, CB is a penalized case base with every penalty set to 0.

When a penalized case base PCB is used, instead of a classical case base, how does it affect the CBR process? An answer is to take into account the penalties of the case by adding them to the cost of the inference. For example, since dist is interpreted as a cost of the simple CBR inference based on the retrieval of a single source case and reusing it as such (cf. the last paragraph of Section 3.2), this approach to CBR consists in selecting the (x s , y s , π s ) ∈ PCB which minimizes dist(x s , x t ) + π s .

Problem and solution variations

This section introduces the notions of problem variations and solution variations that are useful to present our approach. It also relates these notions to the issue of adaptation knowledge learning and to analogies.

Definitions

Intuitively, the variation from a problem x i to a problem x j , denoted by --→ x i x j in this paper, encodes the information necessary to transform x i into x j . More formally, a triple (∆P, +, -→ • ) called the problem variation space and verifying the following postulates is assumed to exist:

(i) (∆P, +) is a commutative group. Its neutral element is denoted by - → 0 ; the inverse of - → u ∈ ∆P is denoted by -- → u . 5 (ii) - → • is an onto mapping (x i , x j ) ∈ P 2 → --→ x i x j ∈ ∆P: for each - → u ∈ ∆P, there exists (x i , x j ) ∈ P 2 such that - → u = --→ x i x j . (iii) For every x i , x j , x k ∈ P, --→ x i x j + --→ x j x k = --→ x i x k .
(iv) For each x i ∈ P and -→ u ∈ ∆P, there exists at most one x j ∈ P such that --→ x i x j = -→ u . This x j , when it exists, is denoted by tr-→ u (x i ) (tr stands for "translation", borrowing the term from the field of vector spaces).

From these postulates, the following properties can be deduced:

--→ x i x j = - → 0 iff x i = x j (2) - --→ x i x j = --→ x j x i (3) if --→ x 1 x 2 = --→ x 3 x 4 then --→ x 1 x 3 = --→ x 2 x 4 (4)
for every x i , x j , x 1 , x 2 , x 3 , x 4 ∈ P.

There are many ways of defining ∆P and the mapping -→ • . They depend partly upon the problem space P. For example:

-If P is an affine space of dimension n on R, ∆P can be the vector space R n associated with P:

--→

x i x j = (x j 1 -x i 1 , x j 2 -x i 2 , . . . , x j n -x i n )
and tr-→ u is the translation operator of vector -→ u . This example explains the notations chosen in this paper. -More generally, if P is defined by attribute-value pairs, the problem of defining --→ x i x j can be reduced to the problem of defining the variation from x i to x j for each attribute. This is considered in particular in [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF].

In the same way and with the same notations, a solution variation space (∆S, +, -→ • ) can be defined. 5 (∆P, +) being a commutative group means that ∆P is a set, that + is an associative and commutative operation on ∆P, and that every -→ u ∈ ∆P has an inverse element

--→ u (meaning -→ u + (--→ u ) = -→ 0 ).

Adaptation knowledge learning expressed in terms of variations

The seminal paper [START_REF] Hanney | Learning adaptation rules from a case-base[END_REF] presents the main principles of the AK learning issue. They are reformulated below, thanks to the notions of variations introduced above.

From the case base, the multiset6

TS = --→ x i x j , --→ y i y j (x i , y i ), (x j , y j ) ∈ CB, with x i = x j
is computed. This multiset is used in the training of a supervised learning process (the inputs of the examples are the --→ x i x j , the outputs are the --→ y i y j ). The learned model is used as adaptation knowledge.

Several studies have followed this scheme, and a few examples are given below. In [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF], a variety of learning techniques are used, in particular decision tree induction and ensemble learning. In [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF], frequent closed itemset extraction in used. The expert interpretation enables to produce adaptation rules to be added to AK. In [START_REF] Jalali | Learning and applying adaptation rules for categorical features: An ensemble approach[END_REF], an ensemble approach provides adaptation rules for a nominal representation (feature-value pairs, where values are categories).

An example of adaptation learning approach suited for discrete representations is as follows. First, a triple

( - → u , - → v , c) ∈ ∆P ×∆S ×[0, ∞[ such that - → u = - → 0
can be seen as an adaptation rule (for (x, y, π), a penalized case and x t ∈ P):

if -→ xx t = - → u then y t = tr-→ v (y) is a plausible solution of x t , with penalty π + c (recall that y t = tr-→ v (y) iff -→ yy t = - → v ). Among the ( - → u , - → v , c) ∈ ∆P × ∆S × [0, ∞[ ( - → u = - → 0
supp ( - → u , - → v ) = ((x i , y i ), (x j , y j )) ∈ CB 2 --→ x i x j = - → u , --→ y i y j = - → v
Hence, the adaptation knowledge learning process consists in computing the pairs ( -→ u , -→ v ) such that their support is above a given threshold τ supp . It is assumed in this paper that τ supp ≥ 2. The value of the support is used on the basis of the following heuristics: the higher the support is, the less the application of the adaptation rule adds uncertainty. Therefore, a value c is computed thanks to a decreasing function f :

N \ {0, 1} → R by c = f (supp ( - → u , - → v )). For our experiments, we have chosen f (n) = 1/n. Finally, the rule ( - → u , - → v , c) is added to AK.
With this adaptation knowledge learning approach, it is noteworthy that for each learned adaptation rule

( - → u , - → v , c) there is another learned adaptation rule (-- → u , -- → v , c). Indeed, --→ x i x j ,
--→ y i y j occurs in the multiset TS with the same multiplicity as --→ x j x i , --→ y j y i .

Variation-based analogies

Let us consider the relation on problems defined, for A, B, C, D ∈ P, as follows:

A : B ::

C : D if --→ AB = --→ CD
It satisfies the postulates of analogy. An analogy on S can be defined likewise. Therefore, using the problem variation space and the solution variation space, an analogy on P and an analogy on S can be built, and thus, the approach to CBR based on the following principle (called extrapolation in [START_REF] Lieber | Making the Best of Cases by Approximation, Interpolation and Extrapolation[END_REF] and used in [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF] and [START_REF] Lepage | Case-Based Translation: First Steps from a Knowledge-Light Approach Based on Analogy to a Knowledge-Intensive One[END_REF]) can be applied:

-Given a target problem x t , a triple ((x 1 , y 1 ), (x 2 , y 2 ), (x 3 , y 3 )) ∈ CB 3 is retrieved such that x 1 : x 2 :: x 3 : x t in the problem space (i.e., --→

x 1 x 2 = --→ x 3 x t ).
-Then, the analogical equation y 1 : y 2 :: y 3 : y in the solution space is solved, and the solution of this equation is given as a plausible solution to x t (in the framework of the postulates given below, this solution, when it exists, is unique, and verifies y = tr-→ v (y 3 ) with -→ v = --→ y 1 y 2 ).

Analogy-based variations

In the domain of strings, it is possible to define a vector corresponding to a ratio as follows (using the notion of ratios introduced in Section 2.2):

--→ AB = A : B However, as mentioned in Section 2.2, the only definition of a ratio does not make an analogy. In such a domain, we impose for (A, B, C, D) ∈ P 4 :

- In other words, in such a domain, we implement the extrapolation approach mentioned at the end of Section 4.3 by restraining ourselves to the use of variations such that both --→ AB = --→ CD and -→ AC = --→ BD hold at the same time. This ensures that the postulates of analogy are verified for the used variations.

CBR by local enrichment of the case base

The enrichment of the case base consists in adding to the original case base CB some (penalized) cases inferred from CB. The inferences considered in this paper consist in applying the learned adaptation rules ( -→ u , -→ v , c) ∈ AK. In theory, all the penalized cases that can be so inferred can enrich CB: this is considered in Section 5.1. However, this leads usually to a penalized case base that is too large. In Section 5.2, a local enrichment is proposed that consists in adding to CB penalized cases that are "around" the target problem.

Theoretical view: global enrichment of CB

The principle of global enrichment of CB is simple: it consists in computing all the penalized cases (x, y, π) that can be inferred from CB by application of one or several adaptation rules, with the constraint π ≤ τ penalty , where τ penalty is a given threshold. The size of the enriched case base, PCB, can be estimated as follows. Let

p = |AK| and d = τ penalty / min{c | ( - → u , - → v , c) ∈ AK} . If no hypothetical case (x, y) is generated twice in the process, then |PCB| = |CB| × p d+1 -1 p -1 , assuming p = 1. Therefore, |PCB| / |CB| = O(p d ).
For example, using p = 10 adaptation rules having the same cost c = 1, if τ penalty = 3, the size of PCB is about a thousand times the size of CB. This illustrates the fact that this global enrichment of the case base approach produces a case base whose size is, for most CBR applications, too large, which motivates the local enrichment of the case base.

Practical view: local enrichment of CB

The principle of local enrichment is based first on the choice of seed cases, i.e., cases from CB that are chosen to produce penalized cases to be added to the case base. If (x s , y s ) is a seed case, then a penalized case (x, y, π) is produced by a gradient descent starting from (x s , y s , 0), by decreasing dist(x, x t ) + π, each step corresponding to the application of an adaptation rule. The penalized case (x, y, π) to be added to the case base thus constitutes a local optimum of the set of cases generated from the seed case (x s , y s ).

The selection of the set of seed cases SC can be done following several strategies, such as the following ones:

-The simplest strategy consists in taking all the source cases: SC = CB. This has the advantage of simplicity, but may lead to an important growth of the case base (the enriched case base size, |PCB|, will be between |CB| and 2|CB|). -If the size of the case base is too large already, only a few additional cases should be added and the following solutions can be proposed:

• Choose SC by a random sampling from CB;

• Choose SC as the k nearest neighbors of x t , e.g. according to dist.

Applications

In the sequel of the paper, we present two applications of local enrichment of the case base during case-based reasoning. Both examples create strings in a second domain (the solution space) that correspond to strings in a first domain (the problem space). The first application is a theoretical example: the problem space and the solution space are formal languages. The second application is actual machine translation: the problem space and the solution space are actual natural languages: French and English.

Machine translation of formal languages

The first example shows how local enrichment of the case base can be used to translate from a regular language into a context-free language. The languages we use are the prototypical examples of these families of formal languages, i.e., the problem space and the solution space are P = {(ab) n | n ∈ N} and S = {A n B n | n ∈ N}, respectively. Let us suppose that our case base contains only the three smallest nonempty members of each of these languages: CB = {(ab, AB), (abab, AABB), (ababab, AAABBB)}.

From such a case base, in the problem space, one variation with a support greater than 1 is extracted. It corresponds to the ratio ab : abab = abab : ababab. 7 This variation in the problem space corresponds to a variation in the solution space: AB : AABB = AABB : AAABBB. Of course, these variations have their corresponding inverse variations in the problem and solution spaces.

An actual trace of the system is given in Figure 1 for the translation of the string (ab) 6 . We choose to select all cases in the case base as seed cases, i.e., SC = CB. The seed cases are sorted by distance to the target problem. Their LCS distance to the target problem is given by δ in Figure 1. Starting from the problems in the seed cases, applying the variation has the effect of enriching the case base with cases of the form ((ab) n , A n B n ) from n = 4 to 6, one after another. This is indeed an induction over n for (ab) n and A n B n simultaneously in both spaces.

During enrichment, the distance from the new source problems to the target problem decreases down to 2. The distance of 0 is not mentioned, as it means that the new source problem is indeed the target problem, for which a solution has been found.

Such an example can be easily amended to translate from a regular language into a context-sensitive language (like {A n B n C n | n ∈ N}), or a context-free language into a context-sensitive language. Changing the direction of translation is also possible: from context-free to regular, etc.

Machine translation of natural languages

The second application deals with machine translation of natural languages. We use French-English as the language pair and data from the Tatoeba Corpus8 as our bilingual corpus. There are important remarks to make on this domain.

Nature of the data: strings of characters. This implies again that variations are defined as in Section 4.4. The case base consists of sentence pairs which are in translation relation. We retain sentences of less than 10 words in length and select 90 % of them for training and the other 10 % for testing. This makes 109,390 sentence pairs in total in the training set. The average length of a sentence in French is 6.9 ± 1.8 words and 6.6 ± 1.6 in English. Such sentence pairs are illustrated in Figure 2. Notice that the sentences are lowercased and tokenized.

PROBLEM SPACE

SOLUTION SPACE CASE BASE

Initial case base = Seed cases

(ab) 1 A 1 B 1 (ab) 2 A 2 B 2 (ab) 3 A 3 B 3
Source problems in seed cases

δ = 6 (ab) 3 δ = 8 (ab) 2 δ = 10 (ab) 1 Enrichment (ab) 1 : (ab) 2 :: (ab) 3 : (ab) 4 A 1 B 1 : A 2 B 2 :: A 3 B 3 : A 4 B 4 (ab) 4 A 4 B 4 (ab) 2 : (ab) 3 :: (ab) 3 : (ab) 4 A 2 B 2 : A 3 B 3 :: A 3 B 3 : A 4 B 4 (ab) 4 A 4 B 4 (ab) 1 : (ab) 2 :: (ab) 2 : (ab) 3 A 1 B 1 : A 2 B 2 :: A 2 B 2 : A 3 B 3 (ab) 3 A 3 B 3 (ab) 2 : (ab) 3 :: (ab) 2 : (ab) 3 A 2 B 2 : A 3 B 3 :: A 2 B 2 : A 3 B 3 (ab) 3 A 3 B 3 (ab) 1 : (ab) 2 :: (ab) 1 : (ab) 2 A 1 B 1 : A 2 B 2 :: A 1 B 1 : A 2 B 2 (ab) 2 A 2 B 2 (ab) 2 : (ab) 3 :: (ab) 1 : (ab) 2 A 2 B 2 : A 3 B 3 :: A 1 B 1 : A 2 B 2 (ab) 2 A 2 B 2
New source problem

δ = 4 (ab) 4
(ab) 1 : (ab) 2 :: (ab) 4 : (ab

) 5 A 1 B 1 : A 2 B 2 :: A 4 B 4 : A 5 B 5 (ab) 5
A 5 B 5 (ab) 2 : (ab) 3 :: (ab) 4 : (ab) 5 A 2 B 2 :

A 3 B 3 :: A 4 B 4 : A 5 B 5 (ab) 5 A 5 B 5
New source problem δ = 2 (ab) 5 (ab) 1 : (ab) 2 :: (ab) 5 : (ab) 6 A 1 B 1 : A 2 B 2 :: A 5 B 5 : A 6 B 6 (ab) 6 A 6 B 6 (ab) 2 : (ab) 3 :: (ab) 5 : (ab) 6 A 2 B 2 : A 3 B 3 ::

A 5 B 5 : A 6 B 6 (ab) 6 A 6 B 6
Final case base

(ab) 1 A 1 B 1 (ab) 2 A 2 B 2 (ab) 3 A 3 B 3 (ab) 4
A 4 B 4 (ab) 5 A 5 B 5 (ab) 6 A 6 B 6

Fig. 1. Trace for the translation from a regular language into a context-free language.

The target problem is (ab) i want this to be over .

: i just want this to be over .

i want someone to talk to . :

i just want someone to talk to . i felt a drop of rain .

: i just felt a drop of rain . Size of the the case base. For case-based reasoning, the case base here is quite large: 109,390 cases. However, in the field of machine translation, on the contrary, it is considered rather small.

Nature of the ratios: they are defined as in Section 2.2 (analogies on strings) as we deal with strings. A ratio is a vector made of the difference between the Parikh vectors of the two strings considered, plus an extra dimension with the LCS distance between the two strings. Notice again that the equality between ratios does not imply the existence of an analogy, on the contrary to arithmetic or geometric analogies on numbers or tuples: dist(A, B) = dist(C, D) does not imply dist(A, C) = dist(B, D). Also, conformity is not transitive, so it is not an equivalence relation.

Nature of the variations: analogical clusters. Because of the nature of the ratios and the nature of conformity, variations are defined as groups of ratios among which an analogy is verified between any two pairs of ratios. We use the tools9 described in [START_REF] Fam | Tools for the production of analogical grids and a resource of n-gram analogical grids in 11 languages[END_REF] to extract all analogical clusters containing at least 2 ratios from the case base in the problem and the solution spaces. Number of variations: It is rather large: almost 8 million analogical clusters were extracted in French, more than half a million in English. The extraction of such variations from an actual corpus is time-consuming. For efficiency, we retain only the first 3,000 largest analogical clusters in number of ratios. Three examples of analogical clusters are given in Figure 3. Typically, variations reflect grammatical oppositions. In the examples of Figure 3, affirmative / negative, masculine / feminine and insertion of the adverb just.

As an example, the translation process of the tokenized sentence vous êtes vraiment trop tatillon . from French into English is given in Figure 4. The seed problems are the 5 most similar French sentences in the case base. The translation process takes three steps corresponding to each block of sentences in the table below. The distance to the target problem is given on the left. Notice the infelicitous enrichment of the case base with an invalid sentence: you really not 're finicky .

An example of a variation applied in the problem and solution spaces during the above translation process is shown in Figure 5. It corresponds to a variation applied on the fourth seed case (boldfaced) in Figure 4. As a result, the case base is enriched with the first case marked as a new case in the above table (δ = 4).

The standard metric BLEU [START_REF] Papineni | BLEU: a method for automatic evaluation of machine translation[END_REF] is used for the evaluation of the accuracy of a machine translation output against a given reference set. BLEU scores range from 0 to 1; the higher, the better. The system described above achieves a BLEU score of 0.51 in translating the 10,998 sentences in the test set. This is a reasonable score when compared with the scores of two much more elaborated systems, a neural system (OpenNMT10 ), and a statistical system (GIZA++, Moses, KenLM, MERT 11 ), which achieve 0.60 and 0.65 respectively, on exactly the same data.

Conclusion, discussion and related work

In this paper, we proposed a new approach to case-based reasoning which consists in enriching the case base while performing reasoning. Enrichment results from the application of adaptation rules to seed cases, i.e., cases taken from the case base as starting points. New cases are created, which get closer and closer to the target problem, but they get penalties characteristic of the uncertainty brought by the application of the adaptation rules. Adaptation rules are given by variations in the problem space and variations in the solution space. The last variations should approach the target problem itself, so that corresponding variations in the solution space will produce (hypothetical) solutions to the target problem. We implemented such a new approach and illustrated it with two applications which shared the fact that the solution and problem spaces were spaces of strings of characters: formal and natural languages.

The general framework can be adapted to various scenarios. Several points can be adapted to the specificity of the domains at hand. For instance, the selection of the seed cases can be performed in various ways suggested in Section 5.2, at random or according to some selection method specific to the domain.

Our approach to case-based reasoning can be seen as a variant of gradient descent or hill climbing. Similarly, our approach exhibits the risk of reaching local minima (or maxima) instead of global minima (or maxima). Here, the landscape is shaped by the variations observed between the cases present in the initial case base. This issue of local optimality can be partially addressed by considering several branches generated from each seed case: instead of a single path approaching the target problem, a tree can be generated rooted at this seed case, whose breadth should be controlled to avoid an explosion of the enriched case base size. This way, several new cases can be generated from a single seed case. The precise study of this idea remains to be done.

From a theoretical viewpoint, the approach is presented in a very constrained framework, in particular for the definition of variations. This makes the explanations simpler, but, in particular for the considered applications in machine translation, some of these constraints do not hold. Thus, a theoretical study on less constrained variation spaces must be carried on.

  satisfies the following postulates (for any (A, B, C, D) ∈ U 4 ): 1 (reflexivity of conformity) A : B :: A : B; (symmetry of conformity) if A : B :: C : D then C : D :: A : B; (exchange of the means) if A : B :: C : D then A : C :: B : D.

  ), the ones that are selected are the ones which are the most supported by the training set. More formally, let supp ( -→ u , -→ v ) (the support of the ordered pair ( -→ u , -→ v )) be the multiplicity of ( -→ u , -→ v ) in TS. In other terms:

  -→ AB = --→ CD if A : B :: C : D, i.e., if A : B = C : D and A : C = B : D

Fig. 3 .

 3 Fig. 3. Three analogical clusters which stand for variations in the solution space

Fig. 5 .

 5 Fig. 5. Variation in the problem and solution spaces resulting in the enrichment of the case base

  6 . It is correctly translated into A 6 B 6 after enrichment of the case base. The problem space is on the left, the solution space in the middle. The case base and its enrichment are shown on the right. The distance to the target problem is denoted by δ. New source problems, solutions and cases are boldfaced; old ones are grayed out.

	French					English
	regardez comment je le fais !		watch how i do it .
	vous m' avez oublié , n' est-ce pas ?	you 've forgotten me , haven 't you ?
	je suis finlandais , mais je parle aussi	i am finnish , but i speak also swedish .
	suédois .
	pensez-vous sérieusement à vendre cela	are you seriously thinking about selling
	sur internet ?			this online ?
	les travailleurs se plaignent de leurs	the workers are complaining about their
	conditions de travail .			working conditions .
	Fig. 2. French and English example sentences, i.e., problems and solutions, in the case
	base for case-based machine translation
	get up . : don 't get up .	he runs . : she runs .	i can 't believe this .	: i just can 't be-lieve this .
	tell me . :	don' t tell	he young . is	: she young .	is	i need a little more time .	:	i just need a little more time .
			me . don 't	he helps us .	: she helps us .
	leave us . :	leave us .	he loves singing .	: she loves singing .
	leave me .	:	don 't leave me .	he just left .	: she just left .

The first author is supported by JSPS Grant-In-Aid 18K11447: "Self-explainable and fast-to-train example-based machine translation using neural networks."

Some authors consider that analogy requires additional postulates[START_REF] Lepage | Proportional analogy in written language data[END_REF]. However, only these three postulates are taken into account in this paper.

The LCS ("longest common subsequence") distance is an edit distance based on the character insertion and character deletion edit operations, with a cost of 1 for both. In other terms, if P and Q are two strings and L is the LCS of P and Q, then dist(P, Q) = (|P | -|L|) + (|Q| -|L|).

If uncertainty is modeled thanks to a probability measure, it is possible to associate to a probability P ∈ [0; 1] a penalty π = -log P ∈ [0; ∞]. However, the representation of uncertainty by penalties is preferred in this paper, for practical reasons.

Once again, costs could be associated to probabilities: cost(hypo) could be defined by -log P (ϕ 2 | ϕ 1 ), where P (ϕ 2 | ϕ 1 ) is the probability of ϕ 2 being true given that ϕ 1 is.

A multiset is denoted with double braces; for example M = { {a, a, b, c, c, c} } contains a with multiplicity 2, b with multiplicity 1 and c with multiplicity 3. Thus the cardinality of M is |M | = 2 + 1 + 3 = 6.

Note that this is the equality of two ratios. Of course, it is also an analogy by itself (ab : abab :: abab : ababab), but this is not what is meant here.

https://tatoeba.org/ and http://www.manythings.org/anki/

https://lepage-lab.ips.waseda.ac.jp/

http://opennmt.net

http://www.statmt.org