Chiara Bosisio

Valentina Quercioli

Giuseppe Chirico

Laura D'alfonso

Stefano Bettati

Samanta Raboni

Barbara Campanini

Maddalena Collini
email: maddalena.collini@mib.infn.it

Effect of the point mutation H148G on GFPmut2 unfolding kinetics by fluorescence spectrocopy

Keywords: GFP, unfolding, fluorescence anisotropy, fluorescence correlation spectroscopy, (H148G, GFPmut2)

We have used fluorescence spectroscopy techniques such as fluorescence correlation spectroscopy and fluorescence anisotropy decay on a wide time range, from nanoseconds to seconds, to investigate the unfolding kinetics induced by guanidinium chloride of GFPMut2 and its point mutation H148G, which has proved to be relevant for GFP photochemistry and photophysics.

The mutation affects the unfolding kinetics of GFP leading to a much faster process at alkaline pH values, where protonation dynamics is negligible, that can be ascribed to a twofold role of His148, either as a proton shutter towards the chromophore and as a conformation stabiliser. For both mutants a soft region located near beta-strand 3 is found that starts to gain flexibility in the ns range at denaturant concentrations far lower than those required to turn off the chromophore fluorescence, as derived from the anisotropy decay of an extrinsic probe covalently bound to the proteins.

INTRODUCTION

Since its widespread use as a cellular reporter [START_REF] Tsien | Constructing and exploiting the fluorescent protein paintbox (Nobel Lecture)[END_REF], either alone as a fluorescent marker in vivo or as a chimeric construct (2), a better and deeper understanding of the unfolding kinetics of the Green Fluorescent Protein (GFP) from Aequorea Victoria is relevant both for basic and applied research where its mutants are used for subcellular localizations. It has been shown (3) that protein structure, and in particular the beta-barrel scaffold, is determinant in ensuring a high fluorescence quantum yield by maintaining a semi-rigid environment around the chromophore because this low conformational flexibility should reduce the non radiative de-excitation pathways. However, some degree of structure flexibility should be welcome in order to allow those structural transitions, such as cistrans isomerizations, protonations, proton transfers [START_REF] Day | The fluorescent protein palette: tools for cellular imaging[END_REF], that can lead to photoswitchable probes. The design of GFP mutants with different photodynamics properties is in fact desirable in view to be exploited for the most recent super-resolution applications of fluorescence microscopy [START_REF] Hell | Towards fluorescence nanoscopy[END_REF][START_REF] Andresen | Photoswitchable fluorescent proteins enable monochromatic multilabel imaging and dual color fluorescence nanoscopy[END_REF].

A good indicator of the integrity of the protein scaffold, which is mainly due to the 11 strands beta barrel structure comes from the fluorescence of the chromophore, which is quenched when it is exposed to the solvent, as suggested by the correlation between the barrel structure detected by far UV circular dichroism and by the green fluorescence [START_REF] Campanini | Unfolding of Green Fluorescent Protein mut2 in wet nanoporous silica gels[END_REF]. GFP unfolding kinetics is extremely slow, reaching equilibrium after hours or days, depending on the mutant and on the denaturant concentration. In the literature, a number of works are found on the unfolding features of cycle3 mutant [START_REF] Fukuda | Folding of green fluorescent protein and the Cycle3 mutant[END_REF][START_REF] Battistutta | Crystal structure and refolding properties of the mutant F99S/M153T/V163A of the Green Fluorescent Protein[END_REF][START_REF] Enoki | Acid denaturation and refolding of green fluorescent protein[END_REF][START_REF] Enoki | The equilibrium unfolding intermediate observed at pH 4 and its relationship with the kinetic folding intermediates in green fluorescent protein[END_REF][START_REF] Huang | Stable intermediate states and high energy barriers in the unfolding of GFP[END_REF][START_REF] Jackson | Understanding the folding of GFP using biophysical techniques[END_REF] which shows stable intermediates upon both acidic and chemical denaturation, and reaches equilibrium on weeks time-scale. A certain degree of irreversibility in the refolding process has been reported [START_REF] Fukuda | Folding of green fluorescent protein and the Cycle3 mutant[END_REF], described by double exponential reaction curves and ascribed, at least partially, to proline residues isomerization. Comparative studies on other fluorescent proteins [START_REF] Hsu | The folding, stability and conformational dynamics of beta-barrel fluorescent proteins[END_REF][START_REF] Huang | Stable intermediate states and high energy barriers in the unfolding of GFP[END_REF][START_REF] Stepanenko | Comparative studies on the structure and stability of fluorescent proteins EGFP, zFP506, mRFP1, "dimer2", and DsRed1[END_REF][START_REF] Stepanenko | Fluorescent proteins as biomarkers and biosensors: throwing color lights on molecular and cellular processes[END_REF][START_REF] Xie | Trigger factor assisted folding of green fluorescent protein[END_REF][START_REF] Hsu | Folding study of Venus reveals a strong ion dependence of its yellow fluorescence under mildly acidic conditions[END_REF] show that all the FPs share uncommonly long unfolding kinetics. As suggested in a recent review [START_REF] Hsu | The folding, stability and conformational dynamics of beta-barrel fluorescent proteins[END_REF], a rough energy landscape with high energy barriers [START_REF] Andrews | The rough energy landscape of superfolder GFP is linked to the chromophore[END_REF][START_REF] Orte | Evidence of an intermediate and parallel pathways in protein unfolding from single-molecule fluorescence[END_REF][START_REF] Bertz | Navigating the folding energy landscape of green fluorescent protein[END_REF][START_REF] Andrews | The dualbasin landscape in GFP folding[END_REF][START_REF] Mickler | Revealing the bifurcation in the unfolding pathways of GFP by using single-molecule experiments and simulations[END_REF][START_REF] Baldini | Evidence of discrete substates and unfolding pathways in green fluorescent protein[END_REF] is likely to characterize the GFP unfolding pathway.

NMR studies [START_REF] Seifert | Backbone dynamics of green fluorescent protein and the effect of histidine 148 substitution[END_REF] has suggested that the mutation of histidine 148 with a glycine in strand 7 could alter the backbone dynamics affecting the protein stability. Since our group has recently characterized the photodynamic effects of such mutation on GFP [START_REF] Bosisio | Protonation and conformational dynamics of GFP mutants by two-photon excitation fluorescence correlation spectroscopy[END_REF],

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

5 it is particularly interesting to investigate the coupling between the structural flexibility and the photodynamics whose understanding seems to be relevant for the development of photochromic GFPs.

In the present paper we investigate the unfolding kinetics of this point mutation H148G of GFPmut2 (S65A/V68L/S72A GFP) compared to the parent protein in the presence of guanidinium chloride (GuHCl). GFPmut2 (Mut2) is a GFP folding mutant optimized for live cell spectroscopy due to high expression yield in bacteria, high fluorescent yield [START_REF] Cormack | FACS-optimized mutants of the green fluorescent protein (GFP)[END_REF] and increased pKa for the transition between the protonated and the highly fluorescent anionic form of the chromophore [START_REF] Chirico | Dynamics of green fluorescent protein mutant2 in solution, on spin-coated glasses, and encapsulated in wet silica gels[END_REF]. However, its unfolding kinetics at pH 7 is still as slow as that of the wild type protein [START_REF] Campanini | Unfolding of Green Fluorescent Protein mut2 in wet nanoporous silica gels[END_REF]. The H148G mutation on Mut2, yielding Mut2G, has a large effect on the chromophore pKa, which is shifted from ~6.0 to ~7.5 [START_REF] Bosisio | Protonation and conformational dynamics of GFP mutants by two-photon excitation fluorescence correlation spectroscopy[END_REF][START_REF] Abbruzzetti | Kinetics of acid-induced spectral changes in the GFPmut2 chromophore[END_REF] and on the chromophore protonation kinetics [START_REF] Bosisio | Protonation and conformational dynamics of GFP mutants by two-photon excitation fluorescence correlation spectroscopy[END_REF], yielding an increase of the protonation rate due to the missing proton shutter, the histidine, between the solvent and the chromophore.

Different techniques such as fluorescence lifetime decay, fluorescence correlation spectroscopy (FCS) and fluorescence anisotropy decay (FPA) have been combined in order to gain insights in the possible conformational changes accompanying the unfolding transition and the coupling of conformational changes to photodynamics with a particular attention to alkaline pH, where the protein is highly fluorescent. Since the fluorescence of the chromophore ceases when it is exposed to the solvent, we also exploited an extrinsic fluorescent probe, tetra-methyl-rhodamine (TMR), bound to the free SH group of Cys48 (beta-sheet 3) in order to detect conformational changes when the chromophore is already quenched.

EXPERIMENTAL PROCEDURES

Protein. Mut2 and Mut2G were expressed and purified as described elsewhere [START_REF] Abbruzzetti | Kinetics of acid-induced spectral changes in the GFPmut2 chromophore[END_REF]. GFP mutants were diluted in Tris-NaCl or acetate buffers at pH=8.4±0.2, and GuHCl (Sigma G9284, Guanidine hydrochloride solution, 8 M) was added to obtain the desired denaturant concentration. For experiments with the extrinsic fluorescent probe, GFP was derivatized with tetramethylrhodamine-5-maleimide (Fluka 94506) on Cys48.

A C C E P T E D

M A N U S C R I P T ACCEPTED MANUSCRIPT 6
The labeling degree, as verified by absorption spectroscopy measurements, was about 30%.

Protein concentration was 10-100 nM for fluorescence kinetics, lifetime and FCS experiments, and 0.5-1 µM for FPA measurements. Actually, since the fluorescence signal can be split on two SPADs, cross correlation detection is used in order to avoid detector dead time and afterpulsing that limit the resolution of decay times in the microseconds region. However, since the two SPADs

Kinetic Fluorescence

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT 7
detect the same fluorescence signal coming from the same volume, the pseudo-cross correlation function can be identified with an autocorrelation function where the detectors "defects" have been cleared out: therefore, in order to simplify the notation in the following, the term ACF will still be used to indicate both the fitting expressions and the experimental curves.

In general, the ACFs were fit to an expression taking into account both the diffusive decay of the ACF and the internal photodynamic part of the time dependence:

G(t) = G(0) 1 + t τ D ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ -1 1 + λ 2πω 0 ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 2 t τ D ⎛ ⎝ ⎜ ⎜ ⎞ ⎠ ⎟ ⎟ -0.5 × 1 + A j 1 + A j exp - t τ j ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ j ∏ (1)
with G(0)= γ /<N>, where γ = 0.076 for TPE is a geometrical factor, <N> is the average number of protein in the excitation volume, ω 0 is the beam waist, λ=890 nm, τ D =ω 0 2 /8D is the diffusional time of GFP with a translational diffusion coefficient D, τ j is the j-th photodynamic characteristic time and A j is the protein fraction in the j-th dark state. In general, the fluorescence lifetime decay can be analysed as a sum of discrete exponential components

Fluorescence Lifetimes in Time

I(t) = α i exp -t / τ i ( ) f i = α i τ i / α i τ i i ∑ i ∑ (2)
where τ i are the lifetime values with amplitudes α i and fractional intensities f i . When performing a fluorescence anisotropy decay measurement, the excitation beam is vertically polarized and the emission is detected both in the parallel I || and in the perpendicular I ⊥ polarizer configuration. The anisotropy r(t) is related to the rotational correlation time of the fluorophore by:

