Senior Member, IEEE Andrea Cozza

Member, IEEE Florian Monsef

On the Influence of Medium Statistics on the Robustness of Time-Reversal Transmissions

Keywords: Time-reversal transmissions, complex media, perturbation analysis

The problem of predicting the performance of Time-Reversal Transmissions (TRT) in a time-varying complex medium is addressed in this paper. The loss of coherence in the propagation medium and its nominal energy contrast are proven sufficient to predict the average loss of quality in received signals.

In particular, it is shown how a perturbation in the medium affects in a different way coherent focusing and background fluctuations. In the extreme case of a diffusive medium (e.g., Rayleigh channels), the fluctuations intensity is unaltered. The predictions of the proposed theoretical models are validated against experimental results measured in a reverberation chamber, where a mechanical paddle (stirrer) acts as the source of perturbation in the medium. It is confirmed that, depending on the medium statistics, perturbations can have a varying impact on TRT performance.

I. INTRODUCTION

Waves propagating through complex media are subjected to a potentially large number of scattering events, generating multiple propagation paths and ultimately leading to phenomena like time-spreading of pulses and frequency selectivity, making signal transmissions less predictable and reliable.

Time-reversal transmissions (TRT) have been studied in the last few years as a potential solution to counter these effects, by providing the best replica of a target signal at the receiver, while at the same time focusing a substantial portion of the energy around it [START_REF] Derode | Taking advantage of multiple scattering to communicate with timereversal antennas[END_REF], [START_REF] Qiu | Time reversal with MISO for ultrawideband communications: Experimental results[END_REF]. Most applications are based on a direct implementation of standard time reversal as described in [START_REF] Fink | Time reversal of ultrasonic fields. I. Basic principles[END_REF]. In short, in order to have a received signal as close as possible to a target signal p(t), the transmitted signal has a Fourier spectrum of the kind P (ν)H * (ν)M (ν), where ν is the frequency variable and H(ν) is the transfer function between the transmitter and the receiver. M (ν) is a weighting function that represents the effects of equalization and compensation schemes that have been used for improving TRT [START_REF] Song | Improvement of time-reversal communications using adaptive channel equalizers[END_REF].

The main weakness of TRT is that even in collaborative configurations, where it makes sense to assume H(ν) to be known, propagation media may change over time. As a matter of fact, real-life propagation scenarios are hardly static, as they often involve moving people/vehicles, and also receiving and transmitting antennas can change position/orientation, e.g., when hand-held mobile terminals are used. Time-varying propagation can be taken into account, by periodically sounding the Part of the work here reported was funded by the French National Research Agency through the grant ANR-12-ASTR-0005, MIMOCHIC project, within the framework of the 2012 ASTRID program.

A. Cozza and F. Monsef are with PIEM, GeePs (UMR 8507), 11 rue Joliot-Curie, 91192 Gif-sur-Yvette, France. Contact e-mail: andrea.cozza@ieee.org. medium response and transfer functions, but this can clearly be done only at discrete times. In between them, TRT risk using signals that no longer represent an accurate description of the medium, resulting in a loss of coherence and ultimately a reduced performance. This problem has been addressed in a few papers, mostly empirically and essentially with the aim of assessing what degree of perturbation would still provide an acceptable performance [START_REF] Tourin | Sensitivity to perturbations of a time-reversed acoustic wave in a multiple scattering medium[END_REF]- [START_REF] Yavuz | On the sensitivity of time-reversal imaging techniques to model perturbations[END_REF]. In diffusive media, such as large cavities, indoor propagation and heavily built urban structures, TRT can be so sensitive that it has been proposed for detecting perturbations in the first place [START_REF] Taddese | Sensing small changes in a wave chaotic scattering system[END_REF].

A case therefore exists to understand under what conditions TRT are more of less sensitive to perturbations. This paper brings some insight into this issue, by demonstrating how the statistical behavior of a medium results into a different sensitivity to perturbations. The predictions of the proposed models are validated against experimental results, confirming their accuracy.

II. RESIDUAL FLUCTUATIONS AND CONTRAST

Signals received with TRT in static media can be expressed as

y(t) = BT dν P (ν)|H(ν)| 2 e j2πνt (1)
where H(ν) is the transfer function between the transmitting antenna and the receiver and B T is the bandwidth over which the spectrum P (ν) of the target signal p(t) is defined. For any medium significantly different from free space, H(ν) would not be a monotonous function of frequency, presenting minima or even nulls over certain frequencies due to reflections and in general interactions with boundary elements. Modelling H(ν) as a random process, fluctuations in y(t) appear as the result of deviations from line-of-sight transmissions. The effectiveness of TRT can be measured by first separating the received signal y(t) as done in [START_REF] Cozza | Multiple-source time-reversal transmissions in random media[END_REF]

y(t) = αp(t) + f (t), (2)
i.e., as made up of a coherent portion proportional to p(t) and residual fluctuations f (t). Projecting the received signal onto the target one yields

α = Y (ν), P (ν) = BT dν Y (ν)P * (ν), (3)
choosing p(t) to have unit energy, here meant as for a mathematical signal, i.e., the square of its L 2 norm. A direct consequence of ( 2) is the orthogonality of f (t) and p(t).

A natural metric is therefore the energy contrast Λ [START_REF] Cozza | Multiple-source time-reversal transmissions in random media[END_REF], which measures the ratio between the energy E c = α 2 of the portion of received signal proportional to the target p(t) and that of the background fluctuations, E f , i.e.,

Λ = E c /E f . (4)
Sec. III is entirely based on this metric, which strongly simplifies the analysis. For a diffusive medium, it was shown [START_REF] Cozza | Multiple-source time-reversal transmissions in random media[END_REF] that its ensemble average Λ ≤ 1, with the extreme case attained only in the case of a Rayleigh or diffusive medium. Introducing the TRT function [START_REF] Cozza | Multiple-source time-reversal transmissions in random media[END_REF] demonstrated that the second-order statistics of W (ν) provide a direct estimate of the energy contrast as Λ = ς -2 W , where ς is the standard deviation of W (ν) normalized to its mean. This relationship is useful as it gives a straightforward understanding of the performance of TRT as a function of the medium statistics and complexity. Nevertheless, it only holds for the average behavior of a medium, so that Λ can exceed the value one on a local basis, as observed in Sec. IV.

W (ν) = |H(ν)| 2 ,
Once the energy contrast is known, it can be translated into a peak contrast, measuring the ratio of the peak of coherent focusing and the rms amplitude of the background fluctuations [START_REF] Cozza | Multiple-source time-reversal transmissions in random media[END_REF].

III. EFFECTS OF PERTURBATIONS ON TRT

We consider a nominal transfer function H o (ν) for the unperturbed medium and H(ν) the one found at the time of transmission, after the perturbation event has occurred; in general, all quantities referring to the unperturbed medium will display a subscript nought. It is convenient to express the modified transfer function as a linear combination of the original function plus a random process δH(ν) modelling the effect of the perturbation, i.e.,

