Anton Landström

Silvia Leccese

Hagop Abadian

Jean-François Lambert

Isabella Concina

Stefano Protti

Ari Paavo Seitsonen

Alberto Mezzetti
email: alberto.mezzetti@sorbonne-universite.fr

Fluorescent silica MCM-41 nanoparticles based on flavonoids: Direct post-doping encapsulation and spectral characterization

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The flavonoid moiety, that consists of two aromatic rings (A, B in Fig. 1a) connected by a pyrane core C, is largely diffuse in the vegetal kingdom. Most molecules belonging to this class play a key role in plants, as photoprotective agents [START_REF] Agati | Multiple functional roles of flavonoids in photoprotection[END_REF] and antioxidants [START_REF] Agati | Flavonoids as antioxidants in plants: Location and functional significance[END_REF] as well as in plant physiology [START_REF] Buer | Flavonoids: New Roles for Old Molecules[END_REF]. Furthermore, flavonoids exhibit interesting biological properties [START_REF] Havsteen | The Biochemistry and Medical Significance of the Flavonoids[END_REF][START_REF] Rodriguez-Mateos | Bioavailability, Bioactivity and Impact on Health of Dietary Flavonoids and Related Compounds: An Update[END_REF], including, among others, antioxidant [START_REF] Borges Bubols | The antioxidant activity of coumarins and flavonoids[END_REF][START_REF] Jovanovic | Flavonoids as antioxidants[END_REF][START_REF] Burda | Antioxidant and antiradical activities of flavonoids[END_REF][START_REF] Musialik | Acidity of Hydroxyl Groups: An Overlooked Influence on Antiradical Properties of Flavonoids[END_REF], neuroprotective [START_REF] Youdim | Flavonoids and the brain: interactons at the blood-brain barrier and their physiological effects on the central nervous system[END_REF][START_REF] Solanki | Flavonoid-based therapies in the early management of neurodegenerative diseases[END_REF][START_REF] Zhao | A Pharmacological Appraisal of Neuroprotective and Neurorestorative Flavonoids Against Neurodegenerative Diseases[END_REF] and anti-cancer activity [START_REF] Kopustinskiene | Flavonoids as anticancer agents[END_REF][START_REF] Rodriguez-Garcia | Dietary Flavonoids as Cancer Chemopreventive Agents: An Updated Review of Human Studies[END_REF][START_REF] Raffa | Recent Discoveries of Anticancer Flavonoids[END_REF]. Flavonoids have also found wide application in analytical chemistry [START_REF] Pyrzynska | Flavonoids as analytical reagents[END_REF][START_REF] Kathyal | Analytical reactions of hydroxyflavones[END_REF].

3-hydroxyflavone (3HF) and 7-hydroxyflavone (7HF) are widely studied (often in parallel) as they possess a hydroxyl group in a key position [START_REF] Das | Exploring the Non-Covalent Binding Behaviours of 7hydroxyflavone and 3-hydroxyflavone With Hen Egg White Lysozyme: Multi-spectroscopic and Molecular Docking Perspectives[END_REF][START_REF] Sengupta | Differential roles of 3-Hydroxyflavone and 7-Hydroxyflavone against nicotine-induced oxidative stress in rat renal proximal tubule cells[END_REF][START_REF] Sengupta | Excited State Proton Transfer of Natural Flavonoids and Their Chromophores in Duplex and Tetraplex DNAs[END_REF][START_REF] Montana | The activity of 3and 7-hydroxyflavones as scavengers of superoxide radical anion generated from photo-excited riboflavin[END_REF]. Furthermore, both 3HF and 7HF have interesting biological [START_REF] Lu | 3-Hydroxyflavone Inhibits Human Osteosarcoma U2OS and 143B Cells Metastasis by Affecting EMT and Repressing u-PA/MMP-2 via FAK-Src to MEK/ERK and RhoA/MLC2 Pathways and Reduces 143B Tumor Growth in Vivo[END_REF][START_REF] Lau | 3-Hydroxyflavone and Structural Analogues Differentially Activate Pregnane X Receptor: Implication for Inflammatory Bowel Disease[END_REF][START_REF] Wang | Inhibition of Enterovirus 71 Replication by 7-Hydroxyflavone and Diisopropyl-Flavon7-yl Phosphate[END_REF], chemical [START_REF] Musialik | Acidity of Hydroxyl Groups: An Overlooked Influence on Antiradical Properties of Flavonoids[END_REF][START_REF] Montana | The activity of 3and 7-hydroxyflavones as scavengers of superoxide radical anion generated from photo-excited riboflavin[END_REF] and photochemical properties [25, 26 and refs therein].

Their photophysical behaviour is of particular interest. Both molecules are fluorescent [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF][START_REF] Lazzaroni | Role of Solute-Solvent Hydrogen Bonds on the Ground State and the Excited State Proton Transfer in 3-hydroxyflavone. A Systematic Spectrophotometric Study[END_REF], showing strong environment-dependent emission properties, but whereas 3HF has been widely studied and characterized in detail [26 and refs. therein], the photophysics of 7HF has been rationalized only a few years ago [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF].

In 3HF, absorption of UV light from the ground state N leads to the singlet N* (hν1) excited state. This excitation is followed by the excited-state intramolecular proton transfer (ESIPT) from the 3-OH to the C=O group to give to the tautomeric excited form T*, which emits in the 500-540 nm region (hνT), showing a remarkable Stokes shift value. However, in polar or protic media, the ESIPT process is hampered due to specific 3HF-solvent interactions, so that fluorescence from the N* state (hνN) can take place competitively.

As a result, in these media a dual fluorescence is normally observed [START_REF] Lazzaroni | Role of Solute-Solvent Hydrogen Bonds on the Ground State and the Excited State Proton Transfer in 3-hydroxyflavone. A Systematic Spectrophotometric Study[END_REF]. This is the main reason for the widespread use of 3HF (and of its derivatives) as fluorescent probes in several fields (see [START_REF] Protti | Any colour you like. Excited state and ground state proton transfer in flavonols and applications[END_REF][START_REF] Mezzetti | Flavonols and 3-hydroxychromones: new applications for a class of environmentsensitive fluorescent molecules[END_REF] for reviews): the ratio between the intensity of the N* and T* bands -as well as parameters such as, among the others, the bandwidth, fluorescence lifetimes and the exact position of emission bands-strictly depends on the microenvironment. 3HF-based sensors for the detection and monitoring of several analytes have also been developed (see for instance [START_REF] Mezzetti | Flavonols and 3-hydroxychromones: new applications for a class of environmentsensitive fluorescent molecules[END_REF][START_REF] Zhu | A flavonoid-based fluorescent probe enables the accurate quantification of human serum albumin by minimizing the interference from blood lipids[END_REF][START_REF] Liu | Solvatochromic fluorescent probes for recognition of human serum albumin in aqueous solution: Insights into structure-property relationship[END_REF][START_REF] Qin | Ratiometric fluorescent monitoring of methanol in biodiesel by using an ESIPT-based flavonoid probe[END_REF] and references therein). In addition, the molecular environment around 3HF (solvents, but also protein binding pockets, nanocavities, etc) can also induce a partial, ground state deprotonation of the 3-OH group, leading to the formation of an anionic species with completely different photophysics [START_REF] Lazzaroni | Role of Solute-Solvent Hydrogen Bonds on the Ground State and the Excited State Proton Transfer in 3-hydroxyflavone. A Systematic Spectrophotometric Study[END_REF][START_REF] Protti | Any colour you like. Excited state and ground state proton transfer in flavonols and applications[END_REF][START_REF] Loco | Critical assessment of solvent effects on absorption and fluorescence of 3HF in acetonitrile in the QM/PCM framework: A synergic computational and experimental study[END_REF]. The anion absorbs at higher wavelength than the neutral form and emits (hν2 and hνA in Figure 1, respectively) in the 460-490 nm region, half-way between the two emission peaks of the dual fluorescence (which becomes therefore a triple fluorescence). As an example, for 3HF in methanol (MeOH) N* emits at 406 nm, T* at 528 nm, and A* at 481 nm [START_REF] Lazzaroni | Role of Solute-Solvent Hydrogen Bonds on the Ground State and the Excited State Proton Transfer in 3-hydroxyflavone. A Systematic Spectrophotometric Study[END_REF].

7HF has a different photophysics [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF], since direct ESIPT cannot take place. The molecule can exist as neutral N, anion A, and cation C, depending on the basic/acid properties of the surrounding microenvironment, while four excited state forms can exist, namely neutral N*, cation C*, anion A*, and phototautomer T*. A* can be formed either by direct excitation of the ground-state anion, or by photodissociation of the N* form; the T* formation depends on the acidity of the environment and can be formed by C* photodissociation or via photoinduced protonation of A* (see Figure 1). Despite the different species involved in its photophysics, 7HF emission has so far found much less applications than 3HF (see for instance [START_REF] Chaudhuri | Ground and Excited State Proton Transfer and Antioxidant Activity of 7-hydroxyflavone in Model Membranes: Absorption and Fluorescence Spectroscopic Studies[END_REF]).

