COMPOSITE STRUCTURES AND LCM PROCESSES USED AT EADS

The proportion of composite materials in the aeronautic sector increases around 9% every year since 2003 (source "JEC"). Their integration rose in particular in the primary structures, like central wing box, rear fuselage, horizontal and vertical tail plane (i.e 26% of the A380 aircraft) or through Helicopters fuselage (NH90 and TIGRE) or airplane (at least 50% of the next aircraft generation A350XWB).

For 30 years EADS has developed composite structures using mainly conventional prepreg technologies. Although the cost of composite structures has been dramatically reduced it remains a little bit more expensive than metallic structures. Manufacturers are looking for cheap way of manufacturing composite structures. Liquid Composite Molding (LCM) technologies seem promising for cost reduction of aircrafts structures. LCM technologies have not to be considered as an alternative to prepreg technologies, but as a to way produce cost efficient composite structures and to increase the potential of applications. Theses technologies provide the opportunity of "low cost" composite parts: low material costs and reduced manufacturing effort compared to other technologies (reduced lay up effort, out of autoclave curing). LCM technologies allow an integral design for composite structures (preform technology) with out-of plane loading capabilities and are suitable for complex parts (e.g. high drape-ability of dry textiles).

SIMULATION OF RTM PROCESSES: RECENT ADVANCES

The industrial context currently requires an optimisation of development cycles, cost reduction of development and operating, the maturity of the product during its implementation on the market by a design phase often multi-sites and multi-partners. The use of simulation becomes in this context inescapable in order to fulfill the current industrial requirements. Nevertheless, the simulation can be effective only while being integrated into the various industrial structures/organisation.

A -Methodology for expertise study of RTM process simulation

Computer simulation of the injection process in RTM can help the mould designer to accomplish three important tasks:

• ensure a complete filling of the mould through adequate positioning of the injection ports and air vents; • verify the integrity of the mould during the filling process through knowledge of the pressure distribution; • optimize the production cycle using information on filling times Through an illustration of a simulation study on an AIRBUS composite part, the process methodology developed by EADS France IW is described. The main objective is to assist the definition of manufacturing process of a composite part. The selected parts are wing spars constituted in thermoset composite materials achieved by injection RTM. This methodology has been applied on different composites parts of EADS : Eurocopter, MBDA, Astrium Space Transportation... The complex geometry of preform (in order to integrate several functions into the part) and its dimensions (strong thicknesses and important length), caused difficulties of impregnation revealed during first injections. In order to attend the comprehension of defects formation and to reduce the optimisation cycle time, simulations of the injection step were achieved. The identified procedure of calculation consists in taking into account the geometry of the mould, to adapt it to the geometry of preform, to integrate the defects occurred in preproduction (gradients of local fibre contents…), to reproduce the injection conditions in the selected calculation method. For each model, some experimental characterizations of behaviour laws governing the process are carried out: permeability measurements, resin rheology at injection temperature (identified in EADS France IW) … After represented defects occurred in pre-production through simulation method, models were used for providing recommendations of the injection step and taking part into the improvement of the final manufacturing process (see Fig. 1). The software used for this study was PAMRTM (ESI Group).

The resin impregnation is usually modelled as a flow through a porous medium. It is governed by Darcy's law [START_REF] Darcy | Les fontaines publiques de la ville de Dijon[END_REF], i.e., the directional flow rate vector q per unit area, also called Darcy's velocity, is proportional to the pressure gradient:

K qp    
(1) where K is the permeability tensor (m2), p the resin pressure (Pa) and μ the fluid viscosity (Pa.s) assumed constant for a Newtonian resin. Combining (1) with the continuity equation .q = 0 gives