H(ν) = ρH o (ν) + δH(ν), (5)
with ρ the linear correlation coefficient between the original and modified functions. By definition, δH(ν) is orthogonal to H o (ν), i.e., their projection

δH(ν), H o (ν) = BT dν δH(ν)H * o (ν) = 0. ( 6
)
The perturbation is assumed not to affect the statistical moments of field-related quantities, but only their specific random realizations. This assumption makes sense when the perturbation does not change either the complexity of the medium or the overall rate of energy dissipated. Under this assumption, introducing the average energy of H(ν), in the sense of squared L 2 norms, i.e., defined as the

E H = BT dν |H(ν)| 2 , (7)
with • the expected value, it is straightforward to prove that

E δH = (1 -ρ 2 )E Ho , (8)
by enforcing the condition

E H = E Ho (9)
and ( 6). In case of no perturbation, the Fourier spectrum of the received signal is

Y o (ν) = |H o (ν)| 2 P (ν), (10)
while, after a perturbation occurs, one would obtain

Y (ν) = H(ν)H * o (ν)P (ν), (11)
yielding, after [START_REF] Tourin | Sensitivity to perturbations of a time-reversed acoustic wave in a multiple scattering medium[END_REF],

Y (ν) = ρ|H o (ν)| 2 P (ν) + δH(ν)H * o (ν)P (ν). (12)
The degradation in the energy contrast in case of a perturbation is naturally measured by the ratio Λ/Λ o , for which we need to compute the new energies for the coherent part of the received signal and the background fluctuations. The coherent energy E c associated to the coherent portion of the received signal, Y c = ρ|H o (ν)| 2 P (ν), after the perturbation has occurred is given by

E c = ρ 2 E c,o , (13)
by recalling ( 5), ( 6) and using the approximation (19) discussed in the Appendix. The average energy of the background fluctuations in the perturbed case reads

E f = BT dν |Y (ν) -Y c (ν)| 2 , (14)
which can be simplified, thanks to (19), into

E f = ρ 2 E f,o + BT dν |δH(ν)| 2 |H o (ν)| 2 . ( 15
)
Following ( 8),

E f = ρ 2 E f,o + (1 -ρ 2 )E c,o , (16)
so that

E f /E f,o = ρ 2 (1 -Λ o ) + Λ o . (17)
Eq. ( 17) implies that the level of fluctuations in signals received in the perturbed medium should not be expected to be the same experienced in the nominal configuration. Fig. 1 shows a contour-level plot of (17); it should be noticed how, for any Λ o = 1, perturbing the medium could either lead to weaker or stronger fluctuations, for a same loss of coherence ρ. Still, even in the case of a reduction in the fluctuations for Λ o < 1, the contrast systematically reduces after a perturbation, as found by combining ( 13) and ( 17)

Λ/Λ o = 1 + 1 ρ 2 -1 Λ o -1 . (18)
Fig. 2 shows how the above ratio depends on the nominal energy contrast and ρ. According to (17), the dependence on Λ o is purely due to the changing intensity of background fluctuations, since the received coherent energy is not expected to depend on Λ o . .

IV. EXPERIMENTAL VALIDATION

In order to validate the implications of our models, access to a medium capable of supporting different field statistics is needed. A reverberation chamber is the ideal facility for these tests since, depending on the degree of overlapping in the frequency responses of its resonant modes, it can support field propagations with a varying Λ o . Different values of modal overlapping, and as a consequence Λ o , can be accessed by changing frequency, as demonstrated in [START_REF] Cozza | The Role of Losses in the Definition of the Overmoded Condition for Reverberation Chambers and Their Statistics[END_REF], [START_REF] Monsef | Average number of significant modes excited in a mode-stirred reverberation chamber[END_REF].

Moreover, reverberation chambers are routinely equipped with at least one metallic paddle acting as a field stirrer, which is a practical way of perturbing the medium in a controllable and reproducible way. But stirrers are usually designed and operated in order to (ideally) generate independent random realizations when rotated. This would lead to only two values of ρ, either 0 or 1. We rather need to define rotation steps of the stirrer in order to evenly sample the entire range of values taken by ρ. As a result, the very small rotation steps used in our experiments should not come as a surprise.

Two monocone antennas were fitted as receiver and transmitter in one of CentraleSupelec's chambers, a cuboid of dimensions 6 × 3.5 × 2.5 m 3 . They were positioned on either side of the stirrer, in order to reduce the incidence of line-ofsight paths, so that modifications in the stirrer position would have an impact on the maximum number of propagation paths within the chamber.

The transfer function between the two antennas was measured with a vector network analyzer from Rohde & Schwarz, model ZVB8, operated between 200 MHz and 700 MHz; the transfer functions were sampled with 40 kHz steps. This 1.3

ρ 2 E f /E f,o
Fig. 3: Comparison between experimental (circles) and theoretical (dashed lines) relationships for the effect of a perturbation in a medium and the energy of the fluctuations at the receiver, for Λ o equal to 0.32 (red), 0.67 (black) and 1.32 (blue).

ρ 2 E c /E c,o
Fig. 4: As in Fig. 3, but here studying the modifications in the coherent energy at the receiver. approach allows a sufficiently fine frequency step, in order to avoid any aliasing in the relatively long impulse responses of the chamber, around 4 µs.

The values of Λ o that the setup can produce were assessed from the transfer functions H(ν), as explained in [START_REF] Cozza | Multiple-source time-reversal transmissions in random media[END_REF], by estimating the normalized variance of W (ν) = |H(ν)| 2 . Three central frequencies were picked as noteworthy, 300, 510 and 695 MHz, where the chamber behaves in a distinctly different way. A bandwidth B T = 30 MHz was chosen for the excitation around each frequency, as a compromise between spectral resolution and statistical uncertainty. For these choices, Λ o was found to be equal to 0.32, 0.67 and 1.32, respectively, for the three central frequencies. These values correspond to the stirrer parked at its original position, in static conditions.

The stirrer was then put in motion by 1-degree steps. For each step, the new transfer function was measured, and the procedure repeated 14 times. For each frequency the linear correlation between the original transfer function and the Λ/Λ o Fig. 5: As in Fig. 3, but here studying the modifications in the energy contrast at the receiver. perturbed ones was computed, together with the resulting modification in energy contrast, coherent and backgroundfluctuation energy at the receiver. Notice that these quantities were computed by directly observing the received signals; no approximation was considered here. These results are shown in Figs. 3, 4 and 5 and compared to the theoretical models derived before.

The models appear to be accurate, as they correctly predict the strong dependence of the background-fluctuation energy on different values of the static Λ o , with relative errors smaller than 20 %. Also, the coherent energy at the receiver is also confirmed to be practically insensitive to Λ o and proportional to ρ 2 . It is therefore confirmed that the main reason for a varying robustness is the changing level of background fluctuations.

Residual errors are likely due to the use of a finite bandwidth B T , resulting in an uncertain estimate of energy averages, which are assumed to be perfect in the model derivation. Another source of errors is the assumption of perfect homogeneity in the transfer functions of the medium as they change over time; in practice, local deviations may occur and thus infringe the assumption on which our models are based.