The interaction between flavonoids and silica matrices is an active research topic interesting several fields, ranging from optics [34, 35 and refs therein] to analytical chemistry (see for instance [START_REF] Maciejewicz | Chemometric characterization of TLC systems of the type silicabinary non-aqueous mobile phase in the analysis of flavonoids[END_REF][START_REF] De Rijke | Analytical separation and detection methods for flavonoids[END_REF]). Among the different applications, one should mention the development of silica nanoparticles (NPs) for flavonoid delivery [START_REF] Lungare | Phytochemical-loaded Mesoporous Silica Nanoparticles for Nose-To-Brain Olfactory Drug Delivery[END_REF][START_REF] Arriagada | Nanoantioxidant-Based Silica Particles as Flavonoid Carrier for Drug Delivery Applications[END_REF] or with special characteristics given by the flavonoids, such as antioxidant [START_REF] Brezoiu | Polyphenols extract from grape pomace. Characterization and valorisation through encapsulation into mesoporous silica-type matrices Food[END_REF][START_REF] Arriagada | Morin Flavonoid Adsorbed on Mesoporous Silica, a Novel Antioxidant Nanomaterial[END_REF] or fluorescent properties [START_REF] Das | Antioxidant flavone analog functionalized fluorescent silica nanoparticles: Synthesis and Exploration of their possible use as a biomolecule sensor[END_REF][START_REF] Ferreira | Synthesis and functionalization of silica-based nanoparticles with fluorescent biocompounds extracted from Eysenhardtia polystachya for biological application[END_REF]. MCM-41 silica NPs are particularly interesting matrices and their relevance goes even beyond the already mentioned fields, as they are used for in chromatography of flavonoids [START_REF] Karpov | Separation of (+)-catechin and quercetin on mesoporous MCM-41 composites: dynamics of the sorption of flavonoids[END_REF], solid-state extraction of flavonoids [START_REF] Wang | A rapid and efficient extraction method based on industrial MCM-41-miniaturized matrix solid-phase dispersion extraction with response methodology for simultaneous quantification of six flavonoids in Pollen typhae by ultra-high-performance liquid chromatography[END_REF] and encapsulation of flavonoids for their preservation [START_REF] Brezoiu | Polyphenols extract from grape pomace. Characterization and valorisation through encapsulation into mesoporous silica-type matrices Food[END_REF][START_REF] Berlier | Stabilization of quercetin flavonoid in MCM-41 mesoporous silica: Positive effect of surface functionalization[END_REF][START_REF] Berlier | MCM-41 as a useful vector for rutin topical formulations: synthesis, characterization and testing[END_REF]. However, a better understanding of the interaction of flavonoids with the silica surface of MCM-41 nanopores is actually lacking.

In the present article we describe a simple procedure for the encapsulation of 3HF and 7HF in MCM-41 silica NPs and the detailed characterization of the so-prepared materials, with a special emphasis on their emission properties. A series of parallel experiments were carried out on isolated flavonoids in solution under specific conditions, in order to rationalize the nature of the emitting species. Besides their obvious relevance for their possible application in fluorescence, the particular environment-sensitive photophysics of the two monohydroxyflavones can also provide information on the interactions of the two molecules with the silica surface in MCM-41 NPs.

Materials and methods

Chemicals. 3-HF and 7-HF were purchased from Sigma-Aldrich and recrystallized from cyclohexane. Acetonitrile (MeCN) for post-doping procedure was of spectroscopic grade; for fluorescence analysis anhydrous acetonitrile was employed.

Synthesis of silica NPs. MCM-41 NPs were prepared by following the protocol described by Meynen et al. [START_REF] Meynen | Verified syntheses of mesoporous materials[END_REF]. An aqueous solution of cetyltrimethylammonium bromide (CTAB), mixed with aqueous ammonia was left under stirring at a constant temperature of 35°C. Then tetraethyl orthosilicate (TEOS) was added. The TEOS/CTAB/NH4OH mixture was left at the same temperature for 2 hours; afterwards, the system was transferred to a tightly sealed Teflon bottle placed in a drying oven at100°C and left under autogenous pressure overnight. After filtration, the final step was the removal of CTAB within the pores of the MCM-41 by calcination. The calcination process was the following: the solid sample was placed in a crucible in a programmable calcination oven under ambient air and the temperature was increased from 20°C to 300°C in 2 ½ hours. Then the temperature was kept constant at 300°C for 2 hours. Subsequently, temperature was increased from 300 to 550°C in 2 hours. Then the temperature was kept constant at 550°C for 12 hours. This liberated the mesoporous space of the MCM-41 silica material.

Nitrogen physisorption (see Figure 2) was performed on the solid material at 77K. The BET analysis showed a high surface area for the MCM-41 around 885m 2 /g. The pore size distribution was determined using BJH (Barrett-Joyner-Halenda) treatment, resulting in a sharp peak for a pore size of 2.62 nm. The porous volume was 0.8002 cm 3 /g. Theoretical calculations. Density functional theory (DFT) [START_REF] Hohenberg | Inhomogenous electron gas[END_REF] and time-dependent DFT [START_REF] Runge | Density-functional theory for time-dependent systems[END_REF] calculations were performed on both flavonoids in different states (neutral, tautomer, anion, cation). DFT was used to calculate the ground-state S0 geometries and vibrational spectra; TD-DFT for the photon absorption and fluorescence spectra, the latter in the first singlet state S1. We employed the B3LYP [START_REF] Kim | Comparison of density functional and MP2 calculations on the water monomer and dimer[END_REF] as the approximation in the exchange-correlation functional. The basis set cc-pVTZ in the calculation of the vibrational spectra and aug-cc-pVTZ in the calculations of TDDFT were used unless otherwise mentioned.

Preparation of flavonoid-doped

The calculations have been performed with a free-standing molecule and using implicit solvation within the conductor-like polarisable continuum model (CPCM) [START_REF] Barone | Quantum calculation of molecular energies and energy gradients in solution by a conductor solvent model[END_REF] for acetonitrile.

The computer codes ORCA [START_REF] Neese | Software update: the ORCA program system, version 4.0[END_REF] and Gaussian09 Revision A.02 [START_REF] Frisch | Gaussian[END_REF] were used. We applied large integration grids and strict convergence criteria, "Grid5" and "$a" in the input of ORCA and "Integral(UltraFine)" in the input of G09. For a detailed description see also Table 1 and2. It was not however possible to precisely quantify the amount of flavonoid encapsulated (normally carried out by looking at the variation of the absorbance of the solution before and after the impregnation) because of turbidity problems, as some MCM-41 was remaining as a suspension. Interestingly, when carrying out the procedure with much more diluted 10 -5 M solutions (not shown), the absorbance of the solution after the withdrawal of flavonoids by MCM-41 impregnation was just divided -roughly -by a factor of two. This suggests that there are some sites with a rather strong affinity (strongly negative free enthalpy of adsorption) of the silica for the two flavonoids, since adsorption is already significant at a low equilibrium concentration.

XRD results clearly indicate that no formation of 3HF or 7HF microcrystals occurs (see Figures S1 andS2 in ESI). This suggests that 3HF and 7HF are molecularly adsorbed on the surface and thus, that the maximum adsorption capacity of the NP is not reached. The low intensity of characteristic IR peaks (see later) confirms that only a limited amount of flavonoid is adsorbed.

FTIR spectra of flavonoid-loaded NPs (see Figure S3 in ESI) shows that MeCN is partially retained within the structure in both cases (peaks at 1375, 1421, 1443, 2294-8 cm -1 ); however, the interaction of MeCN molecules with the surface seems to be different in the presence of 3HF and 7HF (see the band at 2253 cm -1 that is present in 7HF-loaded NPs but absent in 3HF-loaded NPs, and the band at 2263 cm -1 that is very intense in 3HF-loaded NPs but visible as a weak shoulder in 7HF-loaded NPs, Figure S3). It should be noticed that FTIR spectra show very low intensity bands arising from the two flavonoids (see band at 1483 cm -1 for 3HF [START_REF] Wang | Surface Enhanced Raman Scattering of 3-Hydroxyflavone[END_REF]; band at 1646 cm -1 for 7HF [START_REF] Tyukavkina | Ultraviolet absorption of flavonoids II. Ionization constants of 7-and 4′-hydroxy derivatives of flavone and flavonol[END_REF]), suggesting a low loading in both cases. This is not surprising, given the hydrophilic character of the silica surface and the rather hydrophobic character of the two flavonoids. It should be pointed out however that IR bands from the silica matrix, from adsorbed water and MeCN probably hide other IR flavonoid bands (for instance the relatively intense band of 3HF expected at ~1620 cm -1 [START_REF] Seitsonen | Solvent effects on the vibrational spectrum of 3hydroxyflavone[END_REF] which is not distinguishable in our FTIR spectrum).

UV-Vis spectra clearly show that inside the silica matrix the main absorbance properties of the flavonoids remain unaltered compared to those observed in solution, suggesting that in the majority of 3HF and 7HF molecules no chemical modification is taking place because of the interaction of the silica matrix. However, some significant shifts are observed for the main UV absorption band. All the main bands see their amplitude strongly diminished after 10 minutes of strong UV illumination in all samples, most probably due to photodecomposition of the flavonoids [START_REF] Protti | Solvent effects on the photophysics and photoreactivity of 3-hydroxyflavone: A combined spectroscopic and kinetic study[END_REF][START_REF] Schipfer | pH-Dependent fluorescence spectroscopy. Part 12. Flavone, 7hydroxyflavone, and 7-methoxyflavone[END_REF][START_REF] Protti | Photochemistry of metal complexes of 3-hydroxyflavone: towards a better understanding of the influence of solar light on the metal-soil organic matter interactions[END_REF]. This is consistent with the disappearance of the flavonoid IR bands and, in the case of 3HF-loaded NPs, with the appearance of small IR band(s) in the 1700-1760 cm - 1 region (not shown), as expected for the photorearrangement product [START_REF] Protti | Photochemistry of metal complexes of 3-hydroxyflavone: towards a better understanding of the influence of solar light on the metal-soil organic matter interactions[END_REF][START_REF] Tomar | The detection of the precursors of the photorearranged products of 3hydroxyflavones in selected solvents from UV-visible spectra in situ[END_REF].

