Nathalie Di

Miceli Raimondi

Laurent Prat

Numerical study of the coupling between reaction and mass transfer for liquidliquid slug flow in square microchannels

Keywords: Confined flow, liquid-liquid, mass transfer, reaction, simulations

While the benefits of miniaturisation on processes have been widely demonstrated, its impact on microfluidics and local mechanisms such as mass transfer is still little understood. The aim of this work is to simulate coupling between reaction and mass transfer in microchannels for liquid-liquid slug flow. First, the extrapolation to confined flow of the classical model used to calculate interfacial mass fluxes in reactive infinite media was studied. This model consists in estimating transferred fluxes between two phases as a function of the enhancement factor E. Its expression depends on the model used to represent interfacial mass transfer. In infinite media, Lewis and Whitman's stagnant film theory is generally preferred for its simplicity and its reliability. In the case of confined slug flow, the limitation of such a model to predict interfacial fluxes is highlighted. Secondly, the case of liquid-liquid competitive consecutive reactions in microchannels is considered. This work emphasizes the unfavourable impact of the length between droplets on selectivity. This is a direct consequence of mass transport mechanisms in microchannels.

Introduction

Process intensification by miniaturisation opens up numerous perspectives in terms of chemical production. Indeed, decreasing device size allows a reduction of technology constraints to the benefit of chemistry. [START_REF] Wörz | Microreactors, a new efficient tool for optimum reactor design[END_REF][START_REF] De Mello | But what is it good for? Applications of microreactor technology for the fine chemical industry[END_REF][START_REF] Ahmed | Enhancement of reaction rates by segmented fluid flow in capillary scale reactors[END_REF] On one hand, micro-devices are characterised by high surface area to volume ratio which provide them good thermal capacity. [START_REF] Schubert | Microstructure devices for applications in thermal and chemical process engineering[END_REF][START_REF] Commenge | Intensification des procédés par microstructuration[END_REF][START_REF] Jähnish | Chemistry in microstructured reactors[END_REF] On the other hand, it allows the enhancement of mass transfer notably in two-phase flow where high interfacial area can be obtained. [START_REF] Yue | Hydrodynamics and mass transfer characteristics in gas-liquid flow through a rectangular microchannel[END_REF] While the impact of miniaturisation on such geometric parameter is well-known, its impact on microfluidics and local mechanisms such as mass transfer is still little understood. Consequently, to predict reaction results proceeded in a microchannel, many experiments are usually required. Hisamoto et al. (2001) carried out a liquid-liquid diazocoupling reaction in a 20 mL stirred vessel (dispersed flow) and a microchannel (stratified flow). [START_REF] Hisamoto | Fast and high conversion phase-transfer synthesis exploiting the liquid-liquid interface formed in a microchannel chip[END_REF] For a conversion close to 100 % in both devices, they observed the formation of precipitate side products at macroscale while such precipitation did not appear at microscale. They mainly explained this unexpected phenomenon by mass transfer enhancements due to short molecular diffusion distances that characterize microdevices. Wörz and al. (2001) used a micromixer coupled with a micro heat exchanger to carry out an exothermic liquid-liquid reaction. [START_REF] Wörz | Microreactors, a new efficient tool for optimum reactor design[END_REF] They obtained higher conversion than in a fed-batch reactor while diminishing by half the production of byproducts. These results are probably due to better mixing and thermal controls. These works confirm the potential of microtechnologies for chemical reaction, but highlight the complexity of fundamental mechanism coupling at microscale and the importance to acquire knowledge in this domain. Numerous research groups devoted their works on the coupling between hydrodynamics at microscale and mass transfer. [START_REF] Irandoust | Gas-liquid mass transfer in Taylor flow through a capillary[END_REF][START_REF] Kreutzer | Hydrodynamics of Taylor flow in capillaries and monolith reactors[END_REF][START_REF] Van Baten | CFD simulations of mass transfer from Taylor bubbles rising in circular capillaries[END_REF][START_REF] Kockmann | Convective mixing and chemical reactions in microchannels with high flow rates[END_REF][START_REF] Miceli Raimondi | Direct numerical simulations of mass transfer in square microchannels for liquid-liquid slug flow[END_REF][START_REF] Mary | Microfluidic droplet-based liquid-liquid extraction[END_REF] Fewer got interested in the comprehension of phenomenon coupling in two-phase reaction at such scale. [START_REF] Tsoligkas | Kinetic and selectivity studies of gas-liquid reaction under Taylor flow in a circular capillary[END_REF] This article focuses on the numerical study of the coupling between reaction and mass transfer in square microchannels considering liquid-liquid slug flow. This flow configuration is particularly interesting for mass transfer because of recirculation loops inside the droplets which intensify mixing in this phase, [START_REF] Sarrazin | Mixing characterization inside microdroplets engineered on a microcoalescer[END_REF] and a film characterized by a high velocity gradient which allows intense transfers with the droplets. [START_REF] Vandu | Mass transfer from Taylor bubbles rising in single capillaries[END_REF] Study has been carried out as follows :

-Firstly, the impact of reaction on liquid-liquid mass transfer is studied. Reaction can lead to an increase of interfacial mass transfer fluxes. [START_REF] Deckwer | Mass Transfer and Reaction[END_REF] This phenomenon is generally represented through the enhancement factor E, which is commonly used to estimate mass transfer fluxes in infinite reactive media. The objective of this work is to study the extrapolation of this classical model to confined media. -Secondly, this work deals with the impact of mass transfer on reaction. For that purpose, a competitive chemical scheme is considered to characterise the impact of mass transportation in liquid-liquid slug flow in microchannels on reaction selectivity.

Numerical method

Two dimensional (2D) simulations are carried out to calculate the concentration field of a chemical component in a square microchannel. The computations are done in two steps: first, the hydrodynamic characteristics of the flow are determined using a research code developed at the Institute of Fluid Mechanics of Toulouse (IMFT -University of Toulouse, France): JADIM. [START_REF] Legendre | The lift force on a spherical bubble in a viscous linear shear flow[END_REF] This code allows the resolution of continuity and Navier-Stokes equations in twophase flows. The second step consists in the computation of the concentration field of the transferring component, based on the resolution of a mass balance for this component. This last code was developed under Matlab 7.4.

Tryggvason et al. pointed out the difficulty to compute the motion of multiphase flows [START_REF] Tryggvason | A front-tracking method for the computation of multiphase flow[END_REF] . The representation and simulation of deformable phase interfaces is still a major challenge. In their article, they reviewed the most popular numerical techniques used to compute Navier-Stokes equations in the case of multiphase flows. This work has led to a study on reactive mass transfer in bubbles [START_REF] Koynov | Mass transfer and chemical reactions in bubble swarms with dynamic interfaces[END_REF] . Volume-of-fluid method is used in the present work. This numerical method is based on an interface-capturing technique without any interface reconstruction. The two-phase flow is described using the one-fluid approach. The phase tracking is insured by a continuous function ϕ, the so called volume fraction, which equals zero in the continuous phase and one in the droplets: consequently the interface is located in the area where ϕ strictly ranges from zero to one [START_REF] Benkenida | Une méthode de simulation d'écoulements diphasiques sans reconstruction d'interfaces[END_REF] . The equations and balances are discretised on space according to a finitevolume method. This method assumes that (1) the fluids in both phases are Newtonian and incompressible, (2) the physical properties of both phases are constant and not influenced by mass transfer, (3) mass transfer has no impact on the flow (computation of the hydrodynamic parameters and the concentration field decoupled), ( 4) the two-phase flow and the concentration are planar symmetric. Consequently, the computational domain is half a unit cell as shown in Fig. 1. On the figures the interface is fictitious (deduced from volume fraction as it is not calculated by JADIM code). The interface was arbitrary considered in the area where ϕ = 0.75. This value was chosen since the concentration inside the droplets is important to identify mass transfer coefficients in the droplet side from the concentration fields (this is described afterwards). This choice has no impact on the computations. JADIM code was previously validated to describe the hydrodynamics of liquid-liquid slug flow in square microchannels by means of micro-PIV (Particle Image Velocimetry) experiments, [START_REF] Sarrazin | Experimental and numerical study of droplets hydrodynamics in microchannels[END_REF] comparing computed and experimental 3D velocity fields. Sarrazin et al. (2006) also demonstrated that the hydrodymamic structure of slug flow in square microchannel could be well estimated using 2D simulations. [START_REF] Sarrazin | Experimental and numerical study of droplets hydrodynamics in microchannels[END_REF] Indeed, the velocity fields computed with JADIM performing 3D and 2D simulations showed that the flow structures obtained with both kinds of simulation were similar. The purpose of this work is to identify a potential impact of channel size on the coupling between hydrodynamics, mass transfer and reaction. Since the hydrodynamics of liquid-liquid slug flow in microchannel is well represented by 2D simulations, this work exclusively focuses on the calculation of hydrodynamic parameters and concentration fields over 2D computational domains. The whole numerical method was already used to study pure mass transfer in such two-phase systems. [START_REF] Miceli Raimondi | Direct numerical simulations of mass transfer in square microchannels for liquid-liquid slug flow[END_REF] The hydrodynamics and the concentration field computation algorithms are described in details in this reference. The present article will only present the mathematical formulation that allows the concentration field computation for chemical species that are affected by both mass transfer and reaction. This formulation depends on the reaction scheme and kinetic laws considered: therefore, it will be afterwards described in each part dealing with a case study, i.e. the study of the impact of reaction on mass transfer, and reciprocally.

Impact of reaction on mass transfer

In a first part, the impact of reaction on mass transfer is considered. The objective of this work is to study the extrapolation of the classical model used to estimate mass transfer fluxes in reactive infinite media (i.e. based on the enhancement factor E estimation) to confined media. It is considered the case of a reactant A which transfers from the continuous phase to the dispersed phase and reacts to give a product B:

A 1 B in the dispersed phase (1)
This irreversible reaction is a first order reaction whose kinetic rate r d is given by:

d,A d KC r = ( 2
)
where K is the kinetic rate constant of the reaction, and C d,A the concentration of A in the dispersed phase. The extrapolation of the classical model to confined media is studied comparing the mean concentration of reactant A in the droplets over time (1) obtained from concentration field computations (direct numerical simulations), and (2) estimated using the enhancement factor model. Four flow configurations are considered, which present the same droplet volumes and the same unit cell lengths (L UC = 300 µm) but different degrees of confinement as illustrated in Fig. 2. This degree is represented by the ratio of the droplet length L d and the channel width w C (L d /w C = 3.1, 2.0, 0.71 and 0.36).

Concentration field computation