V. CONCLUSIONS

Simple theoretical models derived in this paper predict accurately how perturbations in the transfer functions of a complex medium affect TRT. The main result is the strong sensitivity of the intensity of background fluctuations to the statistics of the unperturbed medium; the coherent energy at the receiver is on the contrary unaffected by the medium statistics and directly controlled by the level of perturbation of the medium.

The accuracy of these models implies that knowing secondorder statistics of a medium TRT transfer functions and its level of potential loss of coherence are sufficient to predict the degradation in TRT schemes and related applications, e.g., imaging of moving targets or changing media.

APPENDIX

This appendix proves that given a random process G(ν) and a piece-wise smooth spectrum P (ν) of mathematical energy E p , the following approximation holds (20)

Each integral acts as an estimator of the ensemble average of G(ν i ), since B i spans a multitude of independent realizations, thus the first approximation in (19). In case of an average independent from frequency, the second approximation in ( 19) is obtained and associated to the central frequency ν c

Fig. 1 :

 1 Fig. 1: E f /E f,o as a function of ρ and Λ o .

Fig. 2 :

 2 Fig. 2: Λ/Λ o as a function of ρ and Λ o .

  BT dν G(ν)|P (ν)| 2 ≃ BT dν G(ν) |P (ν)| 2 ≃ G(ν c ) E P , (19) as long as the coherence bandwidth B G c of G(ν) is much smaller than that of |P (ν)| 2 , B P c .The integral can be computed over a sequence of N contiguous frequency bands B i centered at ν i , covering the entire B T , chosen such thatB P c > B i ≫ B G c . In this way, |P (ν i )| 2 can be approximated as a constant over each B i BT dν G(ν)|P (ν)| 2 ≃ N i=1 |P (ν i )| 2 Bi dν G(ν).


Stochastic fluid structure interaction of three dimensional plates facing a uniform flow

An experiment of a flat rectangular plate facing a uniform flow at Re= 264000 shows the importance on the base pressure loading of the asymmetric static modes of the turbulent wake. The plate is free to rotate around its small symmetry axis. For plates with aspect ratio κ < 6, the angular position exhibits strong random discontinuities between steady states of non zero angles. The steady states have long time durations, more than one order of magnitude larger than the convective timescale. The discontinuities, comparable to rare and violent events are due to strong fluid forces associated with the drastic global change of the three dimensional wake, mainly the switching between the static asymmetric modes. A clear transition occurs at κ = 6 for which the angular fluctuations are minimum leading for κ > 6 to a classical fluid structure interaction with periodic fluctuations. The transition is supported by a recent global stability analysis of rectangular fixed plates in the laminar regime.

Introduction

It is known that for three dimensional bodies, the first bifurcation in the flow solution as the Reynolds number is increased leads to steady symmetry breaking modes. This has been demonstrated for axisymmetric bodies [START_REF] Fabre | Bifurcations and symmetry breaking in the wake of axisymmetric bodies[END_REF][START_REF] Pier | Local and global instabilities in the wake of a sphere[END_REF][START_REF] Bohorquez | Stability and dynamics of the laminar wake past a slender blunt-based axisymmetric body[END_REF]) and for bodies having rectangular blunt base [START_REF] Grandemange | Reflectional symmetry breaking of the separated flow over three-dimensional bluff bodies[END_REF][START_REF] Marquet | Global wake instabilities of low aspect-ratio flat-plates[END_REF]. At low Reynolds number, these steady modes play an important role in problems of fluid structure interaction, such as for instance the dynamics of falling bodies [START_REF] Ern | Wake-Induced Oscillatory Paths of Bodies Freely Rising or Falling in Fluids[END_REF]. Recently, steady symmetry breaking modes have been evidenced at large Reynolds numbers, leading to random multistable dynamics. For bodies having a reflectional symmetry such as the Ahmed body, [START_REF] Grandemange | Turbulent wake past a three-dimensional blunt body. Part 1. Global modes and bi-stability[END_REF] have shown that the wake is bistable with a long time dynamics of random switching between two mirror symmetry breaking modes. These observations have been generalized to axisymmetric geometries by [START_REF] Rigas | Low-dimensional dynamics of a turbulent axisymmetric wake[END_REF] and [START_REF] Grandemange | Statistical axisymmetry of the turbulent sphere wake[END_REF], where the only two asymmetric states are replaced by an infinite number of asymmetric states due to the multiplicity of reflectional symmetries of the axisymmetric geometry.

As shown by [START_REF] Marquet | Global wake instabilities of low aspect-ratio flat-plates[END_REF], simple rectangular plates are subjected to these steady symmetry breaking modes in the laminar regime and one may wonder how they can interfere in the case of fluid structure interaction at large Reynolds numbers. The purpose of this work is to study the consequence of such static symmetry breaking modes dynamics on a very simple fluid structure interaction experiment involving a three dimensional turbulent wake.

The paper is organized as follows. Section 2 describes the flat plate geometry and the measurements. Results in Sec. presence of the static symmetry breaking modes for a fixed plate. The fluid structure interaction mechanism is then investigated in Sec. 3.2. The effect of the plate aspect ratio on the plate dynamics is studied in Sec. 3.3. Results are discussed with concluding remarks and perspectives in Sec. 4.

Experimental set-up

The mechanical system is a simple plate that rotates freely around its small reflectional symmetry axis as depicted in Fig. 1. The plate is made of plexiglass, its thickness L is 6 mm, the height H is 48 mm. The plate dimension accuracy is about 0.05 mm. Aspect ratios κ = H W ranging from 1 to 8 are investigated with plates of different widths W . The plates are pierced with a hole of 4.2 mm in diameter at the position H/2. The position of the hole is only accurate to 0.2 mm because it required a change of the machine tool. A rod (the axis of rotation), with a diameter of 4 mm made of brass and lubricated with silicon oil is passed through the hole. The plate is then free to rotate around a fixed axis. Two teflon annuli avoid the plate to slide along the rod. We denote θ, the angle between the plate and the vertical unit vector e y , taken as positive in the clockwise direction.

The friction torque per unit of lenght γ S (such that the total friction torque is Γ S = γ S W ) is estimated for all the plates in air. The angular velocity decay Ω(t) of the free rotating plate is measured as shown in Fig. 1(c). In that case, I dΩ dt = γ S W , where the plate inertia is I = ρ p H 3 12 W L, and the plate density ρ p = 1080 kg/m 3 . For all the plates, the velocity decrease becomes linear for Ω < 100 rad/s (the typical angular velocity never exceeds 20 rad/s in the following experiments). We find (see Fig. 1c, inlet), that γ S -4 × 10 -3 N for all plates.

The dynamical system is placed in a hydrodynamic tunnel of cross section 150×80 mm. The test section is 800 mm long and completely transparent. The fluid is water (ρ = 1000 kg/m 3 ). The main flow velocity is set to U 0 = 5.5 m s -1 , such that the Reynolds number defined as Re= U0H ν = 264000. There is no cavitation in the flow except during visualizations for which the pressure in the tunnel is reduced to produce enough bubbles to seed the wake.