Conditions

Absorption bands The fluorescence spectra of flavonoid-loaded NPs suggest that the emitting species have different interactions with the surrounding environment as compared to the same molecules in solutions. This can easily be seen by the comparison of the emission spectrum of 3HF in MCM-41 with the one obtained in pure solvents. The main emission band of the fluorescence spectrum (λexc = 320 nm) of 3HF in MCM-41 is centred at 506 nm, a value much lower than what is observed in MeCN, but also in many other solvents, with only the significant exception of 2,2,2-trifluoroethanol [START_REF] Lazzaroni | Role of Solute-Solvent Hydrogen Bonds on the Ground State and the Excited State Proton Transfer in 3-hydroxyflavone. A Systematic Spectrophotometric Study[END_REF]. This suggests that 3HF experiences a surrounding environment characterized by high hydrogen bonding donating (HBD) acidity, as it can be expected given the acidity of silanol groups and the high HBD capability of water molecules adsorbed on the silica surface. This is also confirmed by the presence of a relatively intense band at ~403 nm, typical of a N* emission (always present in hydrogen bonding donating environment [START_REF] Lazzaroni | Role of Solute-Solvent Hydrogen Bonds on the Ground State and the Excited State Proton Transfer in 3-hydroxyflavone. A Systematic Spectrophotometric Study[END_REF]; this band is much weaker in MeCN solutions [START_REF] Loco | Critical assessment of solvent effects on absorption and fluorescence of 3HF in acetonitrile in the QM/PCM framework: A synergic computational and experimental study[END_REF]). In the case of 3HF in MCM-41, stable and strong hydrogen bond interactions between the silanol and the OH and C=O groups of the flavonoid are likely to be formed. This is consistent with a previous study on quercetin in MCM-41 NPs, where the authors underlined the relevance of the hydrogen bonds interactions between silanols and quercetin [START_REF] Berlier | Stabilization of quercetin flavonoid in MCM-41 mesoporous silica: Positive effect of surface functionalization[END_REF].

3HF
The width of the blue-shifted 3HF emission band (extending to ~440 nm, see Figure 3) cannot exclude the presence of some fluorescence from a minor population of 3HF cation, whose emission is expected in the 420-450 nm region (see Table 3; see also [START_REF] Schipfer | pH-Dependent fluorescence spectroscopy. Part 12. Flavone, 7hydroxyflavone, and 7-methoxyflavone[END_REF]).

Excitation at 300 nm of 7HF-MCM-41 samples gives an emission peaking at 390 nm. In order to figure out the nature of the emitting species, fluorescence spectra for 7HF in different MeCN solutions (exposed to air, to mimic the conditions of 7HF in NPs) were recorded. When the fluorescence spectrum of 7HF in neutral MeCN is recorded (λexc = 300 nm) a weak band at 370 nm is observed, along with a weaker and broader band at ~530 nm (see Figure 4). Spectra recorded after some minutes of illumination show an increase of the intensity of the 370 nm band, strongly suggesting that this band can be ascribed to a photodecomposition product 1 . It cannot be excluded that a small contribution arises also from the neutral form of 7HF, given that the excitation spectrum recorded at 400 nm shows a maximum at 293 nm (i.e. very close to the absorption band of neutral 7HF). TD-DFT calculations also foresee an emission at 378 nm for the neutral form of 7HF.

However this is at odds with previous results [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF] where neutral 7HF in MeCN was reported to be nonfluorescent. Whereas this apparent discrepancy could be explained by the high sensitivity of our instrument (the fluorescence quantum yield value is 0.001), the most likely explanation is that the 370 nm emission is essentially given by a photodecomposition product. The huge increase of fluorescence weighs in against neutral 7HF: it is unlikely that the neutral form N would be responsible for such an intense emission. The fluorescence spectra recorded after some minutes of illumination (see [START_REF] Landström | Datain-Brief[END_REF]), on the other hand, suggests that the fluorescence is probably not due to a photodecomposition product (in such case, an increase of its intensity would be expected, as observed in MeCN solution).Fluorescence of the 7HF anion is expected to be at λ > 520 nm (see Figure 4 and TD-DFT results in Table 3; see also [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF]) and therefore is not compatible with the observed fluorescence at 390 nm.

Furthermore, despite the presence of MeCN molecules in the NPs, it is unlikely that they would be able to reproduce conditions observed in MeCN solutions, given the presence of adsorbed water molecules and acidic Si-OH groups on the silica surface. Such an acidic environment could suggest partial formation of a cationic form of 7HF through a silanol-to-carbonyl proton transfer. Indeed, the fluorescence excitation spectrum of 7HF in MCM-41 has a maximum at 337 nm. Interestingly, this excitation wavelength is in rough agreement with the one observed for 7HF cation C in MeOH/H2O (λ = 366 nm) [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF]. The fluorescence of the cation of MeOH is observed at much longer wavelength (λem = 464 nm) but it has been shown that the position of the emission band depends on the acidity of the surrounding medium [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF][START_REF] Wolfbeis | pH-dependent fluorescence spectroscopy XVII: First excited singlet state dissociation constants, phototautomerism and dual fluorescence of flavonol[END_REF]. To get more precise information on this point, we have carried out 7HF absorption and fluorescence studied in MeCN in presence of H2SO4 (concentration 0.02 M) and performed some TD-DFT calculations to reproduced the experimental spectra. In acidified MeCN an absorption maximum is observed at 363 nm (see Figure 4), in good agreement with the maximum of the fluorescence excitation spectrum (361 nm). TD-DFT calculations (Table 3) foresee a UV-Vis absorption maximum at 370 nm. The experimental fluorescence maximum (λexc = 300 nm) is observed at 448 nm, in good agreement with the calculated TD-DFT values of 453 nm (for the conformer "cation2" with the OH of the protonated carbonyl pointing towards the hydrogen in position 3; see Figure S4 in ESI) and of 421 nm (for the conformer "cation1" with the OH pointing in the opposite direction). However, following the discussion in [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF], in such conditions phototautomer formation can take place. Our TD-DFT calculation foresee a fluorescence emission for the tautomer in the 594-610 nm range, which seems too far from the observed 448 nm emission peak. However, it is not excluded that the phototautomer contributes at least to he red-shifted tail of the fluorescence band, which extends beyond 550 nm (see Figure 3).

This may help to clarify the real identity of the emitting species in 7HF-doped NPs, because its emission maximum is at 390 nm (with a long tail extending beyond 550 nm) when the excitation wavelength is 300 nm. Whereas there is no clear evidence that the environment around 7HF (cation) inside MCM-41 pores can be properly simulated by the dielectric constant of MeCN (such assumption was based on the presence of several MeCN molecules per flavonoid molecule inside the NP, and on the polarity of the internal silica surfaces), no speculation can be made on specific 7HF-surface interactions (e.g. hydrogen bonds) and/or on peculiar conformations adopted by 7HF inside the pores of the NP. It is however significant to notice that previous DFT calculations have shown that specific solute-solvent interactions may significantly affect the energetics and electronic structure of 7HF [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF]. Furthermore, our TD-DFT calculations foresee a 32 nm shift in the emission wavelength by simply changing the orientation of the OH of the protonated carbonyl, suggesting that any surface-induced peculiar conformation of 7HF cation may entail a change from the behaviour observed in solution, i.e. an isotropic environment. However, as mentioned above, according to [START_REF] Serdiuk | 7-hydroxyflavone Revisited: Spectral, Acid-Base Properties, And Interplay of the Protolytic Forms in the Ground and Excited States[END_REF], in acidic conditions phototautomer can be formed from the cation. This suggests that the emitting species could be the phototautomer originating from the cationic form of 7HF. The position of the emitting band is far (~200 nm) from what is foreseen by TD-DFT calculation for the tautomer in MeCN, but it should be underlined that these calculations are probably not appropriate to simulate the fluorescence of a phototautomer formed from a cation adsorbed on a hydrated silica surface.

Finally, it is important to underline that the observed UV-Vis spectrum of 7HF-doped NPs shows a maximum at 311 nm and a shoulder at ~321 nm, with a weak shoulder at 368 nm. This suggests that several sub-populations of 7HF exist in MCM-41 NPs, the most fluorescent being probably of cationic or phototautomeric (originating from 7HF cation) forms. The presence of the 311 nm band however suggests that a large fraction of 7HF molecules exist in neutral state.

Time-resolved emission analysis show that both flavonoids have a longer fluorescence lifetime inside NPs compared to solutions (see Figure 5). This outcome is not unexpected: in silica NPs, flavonoid rotation is most probably strongly restricted, and this could reduce the non-radiative dissipation of the excitation energy, leading to and increase of fluorescence lifetime.