The concentration field of component A over the computational domain is governed by the general convective diffusive equations in each phase, where the diffusive fluxes are expressed according to Fick's law:

A d A d A d A d A d KC C D C t C , , 2 , , , - ∇ = ∇ ⋅ ′ + ∂ ∂ u (3) A c A c A c A c C D C t C , 2 , , , ∇ = ∇ ⋅ ′ + ∂ ∂ u ( 4
)
where t is the residence time. u' represents the velocity field in a frame of reference moving with the droplets. D is the mass diffusion coefficient of the transferring component. The subscripts c and d respectively stand for the continuous and dispersed phases. It assumes the concentration at the interface obeys the thermodynamic equilibrium given by Eq. ( 5), m being the distribution coefficient of component A between the two phases.

A c A d mC C , , = at the interface (5)
The resolution of Eqs (3) and ( 4) according to the one-fluid approach requires the concentration to be continuous at the interface. For that purpose, some changes in the concentration formulation are suggested : [START_REF] Yang | Numerical simulation of interphase mass transfer with the level set approach[END_REF][START_REF] Kashid | CFD modelling of mass transfer with and without chemical reaction in the liquid-liquid slug flow microreactor[END_REF]

m C C A d A d / ˆ, , = , m C C A c A c , , ˆ= (6)
Consequently, Eqs. (3), ( 4) and ( 5) can be rewritten as follows:

A d A d A d A d A d C m K C m D C m t C m , , 2 , , , . ˆ- ∇ = ∇ ⋅ ′ + ∂ ∂ u (7) A c c A c A c C m D C m t C m , 2 , , 1 1 ∇ = ∇ ⋅ ′ + ∂ ∂ u (8) A c A d C C , , = at the interface (9)
Therefore, the mass balance in A over the whole computational domain can be represented by a single equation (Eq. ( 10)), where t ˆ, ' û , D ˆ and K ˆare transformed parameters defined as a function of the volume fraction ϕ as shown by Eqs. (11) to (14). The concentration field is computed through the parameter 1 2 3 .