To determine the importance of the friction on the plate dynamics in the uniform water flow, it is convenient to estimate the hydrodynamic torque γ from that of an oblique 2-dimensional flat plate using the inviscid wake model [START_REF] Wu | A free streamline theory for two-dimensional fully cavitated hydrofoils[END_REF]). The theory gives γ = -(θ)F N (θ), where (θ)

1.8 7π Hθ is the distance from the axis of rotation to the application point of the normal force F N (θ) = 1 2 ρU 2 0 H 2π cos θ 4+π cos θ (1 + σ) as sketched in Fig. 2(a). For small angular deviations

γ(θ) - π 4 + π ρU 2 0 H(1 + σ) (θ) = -C(1 + σ)θ, (2.1)
thus defining a hydrodynamic stiffness C = 88 × 10 -3 N/ • taking the cavity number (i.e. base suction) σ = 0 which corresponds to the Helmholtz wake that minimizes the normal force. At an inclination of 1 • , the hydrodynamic torque γ is one order of magnitude larger than the friction torque γ S , friction is then negligible for angular positions θ > 1 • . A Pegasus dual pulse 8 mJ Nd:YLF laser and a camera Photron APX RS with a resolution of 1024 × 1024 pixels are employed for Particle Image Velocimetry (PIV) measurements using the Lavision software. The setup acquires image pairs at a rate of f acq = 60 Hz, corresponding to the dimensionless frequency f * acq = f acq H U0 = 0.52. Conventional notations for the velocity components will be used, say (u, v, w) in the coordinate system ( e x , e y , e z ). The measurements area of the velocity field (plane z = 0 that gives access to u and v) is displayed in Fig. 1(b). The thickness of the laser light sheet is about 3 mm. The interrogation window size is 32×32 pixels with an overlap of 50%. The window corresponds to physical sizes of 3.6 × 3.6 mm. For simultaneous measurements with the plate angle, θ is deduced from the acquired frames. The resolution is then limited by the pixel density of the camera to ∆θ = ±0.15 • , and the sampling frequency of the angle is also 60 Hz. For the flow visualizations, the shutter of the camera is set to f acq = 60 Hz and the repetition rate of the laser to 2 kHz. As a result, bubble trajectories reveal the flow structure over a non dimensional duration of dt * = 1/f * acq = 1.91. For accurate measurements of the angle, a high speed and high precision optical Keyence micrometer (LS-7070M) constituted by a transmission unit which emits light and a receiving unit which detects the position of the shadow of the targeting object is used (see Fig. 1a). The micrometer has an accuracy of ±3 µm and a sampling frequency of 2000 Hz. In our case, it detects the horizontal position of the superior edge of the plate facing the flow as indicated by the δ position in Fig. 1(b). The estimated accuracy for the angle measurements is ∆θ = ±0.01 • .

Results

For the remainder of the paper, a * denotes the non-dimensional value of any quantity a(x, y, z, t) made dimensionless by a combination of the height H of the plate and the inlet velocity U 0 . Time in non dimensional units is thus defined as t * = tU 0 /H. We first study the flow dynamics of the fixed plate using the flow visualization. The striking result is the observation for a plate angle θ = 0 of an intermittency between two quasi-permanent asymmetric recirculations as displayed in Fig. 3(a,b). Their lifetime is random and can be as long as a few seconds, say few hundreds in terms of H U0 units. In Fig. 3(a) a circular anticlockwise recirculation is clearly visible on the upper part of the plate base, we will call this flow structure the N state of the wake. Fig. 3(b) is a mirror symmetry of Fig. 3(a), with a circular clockwise recirculation on the lower part of the base plate, it will be called the P state. The letter P for positive or N for negative refers to the sign of the vertical pressure gradient at the plate base following the same terminology as in [START_REF] Grandemange | Turbulent wake past a three-dimensional blunt body. Part 1. Global modes and bi-stability[END_REF]. The sign can be guessed from the visualization because the circular recirculation is a source of low pressure, it will be confirmed later in the paper when the free plate will be investigated.

These two coherent wake states can be quasi-permanently forced by breaking the topbottom symmetry with a small inclination angle θ = 0. In Fig. 3(c) the state N is forced by a small positive angle while in Fig. 3(d) the state P is forced with a small negative angle. It is worth mentioning that for both cases the base pressure gradient introduces a torque having the same sign as that of the torque in (2.1) resulting from the front pressure distribution. Hence both front and base pressure distributions contribute constructively to a positive stiffness as illustrated by the scheme in Fig. 2(b).

The long time dynamics is better quantified using the velocity field measurements, especially looking at the time series of the base velocity displayed in Fig. 4(a) for 3 fixed angles defined as :

v * b = +1/2 -1/2 dy * 1/3 1/10 dx * v * (3.1)
The bounding box size at the base is displayed on the instantaneous PIV field in Fig. 4(b1).

For the vertical plate (θ = 0), the base velocity in Fig. 4(a) explores both positive and negative values, but strikingly it is able to keep the same sign during long time durations, about 100 non dimensional units, thus confirming the previous visualizations. As expected, the positive base velocity event labeled b1 in Fig. 4(a) is associated with an instantaneous N state in Fig. 4(b1) and the negative base velocity event b2, with an instantaneous P state in Fig. 4(b2). For both cases of a small inclination angle, the base velocity keeps the same sign most of the time corresponding instantaneously to either the N state for the positive angle and positive base velocity (Fig. 4b3) or to the P state for the negative angle and negative base velocity (Fig. 4b4).

Free plate of aspect ratio

κ = 3 2
When the plate is free to rotate, it orientates itself almost perpendicularly to the flow direction (the horizontal position has a negative stiffness and is consequently unstable).

The base velocity and the angle are simultaneously measured using the PIV set-up. Both time series are displayed in Fig. 5 over a non dimensional time duration of 350.

The plate dynamics appears to be very singular, with discontinuities corresponding to high angular velocities. We can see that each of the large angular velocities dθ dt is correlated to an extreme base velocity v * b . Some of the large deviation events are bringing the system toward large |θ|, such as during the periods [o1, o2] or [o3, o4] while others are bringing the system back to small |θ| such as during the period [b1, b2] or [b3, b4].

The wake is first investigated during deviations departing from θ = 0 in Fig. 6(o1-o4). In these figures, the plate picture is extracted from the PIV acquisition from which the velocity field is computed. It can be seen that the P state is present during the clockwise motion of the plate in the phase [o1, o2] with a strong negative base velocity (see Fig. 5).

The clockwise motion indicates that the P state applies a positive torque on the plate. Similarly, the N state is present during the anticlockwise motion in the phase [o3, o4] with a strong positive base velocity (see Fig. 5). The anticlockwise motion indicates that the N state applies a negative torque on the plate. During the phase [o2, b1], the base velocity in Fig. 5 changes sign from an extreme negative value to an extreme positive value. At the instant b1, the wake has effectively changed to state N as can be stated from Fig6(b1), and again a negative torque is applied due to the presence of the N state during the phase [b1, b2]. An identical scenario is observed during the phase [o4, b4] where the base velocity changes sign again from an extreme positive value to an extreme negative value. At instant o4, the N state is present, while at b3 the state definition is not clear, but at b4 the P state is clearly present indicating a positive torque producing a clockwise motion of the plate.