The presence of three different lifetime constants in the in both 3HF-and 7HF-loaded NPs suggests that in both cases three subpopulations of flavonoids are present. For 7HF NPs this observation is in agreement with the presence of three absorption bands at 311, 321, and 368 nm. Both flavonoid-loaded NPs shows a decrease in photoluminescence after prolonged illumination (see Figure 6 and fluorescence spectra in [START_REF] Landström | Datain-Brief[END_REF]), but without significant modification in the emission spectrum. It is interesting to compare this result to the photostability of the flavonoids in MeCN solutions. Both 3HF and 7HF look more stable inside NPs, suggesting a role of the silica matrix in preserving the fluorophore (see Figure 6). Interestingly, both 3HF-doped and 7HF-doped NPs remain fluorescent after two months of exposure to air at room temperature, with roughly the same quantum yield (see Table 2). For 7HF the 540 nm band diminishes its intensity, whereas it grows for the 395 nm. This strongly suggests that the 395 nm is -at least partially -due to a photodecomposition product. Entire fluorescence spectra after increasing illumination times are reported in [START_REF] Landström | Datain-Brief[END_REF]. 3. Calculated absorption and emission spectra for the different species. For the absorption spectra, only the more red-shifted band is indicated. The comparison between gas phase and solvated (MeCN) molecules gives an estimation of the influence of the surrounding environment. See [START_REF] Landström | Datain-Brief[END_REF] for more detailed data.

Figure 1 .

 1 Figure 1. Upper panel: Photophysics of 3-hydroxyflavone (3HF). ESIPT : Excited State Intramolecular Proton Transfer. The numbering scheme of flavonoids is also shown. Lower panel: Photophysics of 7hydroxyflavone (7HF), according to Ref. [25].

  NPs MCM-41 NPs were added to MeCN solutions of 3HF and 7HF.Samples were stirred for 5 minutes, centrifuged for 45 minutes at 4000 rpm in order to separate the solid (containing MCM-41 matrix with the flavonoids encapsulated). The precipitate was left exposed to air for 48h in a Petri dish to let the MeCN evaporate.Characterization of flavonoid-dopedNPs X-ray diffraction (XRD) patterns of the samples were recorded with a Bruker D8 Advance powder diffractometer, using Cu Kα radiation generated at 40 kV and 40 mA and equipped with an X′Celerator detector. Fourier Transform Infrared (FTIR) experiments were performed on a Bruker Vertex 80 rapid-scan spectrometer in the transmission mode equipped with a MCT detector. Samples were sandwiched between two CaF2 disks and sealed with parafilm. UV-Vis spectra of flavonoids in silica NPs were recorded with an Agilent Cary5000 spectrophotometer. An integrating sphere was used to record reflectance; spectra were obtained through Kubelka-Munk transform. Steady-state photoluminescence spectra of flavonoids in silica NPs were recorded with Edinburgh instruments FLS980 spectrofluorimeter. A Xenon arc lamp was used as excitation source. Quantum yield was determined by measuring scattering/absorption and emission in an integrating sphere. Photobleaching tests were performed by doing repeated emission scans of the samples on silica in 3-minute intervals. Time-resolved photoluminescence spectra of flavonoids in silica NPs were recorded with Edinburgh instruments LS980 spectrofluorimeter. A 372 nm picosecond pulsed diode laser was used as excitation source. The lifetime was determined by deconvoluting the measured data and the instrument response function, then fitting the data with a multi-exponential function. The relative number of photons from each decay path is indicated in the plots. UV-Vis absorption spectra in MeCN solutions were carried out by means of a Jasco V-550 spectrophotometer or by a Agilent Cary 5000 spectrophotometer. Fluorescence spectra of MeCN solution were carried out on a Perkin Elmer LS-55 spectrofluorometer or on a Edinburgh instruments FLS980 spectrofluorimeter.

Figure 2 .

 2 Figure 2. BJH pore distribution (upper panel) and full N2 physisorption isotherm (lower panel)

Figure 3 .

 3 Figure 3. UV-Vis, fluorescence excitation spectra, and emission spectra of 3HF-doped MCM-41 NPs (upper traces) and of 7HF-doped MCM-41 NPs (lower traces).For a detailed description see also Table1 and 2.

Figure 4 .

 4 Figure 4. Upper panels: Left, UV-Vis absorption spectrum of 7HF in neutral MeCN. Right, Fluorescence spectrum of 7HF in neutral MeCN with λexc = 300 nm. Inset: fluorescence excitation spectra of 7HF in neutral MeCN, λem = 390 nm

Figure 5 .

 5 Figure 5. Time-resolved fluorescence of 3HF-doped NPs (upper panel, left; λexc = 372 nm; λem = 500 nm). Time resolved fluorescence of 3HF in MeCN (upper panel, right; λexc = 372 nm; λem = 530 nm). Time-resolved fluorescence of 7HF-doped NPs (lower panel, left; λexc = 372 nm; λem = 420 nm), 7HF in MeCN (lower panel, right; λexc = 372 nm; λem = 540 nm)

Figure 6 .

 6 Figure 6. Left panel: Kinetics of decrease of fluorescence intensity recorded every 3 minutes during continuous exposure to UV-light of 3HF-doped NPs (upper left panel; λexc = 320 nm) and 7HF-dopep NPs (upper right panel λexc = 300 nm). Right panel: kinetics of fluorescence intensity for 3HF and 7HF in MeCN solution. For 7HF the 540 nm band diminishes its intensity, whereas it grows for the 395 nm. This strongly

Table 1 .

 1 UV-Vis absorption bands observed for 3HF and 7 HF under different conditions.

	in MeCN	305 nm	341 nm	~352 nm	~410 nm (traces,
	[29]				anion)
	3HF in MCM-41 315 nm	344 nm, broad
	3HF in MCM-41	315 nm	342, broad
	aged sample
	7HF in MeCN	237 nm (sh)	250 nm	300 nm
	7HF in MCM-41		251 nm	311 nm	321 nm (sh)
					368 (very weak
					sh)
	7HF in MCM-41		251 nm	312 nm	320 nm (sh)
	aged sample				368 (very weak
					sh)

Table 2 .

 2 Fluorescence properties of 3HF and 7HF in different systems under different conditions.

This is also in agreement with TLC analysis of a MeCN solution of 7HF after 30 minutes of illumination (not shown), showing indication of a photoproduct more polar than 7HF.

Conclusions

In this work, we have prepared 3HF and 7HF doped silica MCM-41 NPs by a simple post-doping procedure.

Both kinds of NPs have proved to be highly fluorescent, their emission properties being little affected by ageing and only moderately by UV exposure. For 3HF, interestingly, despite its overall hydrophobic character and the capability of donating and accepting hydrogen bonds of the 3OH group and the hydrogen bond basicity of its C=O moiety, the photophysics is strikingly similar to the one observed in solution. For 7HF, the emitting species is probably the cationic and/or the phototautomeric form.

Such results show a simple and efficient way of encapsulating the two flavonoids in silica NPs, keeping their fluorescence properties. On the other hand, it provides some initial information on the interactions between 3HF and 7HF with silica surfaces. Spectroscopic data also suggest that both flavonoids form strong hydrogen bond interactions with silanol groups and adsorbed water molecules; at least in the case of 7HF, a surface-to-flavonoid proton transfer seems to take place in a significant fraction of flavonoid molecules.


Radu Mateescu
email: radu.mateescu@inria.fr

Anton Wijs
email: anton.wijs@inria.fr

Hierarchical Adaptive State Space Caching based on Level Sampling

In the past, several attempts have been made to deal with the state space explosion problem by equipping a depth-first search (DFS) algorithm with a state cache, or by avoiding collision detection, thereby keeping the state hash table at a fixed size. Most of these attempts are tailored specifically for DFS, and are often not guaranteed to terminate and/or to exhaustively visit all the states. In this paper, we propose a general framework of hierarchical caches which can also be used by breadth-first searches (BFS). Our method, based on an adequate sampling of BFS levels during the traversal, guarantees that the BFS terminates and traverses all transitions of the state space. We define several (static or adaptive) configurations of hierarchical caches and we study experimentally their effectiveness on benchmark examples of state spaces and on several communication protocols, using a generic implementation of the cache framework that we developed within the CADP toolbox.

Introduction

In model checking, the state space explosion problem is the most important issue. It stems from the fact that a linear growth of the number of concurrent processes in a specification leads to an exponential growth of the number of states in the resulting state space. This problem strongly limits the possibilities to verify large systems, since state space generation algorithms typically need to keep all generated states in memory, thereby exhausting it quickly. Over the years, many techniques have been introduced to fight it, e.g., partial order reduction [START_REF] Godefroid | Using Partial Orders for the Efficient Verification of Deadlock Freedom and Safety Properties[END_REF][START_REF] Clarke | Model Checking[END_REF], using secondary storage [START_REF] Edelkamp | Real-Time Model Checking on Secondary Storage[END_REF][START_REF] Hammer | To Store or Not To Store" Reloaded: Reclaiming Memory on Demand[END_REF], distributed model checking [START_REF] Garavel | Parallel State Space Construction for Model-Checking[END_REF][START_REF] Blom | Distributed State Space Minimization[END_REF][START_REF] Blom | Distributed Analysis with µCRL: A Compendium of Case Studies[END_REF], and directed model checking [START_REF] Edelkamp | Directed explicit-state model checking in the validation of communication protocols[END_REF][START_REF] Edelkamp | Survey on Directed Model Checking[END_REF].