A A A A C K C D C t C 2 - ∇ = ∇ ⋅ ′ + ∂ ∂ u (10) ϕ 1 1 2 3 4 4 5 6 - + = t m m t t m t ˆ (11) ϕ 1 1 2 3 4 4 5 6 ′ - ′ + ′ = ′ m m m u u u u ˆ (12) m D m D D D D d c d c ) 1 ( ˆϕ ϕ - + 1 2 3 4 5 6 = (13) ϕ K m K = ˆ (14)

Initial condition:

A is initially present in the continuous phase with a concentration 4

2 : ) (1 ˆ0 ϕ - = A A C m C at t = 0 s ( 15
)
Boundary conditions: At the wall and the symmetry plan, there is no mass flux over the direction normal to the flow:

0 ˆ= ∂ ∂ y C A for y = 0 and y = w C /2 (16)
For the boundaries normal to the flow, two fictitious columns are introduced outside the domain to estimate the convective and diffusive terms. They are considered at the same concentration as the boundaries.

From the concentration field, the mean concentration profile of A in the droplets can be obtained using Eq. 17.

77 77

⋅ ⋅ = dxdy dxdy C C d A d ϕ ϕ , ( 17
)

Modelling of the mass transfer enhancement phenomenon due to reaction

The consumption of A during its transfer to the dispersed phase leads to a modification of the mass transfer driving force, resulting in a mass transfer enhancement phenomenon. This phenomenon is generally represented through the enhancement factor E. [START_REF] Roizard | Absorption avec réaction chimique[END_REF] The modelling of mass transfer with reaction is usually based on the Lewis and Whitman's stagnant film theory. This model is easy to apply and gives predictions in terms of transfer fluxes in reactive medium very close to those obtained using more sophisticated theories such as Higbie's penetration theory or Danckwerts' surface renewal model. Lewis and Whitman's stagnant film theory supposes that the interface is composed of two stagnant films which contain all the resistance to mass transfer. In this work, mass transfer is supposed to be at least limited by the resistance in the droplet side. Indeed, two distinct volumes contribute to mass transfer in the continuous phase: the film and the liquid slug between two droplets. [START_REF] Van Baten | CFD simulations of mass transfer from Taylor bubbles rising in circular capillaries[END_REF] The importance of both contributions on interfacial mass transfer kinetic is complex to determine. Previous works show that assuming mass transfer is partly limited by resistance in the droplet side allows good representation of mass fluxes at liquid-liquid interfaces in square microchannels of 50 to 960 µm depth. [START_REF] Miceli Raimondi | Direct numerical simulations of mass transfer in square microchannels for liquid-liquid slug flow[END_REF] According to this model, the mass flux in reactive media transferring from the continuous phase to the droplets by interfacial area unit (Φ m ) c1d can be written in terms of Eq. ( 18). Its expression depends on the enhancement factor E.

) ( ) ( b d i d d d c m C C k E 2 - ⋅ = → (18)
The superscripts i and b respectively refers to the concentration at the interface and in the bulk phase. k d is the droplet mass transfer coefficient. It is defined by Eq. (19), where D d is the mass diffusion coefficient of the transferring component in the dispersed phase, and δ d the stagnant film thickness.

d d d 3 D k = (19)
The mass balance at steady state for reactant A in the stagnant film (droplet side) can be written as follows:

0 2 = + ∇ d,A d,A d,A r C D ( 20
)
This equation relates the diffusive flux in the film, expressed in terms of Fick's law, and the flux consumed by reaction. There is no term relative to the convective flux because the film is supposed stagnant. Lewis and Whitman's theory considers that the mass transfer flux between two phases is directed perpendicularly to the flow. Therefore, considering a 2D representation of a square microchannel, Eq. ( 20) can be rewritten as follows:

d,A d,A d,A KC dy C d D = 2 2 (21)
In order to express Eq. ( 21) in a dimensionless form, changes of variable on the concentration and the coordinate over the width are done (Eqs. ( 22) and ( 23)). Thus, the mass balance in the stagnant film can be written in terms of Eq. (24).

i d,A d,A d,A C C = χ (22) d 3 y Y = (23) d,A d,A d,A d,A d,A d d,A k KD D K3 dY d χ χ χ 2 2 2 2 = = (24)
In this equation appears the dimensionless Hatta number Ha which represents the ratio of the maximal fluxes of reaction and of mass transfer: Boundary conditions:

1 ) 0 ( ) 0 ( = = ⇔ = = Y C y C d,A i d,A d,A χ at the interface (26) b d,A d,A b d,A d d,A Y C 3 y C χ χ = = ⇔ = = ) 1 ( ) ( in the bulk (27)
The integration of Eq. ( 24) leads to an analytical solution. In accordance with the boundary conditions, this solution can be written as follows:

(

⋅ - ⋅ + - - = χ χ 1 (28)
Therefore, the mass transfer flux at the interface can be expressed as a function of Ha:

) ( tanh ) ( cosh ) ( 0 0 Ha Ha Ha C C k dY d C k dy dC D 2 b d,A i d,A d Y d,A i d,A d y d,A d,A d c m 1 1 2 3 4 4 5 6 - = 1 1 2 3 4 4 5 6 - = 1 1 2 3 4 4 5 6 - = = = → χ (29)
Finally, the enhancement factor E is deduced from Eqs. ( 18) and ( 29):

(

)

) ( tanh cosh 1 Ha Ha (Ha) C C C C E b d,A i d,A b d,A i d,A 1 1 2 3 4 4 5 6 - ⋅ - = (30)
In this study, the mean concentration profiles of A in the droplets obtained from the concentration fields (Eq. ( 17)) are compared to those calculated with mass balances on the droplets:

d A d UC d d c A m A d d V C K V a t C V , , , ) ( - Φ = ∂ ∂ → (31)
where A d C , represents the mean concentration of A in the droplets. V d and V UC respectively stand for the volumes of a droplet and a unit cell. a d is the specific interfacial area of the twophase flow, estimated as a function of the capillary number. [START_REF] Miceli Raimondi | Direct numerical simulations of mass transfer in square microchannels for liquid-liquid slug flow[END_REF] The mass flux is calculated with Eqs. ( 18) and (30). It assumes that the concentration of the bulk b A d C , corresponded to the mean concentration in the droplet ( A d C , ). This hypothesis has been chosen for this parameter is easier to experimentally capture than the concentration in the bulk. This assumption leads to an underestimation of the concentration gradient used to calculate interfacial mass flux. At macroscale, the impact of such an assumption is generally negligible as the stagnant film thickness is very small compared to the droplets diameter. At microscale, this assumption may strongly affect the mass transferred flux estimation as it will be seen afterwards. The concentration at the interface i A d C , was deduced from the concentration field computation. In the first unit cell, the concentration in both phases obeys the initial condition given by Eq. ( 15): the thermodynamic equilibrium at the interface is not imposed (Eq. ( 5)). This leads to unrealistic value of the mean concentration of A at the interface on the first times of the operation. Consequently, the profiles obtained from computations and mass balance calculations were compared from the second unit cell: time t = 0 on the graphs presented afterwards corresponding to a real residence time t = T, where T is the flow period.

Results

The extrapolation of the enhancement factor modelling to predict mass transfer in reactive media in microchannels is studied in two regimes defined by different Hatta number : [START_REF] Last | Determination of mass transfer parameters by means of chemical absorption[END_REF] -Ha = 0.1: reaction is slow compared to mass transfer. Most of the reaction occurs in the bulk (within the droplets). -Ha = 1: reaction and mass transfer rates are of the same order of magnitude. Part of the reaction occurs in the stagnant film. When Ha = 0.1, the reaction is too slow to occur in the stagnant film and to induce a significant mass transfer enhancement: E is roughly equals to unity. Indeed, Danckwerts (1970) presents values of enhancement factor as a function of Hatta number. [START_REF] Danckwerts | Gas-Liquid Reactions[END_REF] For a first order reaction, E is estimated at roughly 1.02 when Ha = 0.1, and 1.3 when Ha =1. Consequently, the first part of the simulations does not lead to conclusions on the extrapolation of the enhancement factor modelling in microchannels. However, it will show whether the reaction flux in Eq. ( 31), calculated with an averaged concentration, reliably predicts the reactant consumption in the droplets. Hatta number depends on the mass transfer coefficient k d as shown in Eq. (25). For each flow configuration, this coefficient is firstly identified simulating pure mass transfer operation, i.e. without reaction. A prior study showed that the simulation results obtained with the numerical method used in this work were affected by numerical diffusion. [START_REF] Miceli Raimondi | Direct numerical simulations of mass transfer in square microchannels for liquid-liquid slug flow[END_REF] This numerical diffusion corresponds to a truncation error of the convective term in the general mass transport equation. This error is included in the apparent mass diffusion, leading to a global overestimation of the diffusive mass fluxes. In the simulated conditions, the numerical diffusion coefficient was estimated at about 4110 -9 m 2 /s, which is of the same order of magnitude as mass diffusion coefficient in liquids (about 10 -9 m 2 /s). Hatta number is a function of the mass diffusion coefficient. Therefore, this number numerically obtained from simulations will be underestimated by Eq. ( 25), which will affect the predictions of mass fluxes calculated using the enhancement factor E. In order to make the numerical diffusion impact negligible, a value of mass diffusion coefficient was settled very high compared to the coefficient associated to numerical diffusion: D = D d,A = D c,A = 5110 -8 m 2 /s. In order to check the reliability of the computed concentration field near the interface, the thickness of concentration boundary layer δ m is estimated and compared to the mesh grid size. Slip boundary condition at the interface is assumed to minimize δ m . With such condition, velocity in the film is uniform, equal to -U d in the frame of reference moving with the droplets as illustrated in Fig. 3 (the velocity profile in the film is linear when no-slip boundary condition is assumed). The local equilibrium between mass diffusion and convection can be written as follows:

2 2 y C D x C u ∂ ∂ - = ∂ ∂ ′ (32)
At the limit of the concentration boundary layer, both terms of Eq. (32) are approximated using characteristic parameters of the observed phenomenon:

2 ,s m d d C D L C U δ ∆ ≈ ∆ (33)
where δ m,s is the thickness of concentration boundary layer assuming slip condition, and is estimated as a function of Peclet number Pe:

2 1 2 1 , - = 1 1 2 3 4 4 5 6 ≈ Pe L U D L d d d s m δ (34)
Table 1 shows the result of this layer estimation and the mesh grid size over the y-direction ∆y for the four flow configuration used in this study. The mesh is refined near the wall: the smallest and highest mesh sizes are given. It is observed that the estimated thicknesses of the concentration boundary layer are higher than the mesh sizes. Therefore, grid refinement may be sufficient to predict mass transfer in this area. Finally, the following parameters are used: 0 A C = 10 kg.m -3 , and m = 1.

Identification of the mass transfer coefficient without reaction

The concentration field computation allows the calculation of the mean concentration profiles of A in the droplets, in the continuous phase and at the interface on the droplets side. Fig. 4 shows these profiles for the four flow configurations considered. The concentration at an infinite time rises when the degree of confinement decreases, i.e. when the channel diameter increases. This is logically due to the increase of the continuous phase volume while the droplets volume and the initial concentration From the mean concentration in the droplets, the mass transfer coefficient k d is identified so that the mass balance given by Eq. ( 35), and more precisely the discretised form of this equation (Eq. ( 36)), allows a good fitting of the mean concentration profile in the droplets obtained from the simulation.

( )

i A d A d UC d d A d d C C V a k t C V , , , - - = ∂ ∂ (35) ( ) ) ( ) ( ) ( ) ( , , , , t C t C V V a k dt t C dt t C i A d A d d UC d d A d A d - ⋅ - = + (36)
Fig. 5 shows that the results of the identification are very satisfying. Indeed, the simulated profile and the one calculated from the mass balance present a good adequacy. Table 2 presents the identified mass transfer coefficient for each flow configurations studied.

The values of the kinetic constant to set in the numerical code were determined in order to roughly obtain Ha = 0.1 and 1. Impact of reaction on mass transfer, Ha = 0.1 Fig. 6 shows that the mean concentration profiles in the droplets obtained from the simulations are well predicted by Eq. (37), which is the discretised form of the mass balance given by Eq. (31). Indeed, the simulated and calculated profiles are very close whatever is the degree of confinement of the droplets.

d A d UC i A d A d d d d A d A d V t C K V t C t C a k E V dt t C dt t C ⋅ + ⋅ - ⋅ ⋅ - = + ) ( ) ( ) ( ) ( ) ( , , , , , (37)
This result validates the reliability of the estimation of the reaction fluxes in Eq. (37) using a mean concentration over a droplet. Impact of reaction on mass transfer, Ha = 1 Finally, simulations are carried out with Ha = 1 in order to observe a significant impact of reaction on mass transfer. Fig. 7 shows the comparison between the simulated and calculated concentration profiles in the droplets. This time, it is noticed an important difference between the two profiles. This difference is more important in the confined flow configurations as illustrated on Fig. 8, which represents the relative deviation between the two profiles as a function of the length in the microchannel. When droplets are confined (L d /w C > 1), the deviation is of about 35 %, while it is roughly of 25 % when L d /w C < 1. Moreover, it can be noticed that the calculated concentration profile overestimates the one obtained from the computations. This remark highlights that interfacial mass fluxes are overestimated by the model based on the enhancement factor calculation. Indeed, concentration of the bulk in the droplet was approximated by the mean concentration in this volume. This implies an overestimation of the concentration gradient, and so an underestimation of the mass transfer coefficient k d (see part 3.3.1) to compensate. This coefficient was used to calculate Hatta number as described by Eq. ( 25). Therefore, the classical model for the estimation of interfacial mass flux in reactive liquid-liquid media applied at microscale tends to an overestimation of Hatta number, and so of the enhancement factor which directly impacts on the prediction of mass fluxes.

Impact of mass transfer on reaction selectivity

In a second part, the study focuses on the case of a complex chemical scheme to carry out in a microchannel. Consecutive competitive reactions given by the following scheme are considered:

R1: A + B 1 C in the continuous phase (38) R2: A + C 1 D in the continuous phase (39)
R1 and R2 are irreversible and second order reactions whose respective kinetic rates r c,1 and r c,2 are given by:

c,B c,A c C C K r 1 1 , = (40) c,C c,A c C C K r 2 2 , = (41)
The reactants and products are soluble in both phases but the reactions are supposed to occur only in the continuous phase. The desired product is C, and D the by-product. In homogeneous systems, the selectivity of the reaction would depend on the ratio of the kinetic rate constants K 1 /K 2 and the conversion of B. In two phase systems, mass transfer is a supplementary factor influencing the selectivity. The production of D depends on:

-the residence time of component C in the continuous phase after its formation. This time is linked to the transfer rate of C from the continuous phase to the droplets, -the kinetic of the second reaction. The unit cell length is one of the factors influencing the mass transfer kinetics in microchannels. [START_REF] Miceli Raimondi | Direct numerical simulations of mass transfer in square microchannels for liquid-liquid slug flow[END_REF] Indeed, its increase slows down the transfer between the two phases. In this work, the influence of the unit cell length on the selectivity of the competitive consecutive reaction scheme is studied by means of a numerical study based on the numerical tool described in the second part. The mathematical formulation of the mass balances has been modified to take into account the two reactions and to follow the concentrations of the four components. Two flow configurations are considered which present identical droplet length, velocity and hydrodynamic structures but different unit cell length as it can be seen on Fig. 9 : L UC = 300 and 600 µm.

Mathematical formulation for the concentration field computation

As previously said, the reactions occur in the continuous phase. Consequently, the following mass balances and interfacial equilibrium for each component j (j corresponds to the species A, B, C or D) in both phases can be written as follows:

j d j d j d j d C D C t C , 2 , , , ∇ = ∇ ⋅ ′ + ∂ ∂ u (42) C c A c j B c A c j j c j c j c j c C C K C C K C D C t C , , 2 , 2 , , 1 , 1 , 2 , , , ν ν +
+ ∇ = ∇ ⋅ ′ + ∂ ∂ u (43) j c j j d C m C , , = at the interface (44)
where ν 1,j and ν 2,j stand for the stoichiometric coefficients of reactions R1 and R2. These equations were also formulated according to a one-fluid approach using the transformations described in part 3.1. Simulations are done with m A = 1, and m B = m C = m D = m. The reactant A is initially present in the continuous phase (with a concentration C A 0 = 1 kg/m 3 ) and B in the dispersed phase (with a concentration C B 0 = 10 kg/m 3 ). Therefore, the reaction is initiated by the transfer of B to the continuous phase.

Results

The simulating conditions in terms of distribution coefficient m and ratio of kinetic constants K 1 /K 2 were varied. In order to highlight an impact of mass transport on reaction selectivity, kinetic constant values are set so that mass transfer kinetics are not limiting compared to reaction kinetics. This avoids that the reactions strictly occur at the interface. For that purpose, the simulations were done at low Hatta number: Ha < 0.5.

B, C and D characterised by a high distribution coefficient (m = 500), K 1 /K 2 = 10 The distribution coefficient m was set at 500, which means that B, C and D are preferentially present in the dispersed phase. This condition notably induces that the transfer of the reactant B is limited. The kinetic constant of the secondary reaction is ten times lower than the one of the main reaction (K 1 = 50 m 3 .mol -1 .s -1 ; K 2 = 5 m 3 .mol -1 .s -1 ). Fig. 10 illustrates the concentration fields obtained for each component at a residence time of 8 ms in the flow configuration characterised by the short unit cell length (L UC = 300 µm). The colour scale is not the same for each picture, but was adapted so that the concentrated areas for the different components clearly appear. It is observed that: -concentration of A tends to uniformity in both phase since this component is characterised by a distribution coefficient equal to unity. -concentration of B is much higher in the dispersed phase (m = 500): the mass transferred fluxes of B are low. -concentration of C and D are also higher in the dispersed phase (m = 500) while these components are produced in the continuous phase. It means that most of the reactions occur near the interface, which leads to a rapid transfer of these products to the dispersed phase after their generation. -in the continuous phase, components C and D are in higher concentration in the film than in the interval, notably near the wall. This presumes that the reaction between A and B takes place dominantly in the film rather than in the interval. A small quantity of C tends to accumulate in the film which leads to a significant production of D in this volume. The same observations can be formulated on the concentration fields computed considering the flow configuration where L UC = 600 µm. From these concentration fields, selectivity of the reaction scheme S, defined in terms of Eq. ( 45), is calculated with the concentration of C and D averaged over a unit cell. Fig. 11 illustrates S for both flow configurations over time. During the first milliseconds, the selectivities in both configurations are similar. But then the selectivity in the case characterised by the shortest unit cell length becomes higher than in the other case. This is a direct consequence of the accumulation of C in the film. Indeed, the longest the interval length, the highest the time available for C to stray from the interface to the wall by diffusion through the film. This phenomenon disadvantages its transfer back to the dispersed phase in favour of its consumption by reaction 2. Following this observation, the simulating conditions are modified with the idea to minimize the unfavourable impact of the unit cell length on the selectivity. For that purpose, two cases were investigated:

-Firstly, the kinetic constant of the secondary reaction is increased (K 2 = 50 m 3 .mol -1 .s -1 ; K 1 /K 2 = 1) in order to avoid the diffusion of product C toward the wall by enhancing its consumption by reaction 2. -Secondly, the secondary reaction is limited in the film by impoverishing this volume in reactant A. For that purpose, the flux of B was increased from the dispersed phase to the continuous phase by setting m = 1. In order to assign the impoverishment of A in the film to its consumption by reaction 1, it was set K 1 /K 2 = 10. This is emphasized by the fact that B is in large excess. B, C and D characterised by a high distribution coefficient (m = 500), K 1 /K 2 = 1 The following parameters are set: m = 500 and K 1 = K 2 = 50 m 3 .mol -1 .s -1 . Fig. 12 illustrates the concentration field of D at a residence time of 8 ms in the flow configuration characterised by the short unit cell length (L UC = 300 µm). This by-product is again in high concentration near the wall: it is mainly formed in this area because of the diffusion of C through the film. In fact, despite the high value of K 2 , the transfer of C to the wall is still significant since low Hatta number was imposed. The results in terms of selectivity are similar to what was previously observed: the selectivity decreases when the interval length increases (Fig. 13). Indeed, this figure presents the concentration field of A at a residence time of 8 ms in the flow configuration characterised by the short unit cell length (L UC = 300 µm): it is observed a dark blue coloration of the film which is significant of poorly concentrated areas. However, byproduct D is still in high concentration near the wall (Fig. 14 (b)), which explains once again the negative impact of the unit cell length on the selectivity (Fig. 15).

Conclusion

In this work, the behaviour of reacting liquid-liquid systems in microchannels was studied by means of numerical simulations. It aimed at underlining some issues relative to the proceeding of reaction in such systems, through two themes:

-Firstly, the study focused on the modelling of mass transfer in reactive medium.

Transfer fluxes between two phases are generally estimated as a function of the enhancement factor E. Its expression depends on the model used to represent interfacial mass transfer. In usual device, we generally refer to Lewis and Whitman's stagnant film theory for its simplicity and its reliability. In microchannels, it appeared that the enhancement factor was not well estimated considering such a model. Other theories such as Higbie's penetration theory could be more appropriated to represent interfacial transfer. In other words, the present work shows that the way of apprehending mass transfer must take into account the degree of confinement of slug flows. -Secondly, competitive consecutive reactions were considered in order to analyse the impact of the interval length between the droplets on the scheme selectivity. In the operating conditions simulated (low Hatta number), the selectivity tended to increase with a decrease of the unit cell length for a constant droplets length. This is due to the accumulation of the intermediate product C near the wall by diffusion of this product from the interface through the film. This observation should be validated by an experimental study. This last part also suggests that concentrations in reactants and intermediates products are not uniform in the microchannel which raises the problem of hot spots formation when working with exothermic reactions. However, in our case (reactions occur in the continuous phase), the concentrated areas appear near the wall which is generally the region where the temperature control is optimal by heat exchange.

Notation

Fig. 1 .

 1 Fig. 1. Illustration of a two dimensional computational mesh. The thick line represents the fictitious interface obtained with JADIM.

Fig. 2 .

 2 Fig. 2. Illustration of the streamlines in the flow configurations simulated to study the impact of reaction on mass transfer. (a) L d = 154.4 µm, w C = 50 µm, U d = 0.062 m/s, L d /w C = 3.1. (b) L d = 121.6 µm, w C = 60 µm, U d = 0.039 m/s, L d /w C = 2.0. (c) L d = 84.8 µm, w C = 120 µm, U d = 0.022 m/s, L d /w C = 0.71. (d) L d = 87 µm, w C = 240 µm, U d = 0.014 m/s, L d /w C = 0.36.

1

 1

Fig. 3 .

 3 Fig. 3. Scheme of the concentration boundary layer in the film (a) with slip boundary condition and (b) no-slip boundary condition.

4

 4

1 2

 1 are the same in each flow configuration.

Fig. 4 .

 4 Fig. 4. Mean concentration profiles of A in the droplets, the continuous phase and at the interface, estimated from the simulations without reaction. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36.

Fig. 5 .

 5 Fig. 5. Mean concentration profiles of A in the droplets simulated and calculated (without reaction). (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36.

Fig. 6 .

 6 Fig. 6. Mean concentration profiles of A in the droplets simulated and calculated, Ha = 0.1. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Mean concentration profiles of A in the droplets simulated and calculated, Ha = 1. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36.

Fig. 9 .

 9 Fig. 9. Flow configurations simulated to study the impact of mass transfer on reaction selectivity. (a) L d = 100.8 µm, U d = 0.15 m/s, w C = 60 mm, L UC = 300 µm. (b) L d = 100.8 µm, U d = 0.15 m/s, w C = 60 mm, L UC = 600 µm.

Fig. 10 .

 10 Fig. 10. Concentration fields of the reactants (a) A and (b) B, and the products (c) C and (d) D at a residence time of 8 ms, L UC = 300 µm, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s).

Fig. 11 .

 11 Fig. 11. Evolution of the selectivity for both flow configurations, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s).

Fig. 12 .

 12 Fig. 12. Concentration field of by-product D at a residence time of 8 ms, L UC = 300 µm, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 50 m 3 /(mol s).

Fig. 13 .

 13 Fig. 13. Evolution of the selectivity for both flow configurations, m = 500, K 1 = 50 m 3 /(mol.s), K 2 = 50 m 3 /(mol.s).

Fig. 14 .

 14 Fig. 14. Concentration fields of reactant (a) A and by-product (b) D at a residence time of 8 ms, L UC = 300 µm, m =1, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s).