On the basis of these observations, the stochastic dynamics can be summarized as follows. Each state applies a torque on the plate that is able to produce an inclination angle which provokes the switching to the mirror state. For instance, the N state provokes an inclination towards large negative angles θ < 0 as during the phase [o3, o4], but from the fixed plate experiment, Fig. 4(d) indicates that θ < 0 is the condition for the observation of the P state, not the N state. Then the probability at o4 to change state from N to P is very high. Indeed, the following switching revealed by the change of the base velocity sign is clearly observable during the phase [o4, b3]. Eventually, it is important to mention that for the cases o2, o4 and b4 the base pressure gradient of the wake mode introduces a torque having an opposite sign to that of the torque in (2.1) resulting from the front pressure distribution. These states, depicted in Fig. 2(c), can then correspond to stable equilibrium positions with inclined plate. The lifetime of these equilibrium positions depends on the probability of the wake to change state for a given inclination angle θ.

Statistics and dynamics of free plates having different aspect ratio

Plates of 12 different widths W with free rotation are successively tested to study the aspect ratio κ effect on the fluid structure mechanism evidenced above. Time series are first shown over a non dimensional duration of 1000 in Fig. 7.

At first glance, there is a huge variety of angle dynamics depending on the aspect ratio value. Discontinuities, such as those evidenced in Fig. 5 are observable for κ < 6, with maximal amplitude deviations around κ = 2.4. In this range, the dynamical system is able to keep a non zero constant angle during long non dimensional periods of 100 and sometimes even larger. The power spectra in Fig. 8(a) are computed from time series acquired during a total non dimensional time of 50 000, they are averaged over 500 time units, leading to the frequency resolution df * = 0.002. All the spectra obtained with aspect ratio κ < 3.43 exhibit a high energetic power law at low frequencies for f * < 0.2. The exponent that varies from -2 at κ = 1 to -3 at κ = 3.43 is associated with the random appearance of discontinuities [START_REF] Grandemange | Turbulent wake past a three-dimensional blunt body. Part 1. Global modes and bi-stability[END_REF]. Weak periodic oscillations of θ are observable in the spectra as shown by the peak at St=0.235 for κ = 1. Their frequencies are reduced to St=0.195 as the aspect ratio is increased to κ = 2 and then the periodic mode vanishes completely for aspect ratios even larger.

The probability density functions (PDFs) of the angle θ are presented in Fig. 8(b). The wider distributions of angles are observed in the range κ [2 -4]. For these cases, the distributions are rather uniform, but sometimes (as for κ = 2, 3) we can observe three weak but significant bumps. The central bump around θ = 0 is larger than the two symmetric ones located on both sides.

The mean angle is generally not zero, and some unexpected asymmetry of the distributions are observable. It emphasises the sensitivity to symmetrical imperfection on the lever arm responsible for the plate dynamics, it is mainly due the accuracy in the axis position at H/2 (see Fig. 1b and Sec.2). We made new plates to improve this accuracy. However,the little clearance of 0.2 mm between the hole diameter and the axis diameter required for low friction rotation will create by gravity a small permanent downward displacement of 0.1 mm of the plate from the origin O, thus producing a plate angle equilibrium with the uniform flow at a slightly positive value of θ.

At the aspect ratio κ = 6, the fluctuations of the angular position are minimum and a clear transition to a very different regime occurs. For κ > 6 the spectra of the angular position look like the response of a linear oscillator to a random excitation having an eigen frequency of St= 0.14. The high frequency peaks in the spectrum obtained for κ = 8 are suspected to originate from the vortex shedding of the plate that is comparable to a square cylinder with W = 6 mm sides. The highest frequency peak at St= 1.4 provides a Strouhal number based on W , St W = 0.175 that is reasonable for this assumption. The motion can be caused by a rotation around the long axis of symmetry of the plate due to the small gap clearance around the cylindrical support as well as a sliding motion in the z direction.

Discussion and concluding remarks

For aspect ratio κ < 6, the long time dynamics of the angular position (for frequencies f * < 0.2) is fully stochastic (i.e. no periodicity) with random appearances of high angular velocities. It is shown that static symmetry breaking modes of the wake are responsible for the plate dynamics. Using a global stability analysis of the flow past rectangular plates, [START_REF] Marquet | Global wake instabilities of low aspect-ratio flat-plates[END_REF] predicted the presence of steady symmetry breaking modes as soon as κ < 2.5 and Reynolds number Re> 150. There is then an agreement about the presence of the modes at low aspect ratios leading to a transition when the aspect ratio is increased. The larger critical aspect ratio obtained in the experiment can be ascribed to many effects such as the large Reynolds number, the plate motion, the large blockage in the hydrodynamic tunnel and the cylinder axis presence.

The PDFs in Fig. 8(b) are almost uniform meaning that the dynamics is here multistable (see the succession of steady angles in the dynamics displayed in Fig. 7). From the low Reynolds number study of [START_REF] Marquet | Global wake instabilities of low aspect-ratio flat-plates[END_REF], we actually would expect four modes, a pair of static modes for each axis symmetry breaking. For a sake of simplicity, they can be roughly reduced to one asymmetric spatial mode but with a variable azimuthal phase that can take four values. The static modes in a pair are then just π shifted from each other (mirror modes, denoted P and N). On a more practical point of view, the azimuthal phase of the mode indicates the torque orientation exerted on the body. For our experiment, only both the mode P and N of the small symmetry axis breaking lead to a change of the angular positions of the plate, while the two modes of the long symmetry axis breaking do not have any effect on θ. If the four corresponding azimuthal phases are equally explored during the turbulent dynamics, one would then O. Cadot expect a symmetric three-modal angle distribution with a probability for θ = 0 to be twice the probability at either θ > 0 or θ < 0. It is clearly not the case, however the distributions obtained for κ = 2, 3 in Fig. 8(b) with their three weak bumps may present some similitude with this expectation. Since the distributions are almost uniform, it is likely that the wake dynamics is more similar to that of an axisymmetric body as recently evidenced by [START_REF] Rigas | Diffusive dynamics and stochastic models of turbulent axisymmetric wakes[END_REF]. In that case, the dynamics is a combination of random noise of the azimuthal phase of the static mode together with π phase jumps toward the mirror static mode. The appearances of the modulation in the angular distribution is perhaps due to a small preferences toward azimuthal phase selections compatible with the two reflectional symmetries of the plate.

It is speculated that the projection of the resulting fluid force of the wake dynamics on the only degree of freedom θ of our simple mechanical system can produce the observed dynamics. The low order model based on Langevin equation presented by [START_REF] Rigas | Diffusive dynamics and stochastic models of turbulent axisymmetric wakes[END_REF] will be the next step to investigate the modelling of this stochastic fluid structure interaction.