Another research branch is to consider partial storage of the previously explored states. This idea has lead, roughly speaking, to two classes of approaches: one where exhaustive exploration of the state space is guaranteed, and one where it is not. Since we are concerned with state space generation, i.e., the traversal of all the transitions in a state space, we focus on the first class; the reader is referred to Section 5 for the second one. The first class contains most work on state space caching [START_REF] Holzmann | Automated Protocol Validation in Argos, assertion proving and scatter searching[END_REF], where a cache is employed which can never contain more than n states, and a technique which can be referred to as covering set determination [START_REF] Behrmann | To Store or Not To Store[END_REF] where, by means of static analysis, the goal is to identify which states to store in order to guarantee termination of the exploration. The caching approach is usually reserved for depth-first search (DFS) exploration, since termination can be guaranteed by efficient cycle detection, as opposed to when using breadth-first search (BFS). However, partial storage of explored states for BFS is desirable as well, since BFS (unlike DFS) can be efficiently distributed in order to perform the state space exploration using clusters of machines.

In this paper, we focus on state space generation with the goal of storing the state space on disk, meaning that besides minimising the memory use, we also aim at reducing the number of state revisits, which determines the amount of redundant information in the generated state space. This distinguishes our work from earlier work on state space caching, where the goal was to visit all states (but not necessarily traverse all transitions) and hence memory use was the main factor of importance. First, we propose a framework allowing hierarchies of caches in addition to single caches. To our knowledge, this has not been investigated yet in this context, although it is quite common practice in the field of hardware architectures [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF]. The main idea is that several caches together, each having different characteristics, can be more efficient than one single cache. We study the performance of several hierarchical cache configurations using DFS, some of them improving on results shown by single cache setups. Second, we explain how these caches can be used for BFS by storing search levels instead of individual states in them. This provides a generic (language-independent) on-the-fly covering set estimation, instead of a (language-dependent) one based on static analysis. Our main result in this setting guarantees termination of the BFS with caches if appropriate sampling functions are used to decide which search levels must be stored. Finally, we propose a learning mechanism allowing the BFS algorithm to adapt on-the-fly to the state space structure by detecting its earlier mistakes.

Using the CADP toolbox [START_REF] Garavel | CADP 2006: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF] and the underlying OPEN/CAESAR environment [START_REF] Garavel | OPEN/CAESAR: An Open Software Architecture for Verification, Simulation, and Testing[END_REF] for state space manipulation, we have implemented generic libraries for hierarchical caches, as well as cache-equipped BFS and DFS exploration tools, which allow to finely tune the memory use. We applied these tools on many examples of state spaces, taken either from benchmarks such as VLTS [START_REF] Vlts | The VLTS Benchmark Suite[END_REF], or produced from communication protocols. These experiments allowed us to identify the most effective cache configurations, which can lead to memory reductions of over one order of magnitude, and even to speedups of the generation. Our results improve over existing ones by being language-independent and robust to the variations of the so-called locality (roughly, the size of back jumps during BFS) of state spaces.

The paper is organized as follows. Section 2 defines the terminology we use for state space exploration. Section 3 presents our cache-based BFS algorithm based on sampling of levels, proves its termination, and defines several instances of it using hierarchical caches and adaptive mechanisms. Section 4 briefly describes the implementation within CADP and gives various performance measures. Finally, Section 5 compares our approach with previous work and Section 6 gives concluding remarks and directions for future work.

Preliminaries

Labelled transition systems (LTSs) capture the operational behaviour of concurrent systems. An LTS consists of transitions s ℓ -→ s ′ , meaning that being in a state s, an action ℓ can be executed, after which a state s ′ is reached. Definition 1. A labelled transition system (LTS) is a tuple M = (S , A , T , s 0 ), where S is a set of states, A a set of transition labels, T : S × A × S a transition relation, and s 0 the initial state. A transition (s, ℓ, s ′ ) ∈ T is denoted by s ℓ -→ s ′ . Furthermore, we express that a state s ′ is reachable from s with s → * s ′ , where → * is the reflexive, transitive closure of →. Likewise, we express with s → + s ′ that s ′ is reachable from s by traversing at least one transition. The set of enabled transitions of s is en Before generation, the structure of an LTS is not known. A generation algorithm is given an implicit LTS M im = (s 0 , en), with s 0 an initial state, and en the enabled function which can be used to generate the other states and the transitions between them, thereby creating an explicit LTS in line with Definition 1. We call an LTS finite iff S and A are of a finite size. Whenever a state is newly discovered, we call it a visited state; once we have generated all transitions and successors of s by employing the enabled function, we call s an explored state. Recognising when a newly visited state is already explored is called duplicate detection. In a standard BFS, all previously explored states are stored in memory, in what is called the Closed set, and all visited states yet to be explored are stored in the Open set, also called the search horizon. Given a nonempty Open set, the exploration of all the states therein can be seen as an iteration of the BFS algorithm, which produces a new search level consisting of all the newly generated successors. Subsequently, these states without the duplicates make up the new Open set, which can be subjected to a new iteration. Duplicate detection will happen whenever applicable, and the resulting LTS will contain no redundant states, i.e., states which are de facto equal to other states in the LTS. To make things clear when it comes to partial duplicate detection, we represent LTS generation explicitly by first constructing a generation tree of nodes. Figure 1 depicts the generation of an LTS as the traversal of some system behaviour, using both BFS with and without a Closed set. Left and right of the behaviour are two trees, where the numbering of the nodes firstly indicates the search level in which the node is encountered, and secondly, in what order the nodes are encountered. The dotted lines visualise which system state each node maps to. Using a Closed set, all explored nodes remain in memory, therefore, in the left tree, once nodes 2.4 and 3.5 are visited, they are recognised as essentially being equal to nodes 2.3 and 1.1, respectively, via their associated system states. If we consider BFS without a Closed set, on the right of the figure, we observe partial duplicate detection. Once node 2.4 is encountered, it is recognised as being essentially equal to node 2.3, since 2.3 at that time resides in the Open set. However, later on, node 3.5 is not recognised as being equal to node 1.1, since the latter has not been kept in memory, and the generation continues endlessly. From a generation tree, an LTS is derived by creating a state for each node deemed unique. For the right tree in the figure, this results in redundant states.

(s) = {(s, ℓ, s ′ ) | ∃ℓ ∈ A , s ′ ∈ S .s ℓ -→ s ′ },
For checking duplicates, in practice, often a hash table is used to quickly search the contents of Closed. Such a hash table uses a hash function h : S → N to store h(s) for all s ∈ Closed. If h leads to collisions, that is there are s, s ′ ∈ S such that s = s ′ and h(s) = h(s ′ ), then collision detection is a method to recognise this, which usually means storing multiple states at the same index in a hash array.

BFS with State Space Caching