Fig. 15 .

 15 Fig. 15. Evolution of the selectivity for both flow configurations, m = 1, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s).

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .Fig. 8 .Fig. 9 .

 1234589 Fig. 1. Illustration of a two dimensional computational mesh. The thick line represents the fictitious interface obtained with JADIM. Fig. 2. Illustration of the streamlines in the flow configurations simulated to study the impact of reaction on mass transfer. (a) L d = 154.4 µm, w C = 50 µm, U d = 0.062 m/s, L d /w C = 3.1. (b) L d = 121.6 µm, w C = 60 µm, U d = 0.039 m/s, L d /w C = 2.0. (c) L d = 84.8 µm, w C = 120 µm, U d = 0.022 m/s, L d /w C = 0.71. (d) L d = 87 µm, w C = 240 µm, U d = 0.014 m/s, L d /w C = 0.36. Fig. 3. Mean concentration profiles of A in the droplets, the continuous phase and at the interface, estimated from the simulations without reaction. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36. Fig. 4. Mean concentration profiles of A in the droplets simulated and calculated (without reaction). (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36. Fig. 5. Mean concentration profiles of A in the droplets simulated and calculated, Ha = 0.1. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36. Fig. 6. Mean concentration profiles of A in the droplets simulated and calculated, Ha = 1. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36. Fig. 6. Mean concentration profiles of A in the droplets simulated and calculated, Ha = 1. (a) L d /w C = 3.1, (b) L d /w C = 2.0, (c) L d /w C = 0.71, (d) L d /w C = 0.36. Fig. 7. Relative deviation between the simulated and calculated mean concentration profiles in the droplets as a function of the degree of confinement of the flow. Fig. 8. Flow configurations simulated to study the impact of mass transfer on reaction selectivity. (a) L d = 100.8 µm, U d = 0.15 m/s, w C = 60 mm, L UC = 300 µm. (b) L d = 100.8 µm, U d = 0.15 m/s, w C = 60 mm, L UC = 600 µm. Fig. 9. Concentration fields of the reactants (a) A and (b) B, and the products (c) C and (d) D at a residence time of 8 ms, L UC = 300 µm, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s). Fig. 10. Evolution of the selectivity for both flow configurations, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s). Fig. 11. Concentration field of by-product D at a residence time of 8 ms, L UC = 300 µm, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 50 m 3 /(mol s). Fig. 11. Concentration field of by-product D at a residence time of 8 ms, L UC = 300 µm, m = 500, K 1 = 50 m 3 /(mol s), K 2 = 50 m 3 /(mol s). Fig. 12. Evolution of the selectivity for both flow configurations, m = 500, K 1 = 50 m 3 /(mol.s), K 2 = 50 m 3 /(mol.s). Fig. 13. Concentration fields of reactant (a) A and by-product (b) D at a residence time of 8 ms, L UC = 300 µm, m =1, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s). Fig. 14. Evolution of the selectivity for both flow configurations, m = 1, K 1 = 50 m 3 /(mol s), K 2 = 5 m 3 /(mol s).

Table 1 .

 1 Comparison between the estimated thicknesses of the concentration boundary layer and the mesh grid sizes.

	L d /w C	3.1	2.0	0.71	0.36
	L d (µm) δ film (µm)	154.4 3.1	121.6 3.4	84.8 20.7	87.0 80.1
	U d (cm/s) δ m,s (µm) ∆y (µm)	6.16 11.2 0.3 -1.33	3.68 12.9 0.3 -1.65	2.21 13.9 0.3 -3.47	1.44 17.4 1 -2.97

Table 2 .

 2 Mass transfer coefficients identified and reaction kinetic constants calculated to study the impact of reaction on transfer.

	L d /w C	3.1		2.0		0.71		0.36
	k d (m/s)	3.06e-03	3.03e-03	5.29e-03	3.35e-03
	Ha	0.103	1.03	0.104	1.04	0.104	1.04	0.106	1.06
	K (1/s)	2	200	2	200	6	600	2.5	250

Acknowledgments