Finally, it is noteworthy that for the low aspect ratios (κ < 6), the classical periodic vortex shedding (observed here at Strouhal numbers St 0.235 -0.195) reminiscent from the Hopf bifurcation at low Reynolds number is relegated as a second order contribution to the dynamics emphasizing the dominant strength of the asymmetric static modes and their related stochastic dynamics for large Reynolds numbers.

Figure 1 .

 1 Figure 1. Experimental set-up. Cross section (a) and side view (b) of the hydrodynamic tunnel with the flat plate of aspect ratio κ = H W . In (a) the T and R blocks sketches the optical device that measures the position δ of the plate. The dashed frame in (b) represents the area for visualizations and PIV measurements. Angular velocity (c) during the free decay in air of the plate having κ = 2.4, and solid friction torque γS (inlet) estimated from the linear decay displayed by the straight line.

Figure 2 .

 2 Figure 2. Illustration (a) of the restoring torque due to the potential flow with cavity. Sketch of the low pressure recirculation for the fixed plate (b) and steady state of the free plate with no net torque (c).

Figure 3 .

 3 Figure 3. Visualizations of N (left) and P (right) states of the wake with a fixed plate. (a) and (b): θ = 0 (c): θ > 0, (d): θ < 0.

Figure 4 .

 4 Figure 4. Time series (a) of the base vertical velocity v * b of the fixed plate for, from top to bottom θ > 0; = 0; < 0. The letters b1 to b4 correspond respectively to the instantaneous PIV fields in (b) labeled (b1) to (b4). Velocity fields are displayed with streamlines (black lines) and velocity modulus Uxy (color map) in (x, y) plane. The dashed rectangle in (a) is the integration area for the base velocity computation v * b in (3.1).

Figure 5 .Figure 6 .

 56 Figure 5. Angular position θ (crossed line) and base velocity (smooth line) vs. time extracted from the PIV acquisition. Each label refers to an instantaneous velocity field in Fig. 6.

Figure 7 .

 7 Figure 7. Time series of the angular position θ(t * ) for κ = [1 -8] in descending order from top to bottom.

Figure 8 .

 8 Figure 8. Power spectra (a) and probability density function (b) of the angular position θ(t * ) for κ = [1 -8] in descending order from top to bottom. In (a) frequencies in non dimensional units are defined as f * = f H/U0, dashed lines are -2 and -3 power laws.

† Email address for correspondence: cadot@ensta.fr

Acknowledgments

The work has been motivated by a fruitfull discussion with F. Gallaire and O. Marquet during the 6th International Symposium on Bifurcation and Instabilities in Fluid Dynamics. The author wish to thank O. Doaré for the critical reading of the manuscript and for drawing his attention on a characterization of the solid friction.


Claire Silvani¹
email: claire.silvani@insa-lyon.fr

Julien Réthoré
email: julien.rethore@insa-lyon.fr

Stéphane Bonelli
email: stephane.bonelli@irstea.fr

Measuring rockfill deformation by digital image correlation

Keywords: Rockfill, Granular media, Digital Image Correlation, Strain field

This study focuses on the behaviour of rockfill media under compression. Rockfill media are coarse media composed of quarry rock debris or crushed rock fragments with a characteristic size of up to one meter. This medium has been used in a large number of high embankment dams. Rockfill dams are subjected to deformation processes, which can occur long after the construction of the dam, even during periods when no changes occur in the loading. This issue, which has been previously studied by several authors, is of great importance to dam engineers [START_REF] Hunter | Rockfill modulus and settlement of concrete face rockfill dams[END_REF][START_REF] Justo | Settlement-time behaviour of granular embankments[END_REF][START_REF] Icold | Rock materials for rockfill dams, review and recommendations[END_REF]. Usually, rockfill materials have seldom been tested, because of the size apparatus required, and the corresponding costs and delays for testing, even for small-sized rockfill. However, the trend towards larger works, such as higher rockfill dams with steeper slopes, should be associated with improved knowledge of their behaviour [START_REF] Frossard | Rockfill shear strength evaluation: a rational method based on size effects[END_REF]. Significant incidents have recently marked the commissioning of various rockfill dams [START_REF]Proceedings on the 3rd Symposium on Concrete Face Rockfill Dams[END_REF], attributed to excessive unforeseen deformations, under normal service conditions. Concern is then rising within the profession to return to more rational approaches in design in rockfill dams and underlines a growing need for progress in knowledge in the behaviour in rockfill material, which can been considered as a granular material.

The mechanical behaviour of granular materials is complex essentially due to their discrete nature. To improve the understanding of these granular media it is necessary to understand the evolution of the internal state of this heterogeneous material. Experimental work has been developed here to give insights into the strain behaviour of this rockfill media. Many authors have worked on this topic, but mainly from theoretical and numerical approaches. Recently, some of them have introduced an intermediate scale, called meso-scale, at which strain can be defined using the tools of continuum mechanics [START_REF] Bagi | Analysis of microstructural strain tensors for granular assemblies[END_REF]. Establishing a link between particle level displacements and macro-level deformations is important for researchers who intend to develop micromechanically based constitutive theories [START_REF] Chaze | Analysis of internal state and strains in granular material at meso-scale: influence of particle shape[END_REF]. The aim of this work is to measure the displacement of each individual grain and then to compute macroscopic strains from grain displacements.

In this paper, we present the results of an experimental study based on the development on a Digital Image Correlation (DIC) tool to analyse strain of a rockfill media under oedometric compression. The study of granular materials containing large particles such as rockfill requires suitable laboratory facilities whose dimension must be in proportion to the maximum size of the grains. The oedometric cell used here has been developed by IRSTEA laboratory in Aix-en-Provence (France) and has a square surface of 30cmx30cm and is 40cm high, whereas the grains have a maximum size of 4cm. Some of the cell walls are in Plexiglas, to guarantee the optic accessibility of surfaces. DIC techniques are then used to measure the grains displacements field in 2D and in 3D using 2 cameras. To compute strain, the assembly is replaced by a continuous domain, and displacement of the characteristics points of the equivalent continuum media is equal to the displacement of the particles centers. To define local strain, a meso-scale is defined, whose branches connect the centers of three particles in contact, using Delaunay triangulation. The rotation of each grains is also up-scaled for higher order continuum model evaluation. The gradient of the displacement field of each triangle is then determined on the basis of particle displacements and microlevel geometrical characteristics (see Figure 1).

Figure 1 :

 1 Figure 1: Principe of strain computations: grains displacements fields and Delaunay triangulation (a) and displacement field in Delaunay cells (b)


Bruno Courcelle
email: courcell@labri.fridurand@labri

Irène Durand

Model-checking with fly-automata

Keywords: clique-width, fixed parameter tractable algorithm, automaton on terms, fly-automaton

Model-checking; monadic second-order logic; tree-width

number of occurrences of a particular symbol in the input term. FA can thus check certain graph properties that are not monadic second-order expressible. An example is regularity, the fact that all vertices have the same degree. Furthermore, an FA equipped with an output function that maps the set of accepting states to an effectively given domain D can compute a value, for example the number of k-colorings of the given graph G, or the minimum cardinality of one of the k color classes if G is k-colorable (this number measures how close is this graph to be (k -1)-colorable). We have implemented and tested an FA that computes the number of 3-colorings of a graph.