Caches have a fixed size, and a so-called replacement strategy, which determines which element should be removed next, whenever a new element needs to be added to an already full cache. There have been caching attempts with DFS [START_REF] Holzmann | An Improved Protocol Reachability Analysis Technique[END_REF][START_REF] Courcoubetis | Memory-Efficient Algorithms for the Verification of Temporal Properties[END_REF][START_REF] Stern | Combining State Space Caching and Hash Compaction[END_REF][START_REF] Stern | A New Scheme for Memory-Efficient Probabilistic Verification[END_REF][START_REF] Holzmann | Automated Protocol Validation in Argos, assertion proving and scatter searching[END_REF][START_REF] Godefroid | State-Space Caching Revisited[END_REF][START_REF] Jard | Bounded-memory Agorithms for Verification On-the-fly[END_REF][START_REF] Behrmann | To Store or Not To Store[END_REF], and a few with BFS, which, however, are not guaranteed to terminate [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Tronci | A Probabilistic Approach to Automatic Verification of Concurrent Systems[END_REF].

As with related work on caching with DFS, we intend to restrict the growth of the Closed set. This, usually, has a negative effect on two other aspects of LTS generation, namely the execution time and the size of the output LTS. Unlike most previous work, besides the fact that we focus on BFS, we also try to minimise this negative effect. More precisely, we aim at satisfying three criteria: (a) The approach should be independent of any modelling paradigm, that is, it should not rely on analysis of the specification from which the LTS is derived, e.g., by using techniques such as static analysis, as in [START_REF] Behrmann | To Store or Not To Store[END_REF]; (b) The resulting LTS should contain as few duplicates as possible; restriction of the growth of the Closed set, however, tends to deteriorate duplicate detection, unless the LTS has a tree structure, or we are able to store exactly the right states in Closed, which would require prior knowledge of the LTS structure; (c) Termination of the generation algorithm must be guaranteed. This is not trivial for BFS, and possibly the main reason that few attempts exist of partial duplicate detection with BFS; as regards DFS, cycle detection by keeping the DFS stack in memory suffices to guarantee termination.

Without knowledge of the LTS structure, how can we decide which states to store and which to ignore? Many attempts have been made in the past to predict state space structures, e.g., [START_REF] Behrmann | To Store or Not To Store[END_REF][START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF][START_REF] Pelánek | Properties of state spaces and their applications[END_REF], but theoretically, any state may lead to any other state. Some have observed that, although LTSs may have any conceivable structure, the ones stemming from real specifications, which form our main target, seem to share some structural properties [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF]. Later, we return to this. First, we determine under which conditions the partial storage of explored states in the Closed set does not remove the termination guarantee of BFS.

Partial Storage of Explored States and Termination

Let us consider the relation between partial storage of explored states and termination of BFS. Earlier approaches using BFS all seem to be probabilistic in this respect; termination is at best highly likely [START_REF] Tronci | A Probabilistic Approach to Automatic Verification of Concurrent Systems[END_REF][START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF]. Consider the right search tree from Figure 1, now with Closed = {1.1}. Note that this is sufficient to generate the LTS without any redundancy. But, focusing on termination, there are more possibilities; consider Closed = {2.3}. Even though node 3.5 is not recognised as identical to node 1.1, leading to redundancy in the LTS, the generation will terminate, as node 4.6 will be recognised as identical to the, stored, node 2.3. In other words, the fact that we store search level 2 means that the algorithm terminates. [START_REF] Behrmann | To Store or Not To Store[END_REF] calls a set of vertices in an automaton which ensures termination if states associated with them are stored a covering set. Similarly, we call a set of states a covering set if stored related nodes ensure termination. Periodically storing levels seems sufficient to always have a represented covering set in memory. In those cases where a state s is explored again, some of its 'descendants', either immediate or remote successors, will be recognised as part of a stored level, hence the redundant work resulting from the detection failure at s is finite. The levels should be stored completely, otherwise redundant traces may never be recognised as such (more precisely, levels need to be stored without any internal redundancy: in the example tree, note that node 2.4 does not need to be stored, as it is identical to node 2.3.). We call these stored levels snapshots.

Periodically storing levels allows us the construction of a covering set on-the-fly, as long as there is no bound on the number of snapshots in memory. We investigate this setup in more detail in Section 3.2. However, we are also interested in bounding the number of snapshots in memory, since it allows us to be more rigorous at removing states. Algorithm 1 shows this technique, which we call 'BFS with Snapshots' (BFSWS), where a sampling function f is used to determine at which levels to make snapshots, and n is the maximum number of snapshots in memory. When n → ∞, we are able to store an unbounded number of snapshots.

It is important to note that although duplicates are removed from Next before the new horizon is created, this is not done when making a new snapshot, in order to keep the levels complete. As explained in Section 4, though, storage of states in snapshots can be implemented such that duplicate occurrences cost little extra memory to keep. Next,

Algorithm 1 BFS with Snapshots

Require: Sampling function f : N → B, number of snapshots n procedure BFSWS(s 0 ) i, j ← 0, Open ← {s 0 }, S 0 , . . . , S n-1 ← / 0 {Initial state added to horizon} S j ← Open {First snapshot contains initial state} while Open = / 0 do {Repeat until there are no more states to explore}

i ← i + 1, Next ← / 0 {The next level (i + 1) is currently empty} for all s ∈ Open do {Explore all states in the horizon} Next ← Next ∪ {s ′ | ∃ℓ.(s, ℓ, s ′ ) ∈ en(s)} Open ← Next \ n-1 k=0 S k {Add new states to horizon} if f (i) then j ← j + 1 mod n, S j ← Next
{Should this level be sampled?} Lemma 1 shows under which conditions we can guarantee termination of BFSWS even if the number of snapshots is limited. We prove that BFSWS terminates as long as the sampling period, i.e., the number of levels between the taking of snapshots, increases along the search. From f , we can derive a function p f as follows:

p f (0) = 0, (as we assume f (0) is true)

-p f (i) = d, with i, d ∈ N, i, d > 0, f (p f (0) + . . . + p f (i -1) + d) ∧ ∀0 < d ′ < d.¬ f (p f (0) + . . . + p f (i -1) + d ′ )
In words, p f expresses the subsequent sampling periods observable in f . Now, we need to prove that BFSWS is terminating for finite LTSs if p f is increasing.

Lemma 1. BFSWS of a finite LTS with a finite number of snapshots n > 0, is terminating if p f is increasing.

Proof. Let us consider a cycle of size k in an LTS. In a generation tree of BFSWS without duplicate detection, this cycle will be generated infinitely often, leading to

s 0 , s 1 , . . . , s k-1 , s k . . . , s 2k-1 , s 2k , . . . etc. 1 , with ∀0 ≤ i ≤ k -1, ∀ j ∈ N.s i = s i+ j•k .
We need to prove that by taking n snapshots, with p f increasing, the cycle will be detected. First, we consider the case n = 1. Other cases follow from this. Without loss of generality, we say that the first snapshot including a state from the cycle is taken while traversing the cycle for the first time. We call this state ŝ0 = s d , with 0 ≤ d ≤ k -1. Let us first consider a p f with ∀i ∈ N.p f (i) = p, and p < k. It follows that for subsequent snapshots ŝi = s d+i•p , with i ∈ N. Observe that with ŝ0 , duplicate detection will succeed when reaching state s d+k . But, since p < k, we have s d+p → + s d+k , i.e., ŝ1 → + s d+k . Because n = 1, we lose ŝ0 after creating ŝ1 , hence there is no duplicate detection when we reach s d+k . Similarly, with ŝ1 , duplicate detection can happen when reaching s d+p+k , but ŝ2 → + s d+p+k . In general, with ŝi , detection may happen at state s d+i•p+k , but ŝi+1 → + s d+i•p+k . However, if p ≥ k, we have with ŝi that s d+i•p+k → * s d+(i+1)•p , i.e., s d+i•p+k → * ŝi+1 , so the next snapshot would be created some time after the exploration of s d+i•p+k , but when s d+i•p+k is reached, duplicate detection takes place and the cycle traversal is terminated. If p f is increasing, it follows that there exists i ∈ N such that p f (i) ≥ k, hence BFSWS can, in that case, deal with any cycle of arbitrary size. The case of BFSWS with n > 1 is a generalisation of case n = 1. For a p f with ∀i ∈ N.p f (i) = p, if n • p < k, for all ŝi , detection may happen at state s d+i•p+k , but s d+(i+n)•p → + s d+i•p+k , i.e., ŝi+n → + s d+i•p+k , and ŝi+n replaces ŝi . If n • p ≥ k, then for ŝi , s d+i•p+k → * s d+(i+n)•p , i.e., s d+i•p+k → * ŝi+n , hence duplicate detection will take place at s d+i•p+k . If p f is increasing, clearly BFSWS with n > 1 also terminates.

BFSWS is guaranteed to terminate if the sampling period is bigger than the size of the largest cycle in the LTS. Since we do not know this size a priori, constantly increasing the period ensures that eventually, the sampling period will be big enough. Now that we know under which conditions BFSWS always terminates, we can look at additional techniques to minimise the amount of redundant work, in order to keep the LTSs on disk as small as possible, and the execution time.

Maximising the Efficiency of Partial Duplicate Detection

BFS With Snapshot Caches As explained in Section 1, a cache may contain a finite number of elements. For BFSWS, we can use a cache to store snapshots, as opposed to individual states, which is more common in related work. By choosing complete snapshots as elements, BFSWS is guaranteed to terminate, but it is impossible to enforce a fixed size of the cache. This seems at odds with the principle of a cache, but the caches of webbrowsers work in a somewhat similar manner; such a cache must always contain complete files, not parts of files, even though the files vary in size. For state space caching, this does not cause real problems, since in practice it shows that the gain in memory is still considerable. The size, together with the replacement strategy, which dictates which element to remove in case the cache is full, typically defines a cache. To this, we add the sampling function, which deals with the input of elements, resulting in the following definition.

Definition 2 (state space generation cache). A state space generation cache C i is a triple ( f i , R i , n i ), with f i : N → B the sampling function, R i : 2 2 S ×2 N → 2 S the replacement function, taking a set of snapshots together with meta-data about the snapshots (in the form of natural numbers), and returning a snapshot to be removed next, and n i the maximal number of snapshots in the cache.

Figure 2 illustrates a stream hierarchy of state space generation caches, in a way in which also in hardware architectures, multiple caches can be linked together. The f i of a cache C i decides which snapshots to accept for storage, n i is the maximum number of snapshots it contains, and R i is the replacement strategy. The removal of a snapshot from C i leads to the input of a snapshot in C i+1 , that is, if f i+1 accepts it, etc. In general, R i computes the cost of every snapshot in the cache based on a cost function c : 2 N → N, and picks the snapshot with the lowest cost for the next removal. The cost function can use any accumulated data during the generation, e.g., (a) size of the snapshot, (b) snapshot level number, i.e., the time the snapshot was created, (c) the last time duplicate detection succeeded due to the snapshot, and (d) hit ratio of the snapshot, i.e., how many times duplicate detection succeeded due to the snapshot.

R i f i n i

Fig. 2. A stream hierarchy of state space generation caches

This machinery allows for a wide range of configurations, since it involves at least four new parameters: the number of caches, and per cache a sampling function, a size, and a replacement strategy. Next, we explain which configurations make sense for the generation of LTSs stemming from real specifications.

Exploiting Transition Locality Related attempts to search LTSs with partial duplicate detection often use a notion called transition locality l of states [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF][START_REF] Korf | Frontier search[END_REF]. This is a property of an LTS together with a corresponding traversal tree of traditional BFS, i.e., without caching. It expresses the biggest distance, measured in levels, between any two nodes which are considered equal. In Figure 1, for the LTS together with the left tree, l = 2, as nodes 1.1 and 3.5 are considered equal. It has been claimed [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF][START_REF] Korf | Frontier search[END_REF] that l is extremely low for LTSs resulting from real protocol specifications. This can be exploited by only keeping the last l levels of the tree in memory, which yields a version of BFS called frontier search [START_REF] Korf | Frontier search[END_REF] 2 . Algorithm 1 describes frontier search if f (i) equals true for all i ∈ N, and n = l. Termination is only guaranteed if n ≥ l, n = l being ideal, since it saves as much memory as possible with this technique. However, in practice, l is not known before traversal of the LTS, therefore termination cannot be guaranteed. In addition, our experience points out that, although the majority of equalities concern nodes which are indeed very close to each other, there are usually also some equal nodes which are much further removed from each other, e.g., more than half the total depth of the tree. This differs from the results reported by [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF][START_REF] Korf | Frontier search[END_REF], possibly because we look at a large set of specifications of varying types of systems. In case l is close to the full depth of the tree, which is likely to happen for e.g., cyclic processes, one cannot gain that much memory.

However, the fact remains that often, most nodes which are considered equal are very close to each other in the tree. We choose to exploit this by setting up a stream of caches, the first one sampling frequently, and subsequent ones sampling less often, as identification with 'older' nodes is less likely to happen. Then, for the first cache, we can choose n 1 < l, which not only removes the necessity to know l a priori, but for LTSs where l is large, we can also save more memory compared to frontier search and related techniques. Related to this, Tronci et al. [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF] deal with distances larger than l in a probabilistic way, while we guarantee eventual detection, hence termination. Streams of caches can be set up in many different ways; we consider two, the results of which will be discussed in the next section:

1. The first cache samples often, in fixed periods, and a second cache employs a sampling function with increasing period, i.e., conform Lemma 1. We call this setup Frontier Safety Net, since in addition to having a frontier cache, we also have some safety nets to fall back on. 2. Initially, there is one cache, C 1 , sampling often, in fixed periods. As soon as the cache is full, another one, C 2 , with the same setup is created and connected behind C 1 . Whenever this cache is full, a third one is created, etc. If the sampling period of the caches is not 0, i.e., not every level is sampled, then the further down the stream, the fewer levels are accepted by a cache, hence the longer it takes before the cache is full. Since the number of snapshots allowed in memory is not bounded, this setup guarantees termination of the algorithm. We call this setup Pebble Search, since the distribution of the snapshots over a generation tree resembles the waves produced by a pebble when dropped in a pool, i.e., the further away from the point of impact, i.e., the horizon, the further the distance between waves.

The Backtracking Set In our experience, Frontier Safety Net and Pebble Search lead to good reductions of the memory use, ranging from 50% to sometimes less than 10%, as will be shown in the next section. However, if there are many duplicates to be detected at a distance greater than n 1 × p 1 , with p 1 the constant sampling period of cache C 1 , then this tends to lead to a big increase of redundant work, negatively affecting both the execution time and the output LTS. Consider Figure 3, where in the Open set, node 0 is equal to node 1, which has been explored before, but removed from memory by now. Therefore, node 0 will be re-explored, leading to nodes equal to nodes 2 and 3, the successors of node 1. Since nodes 2 and 3 are also removed, these new nodes are explored as well, and their successors are finally identified as equal to the successors of nodes 2 and 3, since these are present in a snapshot, i.e., the grey bar. All in all, failure to recognise that node 0 has essentially been seen before leads to the traversal of 6 redundant transitions. In state space traversal, the traversal of transitions is the most time-consuming operation, therefore this redundant work has a real impact on the overall execution time. In both our setups, the older the levels, the fewer remain in memory, hence, the larger the distance between equal nodes, the more likely it is that failure of duplicate detection leads to the exploration of many nodes before a snapshot is 'reached'. On the one hand, only keeping a few very old levels makes sense, since new nodes do not often refer back to very old nodes. On the other hand, on those occasions where they do, we often obtain a significant amount of redundant work. Let us call the branching factor, i.e., the average number of successors of a state in the LTS, b, and the distance between an old node and the nearest subsequent snapshot d, then every detection failure leads to approximately ∑ d i=1 b i additional traversals. In practice, it turns out that if a much older node, i.e., older than only a few levels ago, is referred to again once, then it tends to be referred to several times more later on, in our case each time leading to at least ∑ d i=1 b i extra traversals (in subsequent re-explorations, the nearest snapshot may well have been removed from memory, thereby increasing the distance to the next snapshot). 3These nodes seem to represent states which are very common for the specified systems, imagine e.g., the specification of a car; there are many ways to use the car, but eventually you return to the state representing 'off'. By keeping the node representing 'off' in memory, we can avoid a lot of redundant work. Recognising these important nodes is very hard, but we propose a mechanism for BFSWS which can guess which nodes are important. Every time a node is revisited, the mechanism gets closer to discovering this revisiting. For this we introduce an extra, unbounded, set of nodes to be kept in memory, the Backtrack set. While traversing, this set is filled with nodes by following two rules, where very old snapshots are defined as 'not in cache C 1 ': 1) given a node N in the Open set with | succ(N) |> 1, if there exists a snapshot S i not in C 1 such that for all N ′ ∈ succ(N), there exists N ′′ ∈ S i with N ′ = N ′′ (i.e., N ′ is considered equal to N ′′ ), then we add N to Backtrack, and 2) given a node N in the Open set with | succ(N) |> 1, if for all N ′ ∈ succ(N), there exists N ′′ ∈ Backtrack with N ′ = N ′′ , then we add N to Backtrack. The first rule states that if all the successors of a node are detected as duplicates due to a single very old snapshot, then it is very likely that we have explored their parent before. The more successors the node has, the more likely this is, hence we exclude the case here of a single successor. Failure to detect duplicates which only have one successor does not directly lead to much redundant work anyway. The second rule is a continuation of this: if all the successors of a node are suspected of having been re-explored, then we suspect this node as well. With this technique, we bound and lessen the amount of redundant work with each revisit of a node; the n th revisit leads to ∑