This work has been supported by 6th Framework EU under Grant IMPULSE No: NMP2-CT-2005-011816 and the Institut National Polytechnique of Toulouse (see http://www.inptoulouse.fr). Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, an initiative from the French Ministry of Research through the ACI GRID incentive action, INRIA, CNRS and RENATER and other contributing partners (see https://www.grid5000.fr).


M Crochemore
email: maxime.crochemore@kcl.ac.uk

C Epifanio
email: epifanio@math.unipa.it

A Gabriele

F Mignosi
email: mignosi@di.univaq.it

From Nerode's congruence to Suffix Automata with mismatches ⋆

Keywords: Combinatorics on words, indexing, suffix automata, languages with mismatches, approximate string matching

. As second result we present an algorithm that makes use of S k to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.

Introduction

One of the seminal results in string matching is that the size of the suffix automaton of a word, also called DAWG (directed acyclic word graph), is linear [START_REF] Blumer | Linear size finite automata for the set of all subwords of a word -an outline of results[END_REF][START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF][START_REF] Crochemore | Transducers and repetitions[END_REF]. More precisely, in [START_REF] Blumer | Linear size finite automata for the set of all subwords of a word -an outline of results[END_REF] it is proved that the size of the suffix automaton is linear, while in [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF] authors have given an on-line linear time algorithm to build this automaton. Minimality as an automaton accepting the suffixes is in [START_REF] Crochemore | Transducers and repetitions[END_REF].

These results are surprising as the maximal number of subwords that may occur in a word is quadratic according to the length of the word. Suffix trees are linear too, but they represent strings by pointers to the text, while DAWGs work without the need of accessing it.

Literature on languages with mismatches and corresponding data structures involves many results, among the most recent ones [START_REF] Amir | Indexing and dictionary matching with one error[END_REF][START_REF] Buchsbaum | Range searching over tree cross products[END_REF][START_REF] Chávez | A metric index for approximate string matching[END_REF][START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF][START_REF] Epifanio | Languages with mismatches and an application to approximate indexing[END_REF][START_REF] Epifanio | Languages with mismatches[END_REF][START_REF] Gabriele | Indexing structure for approximate string matching[END_REF][START_REF] Huynh | Approximate string matching using compressed suffix arrays[END_REF][START_REF] Landau | Efficient string matching with k mismatches[END_REF][START_REF] Maass | Text indexing with errors[END_REF]. Most of these papers deal with approximate string matching and indexing. In particular, [START_REF] Landau | Efficient string matching with k mismatches[END_REF] presents the most efficient algorithm for approximate string matching with mismatches without indexing. Moreover, in [START_REF] Epifanio | Languages with mismatches and an application to approximate indexing[END_REF][START_REF] Epifanio | Languages with mismatches[END_REF][START_REF] Gabriele | Indexing structure for approximate string matching[END_REF] authors have considered some data structures recognizing words occurring in a text w up to k errors in each substring of length r of the text. The presence of a window in which a fixed number of errors is allowed generalizes the classical kmismatch problem and, at the same time, it allows more errors on the overall.

In this paper we focus on the minimal deterministic finite automaton that recognizes the set of suffixes of a word w up to k errors, denoted by S w,k , or simply by S k if there are no risk of misunderstanding on w. Our contribution is mainly theoretical in nature, even if we give some experimental results that support a conjecture on the size of S k . In the first part of the paper we present two main results. The first one is a characterization of the Nerode's right-invariant congruence that is associated with S k . This results generalizes the classical characterization described in [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF] (see also [START_REF] Crochemore | Algorithms on strings[END_REF][START_REF] Inenaga | On-line construction of compact directed acyclic word graphs[END_REF]). This classical characterization has been used to design an efficient construction of the suffix automaton with no mismatches, which, up to the set of final states, is also called DAWG. Up to now we have only extended Nerode's congruence to the approximate case and we have proved some theoretical results on it. We think these results will be useful for designing an efficient on-line algorithm for the construction of the suffix automaton with mismatches. It still remains an open problem how to design such an algorithm.

The second main result concerns the description of an algorithm that makes use of the automaton S k in order to accept, in an efficient way, the language of all suffixes of w up to k errors in every windows of size r, for a specific integer r called the repetition index. To do this we first provide a linear-time algorithm that finds r.

In the second part of the paper we show some empirical results. We have constructed the suffix automaton with mismatches of a great number of words and have considered overall its structure when the input word is well-known, such as the prefixes of Fibonacci and Thue-Morse words, as well as words of the form bba n , a, b ∈ Σ, n ≥ 1, and some random words generated by memoryless sources. We have studied how the number of states grows w.r.t the length of the input word. Following our experiments on these classes of words, we conjecture that the (compact) suffix automaton with k mismatches of any text w has size O(|w| • log k (|w|)).

Given a word v, Gad Landau wondered if there exists a data structure having a size "close" to |v| that allows approximate pattern matching in time proportional to the query plus the number of occurrences. This question is still open, even if recent results are getting closer to a positive answer. If our conjecture turns out to be true, it would settle Landau's question as discussed at the end of this paper. Moreover, in this case our data structure may be used in some classical applications of approximate indexing and string matching, such as recovering the original signals after their transmission over noisy channels, finding DNA subsequences after possible mutations, text searching in case there are typing or spelling errors, retrieving musical passages, A.I. techniques in feature vector, and so on. It may be important even in other applications, like in the field of Web search tools when we deal with agglutinative languages, i.e. languages that mainly resort to suffixes and declinations such as many Finno-Uralic languages (like Hungarian, Finnish, and Estonian), or in the case of real-time proposal of alternative internet URL in Domain Name Servers, or for deeper analysis of biological sequences.

The remainder of this paper is organized as follows. In the second section we give some basic definitions. In the third section we describe a characterization of the Nerode's right-invariant congruence relative to S k . The fourth section is devoted to describe an algorithm that makes use of the automaton S k to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the value of the repetition index of w. The fifth section contains our conclusions and some conjectures on the size of the suffix automaton with mismatches based on our experimental results.

Basic definitions

Let Σ be a finite set of symbols, usually called alphabet. A word or string w is a finite sequence w = a 1 a 2 . . . a n of characters in the alphabet Σ, its length (i.e. the number of characters of the string) is defined to be n and it is denoted by |w|. The set of words built on Σ is denoted by Σ * and the empty word by ǫ. We denote by Σ + the set Σ * \ {ǫ}. A word u ∈ Σ * is a factor (resp. a prefix, resp. a suffix ) of a word w if and only if there exist two words x, y ∈ Σ * such that w = xuy (resp. w = uy, resp. w = xu). Notice that some authors call substring what we define as a factor. We denote by Fact(w) (resp. Pref(w), resp. Suff(w)) the set of all factors (resp. prefixes, resp. suffixes) of a word w.

We denote an occurrence of a nonempty factor in a string w = a 1 a 2 . . . a n at position i ending at position j by w(i, j) = a i . . . a j , 1 ≤ i ≤ j ≤ n. The length of the factor w(i, j) is ji + 1, and we say that u occurs in w at position i if u = w(i, j), with |u| = ji + 1.

In order to handle languages with errors, we need a notion of distance between words. It is represented by the function d : Σ * ×Σ * → R + ∪{0} defined between two strings x and y on the alphabet Σ as the minimal cost of a sequence of operations that transform x into y (and ∞ if no such sequence exists). In most applications the possible operations are insertion, deletion, substitution and transposition. These operations lead to the definitions of different distances between words. In this work we consider the Hamming distance [START_REF] Sankoff | Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison[END_REF] that allows only substitutions, which cost 1 in the simplified definition. It is finite whenever |x| = |y|. In this case the inequalities 0 ≤ d(x, y) ≤ |x| hold.

In other words, given two strings x and y having the same length, the distance d(x, y) between them is the minimal number of character substitutions that transform x into y.

In the field of approximate string matching, typical approaches for finding a string in a text consist in considering a percentage D of errors, or fixing the number k of them. Instead, we use an hybrid approach introduced in [START_REF] Gabriele | Indexing structure for approximate string matching[END_REF] that considers a new parameter r and allow at most k errors for any factor of length r of the text.

Definition 1 Let w be a string over the alphabet Σ, and let k, r be non negative integers such that k ≤ r. A string u = ǫ occurs in w at position ℓ up to k errors in a window of size r or, simply, k r -occurs in w at position ℓ, if one of the following two conditions holds:

-|u| < r ⇒ d(u, w(ℓ, ℓ + |u| -1)) ≤ k; -|u| ≥ r ⇒ ∀i, 1 ≤ i ≤ |u|-r+1, d(u(i, i+r-1), w(ℓ+i-1, ℓ+i+r-2)) ≤ k.
A string u satisfying the above property has a k r -occurrence of w. A string u that k r -occurs as a suffix of w is a k r -suffix of w.

The empty word ǫ k r -occurs in w at any position ℓ = 0, 1, . . . , |w|. It also represents a k r -suffix of w.

We suppose that the text w is non-empty, r ≥ 2 and 0 ≤ k ≤ r, otherwise the above definition would have no meaning. We denote by L(w, k, r) (resp. Suff (w, k, r)) the set of words (resp. suffixes) u that k r -occur in w at some position ℓ, 1 ≤ ℓ ≤ |w| -|u| + 1. Notice that L(w, k, r) is a factorial language, i.e. if u ∈ L(w, k, r) then each factor of u belongs to L(w, k, r). Moreover, we denote by Suff (w, k) the set of k r -suffixes of w for r = |w|.

Remark 2

The condition r = |w| is equivalent to considering no window on w. Indeed, in this situation, the problem of finding all k r -occurrences of a string u in the text is equivalent to the k-mismatch problem, that consists in finding all occurrences of the string u in w with at most k errors (cf. [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF]).

Example 3 Let w = abaa be a string on the alphabet Σ = {a, b}. The set of words that k r -occur in w, when k = 1 and r = 2, is L(w, 1, 2) = {a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, abaa, abab, abba, bbaa, bbab, bbba}.

Notice that words aab, aaab, bbab, bbba occur with one error every r = 2 symbols, but with two errors in the whole word. Hence, they belong to L(w, 1, 2), but not to L(w, 1, 4). Moreover, Suff(w, 1, 2) = {a, b, aa, ab, ba, aaa, aab, baa, bab, bba, aaaa, aaab, abaa, abab, abba, bbaa, bbab, bbba} and Suff(w, 1) = {a, b, aa, ab, ba, aaa, baa, bab, bba, aaaa, abaa, abab, abba, bbaa}.

Now we can recall the definition of the repetition index, denoted by R(w, k, r), that plays an important role in the construction of an automaton recognizing the language L(w, k, r) (cf. [START_REF] Gabriele | Indexing structure for approximate string matching[END_REF]).

Definition 4

The repetition index of a string w, denoted by R(w, k, r), is the smallest integer h for which all strings of this length k r -occur at most once in the text w.

The parameter R(w, k, r) is well defined because the set of integers h for which all strings of this length k r -occur at most once in the text w is always non empty since the integer h = |w| satisfies the condition. Moreover, it is easy to prove that if k r ≥ 1 2 then R(w, k, r) = |w| (cf. [START_REF] Epifanio | Languages with mismatches and an application to approximate indexing[END_REF]).

In [START_REF] Epifanio | Languages with mismatches and an application to approximate indexing[END_REF] it is proved that R(w, k, r) is a non-increasing function of r and a non-decreasing function of k, and that the equation r = R(w, k, r) admits an unique solution r. Moreover, it is proved, under some hypothesis on the source, that R(w, k, r) has an upper bound that is almost surely logarithmic in the size of the text w. Recall that a sequence of random variables X n converges to a random variable X almost surely, denoted X n → X (a.s.), if ∀ǫ > 0, lim

N →∞ P r{sup n≥N |X n -X| < ǫ} = 1.
Almost surely convergence implies convergence in probability (see also [28, Chapther 2] for further details).

Remark 5 In [START_REF] Gabriele | Indexing structure for approximate string matching[END_REF] authors gave an algorithm for building a deterministic finite automaton (DFA) recognizing the language L(w, k, r) of all words that k roccur in the string w. They proved that the size of such automaton A(w, k, r) is bounded by a function that depends on the length |w| of the text w, the repetition index R(w, k, r), and the number k of errors allowed in windows of size r unique solution of the equation

r = R(w, k, r), namely |A(w, k, r)| = O(|w| • (r) k+1 ).
In the worst case, when both r and k are proportional to |w|, the size of the automaton A(w, k, r) is exponential. But, under the hypothesis that w is a sequence generated by a random memoryless source with identical symbol probabilities and that the number k of errors is fixed for any window of size r, the size of this automaton is

O(|w| • log k+1 (|w|)) almost surely.
Starting from the automaton A(w, k, r), an automaton recognizing the language Suff(w, k, r) can be simply deduced from a procedure that first builds the automaton A(w$, k, r), extending the alphabet Σ by letter $, then sets as terminal states only those states from which an edge labeled by letter $ outgoes, and finally removes all edges labeled $ and the state they reach [START_REF] Crochemore | Algorithms on strings[END_REF].

In this paper we focus on the minimal automaton recognizing Suff(w, k). It is therefore natural to study the Nerode's congruence corresponding to it.

On the Nerode's congruence

In this section, we introduce a right-invariant congruence relation on Σ * used to define the suffix automaton of a word up to mismatches and we prove some properties of it. In particular we give a characterization of the Nerode's congruence relative to S k . This result generalizes a classical result described in [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF] (see also [START_REF] Crochemore | Algorithms on strings[END_REF][START_REF] Inenaga | On-line construction of compact directed acyclic word graphs[END_REF]), where it is used in an efficient construction of the suffix automaton with no mismatches, that is also called DAWG (directed acyclic word graph), up to the set of final states. We think that it is possible to define such an algorithm even when dealing with mismatches. It would be probably more complex than the classical one.

In what follows, we do not consider the window, i. e. we set r = |w|.

Let us start by introducing the following definition, that is a generalization of the one given in [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF].

Definition 6 Let w = a 1 . . . a n be a word in Σ * . For any word y ∈ Σ * , the end-set of y in w up to k mismatches, denoted by end-set w (y, k), is the set of all final positions in which y k-occurs in w, i.e. end-set w (y, k) = {j | y k-occurs in w with ending position j}. Notice that end-set w (ǫ, k) = {0, 1, . . . , n}.

By using Definition 6 we can define an equivalence relation between words on Σ * . Definition 7 Two words x and y in Σ * are end k -equivalent, or ≡ w,k , on w if the following two conditions hold.

(1) end-set w (x, k) = end-set w (y, k);

(2) for any position i ∈ end-set w (x, k) = end-set w (y, k), the number of errors available in the suffix of w starting at position i + 1 is the same after the reading of x and of y, i.e. min{|w|i, kerr i (x)} = min{|w|i, kerr i (y)}, where err i (u) is the number of mismatches of the word u that k r -occurs in w with final position i.

We denote by [x] w,k the equivalence class of x with respect to ≡ w,k . The degenerate class is the equivalence class of words that have no k-occurrences in w (i.e., words with empty end-set in w up to k mismatches).

In other words, two words x and y in Σ * are end k -equivalent if, besides having the same end-set in w up to k mismatches as in the exact case [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF], the number of errors available in the suffix of w after the reading of x and of y is the same. The definition includes two cases depending on the considered final position i ∈ end-set w (x, k) = end-set w (y, k) of x and y in w: 2.a) if this position is sufficiently "far from" the end of the word, which means that |w|i ≥ max{kerr i (x), kerr i (y)}, then the number of errors available after this position is the same in both cases, i.e. kerr i (x) = kerr i (y), which implies that err i (x) = err i (y). In this case min{|w|i, k -

err i (x)} = k -err i (x) = k -err i (y) = min{|w| -i, k -err i (y)}. 2.b) otherwise, if
this position is sufficiently "near" the end of the word, which means that |w|i ≤ min{kerr i (x), kerr i (y)}, then mismatches are possible in any position of the suffix of w having length |w|i. This does not necessarily imply that