Tree-width and clique-width are graph complexity measures that serve as parameters in many FPT algorithms [START_REF] Courcelle | Linear-time solvable optimization problems on graphs of bounded clique-width[END_REF][START_REF] Downey | Parameterized complexity[END_REF][START_REF] Flum | Parametrized complexity theory[END_REF]. Both are based on hierachical decompositions of graphs that can be expressed by terms written with the operation symbols of appropriate graph algebras [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]. The model-checking automata take such terms as inputs. We will present results concerning graphs of bounded clique-width. The similar results for graphs of bounded tree-width reduce to them as we will explain at the end of this section.

Graphs and monadic second-order logic

Graphs are finite, undirected, without loops and multiple edges. The extension to directed graphs, possibly with loops and/or labels is straightforward. A graph G is identified with the relational structure V G , edg G where edg G is a binary symmetric relation representing adjacency.

Rather than giving a formal definition of monadic second-order (MSO) logic, we present the closed formula expressing 3-colorability (an NP-complete property). It is ∃X, Y.Col(X, Y ) where Col(X, Y ) is the formula

X ∩ Y = ∅ ∧ ∀u, v.{edg(u, v) =⇒ [¬(u ∈ X ∧ v ∈ X)∧¬(u ∈ Y ∧v ∈ Y ) ∧¬(u / ∈ X ∪ Y ∧ v / ∈ X ∪Y )]}.
This formula expresses that X, Y and V G -(X ∪Y ) are the three color classes of a 3-coloring. The corresponding colors are respectively 1, 2 and 3.

Definition 1 :

The graph algebra G (a) We will use N + as a set of labels called port labels. A p-graph is a triple

G = V G , edg G , π G where π G is a mapping : V G → N + . If π G (x) = a,
we say that x is an a-port. The set π(G) of port labels of G is its type. By using a default label, say 1, we make every nonempty graph into a p-graph of type {1}.

(b) We let F k be the following finite set of operations on p-graphs of type included in C := {1, ..., k} ⊆ N + :

• the binary symbol ⊕ denotes the union of two disjoint p-graphs, • the unary symbol relab a→b denotes the relabelling that changes every port label a into b (where a, b ∈ C),

• the unary symbol add a,b , for a < b, a, b ∈ C, denotes the edge-addition that adds an edge between every a-port x and every b-port y (unless there is already an edge between them; our graphs have no multiple edges),

• for each a ∈ C, the nullary symbol a denotes an isolated a-port.

(c) Every term t in T (F k ) (the set of finite terms written with F k ) is called a k-expression. Its value is a p-graph, val(t), that we now define. For each position u of t (equivalently, each node u of the syntax tree of t) we define a p-graph val(t)/u, whose vertex set is the set of leaves of t below u. The definition of val(t)/u is, for fixed t, by bottom-up induction on u:

• If u is an occurrence of a, then val(t)/u has vertex u as an a-port and no edge,

• if u is an occurrence of ⊕ with sons u 1 and u 2 , then val(t)/u := val(t)/u 1 ⊕ val(t)/u 2 , (note that val(t)/u 1 and val(t)/u 2 are disjoint), • if u is an occurrence of relab a→b with son u 1 , then val(t)/u := relab a→b (val(t)/u 1 ), • if u is an occurrence of add a,b with son u 1 , then val(t)/u := add a,b (val(t)/u 1 ).
Finally, val(t) := val(t)/root t . Its vertex set is the set of all leaves (occurrences of nullary symbols). For an example, let

t := add 1 b,c (add 2 a,b (a 3 ⊕ 4 b 5 ) ⊕ 6 relab 7 b→c (add 8 a,b (a 9 ⊕ 10 b 11 )))
where the superscripts 1 to 11 number the positions of t. The p-graph val(t) is

:= 8, then t/u = t/w = add a,b (a ⊕ b), however, val(t)/u is the p-graph 3 a -5 b and val(t)/w is 9 a -11 b , isomorphic to val(t)/u. (d)
The clique-width of a graph G, denoted by cwd(G), is the least integer k such that G is isomorphic to val(t) for some t in T (F k ). We denote by G k the set val(T (F k )) of p-graphs that are the value of a term over F k . We let F be the union of the sets F k , and G be the union of the sets G k . Every p-graph is isomorphic to a graph in G, hence, has a clique-width.

(e) An F-congruence is an equivalence relation ≈ on p-graphs such that:

• two isomorphic p-graphs are equivalent, and

• if G ≈ G ′ and H ≈ H ′ , then G ⊕ H ≈ G ′ ⊕ H ′ , add a,b (G) ≈ add a,b (G ′ )
and relab a→b (G) ≈ relab a→b (G ′ ).

(f) A set of graphs L is recognizable if there exists an F -congruence such that, for each finite type C ⊆ N + , the number of equivalence classes of p-graphs of type C is finite.

Definition 2: Fly-automata. (a) Let H be a finite or countable, effectively given, signature. A fly-automaton over H (in short, an FA over H) is a 4-tuple A = H, Q A , δ A , Acc A such that Q A is the finite or countable, effectively given set of states, Acc A is the set of accepting states, a decidable subset of Q A , and δ A is a computable function that defines the transition rules: for each tuple (f, q 1 , . . . , q m ) with q 1 , . . . ,

q m ∈ Q A , f ∈ H, ρ(f ) = m ≥ 0, δ A (f, q 1 , . . . , q m )
is a finite set of states. We write f [q 1 , . . . , q m ] → q (and f → q if f is nullary) to mean that q ∈ δ A (f, q 1 , . . . , q m ). We say that A is finite if F and Q A are finite.

(b) Runs and recognized languages are defined as usual, see [START_REF] Comon | Tree automata techniques and applications[END_REF]. A deterministic FA A (by "deterministic" we mean "deterministic and complete") has a unique run on each term t and q A (t) is the state reached at the root of t. The mapping q A is computable and the membership in L(A) of a term t ∈ T (H) is decidable.

(c) Every FA A that is not deterministic can be determinized by an easy extension of the usual construction, see [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF]; it is important that the sets δ A (f, q 1 , . . . , q m ) be finite.

(d) A deterministic FA over H with output function is a 4-tuple A = H, Q A , δ A , Out A that is a deterministic FA where Acc A is replaced by a total and computable output function