|d-(n-1)| i=0

b i -1 extra traversals. Practice shows that this learning mechanism is very successful, as seen next. By only keeping a few extra nodes in memory according to these rules, we sometimes reduce the amount of redundant work considerably.

Implementation, Caching Setups, and Experiments

We built a generic, application-independent implementation of the caching machinery using the OPEN/CAESAR [START_REF] Garavel | OPEN/CAESAR: An Open Software Architecture for Verification, Simulation, and Testing[END_REF] environment of the CADP toolbox [START_REF] Garavel | CADP 2006: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF], which provides various primitives for state space storage and exploration (hash tables, edge lists, stacks, etc.). The cache library allows to define caches containing a fixed number of elements, either states or snapshots, each one being possibly assorted with user-defined information allowing, e.g., to calculate the cost associated to the element. The replacement strategy used by a cache can be user provided, or selected among five built-in strategies: least/most recently used (LRU/MRU), least/most frequently used (LFU/MFU), and random (RND). The elements of a cache are stored in a balanced heap equipped with a hash table in order to allow fast retrievals of the lowest-cost element and fast searches of elements. A special primitive retrieves the last element replaced after an insertion took place in an already full cache; this allows to manage hierarchical caches (organized, e.g., as trees) by retrieving an element from one cache and inserting it into another.

The most basic usage of the cache library is for storing visited states, assorted with their id's, during a DFS traversal of the state space. A more complex usage is made by the BFSWS approach, where elements stored in the cache are snapshots (lists of states) but the searches carried out for duplicate detection concern individual states. To reduce memory consumption, states belonging to the set of snapshots currently present in a cache are stored uniquely and referenced through pointers; state deletion is done efficiently using a reference counting scheme borrowed from garbage collection [START_REF] Knuth | The Art of Computer Programming -Volume III: Sorting and Searching[END_REF]. Next, we study the performance of several BFS and DFS setups experimentally. For this, we used around 35 LTSs from the VLTS benchmark suite [START_REF] Vlts | The VLTS Benchmark Suite[END_REF] stemming from real, industrial case studies, and also several communication protocols [START_REF]CADP online demo examples[END_REF]. The experiments were run on a LINUX machine with a 2.2GHz CPU and 1 GB memory.

BFS Experiments

Here, we show the results of a representative selection of cases, generated by standard BFS and by BFSWS using some of the most successful cache setups. Caches are described as triples, a sampling function which increases its period by n after every sampling being written as n, a function with constant period n being written as cn, LLNR being a replacement function based on lowest level number, and BT indicating the backtracking mechanism. The top three graphs visualise the results on several instances of the Bounded Retransmission Protocol (BRP), varying in both the size of messages and the number of retransmissions. Here, the techniques are extremely effective, allowing not only to reduce the memory use drastically, but also to make the generation much faster. This is due to the hash table being very small, which speeds up duplicate detection. Usually, this gain is countered by failed detections, leading to more (time consuming) transition traversals, but here such failures hardly occur. Additional tests showed that we could generate the LTS for BRP 300, 300 , consisting of more than 410, 000, 000 states, in 37 hours with (c2, LLNR, 5)(2, LFU, 10), and in 22 hours with backtracking. The bottom three graphs show the generation results for the SCSI-2 bus arbitration protocol, varying the number of competing disks. Here, memory use can be reduced to 20% compared to standard BFS, using a Frontier Safety Net with backtracking. Moreover, both backtracking setups show practically no increase in execution time, and the number of redundant states produced is reasonable.