Fluorescence Anisotropy Kinetics in the Frequency

r(t) = I  -I ⊥ I  + 2I ⊥ = r 0 g j exp -t / θ j ( ) j ∑ (5)
where r 0 is the limiting anisotropy, θ j are the rotational correlation times with relative amplitudes g j normalised to unity. In the frequency domain we measure the difference in phase angles Δ ω and the demodulation ratios Λ ω of the perpendicular component with respect to the parallel one:

Δ ω = φ ⊥ (ω ) -φ  (ω ) Λ ω =M ⊥ (ω ) / M  (ω ) (6)
A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT 9
These are related to the intensity components, according to [START_REF] Abbruzzetti | Kinetics of acid-induced spectral changes in the GFPmut2 chromophore[END_REF]:

L I  ( ) (ω ) / L I ⊥ ( )(ω) = Λ ω exp iΔ ω ( ) (7)
where L(I ⊥,|| )(ω) are the Laplace transforms of the perpendicular and parallel components of the fluorescence intensity. In this work we have always found that the time decay of r(t) can be fitted by the sum of two exponentials, where θ 1 and θ 2 are the rotational correlation times with relative amplitudes g 1 and g 2 =1-g 1 . All fits were performed by VINCI-Analysis (ISS, Champaign, IL) software. The data can be described by a double exponential decay whose longer relaxation time, τ unf, depends markedly upon GuHCl concentration and ranges from few hundreds of seconds (close to the lower limit of manual mixing of our setup, ≈120 s) to thousands of seconds. This component can be related to the apparent kinetic rate constant for the unfolding process, k obs =1/τ unf , that has a linear dependence on the denaturant concentration, as shown in Figure 1D.

RESULTS

Our

On the contrary the shorter component, whose relaxation time falls in the range of 200 s, does not show any appreciable dependence upon the solution conditions, and it has been attributed to specific effects of chloride ions on GFP fluorescence [START_REF] Campanini | Unfolding of Green Fluorescent Protein mut2 in wet nanoporous silica gels[END_REF][START_REF] Cannone | Tracking unfolding and refolding of single GFPmut2 molecules[END_REF]. A control experiment performed in the presence of 4 M NaCl has shown that the fluorescence intensity shows indeed a time dependence, with a characteristic decay time of about 200 ± 30 s, as shown in Figure 2A. In particular, an intensity decrease of 15% and 25% is determined for Mut2 and Mut2G, respectively. NaCl is known to induce a significant decrease in the fluorescence emission of GFP [START_REF] Bizzarri | Development of a novel GFP-based ratiometric excitation and emission pH indicator for intracellular studies[END_REF][START_REF] Wachter | Sensitivity of the yellow variant of green fluorescent protein to halides and nitrate[END_REF] since it has a specific binding site [START_REF] Arosio | Spectroscopic and Structural Study of Proton and Halide Ion Cooperative Binding to GFP[END_REF], and similar findings have been reported also on other proteins [START_REF] D'alfonso | Evidence of heterogeneous 1anilinonaphthalene-8-sulfonate binding to beta-lactoglobulin from fluorescence spectroscopy[END_REF]. This fast fluorescence decay process should therefore not be treated as part of the unfolding process.

Fluorescence Lifetime. The value of the fluorescence lifetime during the unfolding kinetics can give information about changes in the chromophore environment during the action of the denaturant. The GFP chromophore lifetime values in the presence of GuHCl are systematically shorter than those obtained in the absence of denaturant.

This effect can be however ascribed to the protein-chloride ions interaction, similarly to the behaviour observed for the fluorescence emission intensity (Fig. 2A). In particular, measurements in the presence of 4 M NaCl show that the lifetime decreases by 15-20% for Mut2 and Mut2G. Apart from this unspecific effect, the excited state lifetime values, averaged over experiment durations much smaller than the unfolding characteristic time, 1/k obs , remain constant for both mutants independent of GuHCl as shown for example in Fluorescence Polarisation Anisotropy Decay. Fluorescence polarisation anisotropy (FPA) decay is sensitive to motions in the nanosecond time range that is typical of the polymer internal motions [START_REF] Doi | The theory of polymer dynamics[END_REF]. It is used here to obtain information complementary to those obtained by FCS, which is typically sensitive to fluctuations longer than 1 µs. In particular, due to the long unfolding kinetics of GFP, it is possible to follow changes in the fluorescence anisotropy decay of the two mutants as a function of time during the denaturation process.

In the absence of denaturant, the fluorescence anisotropy of the chromophore can be described by a single exponential decay for both mutants. The values of the correlation time, shown in Table 1, are close to 14 ns and are very similar for the two proteins,

showing that the point mutation does not influence appreciably the overall encumbrance when monitored by the chromophore fluorescence.

The rotational correlation time can be related to the volume occupied by a spherical rotator through the well known Einstein relation, θ = ηV / kT = 4πηR eff 3 / 3kT , where η is the solution viscosity at temperature T, by which an effective radius R eff = 2.4

nm can be estimated. No faster components due to possible wobbling motions of the chromophore have been detected within the instrumental time resolution (0.1 ns). The measured effective radius of both mutants, substantially larger than that expected for an equivalent sphere of the same volume as inferred from the crystallographic data, about 1.75 nm, is close to the value found for other mutants [START_REF] Heikal | Multiphoton molecular spectroscopy and excited-state dynamics of enhanced green fluorescent protein (EGFP): acid-base specificity[END_REF][START_REF] Suhling | The Influence of Solvent Viscosity on the Fluorescence Decay and Time-Resolved Anisotropy of Green Fluorescent Protein[END_REF][START_REF] Volkmer | One-and two-photon excited fluorescence lifetimes and anisotropy decays of green fluorescent proteins[END_REF] when taking into account the barrel shape of the protein and the 60 degrees orientation of the chromophore with respect to the axis of the beta-barrel. Therefore, the samples examined are in the monomeric form.

When GuHCl is added to the solution up to 6.0 M concentration, the rotational correlation time increase according to the increased solution viscosity, but the effective radius remains unchanged (Figure 2D). Also when the unfolding kinetics is followed TMR can be excited by the green line of an Argon laser and it emits at wavelengths longer than those of the chromophore (emission peak at 560 nm).

In the absence of GuHCl, the FPA measurements of the labelled protein give two correlation times for both mutants, contrary to the chromophore fluorescence case, as

shown in Table 1. The longer correlation time, about 15 ns, can be related to the overall protein rotation, while the shorter one, ≈1 ns, is related to the libration (wobbling) motion of the probe at the binding site. As deduced from the relative weights, approximately one third of the depolarisation is accounted for by the probe motion. Due to the different time scale of the two motions and assuming that the segmental motion of the probe occur independently of the overall rotational motions, we can describe the FPA decay in terms of a hindered motion of the TMR probe. The FPA drops rapidly from the initial r 0 value to a lower anisotropy value, r ∞ = r 0 g 1 , that decays subsequently to zero with a much slower rate. From the measured r ∞ value, the maximum angle β spanned by the probe during its motion can be derived according to the relation ( 31): The addition of GuHCl to TMR-GFP determine an increase of both differential phase angles and demodulation ratios, as shown in Figure 4, where the upper panels report the differential phase angles and the demodulation ratios, at increasing GuHCl concentration from 0 to 6 M for Mut2 and Mut2G (panel A and B, respectively). The trend of differential phase angles and demodulation ratios at increasing GuHCl is opposite to what expected for an increase of solution viscosity, as suggested by a measurement of the anisotropy decay of TMR-Mut2 in the presence of 4.0 M NaCl, which leads to a solution whose viscosity is almost the same as that induced by 5.5 M GuHCl. In this case in fact, both differential phase angles and demodulation ratios decrease (stars in Fig. 4A), with respect to Mut2 in buffer, leading to a rotational correlation time of 14.5 ± 0.5 ns, in excellent agreement with the value obtained in the absence of salt once rescaled for the higher viscosity. When fitting fluorescence anisotropy data in the presence of GuHCl with a double exponential decay law, the longer correlation time is found to decrease versus GuHCl concentration for both mutants, once rescaled in order to take into account the effect of solution viscosity, as shown in the lower panels of Figure 4 (C and D for Mut2 and Mut2G, respectively). In particular, for Mut2 the correlation time decreases with a sigmoidal shape to a constant value of 5.5 ± 0.5 ns at high GuHCl molarities, whereas for Mut2G the sigmoidal decrease is steeper and reaches a plateau value of 7.5 ± 0.5 ns. Interestingly, for this mutant, at even higher GuHCl concentrations lower values are found that can be ascribed to the presence of an additional kinetic effect, probably related to the overall GFP denaturation.