Out A : Q A → D such that D is an effectively given domain. The function computed by A is Comp(A) : T (H) → D such that Comp(A)(t) := Out A (q A (t)).
Example 1 : The number of accepting runs of an automaton. Let A = H, Q A , δ A , Acc A be a nondeterminisic FA. We construct a deterministic FA B that computes the number of accepting runs of A on any term in T (H). As set of states Q B , we take the set of finite subsets of Q A × N + . The transitions are defined so that B reaches state α at the root of t ∈ T (H) if and only if α is the finite set of pairs (q, n) ∈ Q A × N + such that n is the number of runs of A that reach state q at its root. This number is finite and α can be seen as a partial function : Q A → N + having a finite domain. For a symbol f of arity 2, B has the transition : f [α, β] → γ where γ is the set of pairs (q, n) such that n is the sum of the integers n p .n r over all pairs (p, r) ∈ Q A × Q A such that (p, n p ) ∈ α, (r, n r ) ∈ β and q ∈ δ A (f, p, r). The transitions for other symbols are defined similarly. The function Out A maps a state α to the sum of the integers n such that (q, n) ∈ α ∩ (Acc A × N + ).

Example 2 : An FA for checking 3-colorability. In order to construct an FA that accepts the terms t ∈ T (F ) such that val(t) is 3-colorable, we first construct an FA A for the property Col(X, Y ). For this purpose, we transform F into F (2) by replacing each nullary symbol a by the four nullary symbols (a, ij), i, j ∈ {0, 1}. A term t ∈ T (F (2) ) defines, first, the graph val(t ′ ) where t ′ is obtained from t by removing the Booleans i, j from the nullary symbols and, second, the pair (V X , V Y ) such that V X is the set of vertices u (leaves of t) that are occurrences of (a, 1j) for some a and j, and V Y is the set of those that are occurrences of (a, i1) for some a and i. The set of terms t ∈ T (F (2) ) such that Col(V X , V Y ) holds in val(t ′ ) is defined by a determinitic FA A than we now specify. Its states are Error and the nonempty subsets of C × {1, 2, 3}. Their meanings are as follows:

• at position u of t, the automaton reaches state Error if and only if val(t ′ )/u has a vertex in V X ∩ V Y or an edge between two vertices, either both in V X , or both in V Y , or both in V G -(V X ∪ V Y ), hence of same color, respectively 1,2 or 3;

• it reaches state α ⊆ C × {1, 2, 3} if and only if these conditions do not hold and α is the set of pairs (a, i) such that val(t ′ )/u has an a-port of color i.

All states except Error are accepting. Here are the transitions of A:

(a, 00) → {(a, 3)}, (a, 10) → {(a, 1)}, (a, 01) → {(a, 2)}, (a, 11) → Error.

For α, β ⊆ C × {1, 2, 3}, A has transitions : This FA checks Col(X, Y ). To check, ∃X, Y.Col(X, Y ), we build a nondeterministic FA B by deleting the state Error, by replacing the first three rules of A by a → {(a, 3)}, a → {(a, 1)}, a → {(a, 2)} and by deleting those that yield Error. All states are accepting but on some terms, no run can reach the root, and these terms are rejected. Furthermore, the construction of Example 1 shows how to make B into a deterministic FA that computes the number of 3-colorings, because the 3-colorings of val(t) are in bijection with the accepting runs of B on t.

⊕[α, β] → α ∪ β, add a,b [α] → Error, if (a, i) and (b, i) belong to α for some i = 1, 2, 3, add a,b [α] → α, otherwise, relab a→b [α] → β,
Recognizability Theorem : The set of graphs that satisfy a closed MSO formula ϕ is F -recognizable.

Weak Recognizability Theorem : For every closed MSO formula ϕ, for every k, the set of graphs in G k that satisfy ϕ is F k -recognizable.

Proofs: The Recognizability Theorem is Theorem 5.68 of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]. Its proof shows that the equivalence defined by the fact that the two considered p-graphs have the same type and satisfy the same closed MSO formulas of quantifier-height at most that of ϕ satisfies the conditions of Definition 1(f). (These formulas have unary predicates for expressing port labels). The Weak Recognizability Theorem follows from the former one. It can be proved directely by constructing an FA over F [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF]. (We construct a single FA, not a particular FA for each subsignature F k as in Theorem 6.35 of [START_REF] Courcelle | Graph structure and monadic second-order logic, a language theoretic approach[END_REF]). This construction can be implemented, at least in a number of nontrivial cases. The proof of the strong theorem does not provide any usable automaton.

Counting and optimizing automata

Let P (X 1 , ..., X s ) be an MSO property of vertex sets X 1 , ..., X s . We denote (X 1 , ..., X s ) by X and t |= P (X) means that X satisfies P in the graph val(t) defined by a term t. We are interested, not only to check the validity of ∃X.P (X), but also to compute from a term t the following values: #X.P (X), defined as the number of assignments X such that t |= P (X), SpX.P (X), the spectrum of P (X), defined as the set of tuples of the form (|X 1 |, . . . , |X s |) such that t |= P (X), MSpX.P (X), the multispectrum of P (X), defined as the multiset of tuples (|X 1 |, . . . , |X s |) such that t |= P (X).

These computations can be done by FA. The construction for #X.P (X) is based on Example 1. We obtain in this way FPT or XP algorithms [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Flum | Parametrized complexity theory[END_REF].

Edge set quantifications and tree-width. The two recognizability theorems and the corresponding constructions of FA yielding FPT and XP algorithms hold and can be done for graphs of bounded tree-width and MSO formulas with edge set quantifications: it suffices to replace a graph G by its incidence graph Inc(G), a bipartite graph whose vertices are those of G and its edges, to observe that the clique-width of Inc(G) is bounded in terms of the tree-width of G, and that an MSO formula with edge set quantifications over G can be translated into an MSO formula over Inc(G). Another approach is in [START_REF] Courcelle | On the model-checking of monadic second-order formulas with edge set quantifications[END_REF].

Beyond MS logic

The property that the considered graph is the union of two disjoint regular graphs with possibly some edges between these two subgraphs is not MSO expressible but can be checked by an FA. An FA can also compute the minimal number of edges between X and V G -X such that G[X] and G[V G -X] are connected, when such a set X exists.

Open problems

The parsing problem for graphs of clique-width at most k is NP-complete (with k in the input) [START_REF] Fellows | Clique-Width is NP-Complete[END_REF]. Good heuristics remain to be developped.

Experimental results

These constructions have been implemented and tested [START_REF] Courcelle | Automata for the verification of monadic second-order graph properties[END_REF][START_REF] Courcelle | Computations by fly-automata beyond monadic second-order logic[END_REF][START_REF] Courcelle | Model-checking by infinite fly-automata[END_REF]. We have computed the number of optimal colorings of graphs of clique-width at most 8 for which the chromatic polynomial is known, which allows to verify the correctness of the automaton. We can verify in, respectively, 35 and 105 minutes that the 20×20 and the 6×60 grids are 3-colorable. In 29 minutes, we can verify that the McGee graph (24 vertices) given by a term over F 10 is acyclically 3-colorable.

Recommend reading.

A different approach using games is presented in [START_REF] Kneis | Courcelle's theorem -A game-theoretic approach[END_REF].

  3 a -5 b -11 c -9 a where the subscripts a, b, c indicate the port labels. (For clarity, port labels are letters in examples). If u := 2 and w

  obtained by replacing a by b in each pair of α. Its other transitions are ⊕[α, β] → Error if α or β is Error, add a,b [Error] → Error and relab a→b [Error] → Error.