0    p) μ K .( (2)

B -New Liquid Composites Molding simulation

The DM-RTM (Dispersion Medium -Resin Transfer Molding) process principle is sensibly the same injection process as a RTM process (Fig. 2 and3). A highly permeable dispersion medium (wire netting for example) is incorporated into the laminated preform to accelerate the surface fibre impregnation and allow infusing through thickness the porous media. Thanks to this process larger surfaces can be injected with the same range of injection pressure as RTM process. Moreover, the rigid tooling is replaced by a membrane on the top side, which decreases significantly the tooling mass for large parts. The impregnation of a porous preform by a liquid resin can be modelling as a transient Darcy's flow [START_REF] Darcy | Les fontaines publiques de la ville de Dijon[END_REF]. In the case of the DM-RTM process, a highly permeable dispersion medium is added above the fibrous preform to facilitate resin impregnation of the laminate (see Fig. 4).

LRI dispersion media

Preform carbon

Membrane

Resin

Preform carbon

Rigid tool Important differences between permeability of dispersion media and laminate (more than 1,000 times) induce a complex 3-dimensional resin flow. Due to the higher permeability of the dispersion medium, resin initially flows through it forcing a though-thickness impregnation of the low permeability laminate.

A new numerical solution has been developed by EADS IW in collaboration with Ecole Polytechnique of Montréal [START_REF] Ruiz | A simplified numerical approach to simulate resin transfer molding with a dispersion medium[END_REF]. The simulation module is based on a Darcy's law evolution.

In this case, the flow in the fibrous preform is expressed by equation ( 3).

(

) 3
Where, v is the average superficial fluid velocity, P is the pressure gradient between two adjacent cells, named + andin the equation, [K] is the permeability tensor of the porous medium and μ the resin viscosity.

Some application cases were carried out on composite parts and allowed us to confirm the advantages of the proposed numerical simulation on a real aeronautical part. An example of application consists in a fuselage panel, auto-stiffened panel of 3,5 x 3 meters, with a ratio between length and thickness higher than 1000 (see Fig. 5).

  ˆ2 fib fib Z Z Z X X fib K P P K P v x z x z                   K P P   K P P   Z Z Z K P P Z Z Z   Z Z Z   K P P   Z Z Z                  K P P        K P P     Z Z Z   K P P   Z Z Z        Z Z Z   K P P   Z Z Z                    K P P       K P P        K P P       K P P   fib fib X X K P fib fib K P fib fib X X K P X X v   X X   X X
in-plane flow through-thickness flow A preliminary study showed the difficulties to reproduce the different flows of this kind of process with standard numerical solution. The comparison between the average K solution and the DM-RTM solution developed showed us benefits of the average K solution (see Figure 6). With this new numerical solution, we can evaluate the transverse flow through the preform and the in-plane flow in the DM-RTM (see Figure 7) with a meshing constituted of shell element (easier to set up than tetra element meshing).

Average solution DM-RTM solution

PERMEABILITY MEASUREMENTS : RECENT ADVANCES

The development and optimization of these technologies as well as the associated numerical simulation require knowledge of physical properties of the fibrous material, called preform. The resistance to the resin flow is defined by the permeability tensor of the preform in the model of Darcy's law. Considering the industrial different LCM processes and the targeted fiber content of aeronautical composite parts, a complete identification of the permeability tensor is necessary. Characterization of an adequate permeability value is still on debate: saturated or unsaturated method, accuracy of identification protocol, dual scale flow issues… Furthermore, industrial context force to require the characterizations procedures to be reliable, reproducible and realistic. Moreover, LCM technologies used by EADS Business Units, change in function of targeted part (geometry, thickness, fiber content...) and so induce various flows during the injection stage. In this aim in view, different protocols of permeability measurements have been set up for several years by EADS Innovation works in collaboration with academic partners, in order to be close to our requirements. For each method, we describe the selected protocol, the reasons of the choice and some illustrations of their targeted applications on industrial composite structures.

A reference method of in-plane permeability measurement has been developed in collaboration with Ecole Polytechnique of Montréal. The main advantage consists in a standard measurement procedure of in-plane unidirectional permeability with fully automated instrumentation (see Fig. 8). This concurrent method includes a built-in correlation with Darcy's law and allows an estimation of experimental and numerical errors. Fig. 8 View of global measurement system of the in-plane permeability bench.

The displacement of a newtonian fluid through a porous medium can be predicted by the Darcy's law (1).

In the unidirectional case, we can write:

P L V K i    . . (4)
with Vi, instantaneous velocity of flow, and P L   is the linear pressure drop.

The principle of the measurement consists in using Darcy's law in order to calculate the permeability value. Also, we must:

• follow during the infiltration, the flow front through the fibrous medium,

• measure the pressure gradient present in the reinforcements. The developed protocol takes into account these principles by integration of:

• optical fibers in order to detect the resin position,

• pressure sensors in order to measure the pressure gradient,

• temperature sensors inside the mold cavity in order to calculate the fluid viscosity,

• automatic treatment of measured data in order to estimate the permeability value • GUI (see Fig. 9) in order to follow in real time on a screen the flow front evolution and parameters process (pressure injection as a function of time, for example), • report obtained by computer including results sheet (permeability value, uncertainty) and other recorded information during tests. Three different methods have been developed in order to process data of tests and give three different estimations of permeability value [START_REF] Ferland | Concurrent Method for Permeability Measurement in Resin Transfer Molding[END_REF]. The unidirectional method in opposition of the radial flows method has been selected. The last approach is attractive for non isotropic permeability materials (fabrics for example) because the two principal permeabilities could possibly be evaluated in a single experiment. However, some difficulties have been shown [START_REF] Gauvin | Permeability Measurement and Flow Simulation through fiber Reinforcement[END_REF] concerning the complex data acquisition of a central injection (record of an elliptic flow front with sensors, fit the experimental front position to a perfect ellipse) and the influence to the radius of the injection port during the identification of the permeability value (difficulties of comparison of the experimentally observed wetted areas with an analytical solution of Darcy equation in cylindrical coordinates).

The targeted processes by this permeability measurement protocol are the Resin Transfer Molding (RTM) process including rigid mold and process inducing constant fiber content during the injection. This family of LCM technologies represents the major part of the injected aeronautic composite parts manufactured for EADS products, in order to obtain data about the injectability of the preform. A dedicated numerical approach has been developed in parallel of this protocol and allows having some information on the filling stage of the part [START_REF] Trochu | Numerical Analysis of the Resin Transfer Molding Process by the Finite Element Method[END_REF].

From a few years, some through-thickness permeability measurements have been developed [START_REF] Comas-Cardona | Unidirectional compression of fiber reinforcements, Part 2: A continuous permeability tensor measurement[END_REF][START_REF] Drapier | Characterization of transient through-thickness permeabilities of Non Crimp New Concept (multiaxial fabrics)[END_REF]. EADS France IW proposes in collaboration with the University of Le Havre a new continuous saturated through-thickness permeability (see Fig 10). This apparatus consists of a cylindrical chamber within a guided piston which induces the exact fiber compaction in the transverse direction. The device is introduced into a universal testing machine to control the displacement of the piston and the force applied to the fibrous medium. The fluid is directed to the transverse direction by perforated bronze grids. A pressure transducer is placed below the lower grid. Test samples of fibrous preforms are placed between the two grids. Another device is placed on an other universal testing machine in order to apply a controlled flow rate of fluid on the fibrous reinforcement. When a newtonian test fluid is injected at a constant flow rate through the fibrous reinforcement, an evolution of pressure is measured by the pressure sensor. The transverse permeability Kz is calculated using Darcy's law:

Q P A h K Z    ( 5
)
where μ is the dynamic viscosity of the test fluid, h and A are respectively the thickness and the area of the preform, Q is the imposed flow rate and P is the difference of pressure induced by the constant flow rate of test fluid through the reinforcement.

Finally, the through-thickness permeability is assessed in a continuous way according to fiber content through the controlled compression of the porous medium (see Fig 11). The obtained saturated permeability allows obtaining important information on throughthickness injectability of the preform. The targeted processes by this permeability measurement protocol are processes inducing non constant fiber content during the infusion. This family of LCM technologies represents a new part of the injected aeronautic composite parts manufactured for EADS products (large composite parts with high fiber content). A dedicated numerical approach has been developed in parallel of this protocol and allows having some information on the filling stage of the composite part [START_REF] Ouahbi | Modelling of Hydro-Mechanical Coupling in Infusion Processes[END_REF].

Finally, a permeability measurement specifically dedicated to process including double porous medium has been developed in relation with Ecole Polytechnique of Montréal. The infiltration of the fluid through different porous medium can be represented by different flows (see Fig 4).

Thanks to eq (1), these resin flows can be estimated by applying Darcy's law with a pressure gradient

DM P  in the DM, fibers P 
through the laminate:

  t DM DM DM DM Q P A Q       K and   t fibers fibers fibers fibers Q P A Q       K (6)
where DM Q is the flow rate through the dispersion medium, fibers Q the flow rate in the laminate, t Q the flow rate between the dispersion medium and the laminate, A the in-plane area,  is the dynamic viscosity of the test fluid, , respectively the fiber content and the permeability tensor of the laminate and the dispersion medium.

For thin laminates, the through-thickness flow t Q can be estimated by applying Darcy's law between the DM and the laminate:

) ( fibers DM fibers T fibers t P P A Q     K (7)
where T fibers K is the transverse through-thickness permeability of the laminate, DM P the pressure in the dispersion medium, and fibers P the pressure in the laminate.

One way conceivable to experimentally identify theses properties consists in the characterization of each properties separately: one measurement for DM (in-plane permeability) and two other for fibrous perform (in-plane and through thickness permeabilities). Nevertheless, to obtain accurate thought-thickness permeability of a high fiber content preform and in-plane permeability of DM is still on debate. Secondly, an approach of separated measurement of the both porous medium don't allow taking into account the coupling between the in-plane permeability of DM and fiber content of the preform.

The developed method consists in maintaining the proposed measurement of permeability of first chapter but taking into account the intimate link between the porous media. So, the carried out method induces the characterization of the couple of material in the same measurement (see Fig 12). In the end, we obtain directly the necessary permeability values through only one flow filling of the double porous medium. A specific software has been developed in order to identify the permeability from experimental data (see Fig 13).

Fig. 13 View of data processing and identification of DM and preform permeabilities.

The targeted processes by this permeability measurement protocol are processes inducing infiltration of a double porous medium at constant fiber content like Liquid Resin Infusion process.

For these different methods, numerical solutions were developed in parallel and applied on industrial parts. This clearly demonstrated how these different tasks highly contribute to the integration of composite process simulation in the development of aeronautical structural composite parts.

OPEN ISSUES

Another recurrent important issue encountered in the modeling and simulation of LCM concerns the porosity prediction in the manufactured parts. Preforms exhibit two characteristic length scales, the finest one related to the distance between individual fibers integrating the yarn, and the coarse scale representing the distance between neighbor yarns. Thus, if the injection velocity is dominant with respect to capillary effects, the inter-yarns spaces are fulfilled before the yarn impregnation that results in micro-porosities within the yarn core. On the contrary when capillary effects are dominant a residual porosity is noticed at the mesoscopic scale (in between the yarns). Different models have been proposed concerning a single phase and also multi-phase models [START_REF] Garcia | A flux limiter strategy for solving the transport equations in RTM modeling void formation[END_REF], however no model is at present able to predict quantitatively the experimental observations.

Another issue concerns the injection of reinforced resins involving micro or nano charges (e.g. carbon nanotubes). The use of this kind of additives is important in order to enhance the part properties, like thermal or electrical conductivity. However, at present the dispersion, rheology and filtration of charges when the suspension flows within the porous media need further developments. Moreover, Darcy's flows don't consider microscopuic details, and it is important to remember that the CNTs orientation (and the final properties strongly depend on the orientation distribution) is governed by the microscopic flow features. Certainly for describing orientation effects richer description than the averaged Darcy's flow should be necessary, micro-macro simulations being a potential alternative.

Obviously, the control of porosity in manufactured parts and the use of nano-charges for improving the properties of structures are of major interest in many industrial applications.

CONTROL & OPTIMISATION

Control and optimization techniques require fast solvers able to anticipate filling defects, taking the appropriate actions to avoid them. The issue related to real time simulations is a fashionable topic in many branches of science and engineering. The use of high performance computing, parallel computing platforms … has made possible impressive simulations, but the deployment of resources is far of the availabilities of medium and small industries. Today, new tendencies concern the use of model reduction techniques that have been successfully applied in other contexts [START_REF] Chinesta | On model reduction and its potential applications in chemical eginneering[END_REF]. In the case of RTM, because the evolving geometry (the part of the mould occupied by the fluid) the use of standard model reduction technique remains delicate.

The second ingredient in control and optimization is the definition of a certain cost function that should be minimized. This function can integrate one or many criteria, and in all cases the choice depends on the process and the industrial requirements. For example if the main objective is to avoid dry zones in the mould (filling defect) one could try to define an injection protocol such that all the point defining the flow front at any time are at the same distance to the vent, as illustrated in Fig. 14. Ideally, if this condition is exactly fulfilled we ensure the perfect mould filling.

The idea is simple, but for computations we must describe this vent oriented flow front through a cost function. If we consider that the flow front at any time is described by N points (that define a polygonal curve approaching the flow front), that we consider M flow front positions during the filling process, and that we represents by j i d the distance between the point i x on the flow front at time j t , an appealing choice for the cost function writes: where T is the total filing time and Obviously, this choice is not unique, and many other choices exist. For example in reactive injection one could be also interested in minimizing the differences between the chemical contents of one point with respect to its neighborhood in order to maximize the homogeneity in the subsequent chemical reactions. The interested reader can refer to [START_REF] Sánchez | A process performance index based on gate-distance and incubation time for the optimization of gate locations in liquid composites molding processes[END_REF] and the references therein for a detailed analysis of this kind of strategies.

Figure. 1 -

 1 Figure.1 -Preform filling for different steps of calculation.

Figure 2 :

 2 Figure 2 : RTM process.

Figure 3 :

 3 Figure 3 : DM-RTM process.

Figure 4 :

 4 Figure 4 : Flow description in DM-RTM process.

Figure 5 :

 5 Figure 5 : EADS Innovation Works composite fuselage panel (Barrel test, TANGO Fuselage program).

Figure 6 .

 6 Figure 6. Comparison between the average solution and the developed DM-RTM solution.

FillingFigure 7 .

 7 Figure 7. Illustration of the transverse filling results with the DM-RTM solution.

Fig. 9

 9 Fig. 9 Screenshot of GUI.

Fig. 10

 10 Fig. 10 View of global measurement system of the through-thickness permeability set up.

Fig. 11

 11 Fig. 11 Example of results of through-thickness permeability method.

Fig. 12

 12 Fig. 12 View of experimental test bench.

Fig. 14 .

 14 Fig. 14. Vent oriented flow front.

  the minimization of such cost function implies reducing the filling time as possible subjected to the flow front shape constraint.


Emmanuelle Abisset-Chavanne
email: emmanuelle.abisset-chavanne@ec-nantes.fr

Rabih Mehzer
email: brabih.mezher@ec-nantes.fr

Fransisco Chinesta
email: cfransisco.chinesta@ec-nantes.fr

Two-scales kinetic theory model of short-fibers aggregates

Keywords: CNTs suspension, kinetic theory, multiscale modelling, numerical simulation

come   L'archive ouverte pluridisciplinaire

Introduction

In order to improve some fluid mechanical or thermal properties, one solution is to introduce nanoparticules that change the fluid behaviour and properties, we talk then about ``charged fluid". A challenge is then to be able to predict the new properties of the fluid depending on the type of particles and flow induced microstructure evolution on which depends the macroscopic behaviour . In this work, we focus on suspensions involving rods more or less concentrated.

Depending on this concentration, the rods --short fibers, nanofibers or CNTs --suspensions present different morphologies. When the concentration is dilute enough the microstructure can be described by tracking a population of rods that move with the suspending fluid and orient depending on the velocity gradient according to the Jeffery's equation [1] that relates the orientation evolution with the flow velocity field. In that case the motion and orientation of each fiber is assumed decoupled from the others. As soon as the concentration increases the difficulties appear. In the semi-dilute or semiconcentrated regimes fiber-fiber interactions occur, but in general they can be accurately modelled by introducing a sort of randomizing diffusion term. The worst scenario that we are going to focus on in this paper concerns concentrated suspensions involving clusters of entangled particles and in which aggregation/disaggregation take place.

At the macroscopic scale, a possible way to describe such a charged fluid is to try to fit some powerlaw constitutive equation. However, this description does not allow to describe the microstructure. At the microscopic scale, direct numerical simulations describing complex fiber-fiber interactions can be carried out in small enough representative volumes. However, such a scale does not allow real scale problems resolution. Finally, a natural candidate to be a reasonable compromise between (fine) micro and (fast) macro descriptions consists of considering a mesoscale model, developed in the framework of kinetic theory.

The main advantage of such kinetic theory approaches [START_REF] Doi | The Theory of Polymer Dynamics[END_REF] [3] is their capability to address macroscopic systems, while keeping the fine physics through a number of conformational coordinates introduced for describing the microstructure and its time evolution. At this mesoscopic scale, the microstructure is defined from a distribution function that depends on the physical space, the time and a number of conformational coordinates. The moments of this distribution constitutes a coarser description, in general used in macroscopic modelling [START_REF] Advani | [END_REF].

Thanks to the use of this approach, the charged fluid model will include two scales: the one involving the aggregates and the one related to the rods constituting the aggregates.

In this paper, we first develop the description of suspensions involving rigid clusters, before moving to the description on suspensions involving deformable clusters. Indeed, the study of the rigid clusters allows to define a rigidity term in the deformable cluster modelling. Thus, for both case, starting from a microscopic description of the clusters equilibrium, we move to the mesoscopic one using the kinetic theory approach. Finally, the fluid virial stresses due to the suspensions is derived and, in a last section, compared to experimental results on the apparent viscosity of CNTs suspensions.

Suspension involving rigid clusters

When the concentration of rods in a suspension is high enough, a sort of clusters composed of entangled rods is observed. When this suspension flows, those clusters seem animated of almost rigid motions. The objective of this section is to derive a first model, starting from the microscale, allowing to describe the clusters' evolution and their influence on the virial stress of the fluid.

Clusters can be sketched in two dimensions as entangled aggregates of rods (see Fig. 1). These rods can be idealized by rigid segments joining two opposite beads.

In order to define a simple --but realistic --geometry for the clusters, we extract the beads located on the periphery of the cluster as illustrated in Fig. 2. Then we consider the star configuration depicted in Fig. 3 that will be the cluster idealization on which we are performing the kinematic and dynamic analysis.

Obviously, this process constitutes a tremendous simplification but it constitutes the simplest model that could be enriched without major difficulties to cover more complex and rich systems.

Microscopic description of a rigid cluster composed of rods

We consider a rigid cluster consisting of N rods, oriented in the directions p i as sketched in Fig. 4. In this study, Brownian effects can be neglected and then only flow induced hydrodynamic forces are considered. The rods are assumed to be inertialess and we also assume that the force only applies on the beads. In order to derive the kinematic of the rigid cluster, we first write its equilibrium.

For a cluster subjected to only hydrodynamic forces, a force F i applies on each bead L•p i , assumed given by:

F i = ξ • (∇v • p i • L -ṗi • L) (1)
It can be noticed that this expression consists of two contributions: a sort of affine deformation given by the term ∇v • p i and the second one that removes the deformation in the rod direction because, in presence of other force, the rod is considered inextensible. The coefficient ξ can be seen as a viscosity of the fluid: if ξ is low, the fluid does not have much influence on the cluster kinematics, and on the opposite for large ξ, the orientation of the cluster will be strongly influenced by the fluid flow. The value ξ = 0 is a non-physical one and should be never considered. Now, as the rods and so the cluster are inertialess, we enforce a null resulting moment for the whole cluster.

The moment associated with rod i is given by

M i = 2 • L • p i × F i (2)
where the symbol " × " denotes the cross product.

The forces are by construction self-equilibrated for the whole cluster, thus we only need to enforce the nullity of the resulting moment:

M i = 0 (3)
If we define the cluster angular velocity ω such that

ṗi = ω × p i (4)
then, in the 2D case, and because ω and p i are orthogonal, p i × ṗi = ω ∀i, the kinematics of the rigid 2D cluster can be defined from:

ω = ∑ i=N i=1 p i × (∇v • p i ) N (5)
being the angular velocity of each rod j:

ṗj = ω × p j = ( ∑ i=N i=1 p i × (∇v • p i ) × p j N ( 6
)
By simple manipulations on these relations, we can prove that in order to represents non-infinite aspect ratio 2D particles, it suffices to consider a rigid system composed of two rods, aligning perpendicularly the one with respect to the other, and having lengths 2

• L 1 and 2 • L 2 , L 1 ≥ L 2 ,
as depicted in Fig. 5. Moreover, in [START_REF] Chinesta | From Single-Scale to Two-Scales Kinetic Theory Descriptions of Rods Suspensions[END_REF], the author proves that this description allows to find the Jeffery's expression for an ellipsoid of aspect ratio L 1 L 2 .

Mesoscopic description of a rigid cluster composed of rods

In the microscopic description, the cluster is described by N discrete rods studied individually. To define the mesoscopic description, an alternative description consists in defining its orientation distribution ψ(p). Then, all the discrete sums on N of the microscopic description can be substituted by the corresponding integrals weighted with the distribution function ψ.

Thus in the 2D case Eq. ( 5) leads to:

ω = ∫ S(0,1) p × (∇v • p) • ψ(p) dp (7)
being the angular velocity of any rod q:

q = ω × q = ∫ S(0,1) (p × (∇v • p)) × q • ψ(p) dp (8) Because (p × (∇v • p)) i = ϵ ijk • p j • (∇v) kl • p l , it
is easy to prove that Eq. ( 7) writes:

ω = ϵ : ( a • (∇v) T ) (9)
with a the second moment of the orientation distribution function.

On the other hand we can define the rotation tensor W such that

ω × p = W • p (10)
that allows writting

ṗ = W • p (11)
Thus, the mesoscopic description uses:

   ω = ϵ : ( a • (∇v) T ) ṗ = ω × p ≡ W • p W = W(ω) (12)
These equations show that a rigid cluster rotates with a velocity that only depends on the second moment of its orientation distribution function a. Then, any cluster having the same a will have the same rotational velocity. The cluster kinematics can then be described by the evolution of a, taking its time derivative.

Using the definition of a and the Eq. ( 12), it results:

ȧ = ∫ S(0,1) ((W • p) ⊗ p + p ⊗ (W • p)) • ψ(p) dp = = W • a + a • W T (13)
Remark: the objectivity of ȧ has been proven in [START_REF] Chinesta | From Single-Scale to Two-Scales Kinetic Theory Descriptions of Rods Suspensions[END_REF], along with the non necessity of a closure relation.

Global description of a suspension involving several rigid clusters

The mesoscopic description has shown that rigid clusters rotate with a velocity that only depends on the second moment a of its orientation distribution function ψ(p). This fact suggests that a microstructure involving suspensions of several rigid clusters can be based on a distribution function Ψ(x, t, a) that represents the fraction of clusters that at position x and time t have a configuration described by a related to the orientation of the rods composing it and that was noted by ψ(p).

Virial stress induced by clusters suspension

The objective of this part is to determine the virial stress in the suspension due to the presence of clusters.

Contribution of a unique rigid cluster At the microscopic scale, the contribution of a rigid cluster composed of N rods to the virial stress results:

τ = ξ • L 2 • N ∑ i=1 p i ⊗ (∇v • p i -ṗi ) (14)
that taking into account the expression of ṗi reads:

τ = ξ • L 2 • N ∑ i=1 p i ⊗ (∇v • p i -W • p i ) (15)
or

τ = ξ • L 2 • N ∑ i=1 ( (p i ⊗ p i ) • (∇v) T -(p i ⊗ p i ) • W T ) (16)
In the continuous mesoscopic framework Eq. ( 16) results:

τ i = 2 • N p ∫ S(0,1) ( (p ⊗ p) • (∇v) T -(p ⊗ p) • W T ) • ψ(p) dp = = 2 • N p • ( a • (∇v) T -a • W T ) = 2 • N p • ( a • (D + Ω) T -a • (Ω + F) T ) = = 2 • N p • (a • D + a • F) (17)
where

       W = Ω + F F = ( 0 -f f 0 ) f (D, a) = -D 12 -2 • D 11 • a 12 + 2 • D 12 • a 11 (18)
The identity

D • a -F • a = a • D + a • F ensures the stress tensor symmetry, i.e. τ = τ T .
Contribution of all the rigid clusters Now, by considering all the clusters that contribute to the local stress,

τ = 2 • Ñp • ∫ A (D • a -F • a) • Ψ(a) da (19)
In order to avoid spurious non-symmetries when solving the kinetic model by using stochastic simulations we could consider a symmetrized form of the virial stress:

τ = Ñp • ∫ A (D • a + a • D -F • a + a • F) • Ψ(a) da ( 20
)
where the fact that F T = -F has again being taken into account.

Suspensions involving deformable clusters

In this section we are considering a more realistic scenario, that consisting in deformable clusters. The same reasoning as for the rigid cluster will be develop to finally derive the virial stress due to these deformable clusters.

Microscopic kinematics

Because the cluster is deformable, there's now two kinds of applied forces on each rods bead. The first one is again the one due to the fluid-rod friction once more modelled from:

F H i = ξ • (∇v • p i • L -ṗi • L) (21)
where the superscript "H" refers to its hydrodynamic nature.

Concerning the second one, we assume a force acting on each bead due to the rods entanglements. This force F C i is assumed scaling with the difference between the rigid motion velocity (the one that the bead would have if the cluster would be rigid) and the real one:

F C i = µ • (W • p i • L -ṗi • L) (22)
By adding both forces it results:

F i = F H i + F C i = L • ((µ • W + ξ • ∇v) • p i -(ξ + µ) • ṗi ) (23)
that can be rewritten as:

F i = L • (ξ + µ) • ( µ • W + ξ • ∇v ξ + µ • p i -ṗi ) (24)
In particular the rod rotary velocity results:

ṗi = µ ξ + µ • W • p i + ξ ξ + µ • ∇v • p i - ξ ξ + µ ( p T i • D • p i ) • p i = = ξ ξ + µ • ṗJ i + µ ξ + µ • W • p i = ξ ξ + µ • ṗJ i + µ ξ + µ • ṗR i (25)
where ṗJ i is the Jeffery's dilute contribution and ṗR i the one coming from the rigid cluster contribution. We can notice that when ξ ≫ µ the cluster does not resist the flow induced rod orientation, and in that case ṗi ≈ ṗJ i . In the opposite case, µ ≫ ξ, the cluster is too rigid and the bead adopts the velocity dictated by the rigid cluster kinematics ṗi ≈ ṗR i .

Mesoscopic description

We assume now, as for the rigid cluster, that the deformable cluster is described by the orientation distribution ψ(p) of the rods. As previously, in order to describe the evolution of the suspension, we will consider the evolution of the second order moment of this distribution.

We start considering again the usual second order moment:

a = ∫ S(0,1) p ⊗ p • ψ(p) dp ( 26
)
whose time derivative reads

ȧ = ∫ S(0,1) ( ṗ ⊗ p + p ⊗ ṗ) • ψ(p) dp ( 27
)
where as just deduced the microscopic velocity is given by:

ṗ = ξ ξ + µ • ṗJ + µ ξ + µ • ṗR (28)
that introduced into the expression of the second order moment time derivative results

ȧ = ξ ξ + µ • ȧJ + µ ξ + µ • ȧR (29)
with ȧJ and ȧR given by:

{ ȧJ = Ω • a -a • Ω + D • a + a • D -2 • A : D ȧR = W • a + a • W T = Ω • a -a • Ω + F • a -a • F (30)
where A is the fourth order moment of the distribution. Introducing Eq. (30) into Eq. ( 29) and grouping the different terms it results:

ȧ = Ω • a -a • Ω + ξ ξ + µ • (D • a + a • D -2 • A : D) + µ ξ + µ • (F • a -a • F) (31)
We prove that the model just derived, incorporating drag and network effects, is fully objective.

Global description of a suspension involving several deformable clusters

As for the case of the rigid clusters, we assume that a microstructure involving suspensions of several deformable clusters can be based on a distribution function Ψ(x, t, a) giving the fraction of clusters that at position x and time t have a configuration described by a related to the orientation of the rods composing it and that was noted by ψ(p).

Virial stress induced by deformable clusters suspension

The virial stress associated with a deformable cluster is computed by considering the hydrodynamic forces acting on each bead

L • p F H (p) = ξ • L • (∇v • p -ṗ) (32)
from

τ i = L • ∫ S(0,1) p ⊗ F H (p) • ψ i (p) dp ( 33
)
where the subindex "i" refer to the contribution of cluster i located around point x and time t where the stress is being computed.

If we introduce now into the expression of the hydrodynamic force the expression of the rod velocity given by Eq. (25) the expression of the hydrodynamic forces reduces to:

F H (p) = ξ • L • ( µ ξ + µ • (D • p -F • p) + ξ ξ + µ ( p T • D • p ) • p ) (34)
from with the cluster virial becomes:

τ i = L • ∫ S(0,1) p ⊗ F H (p) • ψ i (p) dp = = 2 • N p • ( µ ξ + µ • τ R i + ξ ξ + µ • τ J i ) (35)
where the cluster and hydrodynamic contributions, τ R i and τ J i , read:

τ R i = D • a -F • a (36)
and

τ J i = A : D (37)
respectively. Coming back to the two limits cases previously addressed: the Jeffery's regime is reached by assuming the cluster contribution negligible, in the opposite way, when cluster effects is dominant, the virial stress related to a rigid cluster is obtained.

Study of the behaviour of a charged epoxy

In order to test the results given by the model presented in the previous part, some numerical results are compared to experimental results reported in Cambridge [START_REF] Ma | [END_REF].

This experimental campaign focused on the evolution of the apparent viscosity of a suspension of CNTs into an epoxy matrix in a simple shear flow with the velocity field defined by (u, v) = ( γy, 0). Results show that the apparent viscosity of the fluid decrease with the increase of the shear rate γ (Fig. 6).

The idea is there to compare this results to the results issued from the model of deformable clusters.

To do so, in our model, we define the apparent viscosity η ap as:

η ap = τ i γ (38)
Now, considering this apparent viscosity, the equations derived in the previous part show that the relation between τ i and γ (related to ∇v) is linear. Then, our model can not describe the experimental results presented in Fig. 6. We then have to introduce a new ingredient in the model to mimic the results. To do so, let's come back to the physics of the behaviour of such suspensions.

As seen before, the deformation of a cluster results from the competition between two forces: the one due to the external fluid flow that tends to align the rods composing the cluster in the flow direction (the hydrodynamic force), and the ``internal'' one, linked to the resistance of the cluster to deform.

In the experiments, increasing the value of γ comes to the same thing as reinforcing the action of the hydrodynamic forces in the flow direction, and then tend to facilitate the alignment of the rods in the cluster. And, a cluster with all rods are almost in the same direction does not create much internal stress because it does not resist the flow.

We can then say that the relevant phenomenon here to explain such experimental results is the competition between the two forces applied on clusters.

In the model developed previously, the competition between these two forces is described by the ratio between the two coefficients ξ and µ.

In order to introduce the non linear dependency of the apparent viscosity with the shear rate γ, we derive a law that define the evolution of the ratio between ξ and µ to mimic the experimental results. The friction coefficient ξ depends on the nature of the solvent and the suspended particles, so it must be considered fixed. However, the parameters describing the cluster rigidity µ can depend on the applied shear, and we can imagine that it could decrease when the rods aligning in the flow direction because the decrease of the entanglements density.

Remark: calculation of the apparent viscosity Depending on the initial orientation distribution used for the calculation and the values of ξ, µ and γ, the apparent viscosity varies in time. Generally, when µ >> ξ, the apparent viscosity is periodic due to the fact that we approach a rigid cluster behaviour with an orientation evolving periodically in time. On the opposite, when µ << ξ, the apparent viscosity varies until reaching the constant null value, once all the clusters are aligned in the flow direction. Between these two behaviours, one can prove that a steady state exists, leading to a constant apparent viscosity. This particular behaviour is obtained for the following initial conditions:

The comparison between the experimental results and the numerical prediction of our model have shown that because the model does integrate the main physical phenomenon that can be observed for such suspensions, it can mimic experimental observations as soon as the identification of the parameters is made carefully.

Conclusions

In this work, a complete multiscale and physically based model of suspensions involving rigid/deformable clusters is developed. This model introduces parameters, as µ or ξ, allowing to describe the different clusters behaviours observed experimentally. In the last section, the application of this model and its confrontation to experimental results have shown that the identification of these parameters and their dependence on the flow conditions must be explained physically, probably by considering richer physics as cluster coalescence or disagregation.

Fig. 1 :Fig. 2 :Fig. 3 :

 123 Fig. 1: Entangled rods constituting a rigid cluster

Fig. 6 :

 6 Fig. 6: Evolution of the apparent viscosity of the charged fluid with the shear rate γ

  Identification of the evolution of µ with γ In Fig.7, one can see the values of µ identified for the different values of shear rate. From this result, we can derive a power function representing the evolution of the parameter µ with the shear rate: µ( γ) = 9.10 -4 γ-3,8 + 0, 55

Fig. 7 :

 7 Fig. 7: Identification of the parameter µ to describe the apparent viscosity dependency with the shear rate (study done for 0, 5% MWNT in epoxy)


Thomas Bellitto

Separating Codes and Traffic Monitoring

This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known, but traffic monitoring presents new challenges that the previous models of separation fall short from modelling such as taking into account the multiplicity and order of the arcs in a walk. We introduce a new and stronger model of separation based on languages that generalises the traffic monitoring problem. We study three subproblems with practical applications and develop methods to solve them by combining integer linear programming, separating codes and language theory.

Introduction

Characterising objects by using as few properties as possible is an important task in diagnosis or identification problems and has been broadly studied under different names such as separating/identifying codes or the test cover problem. The notion of separating codes has many applications in a wide range of domains; in each case, we have to deliver a diagnosis with limited or expensive access to information. Notable examples include visualisation and pattern detection [START_REF] Koen | Approximation algorithms for the test cover problem[END_REF] [START_REF] Patrenahalli | A branch and bound algorithm for feature subset selection[END_REF], routing [START_REF] Laifenfeld | Joint monitoring and routing in wireless sensor networks using robust identifying codes[END_REF] or fault detection [START_REF] Metze | Comments on "derivation of minimal complete sets of test-input sequences using boolean differences[END_REF] in telecommunication networks, as well as many areas of bio-informatics, such as analysis of molecular structures [START_REF] Haynes | A quantitative analysis of secondary rna structure using domination based parameters on trees[END_REF] or in medical diagnosis, where test covers are the core of diagnostic tables (see [START_REF] Willcox | Automatic construction of diagnostic tables[END_REF]) and are therefore important for blood sampling or bacterial identification (see [START_REF] Holmes | A review of numerical methods in bacterial identification[END_REF] for a survey on different methods). Separating codes have also been studied under the name of sieves in the context of logic characterisations of graphs; the size of a minimal separating code determines the complexity of the first-order logic formula required to describe a graph [START_REF] Han | How complex are random graphs in first order logic? Random Struct[END_REF].

The problem this paper mainly addresses is called traffic monitoring. Assume that traffic is going through a network modelled as a directed graph (e.g. cars in a town, packets in a telecommunication network, skiers in a ski resort...) and that we are given the opportunity to install sensors on the arcs of the digraph. Each time an object walks in the digraph and goes through an equipped arc it activates a sensor, and we know how many times and in which order each sensor was activated by that object. We are given the set of possible walks the object can take. Our goal is to find where to place the sensors so that we are able to determine exactly which route the object took from the information given by the sensors. This problem has been proven NP-complete in [START_REF] Maheshwari | Traversal marker placement problem are np-complete[END_REF], even in the case of acyclic digraphs. Aside from the complexity aspect, few results have been obtained on the problem. We have to take into account information such as the multiplicity and the order of the signals sent by the sensors, which place this problem beyond the expressive power of existing models for separating codes and their resolution methods. For the special case of monitoring skiers, Meurdesoif et al. developed a solution for acyclic digraphs [START_REF] Meurdesoif | Meter installation for monitoring network traffic[END_REF]. Their (exponential time) algorithm is based on double-path detection and their approach is very different from ours. In this paper, we adopt a new, more flexible approach based on separating codes that allows us to handle more general problems.

The next section provides all the necessary notions. It gives formal definitions of the separating code and traffic monitoring problems, presents how to solve the standard problem of separating codes by reducing it to integer linear programming and outlines the limitations of this model that make it unsuitable for handling traffic monitoring. We present in Section 3 a new model of separation based on language theory that overcomes these limitations and even generalises the traffic monitoring problem. The next three sections focus on particular cases of traffic monitoring. Section 4 studies the case where the set of walks to separate is finite. Section 5 studies the case where we want to separate every walk starting from a set of given vertices to a set of potential destinations. Such sets of walks can be infinite and would therefore yield infinitely many constraints. We study the underlying language and exhibit some properties that enable us to reformulate the problem as a standard integer linear program with finitely many constraints. Finally, Section 6 solves a more general case where we can give a set of pairs of adjacent arcs that the object may not use consecutively in any walk through the digraph, making this model much more relevant for physical networks such as road networks.

Preliminaries

Separating codes

The separating code problem is, given a set of individuals I and a set of attributes A, to find the smallest subset of attributes C ⊆ A such that each individual is characterised by the attributes of C it possesses. Here, attributes have no value and are simply properties that each individual may or may not possess.

This problem has been particularly studied in the case of graphs, where a separating code is standardly defined as a subset C of vertices such that each vertex of the graph is characterised by the intersection of its closed neighbourhood with C.

In many practical applications, some attributes are more expensive to test than others. Let a cost be associated to each attribute. Then, the weighted separation problem is the problem of finding a separating code of minimal cost.

Given a code, let the signature of an individual i be the set of attributes of the code it possesses. Thus, for separating codes of graphs, the signature of a vertex v is the intersection of its closed neighbourhood with the code. Hence, separating codes are the sets of attributes such that all the individuals have different signatures.

For example, let us consider the following graph and the code C = {x, y, z}: The signature of x is by definition N [x] ∩ C = {x, y}. One can see that the signatures of the vertices are pairwise distinct and that the set C is therefore a separating code.

The notion of separating code of graphs is often combined with another well-known problem of graph theory: domination. A dominating set on a graph is a set of vertices such that all the vertices of the graph are in the set or have a neighbour in the set. A set that is both separating and dominating is called an identifying code. Looking back at Figure 1, one can see that the set {x, y, z} is separating but not dominating since v has no neighbour in the code while the set {v, x, z} is both separating and dominating and is therefore an identifying code. Requiring the additional constraint that each individual should have at least one attribute in a separating code is a well-studied problem. For example in fault detection and security (see [START_REF] Ungrangsi | An implementation of indoor location detection systems based on identifying codes[END_REF]), domination ensures that we will notice quickly if a problem occurs and separation allows us to determine what the problem is.

While separation and domination seem unrelated at first sight, one can actually easily reduce identification to separation. Indeed, notice that separation consists of making the signatures of the individuals pairwise distinct while identification requires that the signatures are both pairwise distinct and non-empty. Therefore, all we have to do is add to our set of individuals an artificial individual that has no attribute and whose signature will thus necessarily be empty, thereby forcing all the other individuals to have non-empty signatures. Hence, the identification problem is resolvable if and only if no two individuals possess exactly the same attributes and each individual possesses at least one attribute.

The problem of separating code appeared first under the name of test cover (see [START_REF] Moret | On minimizing a set of tests[END_REF] or [START_REF] Koen | Approximation algorithms for the test cover problem[END_REF] for important examples). Separating codes for graphs were introduced in [START_REF] Mark | On a new class of codes for identifying vertices in graphs[END_REF] together with identifying codes and have been widely studied for many subclasses of graphs. One can also find variants of identification for hypergraphs, which consists of characterising the vertices by the hyperedges they belong to, or for bipartite graphs, which consists of separating the vertices of V 1 using only vertices of V 2 where (V 1 , V 2 ) is a bipartition of the graph (see [5] [6]). These two problems are actually equivalent to the general problem given by a set of individuals and a set of attributes. The problem has also been studied on directed irreflexive graphs ( [START_REF] Suk | Open neighborhood locating-dominating in trees[END_REF] [26] [START_REF] Iiro | On strongly identifying codes[END_REF]), a model whose expressiveness lies between the problem for graphs and the general problem with individuals and attributes. To the best of our knowledge, the first proof of the NP-completeness of the general test cover problem can be found in [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. The problem of finding the smallest identifying code on a graph was shown to be NP-complete in [START_REF] Charon | Minimizing the size of an identifying or locating-dominating code in a graph is np-hard[END_REF]. The complexity of this problem on specific classes of graphs has also been broadly studied.

We now give a reformulation of the problem as an integer linear program (ILP) on which the methods developed in the next sections are based.

Let I be a set of individuals and A be a set of attributes. Let (i, i ′ ) ∈ I 2 be such that i = i ′ . The separating set of i and i ′ , denoted by Sep(i, i ′ ), is the symmetric difference of their attributes i.e. the set of attributes that exactly one of them possesses. Therefore, i and i ′ will have distinct signatures according to a set of attributes C if and only if C possesses at least one attribute of their separating set.

For each attribute a ∈ A, let x a be a binary variable that indicates whether a ∈ C. We obtain the following system:

           ∀(i, i ′ ) ∈ I 2 with i = i ′ , a∈Sep(i,i ′ ) x a 1 minimise a∈A x a
Polyhedra associated with identifying code problems have been studied thoroughly in [START_REF] Argiroffo | Polyhedra associated with identifying codes[END_REF]. This ILP has a solution if and only if all the separating sets are non-empty i.e. if and only if no two individuals possess exactly the same attributes.

Notice that we obtain an ILP formulation of the weighted separating code problem by taking into account the costs in the objective function. For the sake of simplicity, we will stay with the unweigthed separating code problem in what follows, but the method presented can easily be generalised to the weighted case.

The traffic monitoring problem

We model a network with a directed graph G = (V, A) and have the option of installing sensors on the arcs of the graph. We want to be able to reconstruct the route of objects walking in the graph.

When an object walks in the graph, it activates a sensor each time it goes through an equipped arc. By moving in the graph, the object activates the sensors a certain number of times in a certain order. The ordered sequence of activated sensors is what we call the signature of the walk of the object.

In this problem, we are given the set R of potential routes the object can take and we are looking for the smallest possible set of arcs such that the signatures of all the routes of R are pairwise distinct. Is this is the case, the information given by the sensors is sufficient to determine exactly which route the object picked. Note that we make no assumption on the speed of the object; the time between the activation of two sensors cannot be used to determine what the object did in the meantime. However, we know the order in which the sensors were activated.

As before, variants where some arcs are more expensive to monitor than others or where we also want the walks of R to have non-empty signatures (so that we know if an object is walking in the network) are also of great practical interest.

Again, we have to distinguish a set of individuals (walks in a digraph) by testing as few attributes (the arcs the walks use) as possible. However, while this problem looks close to the the ones we have mentioned so far, it presents three major difficulties that we have not encountered yet which place it beyond the expressive power of the models described previously.

Let us illustrate these difficulties with an example: • The set of activated sensors is not sufficient to identify a walk; on the network of Figure 2, the walks (1, 2, 3, 1) and (1, 2, 3, 1, 2, 3, 1) are different but the sets of arcs they use are the same. Since they do not use these arcs the same number of times, we still can distinguish them -their signatures according to the sensor set {a, b} are respectively a and aa -but this forces us to take into account the multiplicity of the attributes of our individuals, which cannot be done with the previous model.

• The number of times each sensor is activated is not sufficient to identify a walk; in the network of Figure 2, the walks (1, 2, 3, 1, 4, 5, 1) and (1, 4, 5, 1, 2, 3, 1) not only use the same arcs but they also use them the same number of times. They can still be separated; their signatures are indeed respectively ab and ba, but this requires considering the order of the attributes. This also illustrates the limit of the resolution method we showed in the previous section. Indeed, we said that a code separates two individuals if and only if it contains an element that does so, but one can see here that the sensor set {a, b} separates the walks (1, 2, 3, 1, 4, 5, 1) and (1, 4, 5, 1, 2, 3, 1) while neither {a} nor {b} can.

• The set R of potential walks can be infinite; if the graph contains a cycle, the number of walks in it is infinite and R can be any subset of it. Therefore, even checking in finite time whether a given set of sensors separates R is non-trivial since it requires ensuring that all the walks of R have different signatures. A wrong intuition is that the problem can be reduced to separation on elementary paths since non-elementary walks are concatenations of elementary paths (which would be helpful since there are only a finite number of them), but this does not work. For example, assume that the set R we want to separate is the set of cycles starting from and leading to the vertex 1. Our set of sensors {a, b} is not suitable since the cycles (1, 2, 3, 1, 4, 5, 1) and (1, 2, 6, 5, 1) both have the signature ab although all the elementary cycles ((1, 2, 3, 1), (1, 4, 5, 1) and (1, 2, 6, 5, 1)) have different signatures (respectively, a, b and ab).

3. A new model of separation: separation on a language

The problem

We recall that an alphabet is a non-empty finite set whose elements are called letters, a word is a finite sequence of letters and a language is a set of words on a given alphabet. The reader may refer to [START_REF] Hopcroft | Introduction to automata theory, languages, and computation -international edition[END_REF] for basic notions of language and automata theory.

Let A be an alphabet and let C be a subalphabet of A. Let the projection on C, denoted p C , be the function that maps each word u ∈ A * to its longest subword which uses only letters of C. For example, p {a,b} (abacacb) = abaab.

Given a language L on an alphabet A, the problem of separation on a language consists of finding the smallest subalphabet C ⊆ A such that all of the words of L have different projections on C.

For example, let L = {aabcc, acabc, baacb, cbaac}. One can immediately notice that aabcc and acabc use the same letters the same number of times, so one cannot separate them with an alphabet of one letter. Plus, the projection of both these words on the subalphabet {a, b} is aab so this subalphabet also does not separate them. The projections of acabc and cbaac on {b, c} are also the same (cbc). However, the projections of the four words of L on the subalphabet {a, c} are respectively aacc, acac, aac and caac and are pairwise distinct. Hence, {a, c} is a solution of the problem and is the only optimal solution.

The problem of separation on a language is a generalisation of the problem of separating code. Indeed, let I be a set of individuals, let A be a set of attributes and let be a total order on A. Let us associate with each individual i a word on A composed of all the attributes i possesses, exactly once, in increasing order according to . The subalphabet of A that separates the language of the words associated to the individuals of I are exactly the separating codes. Therefore, separation on a language is NP-complete in both the size of the language and the alphabet it is defined on.

Relation to traffic monitoring

Let us consider the set A of arcs of a digraph as an alphabet. Since a walk on a digraph is a sequence of arcs, it is a word and the set R of possible routes is a language on A. Given a set of sensors, the signature of a route is its projection on the subalphabet composed of the arcs that have a sensor. Hence, traffic monitoring is a particular case of separating code on a language (however, the problems are not equivalent since not all languages can be written as a set of routes on the alphabet of the arcs of a digraph).

This reduction allows us to use tools arising from separating codes and language theory to address the traffic monitoring problem. However, the problem remains NP-complete in the size of the language that we want to separate. Moreover, we saw that in some instances, this language can be infinite. Hence, we intend not to solve the problem in general, but to address some classes of sets of routes which are of practical interest.

Separation of a finite language

The easiest place to start is the case where the language we want to separate is finite. This happens in particular when we want to solve traffic monitoring on an acyclic graph or when we can bound the length of the walks on the network. This problem already covers a wide range of applications.

The ILP we designed in the first section was based on the central notion of separating sets. The fundamental property of the separating set of two individuals i and i ′ is that a set of attributes separates i and i ′ if and only if it contains an attribute of their separating set. However, we saw that this property no longer holds for traffic monitoring and separation on a language (see Subsection 2.2). What still holds however is that if a set separates two words w and w ′ , so do its supersets. Hence, we can still look for the minimal sets of attributes that separate two words w and w ′ and we know that a set of attributes separates w and w ′ if and only if it contains one of those minimal sets. We thus define the separating set Sep(w, w ′ ) of two words w and w ′ as follows: given two words w and w ′ on an alphabet A, a subalphabet C of A belongs to the separating set Sep(w, w ′ ) of w and w ′ if and only if C separates w and w ′ and none of its strict subsets does. The separating set of two words is therefore a set of sets of letters.

It follows from the definition that a subalphabet C ⊆ A separates two words w and w ′ if and only if there exists

C ′ ⊆ C such that C ′ ∈ Sep(w, w ′ ).
We now exhibit some properties of the structure of separating sets that are useful in computing them efficiently (Theorem 2). Lemma 1. A word u ∈ A * is characterised by its projections on the subalphabets of A of cardinality 2.

Proof. The letter a is the first letter of a word u if and only if it is the first letter of all projections of u on the subalphabets of cardinality 2 containing a. One can then remove the a in the first position of the projection of u on the subalphabets containing a and find the second letter of u. This can be iterated until u is entirely determined.

For example, let A = {a, b, c} and u ∈ A * such that p {a,b} (u) = abba, p {a,c} (u) = aca, p {b,c} (u) = bbc. Since a is the first letter of the projection of u on {a, b} and {a, c}, we know that a is the first letter of u. Thus, there exists v such that u = av. From the projection of u, we deduce that p {a,b} (v) = bba, p {a,c} (v) = ca, p {b,c} (v) = bbc and the first letter of v is therefore b. Thus, there exists w such that u = abw and by iterating the process, we determine that u = abbca.

Theorem 2. The separating set of two words contains only sets of cardinality at most 2.

Proof. Let u and v be two words on an alphabet A and let C be a subalphabet of A of cardinality at least 3 such that no strict subalphabet of C separates u and v. Hence, for every subalphabet Let u and v be two words of A * . We can build their separating set as follows:

C ′ of C of cardinality 2, p C ′ (u) = p C ′ (v). Since C ′ is a subalphabet of C, we know that p C ′ (u) = p C ′ (p C (u)) and p C ′ (v) = p C ′ (p C (v)).
• If a letter a does not appear the same number of times in u and in v, then a alone suffices to separate them. We thus add {a} to Sep(u, v) and while the pairs containing a all separate u and v, they do not belong to the separating set.

• If a letter a appears neither in u nor in v, containing it would be of no help to separate u and v. Thus, the separating set contains no pair containing a. What is left to investigate are pairs {a, b} composed of two letters appearing the same number of times in u and v. Let k be the number of occurrences of a in u and v (k = 0). Thus, there exists

u 0 , • • • , u k , v 0 , • • • , v k such that u = u 0 au 1 a • • • au k and v = v 0 av 1 a • • • av k .
The pair {a, b} belongs to the separating set if and only if there exists i ∈ [[0, k]] such that u i and v i do not contain the same number of occurrences of the letter b. These decompositions of u and v can then be reused when investigating other pairs containing a.

We can take advantage of Theorem 2 to separate a finite language as follows: let L ⊆ A * be the language we want to separate. For each letter a ∈ A, let x {a} be a binary variable that indicates whether a ∈ C where C is the optimal separating subalphabet we want to build. For each pair of letters {a, b}, let x {a,b} be a binary variable that indicates whether both a and b belong to C (thus, x {a,b} = min(x {a} , x {b} )). We obtain the following ILP:

                     ∀a = b ∈ A, 2x {a,b} x {a} + x {b} (ensures that x {a,b} min(x {a} , x {b} )) ∀a = b ∈ A, x {a,b} + 1 x {a} + x {b} (ensures that x {a,b} min(x {a} , x {b} )) ∀v = v ′ ∈ L, S∈Sep(v,v ′ )
x S 1 (where S can denote a singleton or a pair)

minimise a∈A x {a}
The solution is thus C = {a ∈ A | x {a} = 1}. The inequalities of the second line are not necessary to ensure the validity and the optimality of the solution but they ensure that the values of the pair-variables are determined exactly by the values of the singleton-variables. Hence the number of degrees of freedom of the problem is linear in the cardinality of A and not quadratic.

Separation of walks from a given set of starting points to a given set of destinations

In the problem that we call total separation, we are given a set of potential starting points V I and a set of potential destinations V F . The set R of routes we want to separate is the set of all the routes leading from a vertex of V I to a vertex of V F . If the graph contains a cycle, there will be infinitely many such routes.

Of course, since the number of routes to separate can be infinite, it is not feasible to compute the separating set of each pair of routes. However, notice that the separating set of two routes is included in the powerset of the set A of arcs of the graph and can therefore only take a finite number of values. Thus, while the linear program presented in the previous section would have infinitely many constraints, only a finite number of them would be distinct. If we can determine which values of Sep(v, v ′ ) are actually reached, we would therefore be able to describe the same polytope with only a finite number of constraints.

Study of the reachable languages

We call a language L on an alphabet A reachable if and only if there exists a directed graph G = (V, A) (A is both the alphabet of L and the set of arcs of the graph), a set of vertices V I ⊆ V and a set of vertices V F ⊆ V such that L is the set of walks on G leading from a vertex of V I to a vertex of V F . Let Reach(A) denote the set of reachable languages on an alphabet A.

Lemma 3. If L ⊆ A * is reachable, then: ∀u, u ′ , v, v ′ ∈ A * , ∀a ∈ A, uav ∈ L u ′ av ′ ∈ L ⇒ uav ′ ∈ L u ′ av ∈ L
Proof. The idea of the proof is that since all the walks on the network are possible, the choices the walker has at a given time only depend on the current vertex and cannot be restricted depending on the route previously used. More formally, let G = (V, A) be a directed graph and let V I and V F ⊆ V be such that L is the set of walks leading from V I to V F . Let o a and t a be the origin and target of the arc a. If uav and u ′ av ′ are in a reachable language L, this means that:

• u describes a walk that leads from a vertex i ∈ V I to o a • u ′ describes a walk that leads from a vertex i ′ ∈ V I to o a • v describes a walk that leads from t a to a vertex f ∈ V f • v ′ describes a walk that leads from t a to a vertex f ′ ∈ V f
Hence, uav ′ and u ′ av also describe valid walks leading from a vertex of V I to a vertex of V F and therefore belong to L too.

Let Rat(A) denote the set of rational languages on an alphabet A. We have:

Proposition 4. Reach(A) Rat(A)
Proof.

• Reach(A) ⊆ Rat(A). Given an instance of total separation, one can easily construct an automata recognising the language of all possible routes between V I and V F on a directed graph G = (V, A); A is its alphabet, V is its set of states, T = {(u, (u, v), v) | (u, v) ∈ A} is its set of transitions, V I is its set of initial states and V F is its set of final states. By the theorem of Kleene [START_REF] Kleene | Representation of events in nerve nets and finite automata[END_REF], this proves that reachable languages are rational.

• Reach(A) = Rat(A). Note that the previous construction provides very specific automata: each letter of the alphabet labels at most one transition. There are rational languages that cannot be recognised by such automata. For example, let L be reachable and such that ababa ∈ L. Then, (ab)a(ba) ∈ L and εa(baba) ∈ L. Hence, according to Lemma 3, (ab)a(baba) and a(ba) both belong to L too. Hence, the language {ababa} although rational, is not reachable.

Restrictions of a rational language

We recall that rational languages are exactly those that can be described by regular expressions. We define a restriction of a rational language L and we denote by L the language built from a regular expression of L as follows.

• ∅ = ∅ • ∀a ∈ A * , {a} = {a} • for all rational languages L 1 and L 2 , L 1 + L 2 = L 1 + L 2 • for all rational languages L 1 and L 2 , L 1 L 2 = L 1 L 2 • for all rational language L, L * = ε + L + L 2 .
This notion will be useful for the reduction theorems (Theorem 6 and Theorem 11). Notice that the restriction of a language L is not unique. Indeed, two regular expressions can denote the same language but their associated restrictions can differ. For example,

L * * = L * but unless L = ∅, L * * = 4 i=0 L i = 2 i=0 L i = L * .
Proposition 5. Every restriction L of a rational language L is finite.

Proof. The proof by induction is immediate. Indeed, restricted languages are empty, singletons or built from other restricted languages using only finite unions or concatenations, which are operations that preserve the finiteness of the language.

Reduction theorem and resolution

Theorem 6 (Reduction Theorem). For all reachable languages L on an alphabet A, for all restrictions L of L, if A ′ ⊆ A separates L, then it separates L.

Proof. This theorem will be proved in a more general case in the next section (see Theorem 11).

Note that the converse is obviously true since L ⊆ L. Thus, the languages that separate L are exactly those that separate L.

Hence, given a directed graph, a set V I of potential starting points and a set V F of potential destinations, we proceed as follows to solve the traffic monitoring problem:

• we know that the language of possible routes leading from a vertex of V I to a vertex of V F is rational and therefore admits a regular expression. The graph directly provides an automata which recognises it and we can use Arden's lemma [START_REF] Arden | Delayed-logic and finite-state machines[END_REF] to find an expression of the associated reachable language that we want to separate.

• we use the regular expression of the language to determine a restriction. We know by Proposition 5 that this language is finite.

• we know by the reduction theorem that the solutions on the restricted language are exactly the solutions on the initial language. All that is left to do is use the method described in the previous section to solve the problem on the restricted language that is finite.

Separation of routes with forbidden transitions

Motivation and definition of the problem

Let us consider the following graph that depicts a very simple road: In this case, a driver who wants to go from vertex u to vertex x will simply use the path ace. Still, the model that we presented in the previous section requires us to distinguish all the routes of (a(c(ef ) * d) * b) * a(c(ef ) * d) * c(ef ) * e. Taking into account such paradoxical behaviours is not only superfluous but it also leads to prohibitive computation times and tremendously increases the cost of the solutions. Here, at least three sensors are required to distinguish all the roads leading from u to x while only one of those roads makes sense in practice.

One could be tempted to get around this problem by contracting the arcs a, c and e and the arcs b, d and f in a pre-processing step, which would result in a bi-directed path of length 1 and bring the language to separate down to (ab) * a. However, this is not possible on a more complex road network: indeed, a road network can for example feature crossroads on v and w and transversal roads could lead to those vertices or leave from them. While this does not change the fact that a driver who wants to go from u to x will always pick the route ace, it can make the contraction of the vertices v and w impossible and force us to consider many absurd walks.

The approach we choose here is to set up a new model where certain pair of edges, although adjacent, cannot be taken consecutively. A pair of edge ((u, v), (v, w)) where u, v and w are vertices is what we call a transition. We define a forbidden-transition graph (or FTG) as a triplet (V, A, F ) where V and A are the sets of vertices and arcs respectively and where F is a set of forbidden transitions. A permitted walk on a FTG is a walk that does not use consecutively two arcs a and b with (a, b) ∈ F . To avoid any ambiguity, in this section, we will refer to graphs (i.e. pairs (V, A) with no set of forbidden transitions) as "usual graphs".

For example, on the road network of Figure 3, we can assume that drivers will not make half-turn in the middle of the road and forbid the transitions ab, cd and ef . Thereby, we reduce the set of roads leading from u to x down to {ace}. This also enables us to model situations where certain turns are prohibited, which is very common on road networks. By choosing wisely the forbidden transitions, we only discard routes that would be prohibited or absurd in practice and we can significantly reduce the computation time and the cost of the optimal solutions on large instances.

Graphs with forbidden transitions or equivalent models have already appeared in the literature, see [START_REF] Fleischner | Compatible path-cycle-decompositions of plane graphs[END_REF] for one of the first examples. The complexity of finding paths or cycles with various properties has also received attention (see [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF], [START_REF] Mamadou | Finding paths in grids with forbidden transitions[END_REF] or [START_REF] Dvorak | Two-factors in orientated graphs with forbidden transitions[END_REF] for notable examples) as well as several closely related notions such as properly coloured paths (see [START_REF] Gutin | Properly coloured cycles and paths: Results and open problems[END_REF] for a survey).

Just like in the previous section, an instance of total separation on a FTG is given by a FTG (V, A, F ), a set V I of potential starting points and a set V F of potential destinations and the set of routes R we want to separate is the set of all the permitted routes leading from a vertex of V I to a vertex of V F .

Study of the FTG-reachable languages

As in Subsection 5.1, we call a language L a FTG-reachable language if and only if there exists an instance of total separation on a FTG where L depicts the set of routes to separate. We denote by FTGR(A) the set of FTG-reachable languages on an alphabet A.

Proposition 7. Reach(A) FTGR(A).

Proof.

• Reach(A) ⊆ FTGR(A). Since usual graphs are particular cases of FTGs (with F = ∅), the languages that are reachable with graphs are clearly reachable with FTGs.

• Reach(A) = FTGR(A). Let L be a reachable language on A = {a, b, c, d} such that ac, ad, bc ∈ L. Since both ac and ad are in L, we know that c and d denote arcs starting from the same vertex v and leading to a vertex of V F . Furthermore, since both ac and bc belong to the language, we know that a and b both denote arcs leading to v and starting from a vertex of V I . Hence, bd ∈ L too for every reachable language that contains ac, ad and bc.

Let us now consider the instance of traffic monitoring on the FTG obtained by forbidding the transition (b, d) on the graph given in Figure 4, with V I = {u, w} and V F = {w, x}. One can see that the associated FTG-reachable language contains ac, ad and bc since they describe permitted walks leading from a vertex of V I to a vertex of V F but not bd since it is forbidden. Hence, this FTG-reachable language is not reachable. It is important to note that Lemma 3 also holds for FTG-reachable languages: Lemma 8. For all FTG-reachable languages L ⊆ A * :

∀u, u ′ , v, v ′ ∈ A * , ∀a ∈ A, uav ∈ L u ′ av ′ ∈ L ⇒ uav ′ ∈ L u ′ av ∈ L Proof. Let G = (V, A, F ), V I , V
F be an instance of total separation on a FTG such that the set of routes to separate is L. Let us call L ′ the set of words that denote all the walks leading from a vertex of V I to a vertex of V F on the underlying usual graph G = (V, A) with no forbidden transitions. Hence, L ′ contains all the words of L plus eventually some words that contain transitions of F . Since L ′ is reachable by construction and {uav, u ′ av ′ } ∈ L ⊆ L ′ , we know by Lemma 3 that uav ′ and u ′ av belong to L ′ . Therefore, the only way for uav ′ or u ′ av not to belong to L ′ is to contain two consecutive letters that denote a forbidden transition. However, every sequence of two letters in uav ′ and u ′ av also appears in uav or u ′ av ′ which both belong to L. Thus, uav ′ and u ′ av are in L, which concludes the proof of the lemma.

Proposition 9. FTGR(A) Rat(A).

Proof.

• FTGR(A) ⊆ Rat(A). Let L be a FTG-reachable language and G = (V, A, F ), V I , V F be an instance of total separation on a FTG such that R = L. To prove that L is rational, we create from G an automata that recognises L. To do so we create copies of each vertex of the graph for each possible incidence. For example, if an arc (u, v) leads to a vertex v, instead of just having a state v in our automata, we create a state uv that is final if and only if v is final and from which we can reach any out-neighbour w of v unless ((u, v), (v, w)) ∈ F . More formally, here is a construction of an automata that recognises L:

its alphabet is the set A of arcs of the graph

-its set of states is V I ∪ {uv | (u, v) ∈ A}
for all v ∈ V I , for all out-neighbours w of v, we create a transition from v to vw labelled by the arc (v, w). For all states uv, for all out-neighbours w of v, we create a transition from uv to vw labelled by the arc (v, w) if and only if ((u, v), (v, w)) / ∈ F the set of initial states is still V I the final states are those whose name ends with a vertex v ∈ V F .

• FTGR(A) = Rat(A). The counter-example to the other inclusion is the same as in the proof of Proposition 4: the language ababa is rational but not FTG-reachable since it does not satisfy Lemma 8.

For example, with the graph in Figure 5, F = {(a, b), (c, d), (d, c), (f, e)}, V I = {v} and V F = {w}, the associated FTG-reachable language is recognised by the automata presented in Figure 6 whose initial and final states are respectively {v} and {vw, xw}. Initial and final states are denoted by incoming and outgoing dashed arrows respectively. Note in particular that since FTG-reachable languages are rational, they admit a regular expression and therefore, a restriction.

Reduction theorem and resolution

Irreducible walks in FTGs

In a usual graph, an elementary walk is a walk that does not use the same vertex more than once. Given an instance of traffic monitoring, we can define similarly an elementary word as a word that denotes an elementary walk. Note that with our definition, cycles are not elementary.

Elementary walks or words are exactly those that cannot be decomposed as a concatenation of three walks W 1 W 2 W 3 such that W 2 is non-empty and W 1 W 3 is also a walk on the graph. Indeed, such a decomposition is possible if and only if W 1 and W 2 end on the same vertex, which means that the walk is non-elementary. Therefore, by iterating the deletion of W 2 until the walk is elementary (which will happen within a finite number of iterations since the length of the walk strictly decreases), one can extract from every walk W an elementary walk W ′ with the same start point and end point as W and that uses only vertices and edges that W uses.

On the graph G depicted in Figure 7, one can see that the walk W = abcde is not elementary since it uses the vertex v twice. As explained previously, one can extract from W the walk W ′ = ae that still goes from u to y and uses only vertices and arcs that W uses but is elementary. However, note that W ′ uses a transition (here, (a, e)) that W does not use. If we now forbid the transition (a, e), the vertices u and y can still be connected but not by an elementary walk (which cannot happen in usual graphs) and the walk W , even though non-elementary, does not observe the characterisation of non-elementary walks that we gave in the previous paragraph. We define an irreducible walk in a FTG as a walk that cannot be decomposed as a concatenation of three walks W 1 W 2 W 3 such that W 2 is non-empty and W 1 W 3 is a permitted walk on the graph. Hence, the walk abcde in Figure 7 is irreducible. As before, by iterating the deletion of W 2 , one can extract from any permitted walk W on a FTG an irreducible walk W ′ with same starting and endpoint as W and that uses only vertices or edges that W uses. We call such a walk W ′ a reduced form of W . Note that unlike in usual graphs, the reduced form of a walk in a FTG is not necessarily unique. Similarly, we can define irreducible walks with respect to some additional constraints. For example, if W X is a walk, we can define W ′ as a form of W which is as reduced as possible such that W ′ X is still permitted. Hence, W ′ would not necessarily be irreducible but we know for sure that we could not iterate the decomposition and the deletion of W 2 without making a forbidden transition appear when we concatenate W ′ and X.

Preliminary results

Lemma 10. For all rational languages L, for all restrictions L of L and for all words u ∈ L\L, there exists words v, w 1 , w 2 , w 3 and x such that u = vw 1 w 2 w 3 x, w 1 , w 2 and w 3 are all nonempty and u still belongs to L if we remove one or several of the w i .

Proof. We prove the lemma by induction on a regular expression describing the language L:

• if L = ∅, L \ L = ∅ and the lemma holds on L (universal property on an empty set).

• if L = {u} with u ∈ A * , L \ L = ∅ and the lemma holds.

• if L = L 1 + L 2 and the lemma holds for L 1 and L 2 :

L \ L = (L 1 + L 2 ) \ (L 1 + L 2 ) ⊆ (L 1 \ L 1 ) + (L 2 \ L 2
) and the lemma holds for L.

• if L = L 1 L 2 and the lemma holds for L 1 and L 2 : let u ∈ L 1 and v ∈ L 2 and let us observe that for uv not to belong to

L 1 L 2 , it is necessary that u / ∈ L 1 or v / ∈ L 2 . Hence, L \ L ⊆ (L 1 \ L 1 )L2 + L1(L 2 \ L 2
) and the lemma still holds for L.

• if L = L ′ * and the lemma holds for L ′ : we set M = L ′ \ {ε}. Note that L ′ * = M * . We also set Hence, even if we remove some of the w, u is still a concatenation of words of M and therefore still belongs to M * = L.

M = L ′ -ε. L \ L = i∈N L ′i \ 2 i=0 L ′ i = i∈N M i \ 2 i=0 M i ⊆ 2 i=0 (M i \ M i ) + i 3 M i ⊆ ∅ + (M \ M ) + M 2 \ M
This proves the lemma.

The reduction theorem

Even though reachable languages are strictly included in FTG-reachable languages, the reduction theorem still holds: Theorem 11. For all FTG-reachable languages L on an alphabet A, for all restrictions L of L, if A ′ ⊂ A separates L, then it separates L.

Proof. Let L ⊆ A * be a FTG-reachable language, let A ′ ⊆ A and u, v ∈ L be such that u

= v but p A ′ (u) = p A ′ (v) = a 0 • • • a n . Thus, u = u 0 a 0 u 1 a 1 • • • a n u n+1 and v = v 0 a 0 v 1 a 1 • • • a n v n+1
where for all i, u i and v i belong to (A \ A ′ ) * . We want to prove that for all restriction L of L, there exist two different words in L that have the same signature.

Since u = v, we know that there exists i such that u i = v i . Moreover, since L is FTGreachable, by using Lemma 8 twice, we find that u 0 a 0

• • • u i-1 a i-1 v i a i u i+1 • • • u n+1 =y still belongs
to L. To keep the notation as simple as possible, we set y = a i u i+1 • • • u n+1 .

Let x be the longest common prefix of u i and v i . Hence, u i = xbu ′ i and v i = xcv ′ i where b and c ∈ (A \ A ′ ) ∪ {ε} are the first letters of the suffix after x (or ε if it is empty). Thus, b = c and b or c is empty if and only if x = u i or x = v i respectively (hence, if b = ε then u ′ i = ε too and the same holds for c and v ′ i ). We also set z = u 0 a 0 • • • u i-1 a i-1 x. Thus, u = zbu ′ i y and we know that zcv ′ i y ∈ L too.

Let red(z) be a form of z which is as reduced as possible such that both red(z)b and red(z)c are permitted (we iterate the reduction as long as it is possible). Similarly, let red(u ′ i ) and red(v ′ i ) be forms of u ′ i and v ′ i which are as reduced as possible such that b red(u ′ i ) and c red(v ′ i ) are permitted and let red(y) be a form of y which is as reduced as possible such that u = red(z)b red(u ′ i ) red(y) and v = red(z)c red(v ′ i ) red(y) are both permitted. Since u and v are permitted and have same origin and destination as u, they still belong in L.

First case: both u and v belong to every restriction L of L. We know that b red(u ′ i ) and c red(v ′ i ) cannot both be empty. If one of them is, they are thus necessarily distinct and if none of them are, we know that b and c denote different letters. In all cases, b red(u

′ i ) = c red(v ′ i ) and thus, u = v.
By definition, a reduced form of a word only uses letters that the word itself uses. Since u i and v

i ∈ A \ A ′ , we know that b red(u ′ i ) and c red(v ′ i ) ∈ (A \ A ′ ) * . Hence, p A ′ (u) = p A ′ (red(z)) p A ′ (b red(u ′ i )) =ε p A ′ (red(y)) = p A ′ (red(z)) p A ′ (c red(v ′ i )) =ε p A ′ (red(y)) = p A ′ (v)
Second case: at least one of u and v, say u does not belong to a restriction L of L. Hence, by Lemma 10, we know that u = sw 1 w 2 w 3 t where w 1 , w 2 and w 3 are all non-empty and can be removed. We recall that u can also be written red(z)b red(u ′ i ) red(y). By definition, red(z) is a form of z which is as reduced as possible such that red(z)b and red(z)c are both permitted. This notably means that any reduction on z would change its last letter since it changes the letter we can write after it. Hence, a removable factor of red(z) is necessarily a suffix. Since we know by Lemma 10 that we can remove w 1 without making forbidden transitions appear, this proves in particular that w 1 cannot end strictly before red(z). Similarly, we can prove that a removable factor of red(y) is necessarily a prefix and therefore, that w 3 cannot begin strictly after red(y). Hence, we know that w 2 is a factor of b red(u ′ i ). By definition of red(u ′ i ), we know that it does not contain any factor we can remove without making a forbidden transition appear with b. Therefore, since w 2 is removable and a factor of b red(u ′ i ), it has to contain b. Putting it all together, we find out that w 2 is a prefix of b red(u ′ i ), which means that w 1 is a suffix of red(z) and since w 1 is non-empty, that s is a strict prefix of red(z). Since w 3 is removable and red(u ′ i ) cannot contain a removable factor, we know that w 3 is the concatenation of a suffix of red(u ′ i ) and a non-empty prefix of red(y). Finally, we know that t is a strict suffix of red(y). Let red(w 2 ) be a form of w 2 which is as reduced as possible such that red(w 2 ) is nonempty (possible since w 2 is non-empty itself) and s red(w 2 )t still denotes a permitted walk. By Lemma 10 on u = sw 1 w 2 w 3 t, we know that st and sw 2 t both belong to L and therefore, that s red(w 2 )t ∈ L too.

• By definition, red(w 2 ) is non-empty so st = s red(w 2 )t.

• Since red(w 2 ) uses only letters that w 2 uses and w 2 is a factor of b red(u ′ i ) ∈ (A \ A ′ ) * , it has an empty signature and therefore, p A ′ (st) = p A ′ (s red(w 2 )t).

• By definition, red(w 2 ) cannot contain a removable factor of s red(w 2 )t unless it is removable itself. We also know that a removable factor of red(z) is necessarily a suffix and that s is a strict prefix of red(z), which means that s does not contain a removable factor. Finally, we know that a removable factor of red(y) is necessarily a prefix and since t is a strict suffix of red(y), it cannot contain one. This means that s red(w 2 )t can contain at most two disjoint removable factors (one starting in s and finishing in w 2 and one starting in w 2 and finishing in t). Similarly, st can contain at most one removable factor. By Lemma 10, this means that st and s red(w 2 )t belong to every reduction L of L.

We proved that for all FTG-reachable languages L on an alphabet A, for all subalphabets A ′ ⊆ A, if there exist u = v in L such that p A ′ (u) = p A ′ (v), then there also exist two words in every restriction L of L that are different but still have the same projection on A ′ . The contrapositive of this result is our theorem.

Hence, the method we described at the end of Section 5 to solve the total separation problem on usual graphs also applies for FTGs: given an instance of FTG-reachable separation, we use the construction described in the proof of Proposition 9 to build an automata that recognises the associated language, we determine a regular expression of this language, restrict it and use the tools developed in Section 4 to solve the problem on the resulting language that is finite.

Finally, let us note that while the reduction theorem holds for reachable languages and even for the more general class of FTG-reachable languages, it does not hold for rational languages in general. For example, let L = (ab) * + ababa be a rational language (which is neither FTGreachable nor reachable, we proved in the proof of Proposition 4 that a language that contains ababa and that observes Lemma 3 has to contain aba and abababa too which is not the case here). A restriction of L is L = ε + ab + abab + ababa. One can see that the alphabet A ′ = {a} separates L while ababa and ababab, that both belong to L, have the same image under p {a} .

Conclusion

We studied the problem of traffic monitoring from the point of view of separating codes. To overcome the limitations of this approach (as mentioned in Subsection 2.2), we introduced a new model of separation based on language and addressed the traffic monitoring with tools stemming from language theory. The problem of separation on a language being NP-complete in the size of the language, we outlined three subproblems relevant in practice, namely finite, total and FTG-reachable separations, and we designed algorithms to solve each of these subproblems, even if the set of routes to separate is infinite. The strength and flexibility of our model enabled us to address the case of cyclic graphs, infinite sets of roads to separate and even to impose additional constraints on the sets we separate such as avoiding certain transitions. The expressiveness of our new model of separation on a language and the limitations it overcomes also offer hope that it could be of help in a much wider range of applications than traffic monitoring alone.

Of course, this study also opens the door to many possibilities for improvement. In our opinion, the two most important ones are a deeper understanding of the ILP our reduction leads to and the study of divide-and-conquer algorithms. Other possibilities for further work include the investigation of subproblems other than finite or total separations on graphs or forbidden-transition graphs that could be more suitable for some practical applications.

Figure 1 :

 1 Figure 1: A basic example of a graph.

Figure 2 :

 2 Figure 2: An example of network G. The arcs (1,2) and (5,1) are equipped with sensors called respectively a and b.

  Hence, p C (u) and p C (v) are two words on C whose projections on every subalphabet C ′ of C are identical and therefore, by Lemma 1, p C (u) = p C (v) which means that C does not separate u and v.

Figure 3 :

 3 Figure 3: An instance of traffic monitoring.

Figure 4 :

 4 Figure 4: An example of FTG.

Figure 5 :Figure 6 :

 56 Figure 5: An instance of total separation on a FTG.

Figure 7 :

 7 Figure 7: The graph G.

2 =M

 2 (M \M )+(M \M )M +M 3 M * Since the lemma holds for all words of M \ M = L ′ \ L ′ , it holds for all words of M \M +M 2 \M 2 . Let us now prove it for u ∈ M 3 M * . By definition, u is the concatenation of v = ε, w 1 , w 2 and w 3 ∈ M (which are non-empty by construction of M ) and x ∈ M * .

Figure 8 :

 8 Figure 8: The two decompositions of u.

This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02).

Acknowledgements

I would like to thank my thesis advisor Arnaud Pêcher for his invaluable guidance for the writing of this paper and throughout the research that led to it as well as Feiran Yang and Stefan Bard for their assistance in the proofreading.