In fact, for GuHCl concentrations higher than 5.5 M for Mut2 and 4.5 M for Mut2G, a slow kinetic effect appears, as shown in Figure 5. For GuHCl concentrations up to 5.0 M, no time dependence is found in the differential phase angles and modulation ratios profiles for Mut2, and the derived rotational correlation time is therefore constant versus time up to several hours (Figure 5, panels A and B). A different behaviour is found at 6.0 M GuHCl, where differential phase angles and demodulation ratios increase versus time: in this case the rotational correlation time decreases exponentially with a characteristic time constant of 1700 s down to values as short as 3 ns (Figure 5 Concerning the faster rotational time in TMR-GFP FPA decays, it is found to change only slightly from 0.7 to 0.9 ± 0.1 ns, whereas its weight largely increases from 38±0.5% to 65±1% for Mut2 and from 34±0.5% to 84±1% for Mut2G.

DISCUSSION

Unfolding Kinetics Detected by Chromophore Fluorescence. The unfolding kinetics curves for the two GFP mutants at pH=8.4 can be analysed by two exponential decays as reported in the results session. Apart from an unspecific fast effect due to the Cl -ions, the relaxation time, τ unf , is found to increase at increasing denaturant concentration. In particular, ln(k obs =1/τ unf ) can be fitted to a linear relation, suggesting that we are exploring the unfolding branch of the Chevron plot. The slope of the curves, which is proportional to the change in solvent exposure along the reaction [START_REF] Campanini | Unfolding of Green Fluorescent Protein mut2 in wet nanoporous silica gels[END_REF], is similar for the two mutants, m = ∂ ln k obs / ∂[GuHCl] ≅ 0.85 ± 0.05 s -1 M -1 , and m=1.15±0.05 s - 1 M -1 , for Mut2 and Mut2G, respectively.

The point mutation therefore has the effect of decreasing the thermodynamic stability as the pseudo-equilibrium curve for Mut2G is shifted to lower denaturant concentrations, and to speed up the unfolding process at the same GuHCl concentration.

This effect could either arise from a direct structural role of His148 [START_REF] Seifert | Backbone dynamics of green fluorescent protein and the effect of histidine 148 substitution[END_REF] or be due to an indirect role of the histidine via the modulation of the protonation of the GFP chromophore and of the hydrogen bonding network inside the chromophore pocket [START_REF] Seifert | Backbone dynamics of green fluorescent protein and the effect of histidine 148 substitution[END_REF][START_REF] Remington | Fluorescent proteins: maturation, photochemistry and photophysics[END_REF].

The Chromophore Fluorescence Does Not Reveal Changes During Unfolding. In order to unveil possible complex behaviour of the slow unfolding kinetics, spectroscopic

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT 16
techniques with different time scales have been employed. The behaviour of the chromophore fluorescence lifetime decay, that remains constant (Figure 2B) during all the kinetics seems suggesting that the quantum yield of the chromophore remains constant during the unfolding process. It is intriguing that the quantum yield does not change even after a long interaction with the denaturating agent since this implies that the rigidity of the chromophore pocket is not affected by the unfolding process unless on a time scale much shorter than the bulk experiments durations (≈1/k obs ) discussed above.

The same conclusion can be drawn from the constancy of the rotational correlation time as derived from FPA measurements of the chromophore fluorescence (Figure 2C). In fact, no wobbling or segmental motion appears during the kinetics at any GuHCl concentration employed. The decrease of the fluorescence signal during the unfolding process observed in bulk solutions is then merely due to the decrease of the number of emitting molecules, and the time scale on which the bright-dark transition (coupled to the unfolding transition) occurs is much shorter than 1/k obs .

An estimate of these characteristic times and of the number of fluorescent molecules can be gained by FCS. The decrease of the value of the average number of molecules <N> in the excitation volume, as derived from Eq(1), is in excellent agreement with the analysis of the fluorescence rate decays reported in Figure 1 in the same conditions. Similar quantitative agreement has been found for the other GuHCl concentrations explored. Also the molecular brightness of the proteins measured at different denaturant concentrations for both the GFP mutants (right panels in Figure 3)

does not change appreciably during the unfolding kinetics, in agreement with the constancy of the fluorescence lifetime and quantum yield as reported in Figure 2B and suggesting again that, on the seconds time scale, the unfolding is an apparently on-off behaviour.

FCS Indicates Large 10 kHz Fluctuations During Unfolding. Since fluorescence correlation spectroscopy probes several time decades (from microseconds to seconds), the presence of new time decay components related to the unfolding process might be revealed. In order to avoid the effect of the chromophore protonation dynamics on the ACFs, measurements have been performed at alkaline pH, where its contribution is negligible.

A C C E P T E D M A N U S C R I P T

As shown in Eq. ( 1) and more extensively discussed in ref. [START_REF] Bosisio | Protonation and conformational dynamics of GFP mutants by two-photon excitation fluorescence correlation spectroscopy[END_REF] the photodynamic components in FCS decay exponentially. No new component is requested when fitting the data in the presence of GuHCl: however the fraction of the proteins that are switched off with characteristic times about 100-200 µs in the presence of GuHCl is found to be almost double that of the native protein. This dynamic component has been suggested to be related in the native state [START_REF] Bosisio | Protonation and conformational dynamics of GFP mutants by two-photon excitation fluorescence correlation spectroscopy[END_REF] to conformational cis-trans transitions of the chromophore [START_REF] Luin | Raman study of chromophore states in photochromic fluorescent proteins[END_REF]. The present finding, of a marked overall increase of its amplitude as soon as GuHCl interaction starts, suggests that (i) either these isomerisation processes become more probable thanks to larger conformational fluctuations in the beta strands when GuHCl is present or (ii) a different mechanism is present during unfolding endowed with a characteristic time that is not separable from the cis-trans transition. The presence of flexibility in the microseconds -milliseconds time scale has been suggested by NMR studies [START_REF] Seifert | Backbone dynamics of green fluorescent protein and the effect of histidine 148 substitution[END_REF], thus reinforcing the second hypothesis. The values of both the characteristic times and the associated fractions are similar for the two mutants investigated, and these values do not show time evolution during the unfolding kinetics: therefore they should be attributed to the opening of a dynamic path of the beta-barrel during the unfolding process. As confirmed by control experiments, the fraction of the dark state does not increase in the presence of 4.0 M NaCl, thereby excluding any effect of chloride ions (data not shown).

TMR FPA Indicates the Occurrence of a Soft Region Involving Strand 3. Since the chromophore fluorescence does not reveal changes before the protein unfolds and then it switches off when it becomes exposed to the solvent, the fluorescence of an extrinsic probe, bound to the free cysteine 48 in strand 3, has been monitored.

FPA decays monitored through TMR fluorescence reveal that the probe has some orientational degrees of freedom that can be followed during the unfolding. By measuring FPA at different GuHCl concentrations, the longer correlation time, that refers to an apparent protein rotation, decreases, whereas it is generally reported that the overall protein encumbrance is expected to show a slight increase (43) upon denaturation. The significant decrease of this apparent rotational time can be accounted for if the motion of the portion of the protein to which TMR is bound decouples from that of the whole protein and therefore the longer rotational correlation time monitors a segmental local

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

18 motion more than an overall rotation. In particular, as shown by Lakowicz [START_REF] Lakowicz | Principles of Fluorescence Spectroscopy[END_REF], when a correlation time shorter than that expected for the entire protein motion is found, a segmental motion completely free (not hindered) is present. The complete anisotropy decay can be theoretically described in this case by the sum of three exponential functions, which take into account the protein rotation (θ P ), the segmental motion (θ S ) and the wobbling motion of TMR at the binding site (θ W ):

r(t) = r 0 g W exp(-t / θ W ) + g S exp(-t / θ S ) + g P [
] exp(-t / θ P ) with relative weights g W +g S +g P = 1. In our case, a weighted sum of two exponential decays,

r(t) = r 0 g 1 exp(-t / θ W app ) + g 2 exp(-t / θ tot ) ⎡ ⎣
⎤ ⎦ describes well the experimental data, and one can identify the relevant parameters as g 1 =g W with θ W app = θ W θ P / (θ W + θ P ) and g 2 ≈(g P +g S ) with θ tot -1 = θ P -1 + g S θ S -1 / (g S + g P ) . In the limit g S >> g P we can estimate an upper limit for the segmental correlation time. In particular at the maximum GuHCl concentration explored, the longer correlation time is 5.5 ns with a fraction of 34% for showing that the secondary structure and the protein stability are not substantially affected by the TMR presence.

These findings agree with the increase of the TMR wobbling weight leading to larger angles spanned by the probe during its motion at the binding site (from 45° to 70° for Mut2 and up to 85° for Mut2G), a picture consistent with a progressive structure loosening which is more pronounced for Mut2G [START_REF] Seifert | Backbone dynamics of green fluorescent protein and the effect of histidine 148 substitution[END_REF]. The process of loosening of strand

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT 19
3 is faster than the global GFP unfolding monitored by the chromophore, but its kinetics also contains a very slow phase (Figure 5), two or threefold slower than the kinetic detected by the chromophore fluorescence decrease, suggesting that even after its fluorescence has been quenched by the solvent, local regions of the protein continue to experience conformational changes.

SUMMARY

In this report we characterize the unfolding kinetics of two GFP mutants on a wide time range, from ns to seconds, exploiting spectroscopic techniques with different dynamic ranges.

The single point mutation introduced in Mut2 to yield Mut2G, in addition to the large effect found in the chromophore protonation dynamics resulting in pronounced shift in the chromophore pK, affects the thermodynamic stability of the protein, and also its kinetics leading, at alkaline pH where protonation is negligible, to a much faster unfolding process. The looser structure of Mut2G is evident both in the larger angle spanned by TMR probe and in the larger contribution of the segmental motion as detected by FPA. This peculiarity of Mut2G could be exploited in the rational design of mutants to coupling improved photochromic properties with dynamical structural flexibility.

Concerning the unfolding process of both mutants, the use of an extrinsic fluorescent probe has allowed to point out that the region around strand 3 of the beta barrel structure looses its rigidity, at least at the level of the hinges between the beta strands, far before the chromophore pocket, that is responsible for the rigidity of the chromophore and therefore for its high fluorescence quantum yield. The characteristic time of the hinge motions falls in the region of nanoseconds. In addition to this motions revealed by the probe segmental motions, a far slower conformational change is also detected in this region that starts to loosen up at very low GuHCl concentrations and continue to increase the decoupling from the whole protein even after the beta-barrel has ceased to prevent the exposure of the chromophore to the solvent, therefore on time scales of thousands of seconds.

On the other side, the conformational fluctuations actually occurring around the chromophore are likely to occur on a time scale of 100-200 µs, as revealed by the This very articulate scenario, encompassing equilibrium and kinetic intermediates, or different time scales depending on the reporter chosen, suggests that GFP unfolding is a very complex process also from the kinetic point of view, accomplishing the picture of a series of potential barriers that have to be overcome in order to unfold, as recently depicted [START_REF] Huang | Stable intermediate states and high energy barriers in the unfolding of GFP[END_REF][START_REF] Andrews | The rough energy landscape of superfolder GFP is linked to the chromophore[END_REF][START_REF] Mickler | Revealing the bifurcation in the unfolding pathways of GFP by using single-molecule experiments and simulations[END_REF].

A C C E P T E D M A N U S C R I P T

f D = exp -m GuHCl [ ] mid -GuHCl [ ] ( ) / RT ( ) 1 + exp -GuHCl [ ] mid -GuHCl [ ] / RT

  Measurements. The unfolding reactions were initiated by manual mixing of protein and denaturant solutions. The kinetics have been followed in the time range of 2-200 minutes monitoring the fluorescence signal. All experiments were carried out at 22±0.5 °C. Microspectrometer Setup. A home assembled micro-spectrometer based on an inverted TE 300 Nikon microscope has been used for fluorescence experiments at nanomolar concentrations, lifetime decay in the time domain and FCS. The two-photon excitation (TPE) source was based on a pulsed Ti:sapphire laser (Tsunami 3960, Spectra Physics, CA) coupled to the microscope. The laser provides 280 fs pulses on the sample plane at a repetition frequency of 80 MHz in the range of 700-1000 nm. GFP mutants have been excited at 890 nm. The fluorescence signal, collected by a Plan Apochromat 60× water objective (NA 1.2, Nikon, Japan), is separated from the excitation beam by a dichroic mirror and further selected by an emission band-pass filter (HQ515/30 or HQ570/30, Chroma Inc., Brattelboro, VT). The fluorescence signal is split by a nonpolarizing 50% cube splitter and fed directly to two single-photon avalanche diode (SPAD) modules (Perkin-Elmer, Canada; model SPCM-AQR15). The minimum values of the radial and axial fwhm of the microscope point spread function (PSF) are 240 ± 40 nm and 780 ± 50 nm, respectively, at a wavelength of 800 nm (28). The excitation volume employed in the following experiments was about 0.85 µm 3 . Fluorescence spectra of samples on the microscope stage were acquired by means of a CCD (DV420A-BV, Andor, IRL)-based spectrometer (MS125, Lot-Oriel, U.K.). Fluorescence Correlation Functions. The autocorrelation functions (ACFs) were acquired by an ALV5000E (ALV, Langen, D) board and analysed by means of the non least-squares routine of the Origin 7.0 software (OriginLab Inc., Northampton, MA).

  photon counting (TCSPC) (Time Harp 200, PicoQuant, Berlin, D) was employed to measure the times of arrival (with respect to the laser pulse) of photons collected from protein solutions by the SPAD module. The full half-height width of the intensity response function is about 350 ps.

8 acquisition

 8 Domain. Dynamic fluorescence measurements were performed on a frequency modulated phase fluorometer (Digital K2, ISS, Champaign, IL). The excitation of GFP and of the TMR dye was primed by the 488-nm or the 514-nm emission lines of an argon ion laser (Spectra Physics, 2025, Mountain View, CA). The laser emission was modulated by a Pockels cell over a frequency range of 10-150 MHz and the data acquired through a digital data A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT board at 400Hz cross-correlation frequency (A2D, ISS, Champaign, IL). The accuracy of the phase angles and modulation ratios was at least 0.2° and 0.004, respectively. The Rayleigh and Raman scattering were cut by band-pass filters that select the sample emission at 515/30 nm (for GFP) and at 560/40 nm for TMR and the sample was kept at 22 ± 0.2°C. For further details, see Collini et al. (30). For the lifetime measurements, the emission polarizer was set at the magic angle position (31). The dependence of the phase shift and the demodulation ratio of the fluorescence signal was measured with respect to the excitation beam as a function of the modulation frequency and can be computed from the Laplace transform L(I) of the intensity decay: (4) where m(ω) and φ(ω) are the modulation ratio and the phase shift of the fluorescence output with respect to the reference one. If a multi-exponential function describes the decay as in Eq.2, the fit of phase shifts and demodulation ratios versus modulation frequency to Eq.4 with L(I )(ω ) = f i / (1 + iωτ i ) i ∑ , gives the parameters of the fluorescence decay τ i and f i .

  aim has been to bring into evidence the fluorescence fluctuations related to the protein structure destabilization during the unfolding process in Mut2 and in its single point mutation Mut2G. Since the protonation equilibrium plays a leading role at pH values close or lower than the protein pK, we chose an alkaline pH value of 8.4 where protonation is negligible and the proteins reside in their anionic highly fluorescent state. GFP Unfolding Kinetics. In order to determine the appropriate denaturant concentrations and time range for the FCS experiments, the unfolding kinetics of Mut2 and Mut2G have been monitored at nanomolar protein concentration by manual mixing of the guanidinium chloride (GuHCl) and protein solutions at alkaline (pH=8.4) pH values by steady-state fluorescence. The equilibrium unfolding curves have been measured by acquiring the fluorescence signal several hours after GuHCl addition (Fig.1A). The curves have been described by a two-state model (continuous lines) obtaining a midpoint GuHCl concentration of 2.4 ± 0.2 M and 1.1 ± 0.1 M for Mut2 and Mut2G, respectively, thus ensuring that at GuHCl concentrations larger than 3M the unfolding rate dominates the reaction. Due to the lack of full reversibility (7) as confirmed by the slow relaxations in equilibrium measurements (13), the curves in Fig.1A should be considered as pseudoequilibrium titrations and therefore we cannot derive meaningful values of the free energy gains involved in the unfolding process. The unfolding kinetics have been obtained either by the fluorescence signal at 510 nm (the peak wavelength of the anionic emission (25)), or by acquiring the whole spectrum A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT 10 with a CCD camera spectrometer (time resolution =1 s). In Figure 1 the kinetics profiles are shown for different GuHCl concentrations for Mut2 (panel B) and Mut2G (panel C).

Figure

  Figure 2B at [GuHCl]=5.5 M and 4.5 M for Mut2 and Mut2G, respectively.Quasi Static Fluorescence Correlation Spectroscopy. FCS autocorrelation

From

  the time behaviour of the fluorescence correlation curves we can instead gain information on the protein structural and chemical dynamics. The diffusive component of the ACFs falls around 0.5-1 ms, depending on the GuHCl concentration that affects the solution viscosity. This component is found constant within the experimental error in all the kinetics investigated, giving a translational diffusion coefficient D ≅ 90±5μm 2 /s in the absence of GuHCl and ranging from 70 to 60 μm 2 /s at GuHCl concentrations o 4.4 M to 5.2 M. However, the translational diffusion coefficient is a parameter that is not very sensitive to protein volume changes, since it scales only as the inverse of the protein effective radius: volume changes within 10% give diffusion coefficient variations of about 3%, which are often within the experimental uncertainty. Under native conditions a single photodynamic component (Eq. 1) can be singled out with a characteristic time of about 100-250 microseconds. The fraction of proteins switching to this dark state, probably due to a cis-trans conformational transition is at most 20-25% at the power level used in the experiments, in agreement with a previous A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT 12 systematic study (25). In the presence of denaturant no additional components are brought into evidence in both mutants but a larger fraction (40-60%) of this fast component is needed to fit the ACFs as shown in the inset of Fig.3B. This cannot be ascribed to Cl -ions specific effects as it has been checked by FCS measurements in the presence of 4 M NaCl (data not shown).

  the FPA decay time does not show any change, as shown in Figure2C. To be noted that no additional wobbling components appear in the FPA decay during the whole unfolding process.TMR Fluorescence Polarization Anisotropy. In order to unveil possible intramolecular motions of the beta-barrel during the whole unfolding process, even after the chromophore has lost its fluorescence, we have monitored the fluorescence of an extrinsic probe, TMR, complexed to GFP. The dye was bound through a thioester bond to the cysteine in position 48, located at the end of the beta-strand 3. The position is optimal to detect hinge motions of the beta-barrel structure in a region that is not closely related to the chromophore environment. In order to ascertain whether TMR labelling at residue 48 could alter GFP stability, we have acquired far UV circular dichroism spectra versus denaturant concentration, shown in the inset of Figure4B, at 0, 1M, 2M and 4M of GuHCl for Mut2.

( 8 )

 8 from which we can infer an wobbling angle of 45 ± 1° for TMR bound to both GFP A C C E P T E D M A N U S C R I P T

  . Mut2G shows a similar behaviour, but lower concentrations of denaturant are needed in order to detect kinetics of the correlation time, as shown in panels E and F for 5.0 M GuHCl, where a characteristic time constant of 1900 s is found. This explains why the values of the rotational correlation times versus GuHCl concentration for Mut2G (Figure4D) do not reach a plateau value as for Mut2: the fast kinetics at moderately high denaturant concentrations leads to a decay of the rotational correlation time on time scales shorter than the time employed to record fluorescence anisotropy data. Therefore the value found for the correlation time is affected also by this slow kinetics.

Mut2 and 3 .( 7 , 32 ,

 3732 0 ns with a fraction of 57% for Mut2G, therefore giving markedly different limiting values of the segmental motion of 8.7 ns and 3.5 ns, respectively. Also this dynamic mode activates much earlier than the overall protein denaturation, in fact the behaviour of the FPA correlation times θ tot versus GuHCl concentration can be fit to a sigmoidal curve for a two-state pseudo-equilibrium unfolding process leading to a midpoint denaturant concentration of [GuHCl] 50% = 0.9 ± 0.2 M and [GuHCl] 50% = 0.4 ± 0.1 for Mut2 and Mut2G, respectively. These values are much lower than those found when monitoring the chromophore fluorescence, (Fig1A) Pioselli et al., manuscript in preparation). An effect of TMR bound to GFP can be ruled out by detecting the circular dichroism signal at different GuHCl concentrations,

  this relaxation component in the fluorescence autocorrelation curves indicating that an increase in the fraction of protein falling in a dark state. Both the hinge (ns) and isomerization (≈100 µs) processes occur during the whole unfolding kinetics.

Figure 1 .

 1 Figure 1. Panel A. Pseudo-equilibrium unfolding curves shown as the denatured fraction of proteins versus GuHCl concentration for Mut2 (full circles) and Mut2G (open triangles). A sigmoidal fit is superimposed to the data according to the expression

  Natural logarithm of the effective unfolding constant, k obs , as a function of GuHCl concentration for Mut2 (full circles) and Mut2G (open triangles). Panel C. Mut2 normalized fluorescence signal at 510 nm at pH=8.4 versus time at different denaturant concentrations: 5.0 M GuHCl (squares), 5.2 M GuHCl (circles), 5.5 M GuHCl (up triangles), 6.0 M GuHCl (down triangles). Panel D. Mut2G normalized fluorescence signal at 510 nm at pH=8.4 versus time at different denaturant concentrations: 4.2 M GuHCl (squares), 4.5 M GuHCl (circles), 5.0 M GuHCl (up triangles), 5.2 M GuHCl (down triangles). The continuous lines represent the two exponential fit of the data in both panels.

Figure 2 .

 2 Figure 2. Panel A: ratio of the fluorescence signal at 510 nm in the presence and in the absence of NaCl versus time at pH 8.4 for Mut2 (full circles) and Mut2G (open triangles). Panel B: ratio of the fluorescence lifetime in the presence and in the absence of GuHCl versus time, at pH 8.4 for Mut2 at 5.5 M GuHCl (closed circles) and Mut2G at 4.5 M GuHCl (open triangles). Panel C: ratio of the rotational correlation time probed by the chromophore fluorescence in the absence and in the presence of GuHCl in the same conditions as panel B versus time. Panel D: rotational correlation time probed by the chromophore fluorescence, rescaled according to the solution viscosity, at increasing GuHCl concentration. The symbols are the same as in panel B.

Figure 3 .

 3 Figure 3. Panel A: fluorescence ACFs at increasing time after the addition of 5.2 M GuHCl for Mut2 at pH=8.4. The continuous lines are the fit according to Eq. (1). The curve with full symbols represents the ACF in the absence of GuHCl. Panel B: fluorescence ACFs at increasing time after the addition of 4.4 M GuHCl for Mut2G at pH=8.4. The continuous lines are best fit of the data according to Eq. (1). The curve with

Figure 4 .

 4 Figure 4. Upper panels: differential phase angles (left axis, full symbols) and demodulation ratios (right axis, open symbols) versus modulation frequency at increasing GuHCl concentration from 0 to 6.0 M at pH 8.4 for Mut2 (panel A, circles) and Mut2G (panel B, triangles). In panel A, the stars refer to the addition of 4.0 M NaCl to Mut2. Lower panels: longer relaxation time of the FPA decay versus denaturant concentration as derived from a two exponential data fitting for Mut2 (panel C, circles) and Mut2G (panel D, triangles). The continuous lines represent a sigmoidal fit as discussed in the text. Inset in panel B: residue molar ellipticity (deg cm 2 dmol -1 ) of TMR-Mut2 at different denaturant concentrations: from bottom to top, 0 M, 1M, 2 M 4 M GuHCl.

Figure 5 . 1 . 4 A

 514 Figure 5. Panel A: time-dependence of the rotational correlation times of Mut2 in 5.0 M GuHCl, as derived by fitting the raw data shown in panel B (differential phase angles, left axis, full circles, and modulation ratios, right axis, open circles) versus modulation frequency at different times. Panel C: rotational correlation times for Mut2 in 6.0 M GuHCl versus time. The raw data are shown in panel D (differential phase angles, left axis, full circles, and modulation ratios, right axis, open circles) versus modulation frequency. Panel E: rotational correlation times for Mut2G in 5.0 M GuHCl versus time. The raw data are shown in panel F (differential phase angles, left axis, full triangles, and modulation ratios, right axis, open triangles) versus modulation frequency.

Table 1 .

 1 Fluorescence anisotropy decay parameters for GFP mutants.

	Mutant	θ 1 (ns) g 1 (%) θ 2 (ns) g 2 (%)	r 0	R eff (nm)
	Mut2	13.6 ± 0.1 100	-	-	0.390 ± 0.001 2.37 ± 0.01
	Mut2G	14.4 ± 0.2 100	-	-	0.390 ± 0.001 2.43 ± 0.02
	TMR-Mut2	15.0 ± 0.5 38 ± 2 0.7 ± 0.2 62 ± 2 0.300 ± 0.002 2.45 ± 0.03
	TMR-Mut2G 15.4 ± 0.5 34 ± 2 0.7 ± 0.2 66 ± 3 0.324 ± 0.005 2.47 ± 0.03
	FPA decay parameters for both GFP mutants at pH=8.4 in the absence of GuHCl. The
	first two rows refer to FPA decay acquired through the chromophore fluorescence
	(515/30 nm), the last two rows refer to FPA decay acquired through TMR fluorescence
	(560/40 nm).

ACCEPTED MANUSCRIPT *Graphical Abstract

Acknowledgments. This research has been partially funded by a PRIN Project 2008 (to M.C. and S.B.).


Y Boichut

B Boyer

T Genet

A Legay

Equational Abstraction Refinement for Certified Tree Regular Model Checking

Tree Regular Model Checking (TRMC) is the name of a family of techniques for analyzing infinite-state systems in which states are represented by trees and sets of states by tree automata. The central problem is to decide whether a set of bad states belongs to the set of reachable states. An obstacle is that this set is in general neither regular nor computable in finite time. This paper proposes a new CounterExample Guided Abstraction Refinement (CEGAR) algorithm for TRMC. Our approach relies on a new equational-abstraction based completion algorithm to compute a regular overapproximation of the set of reachable states in finite time. This set is represented by R /E -automata, a new extended tree automaton formalism whose structure can be exploited to detect and remove false positives in an efficient manner. Our approach has been implemented in TimbukCEGAR, a new toolset that is capable of analyzing Java programs by exploiting an elegant translation from the Java byte code to term rewriting systems. Experiments show that TimbukCEGAR outperforms existing CEGAR-based completion algorithms. Contrary to existing TRMC toolsets, the answers provided by TimbukCEGAR are certified by Coq, which means that they are formally proved correct.

Introduction

Infinite-state models are often used to avoid potentially artificial assumptions on data structures and architectures, e.g. an artificial bound on the size of a stack or on the value of an integer variable. At the heart of most of the techniques that have been proposed for exploring infinite state spaces, is a symbolic representation that can finitely represent infinite sets of states. In this paper, we rely on Tree Regular Model Checking (TRMC) [START_REF] Bouajjani | Extrapolating tree transformations[END_REF][START_REF] Kesten | Symbolic model checking with rich assertional languages[END_REF], and assume that states of the system are represented by trees and sets of states by tree automata. The transition relation of the system is represented by a set of rewriting rules. Contrary to approaches that are dedicated to specific applications, TRMC is generic and expressive enough to describe a broad class of communication protocols [START_REF] Abdulla | Simulation-based iteration of tree transducers[END_REF], various C programs [START_REF] Bouajjani | Abstract rmc of complex dynamic data structures[END_REF] with complex data structures, multi-threaded programs [START_REF] Patin | Spade: Verification of multithreaded dynamic and recursive programs[END_REF], cryptographic protocols [START_REF] Genet | Rewriting for Cryptographic Protocol Verification[END_REF][START_REF] Genet | Verification of Copy Protection Cryptographic Protocol using Approximations of Term Rewriting Systems[END_REF][START_REF]Avispa -a tool for Automated Validation of Internet Security Protocols[END_REF], and Java [START_REF] Boichut | Rewriting Approximations for Fast Prototyping of Static Analyzers[END_REF].

In TRMC, the central objective is to decide whether a set of states representing some state property belongs to the set of reachable states. An obstacle is that this set is in general neither regular nor computable in a finite time. Most existing solutions rely on computing the transitive closure of the transition relation of the systems through heuristic-based semi-algorithms [START_REF] Kesten | Symbolic model checking with rich assertional languages[END_REF][START_REF] Abdulla | Simulation-based iteration of tree transducers[END_REF], or on the computation of some regular abstraction of the set of reachable states [START_REF] Bouajjani | Extrapolating tree transformations[END_REF][START_REF] Bouajjani | Abstract rmc of complex dynamic data structures[END_REF]. While the first approach is precise, it is acknowledged to be ineffective on complex systems. This paper focuses on the second approach.

The first abstraction-based technique for TRMC, Abstract Tree Regular Model Checking (ATRMC), was proposed by Bouajjani et al [START_REF] Bouajjani | Abstract regular model checking[END_REF][START_REF] Bouajjani | Abstract regular tree model checking[END_REF][START_REF] Bouajjani | Abstract rmc of complex dynamic data structures[END_REF]. ATRMC computes sequences of automata by successive applications of the rewriting relation to the automaton representing the initial set of states. After each computation step, techniques coming from predicate abstraction are used to over-approximate the set of reachable states. If the property holds on the abstraction, then it also holds on the concrete system. Otherwise, a counter-example is detected and the algorithm has to decide if it is a false positive or not. In case of a spurious counter-example, the algorithm refines the abstraction by backward propagation of the set of rewriting rules. The approach, which may not terminate, proceeds in a CounterExample Guided Abstraction Refinement fashion by successive abstraction/refinement until a decision can be taken. The approach has been implemented in a toolset capable, in part, to analyse C programs. Independently, Genet et al. [START_REF] Genet | Decidable approximations of sets of descendants and sets of normal forms[END_REF] proposed Completion that is another technique to compute an over-approximation of the set of reachable states. Completion exploits the structure of the term rewriting system to add new transitions in the automaton and obtain a possibly overapproximation of the set of one-step successor states. Completion leads to a direct application of rewriting rules to the automaton, while other approaches rely on possibly heavy applications of sequences of transducers to represent this step. Completion alone may not be sufficient to finitely compute the set of reachable states. A first solution to this problem is to plug one of the abstraction techniques implemented in ATRMC. However, in this paper, we prefer another solution that is to apply equational abstraction [START_REF] Meseguer | Equational abstractions[END_REF]. There, the merging of states is induced by a set of equations that largely exploit the structure of the system under verification and its corresponding TRS, hence leading to accurate approximations. We shall see that, initially, such equations can easily be derived from the structure of the system. Later, they are refined automatically with our procedure without manual intervention. Completion with equational abstraction has been applied to very complex case studies such as the verification of (industrial) cryptography protocols [START_REF] Genet | Rewriting for Cryptographic Protocol Verification[END_REF][START_REF] Genet | Verification of Copy Protection Cryptographic Protocol using Approximations of Term Rewriting Systems[END_REF] and Java bytecode applications [START_REF] Boichut | Rewriting Approximations for Fast Prototyping of Static Analyzers[END_REF]. CEGAR algorithms based on equational-abstraction completion exist [START_REF] Boichut | Finer is better: Abstraction refinement for rewriting approximations[END_REF][START_REF] Boichut | Characterizing conclusive approximations by logical formulae[END_REF], but are known to be inefficient.

In this paper, we design the first efficient and certified CEGAR framework for equational-abstraction based completion algorithm. Our approach relies on R /E -automata, that is a new tree automaton formalism for representing sets of reachable states. In R /E -automata, equational abstraction does not merge states, but rather links them with rewriting rules labeled with equations. Such technique is made easy by exploiting the nature of the completion step. During completion steps, such equations are propagated, and the information can be used to efficiently decide whether a set of terms is reachable from the set of initial states. If the procedure concludes positively, then the term is indeed reachable. Else, one has to refine the R /E -automaton and restart the process again.

Our approach has been implemented in TimbukCEGAR. (T)RMC toolsets result from the combination of several libraries, each of them being implemented with thousands of lines of code. It is thus impossible to manually prove that those tools deliver correctly answers. A particularity of TimbukCEGAR is that it is certified. In order to ensure that the whole set of reachable states has been explored, any TRMC technique needs to check whether a candidate overapproximation B is indeed a fixed point, that is if L(B ) ⊇ R * (L(A)). Such check has been implemented in various TRMC toolsets, but there is no guarantee that it behaves correct. In [START_REF] Boyer | Certifying a Tree Automata Completion Checker[END_REF], a checker for tree automata completion was designed and proved correct using the Coq [START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF] proof assistant. Any automaton B that passes the checker can be claimed to formally satisfy the fixed point. TimbukCEGAR implements an extension of [START_REF] Boyer | Certifying a Tree Automata Completion Checker[END_REF] for R /E -automata, which means that the tool delivers correct answers. Our TimbukCEGAR is capable, in part, of analyzing Java programs by exploiting a elegant translation from the Java bytecode to term rewriting systems. Experiments show that TimbukCEGAR outperforms existing CEGAR-based completion algorithms by orders of magnitude.

Related work. Regular Model Checking (RMC) was first applied to compute the set of reachable states of systems whose configurations are represented by words [START_REF] Bouajjani | Regular model checking[END_REF][START_REF] Boigelot | Iterating transducers in the large (extended abstract)[END_REF][START_REF] Dams | Iterating transducers[END_REF]. The approach was then extended to trees and applied to very simple case studies [START_REF] Abdulla | Simulation-based iteration of tree transducers[END_REF][START_REF] Bouajjani | Extrapolating tree transformations[END_REF]. Other regular model checking works can be found in [START_REF] Abdulla | Parameterized verification of infinitestate processes with global conditions[END_REF][START_REF] Abdulla | Parameterized tree systems[END_REF], where an abstraction of the transition relation allows to exploit well-quasi ordering for finite termination. Such techniques may introduce false positives; a CEGAR approach exists for the case of finite word [START_REF] Abdulla | Constrained monotonic abstraction: A cegar for parameterized verification[END_REF], but not for the one of trees. Learning techniques apply to RMC [START_REF] Vardhan | Using language inference to verify omega-regular properties[END_REF][START_REF] Vardhan | Lever: A tool for learning based verification[END_REF] but trees have not yet been considered. We mention that our work extends equational abstractions [START_REF] Meseguer | Equational abstractions[END_REF][START_REF] Takai | A Verification Technique Using Term Rewriting Systems and Abstract Interpretation[END_REF] with counter-example detection and refinement. We mention the existence of other automata-based works that can handle a specific class of system [START_REF] Patin | Spade: Verification of multithreaded dynamic and recursive programs[END_REF]. CEGAR principles have been implemented in various tools such as ARMC [START_REF] Podelski | Armc: The logical choice for software model checking with abstraction refinement[END_REF] or SLAM [START_REF] Ball | Slam and static driver verifier: Technology transfer of formal methods inside microsoft[END_REF]. Those specific tools are more efficient than our approach. On the other hand, RMC and rewriting rules offers a more general framework in where the abstraction and the refinements can be computed in a systematic manner.

Structure of the paper. Section 2 introduces the basic definitions and concepts used in the paper. TRMC and Completion are introduced in Section 3. R /E -automata are introduced in Section 4. A new completion procedure is then defined in Section 5. Section 6 proposes a CEGAR approach for TRMC and Completion. Section 7 presents TimbukCEGAR. Section 8 concludes the paper and discusses future research. Due to space constraints proofs are reported in [START_REF] Boichut | Fast Equational Abstraction Refinement for Regular Tree Model Checking[END_REF].

Background

In this section, we introduce some definitions and concepts that will be used throughout the rest of the paper (see also [START_REF] Baader | Term Rewriting and All That[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF][START_REF] Gilleron | Regular tree languages and rewrite systems[END_REF]). Let F be a finite set of symbols, each associated with an arity function, and let X be a countable set of variables. T (F, X ) denotes the set of terms and T (F) denotes the set of ground terms (terms without variables). The set of variables of a term t is denoted by Var(t). A substitution is a function σ from X into T (F, X ), which can be uniquely extended to an endomorphism of T (F, X ). A position p for a term t is a word over N. The empty sequence λ denotes the top-most position. A term rewriting system (TRS) R is a set of rewrite rules l → r, where l, r ∈ T (F, X ), l ∈ X , and Var(l) ⊇ Var(r). A rewrite rule l → r is left-linear (resp. right-linear) if each variable of l (resp. r) occurs only once in l. A TRS R is left-linear if every rewrite rule l → r of R is left-linear. A TRS R is said to be linear iff R is left-linear and right-linear. The TRS R induces a rewriting relation → R on terms as follows. Let s, t ∈ T (F, X ) and l → r ∈ R, s → R t denotes that there exists a position p ∈ Pos(s) and a substitution σ such that s| p = lσ and t = s[rσ] p . The reflexive transitive closure of → R is denoted by → * R and s → ! R t denotes that s → * R t and t is irreducible by R. The set of R-descendants of a set of ground terms

I is R * (I) = {t ∈ T (F) | ∃s ∈ I s.t. s → * R t}.
An equation set E is a set of equations l = r, where l, r ∈ T (F, X ). The relation = E is the smallest congruence such that for all substitution σ we have lσ = rσ. Given a TRS R and a set of equations E, a term s ∈ T (F) is rewritten modulo E into t ∈ T (F), denoted s → R/E t, if there exist s ∈ T (F) and t ∈ T (F) such that s = E s → R t = E t. Thus, the set of R-descendants modulo E of a set of ground terms

I is R /E * (I) = {t ∈ T (F) | ∃s ∈ I s.t. s → * R/E t}.
Let Q be a finite set of symbols with arity 0, called states, such that Q ∩F = ∅. T (F ∪ Q) is called the set of configurations. A transition is a rewrite rule c → q, where c is a configuration and q is state. A transition is normalized when c = f (q 1 , . . . , q n ), f ∈ F is of arity n, and q 1 , . . . , q n ∈ Q. A ε-transition is a transition of the form q → q where q and q are states. A bottom-up nondeterministic finite tree automaton (tree automaton for short) over the alphabet

F is a tuple A = F, Q, Q F , ∆ , where Q F ⊆ Q, ∆
is a set of normalized transitions and ε-transitions. The transitive and reflexive rewriting relation on

T (F ∪ Q) induced by all the transitions of A is denoted by → * A . The tree lan- guage recognized by A in a state q is L(A, q) = {t ∈ T (F) | t → * A q}. We define L(A) = q∈Q F L(A, q).

Tree Regular Model Checking with Completion

We first introduce Tree Regular Model Checking (TRMC), a tree automata based framework to represent possibly infinite-state systems. In TRMC, a program is represented by a tuple (F, A, R), where F is an alphabet on which a set of terms T (F) can be defined; A is the tree automaton representing a possibly infinite set of configurations I, and R is a set of term rewriting rules that represent a transition relation Rel. We consider the following problem.

Definition 1 (Reachability Problem (RP)). Consider a program (F, A, R) and a set of bad terms Bad. The Reachability Problem consists in checking whether there exists a term of R * (L(A)) that belongs to Bad.

For finite-state systems, computing the set of reachable terms (R * (L(A))) reduces to enumerating the terms that can be reached from the initial set of configurations. For infinite-state systems, acceleration-based methods are needed to perform this possibly infinite enumeration in a finite time. In general, such accelerations are not precise and the best one can obtain is an R-closed approximation

A * R . A tree automaton A * R is R-closed if for all terms s, t ∈ T (F) such that s → R t and s is recognized by A * R into state q then so is t. It is easy to see that if A * R is R-closed and L(A * R ) ⊇ L(A), then L(A * R ) ⊇ R * (L(A)).
A wide range of acceleration techniques have been developed, most of them have been discussed in Section 1. Here, we focus on Completion [START_REF] Genet | Decidable approximations of sets of descendants and sets of normal forms[END_REF], whose objective is to computes successive automata

A 0 R = A, A 1 R , A 2 R , .
. . that represent the effect of applying the set of rewriting rules to the initial automaton. To compute infinite sets in a finite time, each completion step is followed by a widening operator. More precisely, each application of R, which is called a completion step, consists in searching for critical pairs t, q with s → R t, s → * A q and t → * A q. The idea being that the algorithm solves the critical pair by building from A i R , a new tree automaton A i+1 R with the additional transitions that represent the effect of applying R. As the language recognized by A may be infinite, it is not possible to find all the critical pairs by enumerating the terms that it recognizes. The solution that was promoted in [START_REF] Genet | Decidable approximations of sets of descendants and sets of normal forms[END_REF] consists in applying sets of substitutions σ : X → Q mapping variables of rewrite rules to states that represent infinite sets of (recognized) terms. Given a tree automaton A i R and a rewrite rule l → r ∈ R, to find all the critical pairs of l → r on A i R , completion uses a matching algorithm [START_REF] Feuillade | Reachability Analysis over Term Rewriting Systems[END_REF] that produces the set of substitutions σ : X → Q and states q ∈ Q such that lσ → *

A i R q and rσ → * A i R q.
Solving critical pairs thus consists in adding new transitions: rσ → q and q → q. Those new transitions may have to be normalized in order to satisfy the definition of transitions of tree automata (see [START_REF] Feuillade | Reachability Analysis over Term Rewriting Systems[END_REF] for details). As it was shown in [START_REF] Genet | Decidable approximations of sets of descendants and sets of normal forms[END_REF], this operation may add not only new transitions but also new states to the automaton. In the rest of the paper, the completion-step operation will be represented by C, i.e., the automaton obtained by applying the completion step to

A i R is denoted C(A i R ).
Observe that when considering right-linear rewriting rules, we have that C is precise, i.e. it does not introduce in A i+1 R terms that cannot be obtain from A i R by applying the set of rewriting rules. Observe also that if the system is non left-linear, then completion step may not produce all the reachable terms. Non left-linear rules will not be considered in the present paper.

The problem is that, except for specific classes of systems [START_REF] Feuillade | Reachability Analysis over Term Rewriting Systems[END_REF][START_REF] Genet | Reachability analysis of rewriting for software verification[END_REF], the automaton representing the set of reachable terms cannot be obtained by applying a finite number of completion steps. The computation process thus needs to be accelerated. For doing so, we apply a widening operator W that uses a set E of equations5 to merge states and produce an R-closed automaton that is an over-approximation of the set of reachable terms, i.e., an automaton

A * R,E such that L(A * R,E ) ⊇ R * (L(A)
). An equation u = v is applied to a tree automaton A as follows: for all substitution σ : X → Q and distinct states q 1 and q 2 such that uσ → * A q 1 and vσ → * A q 2 , states q 1 and q 2 are merged. Completion and widening steps are applied, i.e.,

A i+1 R,E = W(C(A i R,E )), until a R-closed fixpoint A *
R,E is found. Our approximation framework and methodology are close to the equational abstractions of [START_REF] Meseguer | Equational abstractions[END_REF]. In [START_REF] Genet | Equational tree automata completion[END_REF], it has been shown that, under some assumptions, the widening operator may be exact, i.e., does not add terms that are not reachable.

Example 1. Let R = {f (x) → f (s(s(x))
)} be a rewriting system, E = {s(s(x)) = s(x)} be an equation, and

A = F, Q, Q F , ∆ be a tree automaton with Q F = {q 0 } and ∆ = {a → q 1 , f (q 1 ) → q 0 }, i.e. L(A) = {f (a)}.
The first completion step finds the following critical pair: f (q 1 ) → * A q 0 and f (s(s(q 1 ))) → * A q 0 . Hence, the completion algorithm produces A 1 R = C(A) having all transitions of A plus {s(q 1 ) → q 2 , s(q 2 ) → q 3 , f (q 3 ) → q 4 , q 4 → q 0 } where s(s(q 1 ))

A 1 R * s(q 1 ) * A 1 R q 3 q 2
q 2 , q 3 , q 4 are new states produced by normalization of f (s(s(q 1 ))) → q 0 . Applying W with the equation s(s

(x)) = s(x) on A 1 R is equivalent to rename q 3 into q 2 . The set of transitions of A 1 R,E is thus ∆ ∪ {s(q 1 ) → q 2 , s(q 2 ) → q 2 , f (q 2 ) → q 4 , q 4 → q 0 }. Completion stops on A 1 R,E that is R-closed, and thus A * R,E = A 1 R,E .
Observe that if the intersection between A * R,E and Bad is not empty, then it does not necessarily mean that the system does not satisfy the property. Consider a set Bad = {f (s(a)), f (s(s(a)))}, the first term of this set is not reachable from A, but the second is. There is thus the need to successively refine the Rclosed automaton. The latter can be done by using a CounterExample Guided Abstraction Refinement algorithm (CEGAR). Developing such an algorithm for completion and equational abstraction is the objective of this paper.

R /E -Automata

Existing CEGAR approaches [START_REF] Bouajjani | Abstract regular model checking[END_REF][START_REF] Bouajjani | Abstract regular tree model checking[END_REF][START_REF] Bouajjani | Abstract rmc of complex dynamic data structures[END_REF][START_REF] Boichut | Finer is better: Abstraction refinement for rewriting approximations[END_REF] check for spurious counter examples by performing a sequence of applications of the rewriting rules to A * R,E . To avoid this potentially costly step, we suggest to replace the merging of states by the addition of new rewriting rules giving information on the merging through equations. Formally:

Definition 2 (R /E -automaton). Given a TRS R and a set E of equations, an R /E -automaton A is a tuple F, Q, Q F , ∆∪ε R ∪ε E . ∆ is a set of normalized transitions. ε E is a set of ε-transitions. ε R is a set of ε-transitions labeled by
or conjunctions over predicates of the form Eq(q, q ) where q, q ∈ Q, and q → q ∈ ε E .

Set ε R is used to distinguish a term from its successors that has been obtained by applying one or several rewriting rules. Instead of merging states according to the set of equations, A links them with epsilon transitions in ε E . During the completion step, when exploiting critical pairs, the combination of transitions in ε E generates transition in ε R that are labeled with a conjunction of equations representing those transitions in ε E . In what follows, we use → * ∆ to denote the transitive and reflexive closure of ∆. Given a set ∆ of normalized transitions, the set of representatives of a state q is defined by

Rep(q) = {t ∈ T (F)|t → * ∆ q}.
Definition 3 (Run of a R /E -automaton A).

-t| p = f (q 1 , . . . , q n ) and f (q 1 , . . . , q n ) → q ∈ ∆ then t -→ A t[q] p -t| p = q and q → q ∈ ε E then t

Eq(q,q ) -----→ A t[q ] p -t| p = q and q α -→ q ∈ ε R then t α -→ A t[q ] p -u α -→ A v and v α -→ A w then u α∧α ---→ A w Theorem 1. ∀t ∈ T (F ∪ Q), q ∈ Q, t α -→ A q ⇐⇒ t → * A q
A run α -→ abstracts a rewriting path of → R/E . If t α -→ q, then there exists a term s ∈ Rep(q) such that s → * R/E t. The formula α denotes the subset of transitions of ε E needed to recognize t into q.

Example 2. Let I = f (a) be an initial set of terms, R = {f (c) → g(c), a → b} be a set of rewriting rules, and E = {b = c} be a set of equations. We build A an overapproximation automaton for R * (I), using E. Thanks to ε-transitions, the automaton A represented in Fig. 1 contains some information about the path used to reach terms using R and E. Each state has a representative term from which others are obtained. The equality b = c is represented by the two transitions q c → q b and q b → q c of ε E , taking into account that b and c are the representatives terms for states q b and q c , respectively. Consider now State q c , Transition q b → q c indicates that the term b is obtained from Term c by using the equality. Conversely, Transition q c → q b leads to the conclusion that Term c is obtained from Term b.

q f q g f ( q a ) g( q c ) q a q b q c a b c Eq(qc, q b ) = = Fig. 1: Automaton A
The transition q b → q a denotes that the term b is a descendant of a by rewriting.

Using Definition 3, the runs f (c)

Eq(qc,q b ) ------→ q f indicates that to obtain f (c) from f (a) -the representative term of q f -we used the equality b = c, which is obtained from q c → q b . We indeed observe f (a) → R f (b) = E f (c). If we now consider the transition q g → q f we labeled the transition with the formula Eq(q c , q b ). To reach g(c) from f (a), we rewrite f (c). We have seen this term is reachable thanks to the equivalence relation induced by b = c. By transitivity, this equivalence is also used to reach the term g(c). We thus label the transition of ε R to save this information. We obtain the run g(c)

Eq(qc,q b ) ------→ q f . We observe that the transition q b → q a is labeled by the formula since b is reachable from a without any equivalence. By congruence, so is f (b) from f (a). The run

f (b) -→ q f denotes it.
We now introduce a property that will be used in the refinement procedure to distinguish between counter-examples and false positives. Definition 4 (A well-defined R /E -automaton). A is a well-defined R /Eautomaton, if :

-For all states q of A, and all terms v such that v -→ A q, there exists u a term representative of q such that u → * R v -If q φ -→ q is a transition of ε R , then there exist terms s, t ∈ T (F) such that s φ → A q, t → A q and t → R s.

The first item in Definition 4 guarantees that every term recognized by using transitions labeled with the formula is indeed reachable from the initial set. The second item is used to refine the automaton. A rewriting step of → R/E denoted by q φ -→ q holds thanks to some transitions of ε E that occurs in φ. If we remove transitions in ε E in such a way that φ does not hold, then the transition q φ -→ q should also be removed.

According to the above construction, a term t that is recognized by using at least a transition labeled with a formula different from can be removed from the language of the R /E -automaton by removing some transitions in ε E . This "pruning" operation will be detailed in Section 6.

Solving the Reachability Problem with R /E -automaton

In this section, we extend the completion and widening principles introduced in Section 3 to take advantage of the structure of R /E -automata. We consider an initial set I that can be represented by a tree automaton A 0 R,E = F, Q 0 , Q F , ∆ 0 , and transition relation represented by a set of linear rewriting rules R. In the next section, we will see that the right-linearity condition may be relaxed using additionnal hypotheses. We compute successive approximations

A i R,E = F, Q i , Q f , ∆ i ∪ε i R ∪ε i E from A 0 R,E using A i+1 R,E = W(C(A i R,E )). Observe that A 0
R,E is well-defined as the sets ε 0 R and ε 0 E are empty.

The Completion step C

Extending completion to R /E -automaton requires to modify the concept of critical pair and so the algorithm to compute them. A critical pair for a R /Eautomaton is a triple rσ, α, q such that lσ → rσ, lσ α -→ A i R,E q and there is no formula α such that rσ α -→ A i R,E q. The resolution of such a critical pair consists of adding to C(A i R,E ) the transitions to obtain rσ

α -→ C(A i R,E
) q. This is followed by a normalization step Norm whose definition is similar to the one for classical tree automata.

Definition 5 (Normalization). The normalization is done in two mutually inductive steps parametrized by the configuration c to recognize, and by the set of transitions ∆ to extend. Let Q ∆ new be a set of (new) states not occurring in ∆.

       Norm(c, ∆) = Slice(d, ∆), for one d s.t. c → * ∆ d, with c, d ∈ T (F ∪ Q) Slice(q, ∆) = ∆, q ∈ Q Slice(f (q 1 , . . . , q n ), ∆) = ∆ ∪ {f (q 1 , . . . , q n ) → q}, q i ∈ Q and one q ∈ Q ∆ new Slice(f (t 1 , . . . , t n ), ∆) = Norm(f (t 1 , . . . , t n ), Slice(t i , ∆)), ∃t i ∈ T (F ∪ Q) \ Q Definition 6 (Resolution of a critical pair). Given a R /E -automaton A = F, Q, Q f , ∆ ∪ ε R ∪ ε E and a critical pair p = rσ, α, q , the resolution of p on A is the R /E -automaton A = F, Q , Q f , ∆ ∪ ε R ∪ ε E where -∆ = ∆ ∪ Norm(rσ, ∆ \ ∆ 0 ); -ε R = ε R ∪ {q α -→ q}
where q is the state such that rσ → ∆ \∆0 q ; -Q is the union of Q with the set of states added when creating ∆ .

Note that ∆ 0 , the set of transitions of A 0 R , is not used in the normalization process. This is to guarantee that A is well-defined. The R /E -automaton C(A i R,E ) is obtained by recursively applying the above resolution principle to all critical pairs p of the set of critical pairs between R and A i R,E . The set of all critical pairs is obtained by solving the matching problems l q for all rewrite rules l → r ∈ R and all states q ∈ A i R,E . Solving l q is performed in two steps. First, one computes S, that is the set of all pairs (α, σ) such that α is a formula, σ is a substitution of X → Q i , and lσ α -→ q. The formula α is a conjunction of Predicates Eq(q , q ) that denotes the used transitions of ε E to rewrite lσ in q, in accordance with Definition 3. Due to space constraints the algorithm, which always terminates, can be found in [START_REF] Boichut | Fast Equational Abstraction Refinement for Regular Tree Model Checking[END_REF].

Second, after having computed S for l q, we identify elements of the set that correspond to critical pairs. By definition of S, we know that there exists a transition lσ α -→ A i R,E q for (α, σ) ∈ S. If there exists a transition rσ α -→ A i R,E q, then rσ has already been added to A i R,E . If there does not exist a transition of the form rσ α -→ A i R,E q, then rσ, α , q is a critical pair to solve on A i R,E . The following theorem shows that our methodology is complete.

Theorem 2. If A i R,E is well-defined then so is C(A i R,E ), and ∀q ∈ Q i , ∀t ∈ L(A i R,E , q), ∀t ∈ T (F), t → R t =⇒ t ∈ L(C(A i R,E ), q). Example 3. Let R = {f (x) → f (s(s(x)
))} be a set of rewriting rules and A 0 R,E = F, Q, Q F , ∆ 0 be a tree automaton such that Q F = {q 0 } and ∆ 0 = {a → q 1 , f (q 1 ) → q 0 }. The solution of the matching problem f (x) q 0 is S = {(σ, φ)}, with σ = {x → q 1 } and φ = . Hence, since f (s(s(q 1 ))) -→ A 0 R,E q 0 , f (s(s(q 1 ))), , q 0 is the only critical pair to be solved. So, we have

C(A 0 R,E ) = F, Q 1 , Q F , ∆ 1 ∪ ε 1 R ∪ ε 0 E , with: ∆ 1 = Norm(f (s(s(q 1 ))), ∅) ∪ ∆ 0 = {s(q 1 ) → q 2 , s(q 2 ) → q 3 , f (q 3 ) → q 4 } ∪ ∆ 0 , ε 1 R = {q 4 -→ q 0 }, since f (s(s(q 1 ))) → ∆ 1 \∆ 0 q 4 , ε 0 E = ∅ and Q 1 = {q 0 , q 1 , q 2 , q 3 , q 4 }. Observe that if C(A i R,E ) = A i R,E
, then we have reached a fixpoint.

The Widening Step

W Consider a R /E -automaton A = F, Q, Q f , ∆ ∪ ε R ∪ ε E , the widening consists in computing a R /E -automaton W(A) that is obtained from A by using E.
For each equation l = r in E, we consider all pair (q, q ) of distinct states of Q i such that there exists a substitution σ to obtain the following diagram. Observe that = -→ A , the transitive and reflexive rewriting relation induced by ∆ ∪ ε E , defines particular runs which exclude transitions of ε R . This allows us to build a more accurate approximation. The improvement in accurary is detailed in [START_REF] Genet | Equational tree automata completion[END_REF].

lσ E = A rσ = A q q
Intuitively, if we have u = -→ A q, then we know that there exists a term t of Rep(q) such that t = E u. The automaton W(A) is given by the tuple

F, Q, Q f , ∆ ∪ ε R ∪ ε E ,
where ε E is obtained by adding the transitions q → q and q → q to ε E (for each pair (q, q )).

Theorem 3. Assuming that A is well-defined, we have A syntactically included in W(A), and W(A) is well-defined.

Example 4. Consider the R /E -automaton C(A 0 R,E ) given in Example 3. Using Equation s(s(x)) = s(x), we compute A 1 R,E = W(C(A 0 R,E )).
We have σ = {x → q 1 } and the following diagram. We then obtain

A 1 R,E = F, Q 1 , Q f , ∆ 1 ∪ε 1 R ∪ ε 1 E , where ε 1 E = ε 0 E ∪ {q 3 → q 2 , q 2 → q 3 } and ε 0 E = ∅.
s(s(q 1 ))

E = C(A 0 R,E ) s(q 1 ) = C(A 0 R,E ) q 3 q 2 Observe that A 1 R,E is a fixpoint, i.e., C(A 1 R,E ) = A 1 R,E .
6 A CEGAR procedure for R /E -automata

Let R be a TRS, I be a set of initial terms characterized by the R /E -automaton A 0 R,E and Bad the set of forbidden terms represented by A Bad . We now complete our CEGAR approach by proposing a technique that checks whether a term is indeed reachable from the initial set of terms. If the term is a spurious counterexample i.e. a counter-example of the approximation, then it has to be removed from the approximation automatically, else one can deduce that the involved term is actually reachable.

Let

A k R,E = F, Q k , Q f , ∆ k ∪ ε k R ∪ ε k E be a R /E
-automaton obtained after k steps of completion and widening from A 0 R,E and assume that

L(A k R,E ) ∩ Bad = ∅. Let S A k
R,E ∩A Bad be a set of triples q, q , φ where q is a final state of A k R,E , q is a final state of A Bad and φ is a formula on transitions of ε k E and such that for each triple (q, q , φ), the formula φ holds if and only if there exists

t ∈ L(A k R,E , q) ∩ L(A Bad , q ) and t φ -→ A k R,E q. Note that S A k R,E
∩A Bad can be obtained using an intersection based algorithm defined in [START_REF] Boichut | Fast Equational Abstraction Refinement for Regular Tree Model Checking[END_REF]. We consider two cases. First, as A k R,E is well-defined, if φ = , we deduce that t is indeed a reachable term. Otherwise, φ is a formula whose atoms are of the form Eq(q j , q j ), and t is possibly a spurious counter-example, and the run t

φ -→ A k R,E q must be re- moved. Refinement consists in computing a pruned version P(A k R,E , S A k R,E ∩A Bad ) of A k R,E . Definition 7. Given an R /E -automaton A = F, Q, Q F , ∆ 0 ∪ ∆ ∪ ε R ∪ ε E
and a set of terms specified by the automaton A Bad , the prune process is defined by

P(A, S A∩A Bad ) =        P(A , S A ∩A Bad ) if S A ∩A Bad = ∅ and with A = Clean(A, S A∩A Bad ) A if S A∩A Bad = ∅ or there exists t ∈ Bad s.t. t -→ A q f and q f ∈ Q F .
where Clean(A, S A∩A Bad ), consists of removing transitions of ε E until for each q f , q f , φ ∈ S A∩A Bad , φ does not hold, i.e., φ =⊥ with q f , q f respectively two final states of A and A Bad .

To replace Predicate Eq(q, q ) by ⊥ in φ, we have to remove the transition q → q from ε E . In addition, we also have to remove all transitions q α -→ q ∈ ε R , where the conjunction α contains some predicates Eq(q 1 , q 2 ) whose transition q 1 → q 2 has been removed from ε E . In general, removing Transition q → q may be too rough. Indeed, assuming that there also exists a transition q → q of ε E , removing the transition q → q also avoids the induced reduction q → q from the automaton and then, unconcerned terms of q are also removed. To save those terms, Transition q → q is added to ε E , but only if it has never been removed by a pruning step. This point is important to refine the automaton with accuracy. The prune step is called recursively as inferred transitions may keep the intersection non-empty. Theorem 4. Let t ∈ Bad be a spurious counter-example. The pruning process always terminates, and removes all the runs of the form t φ -→ q.

Example 5. We consider the R /E -automaton A of Example 2. It is easy to see that A recognizes the term g(c). Indeed, by Definition 3, we have g(c)

Eq(qc,q b ) ------→ q f . Consider now the rewriting path f (a) → R f (b) = E f (c) → R g(c). If we remove the step f (b) = E f (c) denoted by the transition q c → q b , then g(c) becomes unreachable and should also be removed. The first step in pruning A consists thus in removing this transition. In a second step, we propagate the information by removing all transition of ε R labeled by a formula that contains Eq(q c , q b ). This is done to remove all terms obtained by rewriting with the equivalence b = E c. After having pruned all the transitions, we observe that the terms recognized by A are given by the set {f (a), f (b)}.

Let us now characterize the soundness and completness of our approach.

Theorem 5 (Soundness on left-linear TRS). Consider a left-linear TRS R, a set of terms Bad, a set of equations E and a well-defined R /E -automaton A 0 . Let A * R,E be a fixpoint R /E -automaton of P(A , S A ∩A Bad ) and A = W(C(A i ))

for i ≥ 0. If L(A * R,E ) ∩ Bad = ∅, then Bad ∩ R * (L(A 0 )) = ∅.
Theorem 6 (Completeness on Linear TRS). Given a linear TRS R, a set of terms Bad defined by automata A Bad , a set of equations E and a welldefined R /E -automaton A 0 . For any i > 0, let A i be the R /E -automaton obtained from A i-1 in such a way: A i = P(A , S A ∩A Bad ) and A = W(C(A i-1 )).

If Bad ∩ R * (L(A 0 )) = ∅ then there exists t ∈ Bad and j > 0 such that t → Aj q f and q f is a final state of A j . This result also extends to left-linear TRS with a finite set of initial terms (cardinality of Rep(q) is 1 for all state q of A 0 ). Theorem 7 (Completeness on Left-Linear TRS). Theorem 6 extends to left-linear TRS if for any state q of A 0 , the cardinality of Rep(q) is 1.

Implementation, Application and Certification

Our approach has been implemented in TimbukCEGAR that is an extension of the Timbuk 3.1 toolset [START_REF] Genet | Timbuk 2.0 -a Tree Automata Library[END_REF]. Timbuk is a well-acknowledged tree automata library that implements several variants of the completion approach. TimbukCE-GAR consists of around 11000 lines of OCaml, 75% of which are common with Timbuk 3.1. TimbukCEGAR exploits a BDD-based representation of equation formulas through the Buddy BDD library [START_REF] Lind-Nielsen | Buddy 2.4[END_REF].

A particularity of TimbukCEGAR is that it is certified. At the heart of any abstraction algorithm there is the need to check whether a candidate overapproximation B is indeed a fixed point, that is if L(B ) ⊇ R * (L(A)). Such check has been implemented in various TRMC toolsets, but there is no guarantee that it behaves correctly, i.e., that the TRMC toolset gives a correct answer. In [START_REF] Boyer | Certifying a Tree Automata Completion Checker[END_REF], a checker for tree automata completion was designed and proved correct using the Coq [START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF] proof assistant. As such, any TRMC toolset that produces an automaton B that passes the checker can be claimed to work properly. TimbukCEGAR implements a straightforward extension of [START_REF] Boyer | Certifying a Tree Automata Completion Checker[END_REF] for R /E -automata, which means that the tool delivers provably correct answers. In what follows, we describe how Java programs can be analyzed using our approach. Both Timbuk and Tim-bukCEGAR are available at http://www.irisa.fr/celtique/genet/timbuk/.

In a french initiative called RAVAJ [START_REF] Ravaj | Rewriting and Approximations for Java Applications Verification[END_REF], we have defined a generic certified verification chain based on TRMC. This chain is composed of three main links. The two first links rely on an encoding of the operational semantics of the programming language as a term rewriting system and a set of rewrite rules. The third link is a TRMC toolset, here TimbukCEGAR. With regards to classical static analysis, the objective is to use TRMC and particularly tree automata completion as a foundation mechanism for ensuring, by construction, safety of static analyzers. For Java, using approximation rules instead of abstract domains makes the analysis easier to fine-tune. Moreover, our approach relies on a checker that certifies the answer to be correct.

We now give more details and report some experimental results. We used Copster [START_REF] Barré | Copster homepage[END_REF], to compile a Java .class file into a TRS. The obtained TRS models exactly a subset of the semantics6 of the Java Virtual Machine (JVM) by rewriting a term representing the state of the JVM [START_REF] Boichut | Rewriting Approximations for Fast Prototyping of Static Analyzers[END_REF]. States are of the form IO(st,in,out) where st is a program state, in is an input stream and out an output stream. A program state is a term of the form state(f,fs,h,k) where f is current frame, fs is the stack of calling frames, h a heap and k a static heap. A frame is a term of the form frame(m,pc,s,l) where m is a fully qualified method name, pc a program counter, s an operand stack and t an array of local variables. The frame stack is the call stack of the frame currently being executed: f. We consider the following program: the empty list of outputs. Starting from this initial set of terms, completion is likely to diverge without approximations. Indeed, the program is going to allocate infinitely many objects of class List in the heap and, furthermore, compute an unbounded sum in the method printSum. In the heap, there is one separate heap for each class. Each heap consists of a list of objects. For instance, in the heap for class List, objects are stored using a list constructor stackHeapList(x,y). Thus, to enforce termination we can approximate the heap for objects of class List using the following equation stackHeapList(x,y)=y. The effect of this equation is to collapse all the possible lists built using stackHeapList, hence all the possible heaps for class List. The other equations are succ(x)=x and pred(x)=x for approximating infinitely growing or decreasing integers.

By using those equations, TimbukCEGAR finds a counterexample. This is due to the fact that, amongst all considered input streams, an input stream consisting of a list of 0 results into a 0 sum. The solution is to restrict the initial language to non-empty non-zero integer streams. However, refinement of equations is needed since succ(x)=x and pred(x)=x put 0 and all the other integers in the same equivalence class. Refining those equations by hand is hard, e.g. using equations succ(succ(x))=succ(x) and pred(pred(x))=pred(x) is not enough to eliminate spurious counterexamples. After 334 completion steps and 4 refinement steps, TimbukCEGAR is able to complete the automaton and achieve the certified proof. The resulting automaton produced by the tool has 3688 transitions which are produced in 128s. Then, it can be Coq-certified in 17017s. The memory usage for the whole process does not exceed 531M b. One of the reasons for which certifying automata produced by TimbukCEGAR takes more time than for Timbuk 3.1 is that the checker has to normalize epsilon transitions of R /E -automata. This is straightforward but may cause an explosion of the size of the tree automaton to be checked. However this can be improved a lot by defining a specific Coq-checker for R /E -automata. It is worth mentioning that the TRS produced by Copster from Java programs are left-linear but not rightlinear. Hence, our soundness theorem applies but not the completeness theorem, since the TRS is not right-linear and the initial language is not finite. However, here completion steps do not introduce spurious counter examples. Some other examples of application can be found in [START_REF] Boichut | Fast Equational Abstraction Refinement for Regular Tree Model Checking[END_REF]. Those experiments show, in particular, that the overhead due to the use of R /E -automata in completion can be limited thanks to BDDs. As a consequence, TimbukCEGAR performances are similar to those of Timbuk 3.1 when no refinement is performed, and Tim-bukCEGAR outperforms the other known CEGAR completion implementation when refinement is needed.

Conclusion

We have presented a new CounterExample Guided Abstraction Refinement procedure for TRMC based on equational abstraction. Our approach has been implemented in TimbukCEGAR that is the first TRMC toolset certified correct. Our approach leads, in particular, to a Java program analyzer starting from code to verification. Unlike most of existing works, our method works with the Java semantics itself rather than with some abstract model that is statically or even manually derived from the code. One additional feature is that the complete verification is certified by an external proof assistant. We are convinced that our work open news doors in application of RMC approaches to rigorous system design. One challenge for future work is definitively to consider non left-linear TRS -a formalism that can be used to model cryptographic protocols. In [START_REF] Genet | Reachability analysis of rewriting for software verification[END_REF][START_REF] Genet | Rewriting for Cryptographic Protocol Verification[END_REF][START_REF] Genet | Verification of Copy Protection Cryptographic Protocol using Approximations of Term Rewriting Systems[END_REF][START_REF]Avispa -a tool for Automated Validation of Internet Security Protocols[END_REF], it has been shown that an extension of the completion algorithm can lead to a powerful verification toolset for cryptographic protocols. However, this existing setting is still lacking an abstraction refinement procedure to be made fully automatic. On the one side, the theoretical challenge is thus to extend the CEGAR completion to non left-linear TRS. On the other side, the technical challenge is to extend the Coq checker to handle non left-linear TRS and R /Eautomata, in order to improve the Coq-checking time. Tackling those two goals will allow us to propose the first certified automatic verification tool for security protocols, a major advance in the formal verification area.

  The set Pos(t) of positions of a term t is inductively defined by Pos(t) = {λ} if t ∈ X and Pos(f (t 1 , . . . , t n )) = {λ} ∪ {i.p | 1 ≤ i ≤ n and p ∈ Pos(t i )} otherwise. If p ∈ Pos(t), then t| p denotes the subterm of t at position p and t[s] p denotes the term obtained by replacement of the subterm t| p at position p by the term s.

Those equations have to be provided by the user. In many cases, they can be produced when formalizing the problem in the TRMC framework[START_REF] Takai | A Verification Technique Using Term Rewriting Systems and Abstract Interpretation[END_REF]. The situation is similar for the predicates used in[START_REF] Bouajjani | Abstract regular model checking[END_REF][START_REF] Bouajjani | Abstract regular tree model checking[END_REF][START_REF] Bouajjani | Abstract rmc of complex dynamic data structures[END_REF].

essentially basic types, arithmetic, object creation, field manipulation, virtual method invocation, as well as a subset of the String library.

Acknowledgements Thanks to F. Besson for his help in integrating Buddy.

Let us now check that the sum output by the program can never be equal to zero, for all non-empty input stream of integers. The TRS generated by Copster has 879 rules encoding both the JVM semantics and the bytecode of the above Java program. Note that, this example is bigger than those generally used by other TRMC techniques. The complete TRS is available with TimbukCEGAR distribution. Initial terms are of the form IO(s,lin,nilout) where s is the initial JVM state, lin is a non-empty unbounded list of integers and nilout is