err i (x) = err i (y). Therefore min{|w| -i, k -err i (x)} = |w| -i = min{|w| -i, k -err i (y)}.
Example 8 Let us consider the prefix of length 10 of the Fibonacci word, w = abaababaab, and let us suppose that the number k of errors allowed in any factor is 2.

-The words x = baba and y = babb have the same end-set, that is endset w (baba, 2) = {5, 6, 8, 10} = end-set w (babb, 2), but the two words are not end k -equivalent because it is not true that for any position i ∈ end-set w (baba, 2) = end-set w (babb, 2), the number of errors available in the suffix of w having i + 1 as first position is the same after the reading of x and of y. In fact, if we consider i = 5, err 5 (baba) = 2 and err 5 (babb) = 1 and then min{|w| -5, 2err 5 (baba)} = 0 = 1 = min{|w| -5, 2err 5 (babb)}.

-The words x = abaababa and y = baababa are trivially end k -equivalent because they have the same end-set, that is end-set w (abaababa, 2) = {8} = end-set w (baababa, 2), and for i = 8 the number of errors available in the suffix of w having i + 1 as first position is the same after the reading of x and of y. In fact, if we consider i = 8, err 8 (abaababa) = 0 and err 8 (baababa) = 0 and then min{|w| -8, 2err 8 (abaababa)} = 2 = min{|w| -8, 2err 8 (baababa)}.

-The words x = abaababaa and y = baababab have the same end set, that is end-set w (abaababaa, 2) = {9} = end-set w (baababab, 2), and for i = 9 the number of errors available in the suffix of w having i + 1 as first position is the same after the reading of x and of y, even if err 9 (abaababaa) = 0 and err 9 (baababab) = 1. In fact, one has that min{|w| -9, 2err 9 (abaababaa)} = 1 = min{|w| -9, 2err 9 (baababab)}, and then x and y are end k -equivalent.

The following lemma and theorem summarize some properties of end k -equivalence. Before stating them, we recall that an equivalence relation ≡ on Σ * is right invariant if, for any x, y, z ∈ Σ * , x ≡ y implies that xz ≡ yz.

PROOF.

(i) ≡ w,k is an equivalence relation. Indeed it is obviously reflexive, symmetric and transitive. Moreover this relation is a right-invariant equivalence. For any x, y ∈ Σ * , if x ≡ w,k y, then end-set w (x, k) = end-set w (y, k) and for any position i ∈ end-set w (x, k) = end-set w (y, k), min{|w|i, kerr i (x)} = min{|w|i, k -err i (y)}. Since the number of errors available in the suffix of w having i as first position is the same after the reading of x and of y, then for any z ∈ Σ * xz is a k-occurrence of w if and only if yz is a k-occurrence of w. Hence, end-set w (xz, k) = end-set w (yz, k) and for any position j ∈ endset w (xz, k) = end-set w (yz, k) the number of errors available in the suffix of w having j as first position is the same after the reading of xz and of yz.

-i, k -err i (y)} = k -err i (y). Since k -err i (xy) ≤ k - err i (y) ≤ |w| -i, then min{|w| -i, k -err i (xy)} = k -err i (xy). Since min{|w| -i, k -err i (xy)} = min{|w| -i, k -err i (y)}, then k -err i (xy) = k -err i (y)
and all the err i (xy) errors are in y and x occurs exactly in w.

(2) Let min{|w| -i, k -err i (y)} = |w| -i. Since min{|w| -i, k -err i (xy)} =
min{|w|-i, k -err i (y)}, one has that the number of errors available in the suffix of w having i+1 as first position is min{|w|-i, k-err i (xy)} = |w|-i. Therefore the maximal allowed number of errors in x is k-[err i (y)+(|w|i)] ≥ 0. Hence, for any i ∈ end-set w (xy, k) = end-set w (y, k), the k-occurrence of y with final position i is immediately preceded by a t-occurrence of x, where t = max{(kerr i (y) -(|w|i), 0)}.

Let us suppose, now, that for any i ∈ end-set w (xy, k) = end-set w (y, k), the k-occurrence of y with final position i is immediately preceded by a toccurrence of x, where t = max{(kerr i (y)) -(|w|i), 0)}. By hypothesis, end-set w (xy, k) = end-set w (y, k). Let us distinguish two cases.

(1) Let us consider positions i ∈ end-set w (xy, k) = end-set w (y, k) such that t = 0. In this case all the err i (xy) are in y and the number of errors available in the suffix of w having i + 1 as first position is the same after the reading of xy and of y. -Suppose that z is such that |z| ≤ min{kerr i (x), kerr i (y)}. For such z one has that min{|w|-i, k-err i (x)} = |w|-i and min{|w|-i, k-err i (y)} = |w|i and the thesis is proved.

(2) Let us, now, consider positions i ∈ end-set w (xy, k) = end-set w (y, k) such that t = (k -err i (y)) -(|w| -i).
-Suppose that z is such that |z| ≥ max{kerr i (x), kerr i (y)}. For such z one has that min{|w|i, kerr i (x)} = kerr i (x) and min{|w|i, kerr i (y)} = kerr i (y). By hypothesis, for any position i ∈ endset w (x, k) = end-set w (y, k), any word z ∈ Σ * having i + 1 as first position is such that xz is a k-suffix of w if and only if yz is a k-suffix of w and then kerr i (x) = kerr i (v) and the thesis is proved.

2

In what follows we use the term partial DFA (with respect to the alphabet Σ) for a deterministic finite automaton in which each state has not necessarily a transition for every letter of Σ. The smallest partial DFA for a given language is the partial DFA that recognizes the language and has the smallest number of states. It is called the minimal DFA recognizing the language. Uniqueness follows from Nerode's Theorem [START_REF] Lothaire | Combinatorics on Words[END_REF] of the right invariant equivalence relation.

By using Nerode's theorem and by Theorem 10 we have the following result. PROOF. Since the union of the equivalence classes that form the accepting states of S k is exactly the set of all k-suffixes of w, by Nerode's Theorem one will add a flag information to each state and we will turn this flag information to "red" only to these states.