The graphs below compare execution times and state generation of BFS and 3 sampling setups. Execution times of the setups are often much longer than for BFS, due to using more complex data structures, and the redundant work. However, this effect becomes mainly apparent with small examples. The bottom two graphs relate output LTS sizes with the original sizes, indicating the number of states in memory by the size of the bubbles. Bubbles on the same horizontal line relate to the same case. Pebble Search with backtracking sometimes produces remarkably smaller LTSs than the other methods, and faster, suggesting that for these cases, keeping snapshots which are more evenly distributed over the history of the generation pays off. In Frontier Safety Net, the second cache samples more and more infrequently, eventually leaving a big 'hole' in the stored history. There is still room for improvement, though, which we plan as future work. For most cases, memory use can be reduced to about 30% using the sampling mechanism. The graphs show that either backtracking has a very positive effect (e.g. in execution time), or no effect; a negative effect hardly ever occurs. This makes backtracking a useful feature to enable by default in the BFSWS state space generator.

DFS with caches

Our generic cache machinery can also be used in conjunction with other graph traversals in order to reduce the amount of memory needed for generating an LTS. The figure below shows the behaviour of DFS equipped with cycle detection (by searching states on the DFS stack) and a hierarchical MFU, LRU cache, executed on a subset of the VLTS benchmark suite. For each example, the figure gives the minimal size of the cache yielding an output LTS of size at most double w.r.t. the input LTS. Among the five built-in replacement strategies, LRU performs best on all examples (reducing the cache size down to 40% of the number of states), followed closely by MFU and RND. LRU is close to the strategy removing the oldest states, which was rated best among the strategies analysed in [START_REF] Holzmann | Automated Protocol Validation in Argos, assertion proving and scatter searching[END_REF]. If we split the cache into two cascading subcaches of varying sizes and different replacement strategies, the best cache size reduction (down to 30% of the number of states) was achieved by using an MFU or RND subcache followed by an LRU subcache (of about 25% of the whole cache). Overall performance (see the figure above) was further improved by increasing the LRU subcache to 75%. Compared to BFSWS, the success of DFS setups differs a lot from one case to another. Moreover, a difficulty with 'fixed size' DFS caching is to determine the right size of the cache, which, in order to be effective, should lie between 30 -60% of the (a priori unknown) LTS size; BFSWS, on the other hand, simply takes whatever memory it needs.

Related Work

As mentioned in the introduction, existing approaches for state space generation can roughly be divided in two classes. In the second class, where exhaustiveness is not guaranteed, hashing without collision detection is often used, which is a way to ensure that the hash table stores a fixed number of states. Concerning collisions, [START_REF] Holzmann | An Improved Protocol Reachability Analysis Technique[END_REF][START_REF] Courcoubetis | Memory-Efficient Algorithms for the Verification of Temporal Properties[END_REF] assume that whenever a collision happens in the hash table, the new state has already been visited. In [START_REF] Courcoubetis | Memory-Efficient Algorithms for the Verification of Temporal Properties[END_REF], this is used for a nested DFS to search for errors in LTSs. Collision avoidance in this way guarantees termination. [START_REF] Tronci | Exploiting Transition Locality in Automatic Verification[END_REF][START_REF] Della Penna | Exploiting Transition Locality in the Disk Based Murphi Verifier[END_REF] take the opposite approach concerning this. They fully depend on LTSs of protocols having small localities. They avoid collision detection, by removing a previously stored state if there is a hash collision with a new state, arguing that in most cases this means removing a state beyond the locality region. Termination is handled by stopping the search once the collision rate is sufficiently high, or a maximum search depth has been reached. In [START_REF] Tronci | A Probabilistic Approach to Automatic Verification of Concurrent Systems[END_REF], a fixed size cache and Open set is used for a probabilistic, randomised BFS, where states are replaced at random. These last two cases report memory savings of 40% on average, the first case achieving this partly by keeping the Open set on disk. In [START_REF] Stern | Combining State Space Caching and Hash Compaction[END_REF], the probability of failures is reduced by using open addressing and t-limited lookups and insertions in the hash table, where a hash function provides not one position for a state in the hash table, but a sequence of t possible locations. In addition to this, [START_REF] Stern | A New Scheme for Memory-Efficient Probabilistic Verification[END_REF] includes the level number of a state in a BFS in calculating its omission probability.

The other class, guaranteeing exhaustiveness, includes most state space caching work, which has been done for DFS [START_REF] Holzmann | Automated Protocol Validation in Argos, assertion proving and scatter searching[END_REF][START_REF] Godefroid | State-Space Caching Revisited[END_REF][START_REF] Jard | Bounded-memory Agorithms for Verification On-the-fly[END_REF][START_REF] Geldenhuys | State Caching Reconsidered[END_REF]. In [START_REF] Holzmann | Automated Protocol Validation in Argos, assertion proving and scatter searching[END_REF], several replacement strategies are used for a single LTS, and the conclusion is that the one selecting the oldest states is the best. [START_REF] Jard | Bounded-memory Agorithms for Verification On-the-fly[END_REF] continue on this, believing the conclusion to be a random strategy. [START_REF] Geldenhuys | State Caching Reconsidered[END_REF] reinvestigates this, employing many other strategies on many examples, some of them from practical cases. In those cases, a proposed strategy called stratified caching with random replacement performs best. Here, strata are created, very similar to our snapshots. The states of certain strata, however, are candidates for removal from memory, as opposed to storing in memory. Caching is combined with static analysis and partial order reduction in [START_REF] Godefroid | State-Space Caching Revisited[END_REF]. Our setting allows hierarchies of caches, and they can be used to store snapshots in case of BFS. In [START_REF] Behrmann | To Store or Not To Store[END_REF], an unbounded set of states is stored based on a storing strategy, usually based on static analysis. They claim that up to 90% can be saved in memory use, but, as reported by [START_REF] Hammer | To Store or Not To Store" Reloaded: Reclaiming Memory on Demand[END_REF], this leads to an extensive amount of redundant work. In [START_REF] Hammer | To Store or Not To Store" Reloaded: Reclaiming Memory on Demand[END_REF], a hash table is initially used in a traditional manner, until it fills up the whole memory, at which point older states are moved to secondary storage.

The number of lookups on disk is reduced by using a Bloom filter. Instead of trying to use memory in a smarter way, they want the generation to be able to continue once the memory is filled. We experience that trying to avoid a big Closed set pays off in terms of execution time, since the hash table is kept small. However, our BFS method may still run out of memory. It could be interesting to look at a combination of the two.

In Artificial Intelligence (AI), connecting to directed model checking, multiple methods are presented to bound the memory use of exhaustive search algorithms, e.g., IDA * [START_REF] Korf | Depth-first iterative-deepening: An optimal admissible tree search[END_REF], MA * [START_REF] Chakrabarti | Heuristic Search in Restricted Memory[END_REF], and extensions IE and SMA * [START_REF] Russell | Efficient memory-bounded search methods[END_REF]. As is common in this field, the algorithms employ a cost function, mapping states to costs. For memory-bounding, this function is used to decide which states to remove from memory. The cost function provides knowledge of the LTS structure a priori, and its main purpose is to guide the search to a goal state. In this paper, we are neither concerned with a subset of goal states, nor have any structural knowledge. It is, however, possible to incorporate the AI algorithms in our framework, like DFS and BFS, in order to obtain more memory efficient variants.

Conclusion and Future Work

We presented generic machinery for hierarchical, adaptive state space caching, implemented using the OPEN/CAESAR environment [START_REF] Garavel | OPEN/CAESAR: An Open Software Architecture for Verification, Simulation, and Testing[END_REF] of the CADP toolbox [START_REF] Garavel | CADP 2006: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF]. This machinery can be used in a very flexible manner for state space generation, in conjunction with DFS and BFS traversals. Our algorithm BFSWS is exhaustive and guaranteed to terminate, and its behaviour can be finely tuned using the caching and learning mechanisms introduced in Section 3. These techniques compete favourably with earlier ones, such as hashing without collision detection and frontier search, which only concern LTS search (and not generation), lack termination or exhaustiveness (or both), or are dedicated to LTSs with small localities. The learning mechanism for BFSWS strongly reduces the amount of redundant work, and is also able to speed up the generation.

As future work, we will study other BFSWS configurations on further examples (e.g., the BEEM benchmark [START_REF] Pelánek | Properties of state spaces and their applications[END_REF]), and try to design additional mechanisms to deal more efficiently with different LTS structures. Secondly, we plan to adapt the machinery for distributed state space generation [START_REF] Garavel | Parallel State Space Construction for Model-Checking[END_REF]. Finally, we want to investigate its use in conjunction with on-the-fly LTS reduction modulo τ-confluence and branching bisimulation.

  and the set of successor states succ(s) = {s ′ ∈ S | ∃ℓ ∈ A .(s, ℓ, s ′ ) ∈ en(s)} consists of all states reachable from s via a single transition.

Fig. 1 .

 1 Fig. 1. BFS with and without a Closed set

Fig. 3 .

 3 Fig. 3. Duplicate work

As we enumerate the states of the cycle here, s 0 is not necessarily the initial state of the LTS.

In the original setting of Artificial Intelligence, a predecessor function is assumed to be available to have access to the recent predecessors. Lacking such a function in on-the-fly model checking, the last l levels should be stored[START_REF] Edelkamp | Survey on Directed Model Checking[END_REF].

[START_REF] Holzmann | Automated Protocol Validation in Argos, assertion proving and scatter searching[END_REF] reports that no relation is found between the number of previous visits to a state and the likelihood that it will be visited again in the future. We found that revisits are likely to states which had 'late' revisits, i.e., revisits many levels after the first visit.