The graph G underlying S k is a directed acyclic graph (DAG in short) because the language of S k is finite. Thus, the inverse Ĝ of G, that is the graph where all arcs are inverted, is also a DAG. In order to simplify the algorithm we add an initial state q to Ĝ that goes with one arc to each final state of S k . It is well known that it is possible to find all single source minimal paths in linear time in a DAG and an algorithm V is described in [START_REF] Cormen | Introduction to Algorithms and Java CD-ROM[END_REF]. We refer to such algorithm V and to each step of it we add at most a constant number of extra steps. Roughly speaking, if during the execution of this algorithm the field distance of a state has been updated more than once, then the flag information has to be turned in red. More in details, the flag information can be white, green or red. The flag white means that the node has not yet been met during the execution of V, the green one means that, up that moment during the execution of V, the node has been encountered at least once and that the field distance has not been updated more than once i.e. all paths in G to a final state have same lengths. The flag red means that there are at least two paths in G to a final state having different lengths, or that, equivalently, the field distance has been updated more than once. The flag of the initial state q is set to be green and its distance is set to 0 while the flags of all other nodes are set to be white and distance equal to +∞. If a node with white flag is reached starting from a node with a green flag, then its flag is set to green and its distance becomes the distance from the initial state, i.e. the distance of previous node plus one. If a node with green flag is reached starting from another node with a green flag and if its distance is equal to the distance of previous node plus one, then the flag remains green, otherwise it is set to red. Red flags propagate in the sense that the flag information of any state that is reached starting from a state with a red flag is set to be red. The fact that red flags propagate corresponds to the fact that if in G there is an arc from q ′ to q ′′ (i.e. there is an arc from q ′′ to q ′ in Ĝ) and from q ′′ there are two paths having different lengths to a final state then also from q ′ there are two paths having different lengths to a final state.

The formal proof that the flag information is red only for all states q ′ such that there are two paths having different lengths from it to a final state in G, is left to the reader.

At this point we have to find the greatest length of all words that reach a state having red flag in S k or, equivalently, we have to find the length of a maximal path in G from q 0 to a state with a red flag. Since G is a DAG, we now behave analogously as suggested in [START_REF] Cormen | Introduction to Algorithms and Java CD-ROM[END_REF] as an application of the linear time algorithm V for single source shortest paths in DAG's. The application described in [START_REF] Cormen | Introduction to Algorithms and Java CD-ROM[END_REF] concerns PERT's diagrams where one has to find longest paths and not anymore shortest paths. A simple solution is to set the weight of each arc in G to be equal to -1 and look for the shortest path and the minimal distance. Changing the signs to these distance in each node will give the length of the longest path to each node.

The repetition index minus one r -1 is the greatest value among all nodes having red flag. The algorithm outputs r.

2

Remark 14 As a side effect of this algorithm, each state of the automaton S k is equipped with an integer that represents a distance from this state to the end. For this purpose, it is sufficient to make a linear-time visit of the automaton.

Now we can describe the algorithm that accepts the language Suff (w, k, r). It makes use of S k and the value r computed by previous algorithm. We can distinguish two cases.

i) If a word u has a length no more than r then we check if the word u is accepted by the automaton S k . If u is accepted by this automaton then it is in the language Suff (w, k, r), otherwise it does not belong to the language. ii) If a word u has a length greater than r then we consider its prefix u ′ of length r. Let q be the state that is reached after reading u ′ and let i be the integer associated with this state (cf. Remark 14). We have that |w|ir + 1 is the unique possible initial position of u. Given a position, checking whether a word k r-occurs at that position in the text w can be done in linear time.

Remark 15 A simple variation of above algorithm allows us to find a pattern word in the text with more mismatches than k in each window of size r. It is sufficient that its prefix of length r occurs in the text up to k mismatches, while the remaining suffix can have an arbitrary large number of mismatches.

As stated in ii) of previous algorithm, this can be done in linear time.

Experimental results and conclusions

This section is devoted to some experimental results and conjectures following from these.

We have constructed the suffix automaton with mismatches of a great number of words and we have considered overall its structure when the input word is well-known, such as the prefixes of Fibonacci and Thue-Morse words, as well as words of the form bba n , a, b ∈ Σ, n ≥ 1 and some random words. We have studied how the number of states grows w.r.t. the length of the input word.

The algorithm we have used for the construction of the suffix automaton with mismatches is neither efficient nor on-line. This is the reason for leaving out its description in this paper.

Concerning the prefixes of length n of the Fibonacci word, in the non approximate case, a result in [START_REF] Carpi | Words and special factors[END_REF], together with a result in [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF], implies that the following result holds.

Proposition 16

The suffix automaton of any prefix v of the Fibonacci word f has |v| + 1 states.

PROOF. In [START_REF] Carpi | Words and special factors[END_REF] it is proved that there exists an infinite set X of prefixes of the Fibonacci word (X is the set of the special prefixes) such that for any v in X the suffix automaton of v has |v| + 1 states. In [START_REF] Blumer | The smallest automaton recognizing the subwords of a text[END_REF] it is proved that the suffix automaton of va has either 1 or 2 states more than the suffix automaton of v, for any v in Σ * , a in Σ. Therefore, for any prefix v of the Fibonacci word f , its suffix automaton has |v| + 1 states. 2

Remark 17 The result in [START_REF] Carpi | Words and special factors[END_REF] holds for the whole class of special Sturmian words. Therefore, above proposition can be extended to this class of infinite words.

Our experimental results in the approximate case have led us to the following sequence {q ′ n } n , representing the number of states of the suffix automaton with one mismatch: 4, 6, 11, 15, 18, 23, 28, 33, 36, 39, 45, 50, 56, 61, 64, 67, 70, 73, 79, 84, 90, 96, 102, 107, 110, 113, 116, 119, 122, 125, 128, 134, 139, 145, 151, 157, 163, 169, 175, 180, 183, 186, 189, 192, 195, 198, 201, 204, 207, 210, 213, 216, 222, 227, 233, 239, 245, 251, 257, 263, 269, . . . This means that the sequence of differences between two consecutive terms is: 2, 5, 4, 3, 5, 5, 5, 3, 3, 6, 5, 6, 5, 3, 3, 3, 3, 6, 5, 6, 6, 6, 5, 3, 3, 3, 3, 3, 3, 3, 6, 5, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 3, 3, 3, 3, 3, 3, 3, 3, . . . . We note that after an initial part, there are (f ib i-1 -2) consecutive 6s, one 5, (f ib i -1) consecutive 3s, one 6, one 5,etc, where f ib i denotes the i-th Fibonacci number, i = 4, 5, 6 . . . . This leads to the following recursive formula:

{q ′ n } n = 2,
{q ′ n+1 -q ′ n } n = 2,
q ′ f ibn = q ′ f ib n-1 + 3(q ′ f ib n-3 -1) + 10 + 6(q ′ f ib n-4 -1).
From this recursion an explicit formula is easy to find. We did not prove the rule that describes the growth of the suffix automaton with one mismatch, but we checked that this rule holds true up to prefixes of length 2000 of the Fibonacci word f .

Conjecture 18

The size of the suffix automaton with one mismatch of the prefixes of the Fibonacci word grows according to the recursive formula q ′ f ibn = q ′ f ib n-1 + 3(q ′ f ib n-3 -1) + 10 + 6(q ′ f ib n-4 -1).

Concerning the size of the suffix automaton with two mismatches of the prefixes of the Fibonacci word, our experimental results have led us to the following sequence {q ′′ n } n , representing the number of states of the suffix automaton with two mismatches: [START_REF] Baeza-Yates | Indexing methods for approximate string matching[END_REF][START_REF] Buchsbaum | Range searching over tree cross products[END_REF][START_REF] Cormen | Introduction to Algorithms and Java CD-ROM[END_REF][START_REF] Galil | Data structures and algorithms for approximate string matching[END_REF][START_REF] Sankoff | Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison[END_REF]38,49,63,73,82,103,127,148,168,182,191,200,209,230,251,276,298,320,340,354,365,374,383,392,401,410,431,452,475,501,525,547,569,591,611,625,636,647,658,667,676,685,694,703,712,721,730,751,772,795,819,843,869,893,917,939,961,983,1005,1027,1047,1061,1020,1072,1083,1094,1105,1116,1127,1136,1145,1154,1163,1172,1181,1190,1199,1208,1217,1226,1235,1244,1265,1286,1309,1333,1357,1381,1405,1429 . . . This means that the sequence of differences between two consecutive terms is: 3, 4, 8, 9, 11, 14, 10, 9, 21, 24, 21, 20, 14, 9, 9, 9, 21, 21, 25, 22, 22, 20, 14, 11, 9, 9, 9, 9, 9, 21, 21, 23, 26, 24, 22, 22, 22, 20, 14, 11, 11, 11, 9, 9, 9, 9, 9, 9, 9, 9, 21, 21, 23, 24, 24, 26, 24, 24, 22, 22, 22, 22, 22, 20, 14, 11, 11, 11, 11, 11, 11, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 21, 21, 23, 24, 24, 24, 24, 24, . . . . We note that after an initial part, there is one 23,(f ib i-2 -3) consecutive 24s, one 26, (f ib i-3 -1) consecutive 24s, (f ib i-2 ) consecutive 22s, one 20, one 14, (f ib i-1 -2) consecutive 11s, f ib i consecutive 9s, two consecutive 21s etc, where f ib i denotes the i-th Fibonacci number, i = 6, 7, . . . . This leads to the following recursive formula:

{q ′′ n } n = 2,
{q ′′ n+1 -q ′′ n } n = 1,
q ′′ f ibn = q ′′ f ib n-1 + 125 + 24(q ′′ f ib n-5 -4) + 22(q ′′ f ib n-6 ) + 11(q ′′ f ib n-5 -2) + 9(q ′′ f ib n-4 ).

Conjecture 19

The size of the suffix automaton with two mismatches of the prefixes of the Fibonacci word grows according to the recursive formula

q ′′ f ibn = q ′′ f ib n-1 + 125 + 24(q ′′ f ib n-5 -4) + 22(q ′′ f ib n-6 ) + 11(q ′′ f ib n-5 -2) + 9(q ′′ f ib n-4 ).
Given a word v, Gad Landau wondered if a data structure having a size "close" to |v| and that allows approximate pattern matching in time proportional to the query plus the number of occurrences exists. In the non approximate case, suffix trees and compact suffix automata do the job (cf. [START_REF] Crochemore | Reducing space for index implementation[END_REF][START_REF] Inenaga | On-line construction of compact directed acyclic word graphs[END_REF]). Let us see the approximate case. In [START_REF] Epifanio | Languages with mismatches and an application to approximate indexing[END_REF][START_REF] Gabriele | Combinatorics on words with mismatches, algorithms and data structures for approximate indexing with applications[END_REF][START_REF] Gabriele | Indexing structure for approximate string matching[END_REF][START_REF] Maass | A new method for approximate indexing and dictionary lookup with one error[END_REF][START_REF] Maass | Text indexing with errors[END_REF] it is proved that for a random text w, the size of its compact suffix automaton with k mismatches is linear times a polylog of the size of w, i.e. O(|w| • log k |w|). From our experimental results it seems that the multiplicative constant hidden on the O notation in this random case is very small (less than 3). By using this data structure, the time for finding the list occ(x) of all occurrences of any word x in the text w up to k mismatches is proportional to |x| + |occ(x)|. Therefore, for random texts the open problem of Landau has a positive answer. For prefixes of Fibonacci word our previous conjecture tells us that suffix automata do the same. In the case of words of the form bba n , a, b ∈ Σ, n ≥ 1, our experimental results have led us to the following formula describing the behaviour of the sequence of differences between two consecutive terms involving words having n greater than or equal to 4: {a n+1 -a n } = 19+6 * (n-4). We have experimented also on prefixes of Thue-Morse words and, even if we have not obtained a well-formed formula, we have tested that the size of the compact suffix automata with 1 mismatch obtained is less than or equal to 2•|w|•log(|w|). Moreover, the result is true also in the case of periodic words. We also made an exhaustive search of the worst case for binary strings of length up to 18, i.e. we looked for strings whose suffix automaton with k mismatches has the greatest number of states in the case of one and two mismatches. The result was somewhat surprising. Both for one mismatch and for two mismatches one such string for any length greater than or equal to 12 in the case of one mismatch and greater than or equal to 8 in the case of two mismatches has the form 001 p 01 q 0. The number q seems to be always greater than p and the ratio between q and p seems to slowly decrease and it is different in the case of one mismatch with respect to the case of two mismatches.

When we deal with non compacted suffix automaton with mismatches, the worst case within this family of strings leads to a number of states that seems to grow like O(|w| • log 2k (|w|)), where k is the number of mismatches. This result is not bad at all if we consider that the language they represent has size Ω(|w| k+2 ).

If we deal with the compacted versions, results are better, but the asymptotic growth seems to be the same. It is still an open problem to find an algorithm for constructing this automaton in an efficient way.

The minimal deterministic finite automaton S k is useful for solving the problem of approximate indexing and the applications of it. Classically, an index (cf. [START_REF] Crochemore | Algorithms on strings[END_REF]) over a fixed text w is an abstract data type based on the set F act(w). Such data type is equipped with some operations that allow it to answer to the following queries. 1) Given a word x, say whether it belongs to F act(w)

or not. If not, an index can optionally give the longest prefix of x that belongs to F act(w). 2) Given x ∈ F act(w), find the first (respectively the last) occurrence of x in w. 3) Given x ∈ F act(w), find the number of occurrences of x in w. 4) Given x ∈ F act(w), find the list of all occurrences of x in w. In the case of exact string matching, the classical data structures for indexing are suffix trees, suffix arrays, DAWGs, factor automata or their compacted versions (cf. [START_REF] Crochemore | Algorithms on strings[END_REF]). The algorithms that use them run in a time usually independent of the size of the text or at least substantially smaller than it. The last property is required by some authors to be an essential part in the definition of an index (cf. [START_REF] Amir | Indexing and dictionary matching with one error[END_REF]). All the operations defined for an index can easily be extended to the approximate case. But in the case of approximate string matching the problem is somehow different. We refer to [START_REF] Baeza-Yates | Indexing methods for approximate string matching[END_REF][START_REF] Galil | Data structures and algorithms for approximate string matching[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF][START_REF] Navarro | A guided tour to approximate string matching[END_REF] and to the references therein for a panorama on this subject and on approximate string matching in general.

The minimal deterministic finite automaton S k introduced in this paper is useful for solving the problem of approximate indexing. More precisely, it is easy to answer queries 1) and 2), but the other questions are more complex and they can be solved by using techniques analogous to those in [START_REF] Gabriele | Indexing structure for approximate string matching[END_REF].

Moreover, if the Conjecture 20 is true and constants involved in O-notation are small, our data structure is useful for some classical applications of approximate indexing, as mentioned in the introduction.

Finally, we think that it is possible to connect the suffix automaton S k of the language Suff (w, k, |w|) (without window) to the suffix automaton S k,r of the language Suff (w, k, r), with r the unique solution of the equation r = R(w, k, r). More precisely, we conjecture that if S k and S k,r are the suffix automata of the languages Suff (w, k) (without window) and Suff (w, k, r), respectively, then |S k,r | = O(|S k |). From experimental results, it seems that S k,r has a greater size than S k . Therefore, the algorithm described in Section 4 that accepts the language Suff (w, k, r) seems to be more space-efficient than the automaton S k,r .

Aknowledgments

We warmly thank Gad Landau for interesting discussions on approximate text searching. We also would like to thank the anonymous referees for their suggestions leading to an improved writing of the paper.

Lemma 9 (

 9 i) ≡ w,k is a right-invariant equivalence relation on Σ * . (ii) If x and y are end k -equivalent on w and end-set w (x, k) = end-set w (y, k) = ∅, then one is a suffix of the other up to 2k errors. (iii) Words xy and y are end k -equivalent on w if and only if for any i ∈ endset w (xy, k) = end-set w (y, k), the k-occurrence of y with ending position i is immediately preceded by a t-occurrence of x, where t = max{(kerr i (y)) -(|w|i), 0)}.

(

  ii) By definition x and y are such that end-set w (x, k) = end-set w (y, k). Therefore, for any i ∈ end-set w (x, k) = end-set w (y, k), both x and y k-occur in w with final position i, which implies that one of them is a suffix of the other up to mismatches. By the triangular inequality, y) ≤ d(x, w)+d(w, y) ≤ 2k. Hence, by definition, x and y are one a 2k-suffix of the other. (iii) Let us suppose, by hypothesis, that xy ≡ w,k y. Therefore, end-set w (xy, k) = end-set w (y, k) and for any position i ∈ end-set w (xy, k) = end-set w (y, k), min{|w|i, kerr i (xy)} = min{|w|i, kerr i (y)}. Since err i (y) ≤ err i (xy), then kerr i (xy) ≤ kerr i (y). For any i ∈ end-set w (xy, k) = end-set w (y, k), we can distinguish the following cases. (1) Let min{|w|

Corollary 11

 11 For any w ∈ Σ * , the (partial) deterministic finite automaton having input alphabet Σ, state set {[x] w,k | x is a k occurrence of w}, initial state [ǫ] w,k , accepting states those equivalence classes that include the ksuffixes of w (i.e., whose end-sets include the position |w|) and transitions{[x] w,k -→ a [xa] w,k |x and xa are k-occurrences of w}, is the minimal deterministic finite automaton, denoted by S w,k (or simply by S k if there are no risks of misunderstanding on w), which recognizes the set Suff(w, k).

Conjecture 20

 20 The compact suffix automaton with k mismatches of any text w has worst-case size O(|w| • log 2k (|w|)).

  PROOF. By Lemma 9(i), if x and y are end k -equivalent, then for any z ∈ Σ * xz and yz are end k -equivalent and then xz is a k-suffix if and only if yz is a k-suffix.Let us suppose, now, that for any z ∈ Σ * , xz is a k-suffix if and only if yz is a k-suffix. Therefore end-set w (x, k) = end-set w (y, k). Moreover, for any z such that xz and yz are suffixes of w, the ending position i of x and y is such that |w|i = |z|. By hypothesis, we can have two cases depending on |z|.

In this case kerr i (y) ≥ |w|i and then min{|w|i, kerr i (y)} = |w|i. By hypothesis, this k-occurrence of y is immediately preceded by an occurrence of

x up to t = (k-err i (y))-(|w|i) errors. Therefore, kerr i (xy) ≥ k -[k -(err i (y) + |w|i) + err i (y)] = |w|i and min{|w|i, kerr i (xy)} = |w|i.

2

Theorem 10 Words x and y are end k -equivalent if and only if they have the same future in w, i.e. for any z ∈ Σ * , xz is a k-suffix of w if and only if yz is a k-suffix of w.

⋆ Partially supported by MIUR National Project PRIN "Automi e Linguaggi For-

has that S k recognizes the language of all k-suffixes of w, i.e. the set Suff (w, k). The minimality follows by Theorem 10.

2

Remark 12 We note that Suff(w,k)=Suff(w,k,r) with r = |w|, which is equivalent to saying that there are at most k errors in the entire word without window, and that Suff(w,k,r) ⊆ L(w, k, r).

Allowing more mismatches

In this section we present the second main result of the paper, that is the description of an algorithm that makes use of the automaton S k in order to accept, in an efficient way, the language Suff (w, k, r) of all suffixes of w up to k errors in every window of size r, that is the unique solution of the equation r = R(w, k, r). As proved in [START_REF] Epifanio | Languages with mismatches and an application to approximate indexing[END_REF][START_REF] Epifanio | Languages with mismatches[END_REF][START_REF] Gabriele | Combinatorics on words with mismatches, algorithms and data structures for approximate indexing with applications[END_REF] from r up to |w| the repetition index gets constant, i.e. for any value t ≥ r one has that r = R(w, k, t). This is also valid when the parameter t is such that t = |w|, which implies that r = R(w, k, |w|) = R(w, k). These two extremal cases are the two cases we are considering. This fact implies that any word u of length |u| = r has the following property: if u k r-occurs or k-occurs in w, then, in both cases, it occurs only once in the text |w|.

Before describing our algorithm, we give a preliminary result that is important both for the following and on its own. Lemma 13 Given the automaton S k , there exists a linear-time algorithm that returns r.

PROOF.

In this proof we consider w to be fixed. Let q 0 be the initial state of S k and let δ be its transition function. We call δ * its extension to words, i.e. δ * (q, w) is recursively defined as δ * (q, w) = q if w is the empty word and δ * (q, w) = δ(δ * (q, w -), a), where w -is the word w without the last letter and a is the last letter of w.

If u k-occurs twice in w, then from state q ′ = δ * (q 0 , u) there are two paths having different lengths to a final state. Conversely, if from a state q ′ there are two paths having different lengths to a final state, then any word u such that q ′ = δ * (q 0 , u) k-occurs twice in w. Therefore r -1 is the greatest length of all words that reach a state from which there are two paths having different lengths to a final state. In what follows in this proof we will describe an algorithm that finds r -1 in linear time and outputs r.

We firstly find all states q ′ such that there are two paths having different lengths from it to a final state. For "finding" these states we mean that we