Dr Bo Li

Dr Rachida Aid-Launais

Marie-Noëlle Labour

Dr Alina Zenych

Maya Juenet

Dr Christine Choqueux

Dr Véronique Ollivier

Dr Olivier Couture

Dr Didier Letourneur

Cédric Chauvierre
email: cedric.chauvierre@inserm.fr

Marie-Noelle Labour

M-N Labour

Functionalized Polymer Microbubbles as New Molecular Ultrasound Contrast Agent to Target P-selectin in Thrombus

Keywords: polymer microbubbles, fucoidan, P-selectin, molecular ultrasound imaging, thrombosis

come   L'archive ouverte pluridisciplinaire

Introduction

Thrombotic diseases, such as deep vein thrombosis, are often called "the silent killer" because they rarely cause symptoms until an advanced stage [START_REF] Mackman | Triggers, targets and treatments for thrombosis[END_REF][START_REF] Lippi | Arterial thrombus formation in cardiovascular disease[END_REF][START_REF] Jackson | Arterial thrombosis--insidious, unpredictable and deadly[END_REF]. Early detection and treatment can improve the prognosis and reduce mortality. P-selectin, an adhesion molecule, mainly expressed on the surface of activated platelets and injured vascular endothelium, is involved in the pathophysiology of intraluminal thrombus formation and other cardiovascular diseases [START_REF] Choudhury | Molecular, cellular and functional imaging of atherothrombosis[END_REF][START_REF] Yokoyama | Platelet P-selectin plays an important role in arterial thrombogenesis by forming large stable platelet-leukocyte aggregates[END_REF]. These features suggest that P-selectin can be an important target for molecular imaging of thrombosis or in acute and chronic cardiovascular diseases [START_REF] Boersma | P-selectin imaging in cardiovascular disease: what you see is what you get?[END_REF][START_REF] Schaefer | New biomarkers and imaging approaches for the diagnosis of deep venous thrombosis[END_REF][START_REF] Brangsch | Molecular Imaging of Abdominal Aortic Aneurysms[END_REF].

We have previously demonstrated that fucoidan, an abundant and cost-effective marine polysaccharide with sulfated chains, exhibits a high affinity for immobilized P-selectin in vitro [START_REF] Bachelet | Affinity of low molecular weight fucoidan for P-selectin triggers its binding to activated human platelets[END_REF][START_REF] Silva | Polysaccharide Nanosystems for Future Progress in Cardiovascular Pathologies[END_REF]. 99m Tc-fucoidan as a radiotracer has already proved in vivo to be able to detect thrombus and heart ischemia associated with the P-selectin overexpression in our previous studies [START_REF] Rouzet | Radiolabeled fucoidan as a p-selectin targeting agent for in vivo imaging of platelet-rich thrombus and endothelial activation[END_REF][START_REF] Saboural | Purification of a low molecular weight fucoidan for SPECT molecular imaging of myocardial infarction[END_REF]. Recently, we have developed fucoidan functionalized core-shell polymer microcapsules and proved that they have high specific binding efficiency to P-selectin under flow conditions [START_REF] Li | Development of Polymer Microcapsules Functionalized with Fucoidan to Target P-Selectin Overexpressed in Cardiovascular Diseases[END_REF]. Moreover, fucoidan functionalized nano-/microparticles have also been developed as a molecular contrast agent to monitor thrombi by Magnetic Resonance Imaging (MRI) or Single-Photon Emission Computed Tomography (SPECT) imaging [START_REF] Suzuki | Ultrasmall superparamagnetic iron oxide nanoparticles coated with fucoidan for molecular MRI of intraluminal thrombus[END_REF][START_REF] Bonnard | Abdominal Aortic Aneurysms Targeted by Functionalized Polysaccharide Microparticles: a new Tool for SPECT Imaging[END_REF][START_REF] Bonnard | Leukocyte mimetic polysaccharide microparticles tracked in vivo on activated endothelium and in abdominal aortic aneurysm[END_REF].

Compared to other imaging modalities, ultrasound imaging has numerous advantages, including comfortable, noninvasive, portable, low cost real-time imaging, lack of ionizing radiation and excellent safety profile [START_REF] Emilia | Perfluorooctyl Bromide Polymeric Capsules as Dual Contrast Agents for Ultrasonography and Magnetic Resonance Imaging[END_REF][START_REF] Perera | Ultrasound imaging beyond the vasculature with new generation contrast agents[END_REF]. Ultrasound imaging equipment is already present in most hospitals all around the world and even in private health centers. However, ultrasound image quality is limited by its poor contrast due to the low differences in acoustic characteristics of organs in vivo. The development and use of microbubbles (MBs) have redeemed this shortage tremendously [START_REF] Stride | Microbubble ultrasound contrast agents: a review[END_REF][START_REF] Cosgrove | Ultrasound contrast agents: an overview[END_REF][START_REF] Gessner | Advances in molecular imaging with ultrasound[END_REF][START_REF] Kiessling | Ultrasound microbubbles for molecular diagnosis, therapy, and theranostics[END_REF].

Traditional MBs are mainly made up of albumin/lipid/surfactant shells and have not only been applied as ultrasound agents, but also have been used in versatile biomedical applications including drugs, genes and drug-loaded nanoparticles targeted delivery [START_REF] Wang | A Novel Microbubble Capable of Ultrasound-Triggered Release of Drug-Loaded Nanoparticles[END_REF][START_REF] Huang | Advances in ultrasound-targeted microbubble-mediated gene therapy for liver fibrosis[END_REF]. Recently, polymeric shells MBs have received increasing attention due to their improved stability and some polymersomes have also been applied in drug controlled release at the target site under a specific stimulus such as ultrasound [START_REF] Xiong | Polymeric microbubbles for ultrasonic molecular imaging and targeted therapeutics[END_REF][START_REF] Liao | Recent advances in formation, properties, and applications of polymersomes[END_REF]. Poly(AlkylCyanoAcrylate) with long alkylcyanoacrylate monomers (for example, n-butyl, isobutyl, isohexyl and octyl) has been extensively investigated to design micro-/nanocarriers since the 80s [START_REF] Vauthier | Poly(alkylcyanoacrylates) as biodegradable materials for biomedical applications[END_REF][START_REF] Delplace | Degradable vinyl polymers for biomedical applications[END_REF]. The first Poly(ButylCyanoAcrylate) microbubbles called Sonavist ® were manufactured by one-step process through adding the n-butyl-2-cyanoacrylate monomers into gas-water emulsion [START_REF] Stein | Ultrasonic imaging agents, process for their preparation and their diagnostic and therapeutical use[END_REF][START_REF] Harris | The structure of gas-filled n-butyl-2-cyanoacrylate (BCA) polymer particles[END_REF].

Palmowski et al. further synthesized streptavidin-coated PBCA microbubbles and investigated their physicochemical properties [START_REF] Palmowski | Vessel fractions in tumor xenografts depicted by flow-or contrast-sensitive three-dimensional high-frequency Doppler ultrasound respond differently to antiangiogenic treatment[END_REF][START_REF] Palmowski | Molecular profiling of angiogenesis with targeted ultrasound imaging: early assessment of antiangiogenic therapy effects[END_REF][START_REF] Palmowski | Pharmacodynamics of streptavidin-coated cyanoacrylate microbubbles designed for molecular ultrasound imaging[END_REF]. Subsequent studies proved that these microbubbles could be functionalized by conjugating with monoclonal antibodies that recognize receptor proteins involved in various diseases [START_REF] Koczera | Fluorescently labeled microbubbles for facilitating translational molecular ultrasound studies[END_REF][START_REF] Fokong | Image-guided, targeted and triggered drug delivery to tumors using polymer-based microbubbles[END_REF][START_REF] Wu | Rhodamine-loaded intercellular adhesion molecule-1-targeted microbubbles for dual-modality imaging under controlled shear stresses[END_REF].

However, employing, for instance, biotin/streptavidin and antibodies limited their use in humans because of the costs and potential immunogenicity of streptavidin and antibodies. Recently, various bubbles using small peptides instead of antibodies for binding without using the biotin-streptavidin coupling strategy have already been developed to address these problems [START_REF] Fokong | Ultrasound molecular imaging of E-selectin in tumor vessels using poly n-butyl cyanoacrylate microbubbles covalently coupled to a short targeting peptide[END_REF][START_REF] Spivak | Low-Dose Molecular Ultrasound Imaging with E-Selectin-Targeted PBCA Microbubbles[END_REF]. Among them, BR55, as the most potential targeted-MBs contrast agent, shows that it could be used to detect the prostate cancer or monitor breast and ovarian lesions in human clinical trials [START_REF] Smeenge | First-in-Human Ultrasound Molecular Imaging With a VEGFR2-Specific Ultrasound Molecular Contrast Agent (BR55) in Prostate Cancer: A Safety and Feasibility Pilot Study[END_REF][START_REF] Willmann | Ultrasound Molecular Imaging With BR55 in Patients With Breast and Ovarian Lesions: First-in-Human Results[END_REF].

In the view of future clinical applications, MBs assembled by clinically approved polymers and suitable targeting ligands are interesting for clinical use and market requirements.

In this work, we report a new one-step process to obtain polysaccharide-coated poly(IsoButylCyanoAcrylate) (PIBCA) microbubbles. Among them, fucoidan functionalized microbubbles (Fucoidan-MBs) were considered as a targeted ultrasound molecular imaging probe for P-selectin. Targeting of Fucoidan-MBs was evaluated in vitro using flow chambers with activated human platelets. In vivo experiments performed in a FeCl 3 -induced thrombus rat model showed that Fucoidan-MBs were located in the thrombotic area but not in healthy rats, which confirms the ability of Fucoidan-MBs to specifically target P-selectin. These functionalized echogenic microbubbles appear as new tools for imaging at molecular level cardiovascular events in which P-selectin is overexpressed.

Materials and Methods

Materials

Environmental Scanning Electron Microscopy (ESEM) and Scanning Electron

Microscopy (SEM): The surface morphology of microbubbles was imaged using an ESEM apparatus (Philips XL30 ESEM-FEG, Amsterdam, Netherlands) and SEM apparatus (JSM-IT100, Jeol, Japan). The interaction of Fucoidan-MBs with activated platelets on an ex vivo platelets-rich thrombus was also visualized using ESEM.

Briefly, to obtain the ex vivo platelets-rich thrombus, the blood was collected in citrate tubes and then centrifuged at 120 G for 15min. Plasma rich in platelets (PRP) was collected and distributed in small glass tubes (370 µL). To activate platelets, calcium chloride was added (7 µL at 1M) and the tubes were incubated at 37 °C for 1h. The platelet-rich thrombus was detached from the walls of the glass tubes and then transferred to a 96-well plate where it was be put in contact with Fucoidan-MBs for 5 min. After several rinses with 0.9% NaCl, the thrombus was fixed at 4% paraformaldehyde for 24 hours and then rinsed for visualization by ESEM.

The binding of Fucoidan-MBs on the luminal thrombus of inferior vena cava was observed using ESEM. Briefly, we performed an inferior vena cava thrombus rat model induced by ferric chloride (FeCl 3 ), and injected Fucoidan-MBs. The rat was then euthanatized and the inferior vena cava with thrombus was picked up and fixed in 4% paraformaldehyde for 24 hours and rinsed in saline. The inferior vena cava was opened longitudinally on the top to observe the thrombus by ESEM.

Confocal imaging: Microbubbles were imaged using Zeiss LSM 780 confocal microscope fitted with 63X objective. Microbubbles were detected using rhodamine B and polysaccharides with FITC-Fucoidan and FITC-CM-Dextran.

Quantification of Fucoidan content:

The amount of fucoidan in microbubbles was determined by methylene blue staining of sulfated polysaccharides [START_REF] Lee | Solid-Phase Colorimetric Method for the Quantification of Fucoidan[END_REF]. Several 1×1 cm square chromatography paper were placed in 24-well plate. The solution was cautiously added dropwise at the center of these squares, 2 μL for each drop; the next portions were dropped on the same point after drying off the last drop in the oven (Jouan, France) for 10 min at 50°C. The filter papers with loaded sample drops were kept in the oven overnight at 50°C, dried thoroughly and then treated with a mixture of methanol and acetone (6:4) for 3 min. Fucoidan spots on filter paper were visualized after 10 min at room temperature in staining solution containing 50 mM HCl and 0.1% (w/w) methylene blue in a mixture of methanol/acetone/water (6:4:15).

The filter paper was washed several times with a mixture of acetic acid/methanol/acetone/water (5:6:4:75) to remove the excess of methylene blue.

Images were taken, and filter paper squares were put into 1.5 ml Eppendorf centrifuge tubes with 0.5 ml of methanol containing 2% SDS during 15 min at 50°C. A volume of 0.1 ml of this extract was transferred into 96-well plate, and absorbance was Flow Chamber Experiments: Platelet dynamic binding experiments were performed according to our previous methods [START_REF] Li | Development of Polymer Microcapsules Functionalized with Fucoidan to Target P-Selectin Overexpressed in Cardiovascular Diseases[END_REF]. Briefly, Vena8 Fluoro+ channels were coated with 50 μg.mL -1 of collagen overnight in a wet chamber at 4°C and washed with 0.9% NaCl before use. Collagen fibers covering the channels were visualized by phase contrast microscopy. Human whole blood samples (EFS, Hôpital Bichat, Paris, France) were collected in 75 μM PPACK tubes and perfused through the channels for 5~10 min at arterial shear stress (67.5 dyn.cm -2 ). Platelet activation and aggregation through contact with collagen in the channels were visualized in real time with phase contrast microscopy (Carl Zeiss Microscopy, Oberkochen, Germany).

Channels were washed for 1 min with 0.9% NaCl. To confirm P-selectin expression on platelets, 20 µg.mL -1 of FITC anti-CD62P antibody was infused into one channel after platelet aggregation at arterial shear stress for 5 minutes, and the same concentration of isotype-matched FITC-IgG was injected through the other channel as a control. For binding assay, platelets were labeled with DIOC6 (0.15 × 10 -3 M) before their injection. After platelet aggregation, fluorescent microbubbles (CM-Dextran-RhoB-MBs or Fucoidan-RhoB-MBs) were injected through the channels at 1 × 10 8 mL -1 for 5 min under venous shear stress (6.75 dyn.cm -2 ).

Channels were finally washed for 15 min with 0.9% NaCl at the same shear stress.

Fluorescence microscopy videos and images were taken along each channel using the same parameters. Quantitative analysis was performed on 7 channels per type of microbubbles. The mean fluorescent intensity of the red fluorescence channel of twenty aggregates was measured using Zen 2012 Software (Carl Zeiss, Oberkochen,

Germany).

In Vitro Ultrasound Imaging: Ultrasound imaging performances were evaluated with a VisualSonics Vevo ® 2100 imaging system (FUJIFILM VisualSonics Inc., Canada) connected to a high-frequency transducer (MS550D, VisualSonics). The set-up parameters were: frequency (40 MHz), the acquisition contrast gain (20 dB), the transmit power (4%), the frame rate (33) and the dynamic range (35 dB). All the parameters were constant throughout all image acquisition. A suspension of MBs (10 5 mL -1 ) dispersed into thin-wall PCR tubes was placed on the top of the probe, and the images were obtained by B-mode and linear contrast mode. The burst of microbubbles was performed by using high mechanical index destructive pulse (duration: 1 second).

The values of B-mode mean power of 100 frames before and after the destructive pulse were calculated by VevoCQ™ advanced contrast quantification software and shown within the scatter plot. To analyze quantitatively the contrast enhancement effect, the mean values of B-mode power of 100 frames before and after burst were calculated.

In Vitro Cytotoxicity: Mouse fibroblast 3T3 cells were cultured in Dulbecco's Modified Eagle Medium (DMEM) supplemented with 10% (v/v) fetal bovine serum, 4 mmol of L-glutamine, 1% (v/v) of penicillin and 1% (v/v) of streptomycin. The cells were kept in an incubator at 37°C in a humidified atmosphere of 5% CO 2 , 95% air. Cells were seeded (at the density of 10 4 cells per well) in 96-well plates and incubated for 24 h. The cell culture medium was removed, and 200 µL of series of dilution (10 7 , 10 6 , 10 5 and 10 4 mL -1 ) of microbubbles were added in the medium.

Culture media were used as a control. After 24 h of incubation, the supernatant was removed, 10 µL (5 mg mL -1 ) of MTT solution was added to the medium in each well, and the plates were incubated for 4 h at 37°C and 5% CO 2 . The medium with MTT was removed, and 100 µL per well of isopropanol solution was added to each well to dissolve the formazan crystals. Absorbance was measured immediately using a TECAN (Infinite M200 PRO) at 490 nm. The relative cell viability was expressed as (absorbance of microbubbles/absorbance of the control) × 100%. Biodistribution of Fucoidan-RhoB-MBs was studied in a similar way. Briefly, liver, spleen, lungs, and kidneys were excised and washed at 1 h after injection of Fucoidan-RhoB-MBs. The samples were cryosectioned, cell nuclei were labeled with DAPI, and observed by fluorescence microscopy.

In Vivo Model of Thrombosis on Rat

Statistical Analysis: All results are presented as the mean ± standard deviation (SD). Statistical differences for multiple groups were determined using a one-way ANOVA, and each experiment was performed using Student's t-test. Probabilities of p < 0.05 were considered significant. Statistical analyses were performed using GraphPad Prism 5.0.

Results and Discussion

Preparation and Characterization of Microbubbles

Limitations of the first generation of MBs were addressed either by incorporating the echogenic reflective air component into less permeable coatings, such as organic polymers and cross-linked proteins, or by employing less soluble gaseous compounds [START_REF] Guvener | Recent advances in ultrasound-based diagnosis and therapy with micro-and nanometer-sized formulations[END_REF]. Since the first PBCA MBs developed by Harris et al., several antibodies and peptides were employed to produce targeted PBCA MBs with a multi-step synthesis for molecular ultrasound imaging [START_REF] Curaj | Molecular Ultrasound Imaging of Junctional Adhesion Molecule A Depicts Acute Alterations in Blood Flow and Early Endothelial Dysregulation[END_REF]. However, immunogenicity and cost of antibodies limited their use in humans. Moreover, the production of these targeted bubbles is also time-consuming due to their multi-step synthesis (carboxyl groups introduced on the surface through partial hydrolysis of the shell of PBCA MBs [START_REF] Koczera | PBCA-based polymeric microbubbles for molecular imaging and drug delivery[END_REF]).

Furthermore, the degree of hydrolysis is difficult to control, and the excess of hydroxyl or redundant reaction time may induce rapid depolymerization reaction destroying the structure of MBs and producing short chains of PBCA [START_REF] Ryan | Novel sub-ceiling temperature rapid depolymerization-repolymerization reactions of cyanoacrylate polymers[END_REF]. In this work, we reported air-filled PIBCA MBs coated with various polysaccharides in a novel simple one-pot procedure (Figure 1). The size distribution of MBs before and after polysaccharide functionalization was not altered (Table 1), all MBs showing a single peak with a narrow size distribution (Figure S1 Left). The surface charge of MBs was similar to the charge of polysaccharides (Table 1 and

Figure S1 Right),
indicating that polysaccharides were present at the surface of the MBs [START_REF] Chauvierre | Novel Polysaccharide-Decorated Poly(Isobutyl Cyanoacrylate) Nanoparticles[END_REF][START_REF] Chauvierre | A new generation of polymer nanoparticles for drug delivery[END_REF].

Among the polysaccharides, DEAE-Dextran and CM-Dextran could respectively provide amino groups and carboxyl groups on the surface of PIBCA MBs for further functionalization.

Table 1. Characteristics of non-functionalized and polysaccharide functionalized microbubbles.

Since CM-dextran had a similar negative surface charge but without the sulfate groups of fucoidan that are involved in its interaction with P-selectin, CM-Dextran-MBs were chosen as a control to assess the benefit of using targeted MBs (Fucoidan-MBs). Morphology images of CM-Dextran-MBs and Fucoidan-MBs obtained by electron microscopy showed that all MBs were spherical with an empty The amount of fucoidan coupled to the MBs was quantified by a solid-phase colorimetric assay described by Lee. [START_REF] Lee | Solid-Phase Colorimetric Method for the Quantification of Fucoidan[END_REF]. Based on the standard curves, we calculated the fucoidan content of Fucoidan-MBs to be of 8.6 × 10 -15 g per Fucoidan-MB (Figure S3).

As a potential contrast agent, the storage of MBs is very important. Long-term storage stability of the MBs in aqueous suspensions at 4 o C was evaluated. Results showed that size and zeta potential remained stable for at least 2 months for both MBs (Figure 3).

In vitro Flow Experiments

Flow chamber experiments are used to mimic the interactions of MBs with purified P-Selectin or activated human platelets under physiological conditions in vitro [START_REF] Wu | Rhodamine-loaded intercellular adhesion molecule-1-targeted microbubbles for dual-modality imaging under controlled shear stresses[END_REF][START_REF] Wu | In Vivo Ultrasound Molecular Imaging of Inflammatory Thrombosis in Arteries With Cyclic Arg-Gly-Asp-Modified Microbubbles Targeted to Glycoprotein IIb/IIIa[END_REF]. After perfusion of human whole blood at high shear stress, activated DIOC6 stained human platelets aggregated on collagen-coated chambers. Human platelet aggregates were visualized in real time under the fluorescent microscope (Video S1).

P-selectin expression on activated platelets was evidenced by the green fluorescence uptake observed after injection of FITC-anti-CD62P antibody through the channel; no signal was detected after injection of FITC-IgG control (Figure S4). After perfusion at venous shear stress (6.75 dyn.cm -2 ) to mimic venous flow conditions of To confirm the binding of Fucoidan-MBs to activated platelets, we performed an ex vivo platelets-rich thrombus and added a suspension of Fucoidan-MBs for 5 minutes.

After rinsing with saline, we observed the thrombus by Environmental Scanning Electron Microscopy. The ESEM images of the platelets-rich thrombus without MBs exhibited activated platelets and fibrin (Figure S5 Left). In contrast, the ESEM images of the platelets-rich thrombus in contact with Fucoidan-MBs showed many spherical micrometer particles (as Figure 2 Left) associated with the activated platelets confirming that Fucoidan-MBs bind to activated platelets overexpressing P-selectin.

In vitro Ultrasound Imaging

The potential of CM-Dextran-MBs and Fucoidan-MBs as contrast agents for ultrasound imaging was first assessed in vitro. A suspension of MBs ( 10

Cell Viability

The cytotoxicity of Fucoidan-MBs was evaluated by MTT assay [START_REF] Matuszak | Nanoparticles for intravascular applications: physicochemical characterization and cytotoxicity testing[END_REF] with mouse fibroblast 3T3 cells exposed to various concentrations of Fucoidan-MBs or CM-Dextran-MBs. As shown in Figure S6, the results demonstrated that none of these MBs affected the cell viability (cell viability > 80% even at the highest concentrations of 10 7 mL -1 ), suggesting an excellent in vitro safety of these MBs.

Moreover, no significant difference was observed between CM-Dextran-MBs and Fucoidan-MBs.

In vivo Ultrasound Imaging and Environmental Scanning Electron

Microscopy

To evaluate the in vivo targeting of Fucoidan-MBs to P-selectin overexpressed on thrombus, the ferric chloride (FeCl 3 ) induced inferior vena cava (IVC) non-occlusive thrombus rat model was performed. The presence of non-occlusive thrombus was inspected by B-mode, and the venous blood flow around thrombi was confirmed by

Color Doppler Flow Imaging (Figure S7). Ten minutes after the injection of Fucoidan-MBs, the presence of bound Fucoidan-MBs in the thrombus region was accurately validated (green color) (Video 2). The signal intensity of binding area in the thrombus was remarkably decreased after MBs burst by destructive pulse (Figure 6B). In contrast, the rats injected with control CM-Dextran-MBs showed few MBs in the thrombus region (Video S4), and the signal intensity declined only slightly after the destructive pulse (Figure 6A). Subsequent quantifications of the decreased signal intensity in the thrombus area before and after destructive pulse evidenced a significantly higher accumulation of Fucoidan-MBs in comparison to CM-Dextran-MBs (85.5 ± 2.7% versus 50.8 ± 8.4%, respectively, p<0.0001) (Figure 6C). Furthermore, no Fucoidan-MBs were detected in the inferior vein wall of healthy rats (Figure S8). In addition, the healthy rats used in these experiments were still alive a few months after injection of MBs and without any side effects. Owing to the poor contrast, quantitative analysis of ultrasound signal modification has been a difficult issue in the field of ultrasound molecular imaging [START_REF] Wang | Click-Chemistry-Mediated Rapid Microbubble Capture for Acute Thrombus Ultrasound Molecular Imaging[END_REF][START_REF] Wang | Novel single-chain antibody-targeted microbubbles for molecular ultrasound imaging of thrombosis: validation of a unique noninvasive method for rapid and sensitive detection of thrombi and monitoring of success or failure of thrombolysis in mice[END_REF][START_REF] Wang | Thrombus-Targeted Theranostic Microbubbles: A New Technology towards Concurrent Rapid Ultrasound Diagnosis and Bleeding-free Fibrinolytic Treatment of Thrombosis[END_REF]. Unlike non-motile solid tumor, blood vessel walls are always dilated or contracted due to the heartbeat, adding to the difficulty of thrombi imaging analysis. Currently, the main ultrasound imaging methods of thrombus analysis are based on the contrast overlay data that is created by comparing the imaging before and after the injection of MBs [START_REF] Wang | Click-Chemistry-Mediated Rapid Microbubble Capture for Acute Thrombus Ultrasound Molecular Imaging[END_REF][START_REF] Wang | Novel single-chain antibody-targeted microbubbles for molecular ultrasound imaging of thrombosis: validation of a unique noninvasive method for rapid and sensitive detection of thrombi and monitoring of success or failure of thrombolysis in mice[END_REF][START_REF] Wang | Thrombus-Targeted Theranostic Microbubbles: A New Technology towards Concurrent Rapid Ultrasound Diagnosis and Bleeding-free Fibrinolytic Treatment of Thrombosis[END_REF]. This approach could potentially overcome the interference of motion artifacts, but it failed to distinguish the false increased contrast signal caused by the growth of thrombi. Herein, we exploited a differential imaging method to evaluate the targeting efficiency of MBs. Thanks to this method, we were able to distinctly see the binding site of MBs, quantify the number of targeted MBs, and also monitor the elimination of MBs. Previous studies have shown that the combination of MBs and ultrasound can help temporarily to open the blood-brain-barrier via sonoporation mechanisms, these phenomena can contribute to the delivery of pharmaceutical treatments [START_REF] Nakatsuka | Aptamer-Crosslinked Microbubbles: Smart Contrast Agents for Thrombin-Activated Ultrasound Imaging[END_REF][START_REF] Unger | Cardiovascular drug delivery with ultrasound and microbubbles[END_REF][START_REF] Lammers | Theranostic USPIO-Loaded Microbubbles for Mediating and Monitoring Blood-Brain Barrier Permeation[END_REF][START_REF] Fan | Ultrasound targeted CNS gene delivery for Parkinson's disease treatment[END_REF]. Herein, we observed for the first time that Fucoidan-MBs which were localized in the thrombus could be destroyed by a destructive pulse. These results indicated that Fucoidan-MBs carrying thrombolytic drugs could be a promising delivery system to improve thrombolytic efficiency while reducing hemorrhagic complications via the local release of the drug-loaded Fucoidan-MBs at the pathological site.

Tissue Distribution in Healthy and Thrombus-Induced Rats.

To evaluate the biodistribution in healthy rats, the presence of Fucoidan-RhoB-MBs in four main organs of excretion (liver, spleen, lungs and kidneys) was assessed by histological analysis of several sections for each organ (Figure S9). Results revealed that few Fucoidan-RhoB-MBs were found in liver, lungs and kidneys (indicated by the arrows). Conversely, red fluorescence was detected in the spleen with irregular shapes probably due to the degradation of the microbubbles. Indeed, various degradation processes of PACA nanoparticles were described [START_REF] Lenaerts | Degradation of poly (isobutyl cyanoacrylate) nanoparticles[END_REF][START_REF] Muller | In vitro model for the degradation of alkylcyanoacrylate nanoparticles[END_REF]. One leading view was that the main products of biodegradation of PACA nanoparticles were polymer chains and the corresponding alcohol, which were formed after cleavage of ester bond by esterases [START_REF] Stein | Degradation of polybutyl 2-cyanoacrylate microparticles[END_REF][START_REF] Scherer | Influence of enzymes on the stability of polybutylcyanoacrylate nanoparticles[END_REF][START_REF] O'sullivan | Hydrolysis of poly (n-butylcyanoacrylate) nanoparticles using esterase[END_REF]. This also confirmed that the red fluorescent fragments we observed possibly arise from enzymatic hydrolysis in the spleen. Considering the results of the absence of cell toxicity and the low injection doses of Fucoidan-MBs or CM-Dextran-MBs in vivo, these MBs seem to be safe.

To assess whether Fucoidan-MBs accumulated in vivo within an inferior venous thrombus, histology was performed under bright field and fluorescent microscopes.

Results confirmed that thrombus existed in the inferior deep vein (Figure 8A

Conclusion

In this work, various polysaccharide-coated PIBCA MBs were developed according to a new easy one-step polymerization reaction. This method allowed convenient modulation of the different surface functional groups of MBs, which were prone to further functionalization. Among the polysaccharides, fucoidan was especially considered to functionalize the MBs due to its high affinity for P-selectin. Compared to anionic carboxymethylated dextran MBs, Fucoidan-MBs specifically bind to P-selectin expressed by human activated platelets at venous shear stress. An in vivo rat model showed that Fucoidan-MBs were able to target thrombus. We evidenced their presence in the thrombus by ultrasound imaging and histology analysis. This approach offers a sensitive and specific method to detect microthrombi before complete occlusion of the vessel using an inexpensive and widely used ultrasound equipment in hospitals and medical centers worldwide. Fucoidan-MBs application could also be extended to molecular monitoring of P-selectin expression in severe diseases. More in-depth studies of the in vivo performance of Fucoidan-MBs should be performed before moving towards clinical implementation. In addition, antithrombotic or fibrinolytic drugs could be incorporated into the Fucoidan-MBs, and these targeted MBs burst by ultrasound could locally deliver the drugs at the thrombus site, which represents a new promising theranostic system.

:FITC

  Dextran 70, anionic CarboxyMethyl-Dextran 40 (CM-Dextran), -Dextran 70 (DEAE-Dextran) were provided from TdB Consultancy (Uppsala, Sweden). Fucoidan (Mn = 18 kDa / Mw = 104 kDa) was obtained from Algues & Mer (Ouessant, France). Isobutylcyanoacrylate (IBCA) monomers were purchased by ORAPI (Saint Vulbas, France). Methylene blue hydrate was purchased from Sigma-Aldrich. Chromatography was obtained from GE Healthcare. Mouse anti-human CD62P-FITC and mouse IgG1-FITC Isotype Control were provided from Beckman Coulter (Villepinte, France). Fibrillar type I collagen Horm ® was obtained from Takeda (Linz, Austria). 24-, 96-Well Cell Culture Plates (Costar) were obtained from Corning Incorporated. PPACK tubes were purchased from Cryopep (Montpellier, France). Flow chambers (Vena8 Fluoro+) were provided from Cellix Ltd (Dublin, Ireland). Synthesis of Microbubbles: Poly(IsoButylCyanoAcrylate) (PIBCA) shelled air-containing microbubbles (MBs) were prepared by modification of established emulsion polymerization process as described by Palmowski et al. [33]. Briefly, 700 µL of IBCA monomer was loaded in a 1 mL plastic syringe, injected into 50 mL of an aqueous solution of 1% Tween 20 at pH 2.5 via a catheter at a constant flow rate of 5 mL h -1 , and dispersed at 20,000 rpm for 60 min with a homogenizer (ULTRA-TURRAX ® , IKA, Germany). The syringe pump (AL-300, World Precision Instruments, Florida, USA) was used to control flow rate. The resulting microbubble suspension was then washed three times by centrifugation (500 rpm, 20 min, 5702RH centrifuge Beckman Coulter, Villepinte, France) to obtain the monodispersed bubble populations and to remove the polymeric scrap. Subsequently, the resulted emulsion was placed into a separatory funnel overnight, and the aqueous layer was removed. The microbubbles layer was redispersed in 30 mL of 0.02% Tween 20 for storage at 4°C. To prepare polysaccharide functionalized microbubbles (Dextran-MBs, DEAE-Dextran-MBs, CM-Dextran-MBs and Fucoidan-MBs), 500 mg of corresponding polysaccharides were dissolved in an aqueous solution before IBCA introduction. For Rhodamine B loaded CM-Dextran-MBs and Fucoidan-MBs (CM-Dextran-RhoB-MBs and Fucoidan-RhoB-MBs, respectively), 1 mg of Rhodamine B was added into an aqueous solution before synthesis. FITC-CM-Dextran-MBs and FITC-Fucoidan-MBs were obtained by using 10 mg of FITC-CM-Dextran mixed with 490 mg of CM-Dextran and 10 mg of FITC-Fucoidan mixed with 490 mg of Fucoidan, respectively. Rhodamine B loaded FITC-CM-Dextran-MBs and FITC-Fucoidan-MBs were prepared by combining two protocols. Microbubbles Size and Zeta Potential Analysis: The size range of microbubbles was determined using a Mastersizer 3000 (Malvern Instruments, UK) equipped with a Hydro SM sample dispersion unit. A suspension of microbubbles was dispersed into 0.02% Tween 20 solution and stirred at 1,500 rpm for 1 minute before an examination. Zeta potential (ζ) of the microbubbles was measured with samples diluted into electrolyte solution (1 × 10 -3 M KCl & 0.02% Tween 20) using electrophoretic light scattering apparatus (Nano ZS, Malvern Instruments, UK) at 25°C. All the measurements were performed at least three times.

  determined at 663 nm by infinite ® 200 PRO (TECAN, Switzerland). The series of filter paper squares containing stained standard solution spots was obtained by adding 5 drops (10 μL) of different concentration of fucoidan or CM-Dextran solutions (0.5, 0.25, 0.125, 0.0625 and 0.3125 mg mL -1 ) to each filter paper. The relative absorbance (△abs) of fucoidan -methylene blue complex at A 663 nm was expressed as [abs (fucoidan) -abs (CM-Dextran)]. Fucoidan content was plotted against the △abs for the regression line. For MBs samples, 3 × 10 8 Fucoidan or CM-Dextran microbubble suspension was placed into a separatory funnel overnight, and the aqueous layer was removed to eliminate free fucoidan. The clot of microbubbles was totally hydrolysed by mixing with alkaline solution (0.1 N NaOH and 0.02% Tween 20) overnight, and the resulted solution was added dropwise on filter paper square.

  Deep Vein: Animal studies were done in accordance with principles of laboratory animal care and with the approval of the animal care and use committee of the Claude Bernard Institute (N°2012-15/698-0100, Paris, France). FeCl 3 -induced thrombosis model on rat deep vein was induced based on the previous work[START_REF] Wang | Click-Chemistry-Mediated Rapid Microbubble Capture for Acute Thrombus Ultrasound Molecular Imaging[END_REF]. Briefly, Wistar male rats (Janvier Labs, Le Genest-Saint-Isle, France) aged around 7 weeks were anesthetized with an intraperitoneal injection of pentobarbital (1 μL g -1 body weight, Ceva Santé Animale SA, La Ballastiere, France). A midline abdominal incision was performed to expose the inferior vena cava (IVC). Venous thrombus was generated by applying a 2 mm Whatman chromatography paper saturated with 10% FeCl 3 on top of the IVC in contact with the adventitial surface of the vessel for 5 minutes. After the paper was removed, the vein was washed several times with a saline solution. Typically, thrombus development was completed 30 minutes post FeCl 3 injury. Ten thrombosis-bearing rats were randomly divided into two groups, one group of rats received Fucoidan-MBs intracavernous injection (200 μL, 1 × 10 8 /mL), the other group was injected with CM-Dextran-MBs (200 μL, 1 × 10 8 /mL). As the control, three healthy rats were also injected with Fucoidan-MBs (200 μL, 1 × 10 8 /mL). All rats were kept anesthetized during the entire imaging process.In Vivo Ultrasound Molecular Imaging: Ultrasound imaging of venous thrombosis (in rat thrombus model) or venous wall (in healthy rats) was performed using a VisualSonics Vevo ® 2100 imaging system with the same parameters used in vitro. Briefly, the ultrasound transducer was placed perpendicular and parallel to the IVC, 10 minutes after injection of MBs. A cine loop was acquired in the B-mode and linear contrast mode which made series of imaging frames before and after a high mechanical index destructive pulse (duration: 1 second). Using the Advanced Contrast Quantification Software Analysis Tool (VevoCQ, VisualSonics, Canada), a region of interest (ROI) was defined around the bound MBs area (1 cm 2 ). The mean contrast intensity within the ROI before and after the destructive pulse was evaluated, and each data point corresponded to the mean of the contrast intensity in the ROI in each frame. To highlight the contrast effect of targeted MBs, 50 frames after the destructive pulse were selected to create a reference baseline, and the frames before destructive pulse were overlaid to the reference baseline. The system isolated the targeted MBs echo from the tissue ultrasound signal data and identified them in green color. The process persistence filter was set to Smooth (to remove transient bubble data from the image), the contrast overlay dynamic range and threshold were used as default (50%).To analyze quantitatively the contrast enhancement effect, the mean values of contrast power of 200 frames before and after the destructive pulse were calculated by VevoCQ™ advanced contrast quantification software. The signal from the targeted MB was determined by subtracting the mean value after the destructive pulse from the one before. The obtained signal from the targeted MB was normalized to the value before the destructive pulse. Histological Evaluations: Rats were sacrificed with pentobarbital overdose 1 hour after injection of Fucoidan-RhoB-MBs. Inferior vena cave with thrombus was removed, washed in 0.9% NaCl, fixed in paraformaldehyde 4% (w/v), and then frozen. The vena samples were cryosectioned at 10 µm thickness and then stained with hematoxylin and eosin. The cell nuclei of a venous vascular wall were labeled with 4'6-DiAmidino-2-PhenylIndole (DAPI) contained in mounting medium (Vecto laboratories), and Fucoidan-RhoB-MBs were visualized in red thanks to rhodamine B. Stained sections were observed by light/fluorescence microscopy using the NDPview software (Hamamatsu, Japan). The magnified images of the region of interest were used to show the position of microbubbles.

Figure 1 .

 1 Figure 1. Overall schematic diagram of one-step protocol for microbubbles and their use as molecular ultrasound contrast agent.

  MBs presented similar size by DLS measurement. Fluorophore-labeled MBs in combination with fluorescence microscopy were very powerful tools for clearly visualizing and validating in vitro and in vivo binding studies. However, the loading strategy should be carefully designed to avoid an alteration of the surface functional groups of MBs. Here, rhodamine-loaded Fucoidan-MBs (Fucoidan-RhoB-MBs) and CM-Dextran-MBs (CM-Dextran-RhoB-MBs) were prepared by modification of the synthesis methods of Liu. [49]. The loading of rhodamine into the MBs polymer membrane did not affect the size distribution and zeta potential of MBs. To demonstrate the presence of CM-Dextran or fucoidan on MBs, FITC-CM-Dextran or FITC-fucoidan was added, respectively (Figure S2). Size distribution and zeta potential of all the labeled MBs were presented in Table S1. The double-labeled MBs observed by confocal microscopy imaging confirmed the core-shell structure of MBs and the presence of polysaccharides on the shell (Figure 2 Right).

Figure 2 .

 2 Figure 2. Morphology characterizations of CM-Dextran-MBs and Fucoidan-MBs (Left) and

Figure 3 .

 3 Figure 3. Stability of size and zeta potential of CM-Dextran-MBs and Fucoidan-MBs kept at 4°C

  Fucoidan-RhoB-MBs (Video 1) or CM-Dextran-RhoB-MBs (Video S2) on preformed platelet aggregates, an uptake of red fluorescence was observed over time at the surface of the aggregates. After washing, bound Fucoidan-RhoB-MBs remained attached to the aggregates, whereas almost no remaining binding was observed with control CM-Dextran-RhoB-MBs (Figure4A). Quantitative analysis confirmed that the mean fluorescent intensity (MFI) of fluorescent MBs was significantly higher for Fucoidan-RhoB-MBs than for CM-Dextran-RhoB-MBs (4387 ± 178.9 versus 1640 ± 10.53, respectively, p<0.0001) (Figure4B). To further confirm these results, CM-Dextran-RhoB-MBs and Fucoidan-RhoB-MBs were successively perfused into the same channel at constant shear stress, and the results showed clearly different targeting responses (Video S3).

Figure 4 .

 4 Figure 4. Binding of microbubbles on activated platelet aggregates under flow conditions in vitro.

  5 mL -1 ) was put into the thin-wall tube and placed on the top of the probe (Figure 5A Left), and the echogenicity of MBs was evaluated by Vevo 2100. A Control suspension was used to check the background signal (Figure 5A Middle) which remained at low level (Figure 5A Right). For MBs suspensions, the imaging showed a high and stable enhancement of monodisperse contrast signal, which could be eliminated by destructive pulse (Figures 5B).Quantitative analysis proved that CM-Dextran-MBs and Fucoidan-MBs have similar contrast signals and both of them could be reduced to background level after burst (Figures 5C).These results indicated that the variation in echo after the burst could be used in vivo to ensure that the enhanced contrast signal was coming from MBs and not from motion artifact caused by respiratory and cardiac activities.

Figure 5 .

 5 Figure 5. In vitro ultrasound signals of CM-Dextran-MBs and Fucoidan-MBs under B-mode. A)

Figure 6 .

 6 Figure 6. The thrombus area ultrasound imaging of ferric-chloride-induced inferior vena cava

Figure 7 .

 7 Figure 7. Environmental Scanning Electron Microscopy (ESEM) images of a non-occlusive

  ), smooth muscle cells from venous vascular wall labeled with DAPI showed blue color (Figure 8B), and many scattered Fucoidan-RhoB-MBs (indicated by the arrows) were localized in the thrombus area (Figures 8C & 8D). Few MBs showed microbubble-like shapes, most of them were altered and fractured (Figures 8C & 8D

Right),

  likely due to high destructive pulse that destroyed their structure.

Figure 8 .

 8 Figure 8. Histological analysis of thrombi in the IVC sections. Hematoxylin and Eosin staining (A)

Acknowledgements

This study was supported by Inserm, Paris Diderot University, and Paris 13 University. Dr. B. Li is a recipient of the China Scholarship Council (CSC, No. 201206180031), he designed the study, collected and interpreted the data, and wrote the draft version of the manuscript. R. Aid-Launais (Engineer) carried out the rat experiment, histology and cytotoxicity analysis. Dr. M-N. Labour (Post-Doc) performed the confocal imaging. A. Zenych (PhD student), a recipient of the European Union's Horizon 2020 research and innovation programme (Marie Skodowska-Curie grant # 665850), realized the physico-chemical characterizations of the MBs and M. Juenet (PhD student) the characterization of fucoidan content. C. Choqueux (Engineer) designed and performed the Environmental Scanning Electron Microscopy experiments. V. Ollivier (Engineer) designed the flow experiments. D. Letourneur (Head of the Unit) provided the funding, discussed the results and corrected the manuscript. O. Couture (Researcher) analyzed the in vitro and in vivo ultrasound imaging. C. Chauvierre (Researcher) supervised the thesis of Bo Li, discussed the results and corrected the manuscript. The authors are most grateful to E. Teston (INSERM U979) for in vitro ultrasound imaging experiment on agarose, F. Nadaud (UTC Compiègne, France) for ESEM images and to CRI U1149 imaging facilities for confocal imaging. This work received the financial support of the ANR (ANR-12-EMMA-0020-01 "MicroSound" and ANR-13-LAB1-0005-01 "FucoChem"), and the EU project FP7-NMP-2012-LARGE-6-309820 "NanoAthero". The authors have declared that no

Data availability statement

Authors confirm that the raw/processed data required to reproduce these findings can be shared upon demand.

competing interest exists.

Video Legends

Video 1: In vitro real time fluorescent images of Fucoidan-MBs infusion onto activated platelet aggregates in venous conditions.

Video 2: In vivo real time ultrasound imaging before and after burst of Fucoidan-MBs on thrombus.

Supplementary Data


Nathanaël Fijalkow

Sophie Pinchinat

Olivier Serre

Emptiness Of Alternating Tree Automata Using Games With Imperfect Information *

Keywords: 1998 ACM Subject Classification F.1.1 Models of Computation Keywords and phrases Alternating Automata, Emptiness checking, Two-player games, Imperfect Information Games

We consider the emptiness problem for alternating tree automata, with two acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game. However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known.

We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem. Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games played over infinite graphs.

Introduction

Tree automata [START_REF] Thomas | Languages, automata, and logic[END_REF][START_REF] Flum | Logic and Automata: History and Perspectives[END_REF] are a powerful tool to handle sets of infinite trees which are widely needed in verification, since they provide a natural representation of branching-time system executions. It is well known that by equipping tree automata with the parity condition, one captures all ω-regular tree languages [START_REF] Grädel | Automata, Logics, and Infinite Games[END_REF]. Additionally, tree automata may use alternation [START_REF] Chandra | [END_REF], which makes their complementation a simple task. In particular, combining alternation with the parity condition yields the automata-theoretic counterpart of the propositional µ-calculus, where the translation from one to the other can be done in linear time [START_REF] Arnold | Rudiments of µ-calculus[END_REF][START_REF] Grädel | Automata, Logics, and Infinite Games[END_REF]. Hence, the model-checking and the satisfiability/validity of logical formulas amount to respectively verifying membership and non-emptiness/universality on their corresponding tree automata.

The membership problem for alternating tree automata has a fairly simple algorithm: one compiles the input tree and the automaton into a polynomial size perfect information parity game and solves it. On the contrary, the usual roadmap to check emptiness of an alternating tree automaton is more involved. First one builds an equivalent non-deterministic automaton thanks to the Simulation Theorem [START_REF] Muller | Simulating alternating tree automata by nondeterministic automata[END_REF], and then one checks emptiness of this latter automaton by solving an associated two-player perfect information game. This yields an exponential time algorithm, which is optimal as the emptiness problem is EXPTIME-complete.

The first contribution of this paper is an alternative technique to solve the emptiness problem of alternating tree automata, by directly reducing it to two-player games with imperfect information. This builds on a long tradition initiated by Reif in [START_REF] Reif | Universal games of incomplete information[END_REF], that advocates the use of games with imperfect information to solve algorithmic problems for automata; in his seminal paper, Reif introduced the notion of blindfold games and used them to check the universality of nondeterministic automata over finite words. This approach has been later extended in [START_REF] Doyen | Antichain algorithms for finite automata[END_REF][START_REF] De Wulf | Antichains: A new algorithm for checking universality of finite automata[END_REF] and combined with antichains representations, to check universality and inclusion of nondeterministic automata, as well as emptiness for alternating automata. This was backed with solid experimental results (see e.g. the tool Alaska [START_REF] De Wulf | Alaska[END_REF]), where the emptiness of alternating Büchi word automata was considered, building on the Miyano-Hayashi construction [START_REF] Miyano | Alternating finite automata on omega-words[END_REF]. To the best of our knowledge, antichains approaches have not yet been extended to alternating parity tree automata. However, solving the emptiness problem for alternating parity tree automata through games of imperfect information has been considered by Puchala in his PhD [START_REF] Puchala | Synthesis of Winning Strategies for Interaction under Partial Information[END_REF], where he provides a reduction of the emptiness problem for alternating parity automata to solving a three-player game with imperfect information, but no algorithm to solve the latter.

We first illustrate our technique in the classical case of alternating parity tree automata, reducing the emptiness problem to two-player parity games with imperfect information. This does not lead to a gain in complexity due to intrinsic hardness, but unravels the two key ingredients: the first one is the positional determinacy of parity games, to prove the correctness of the reduction, and the second is the determinisation property of ω-word automata, to solve the obtained two-player imperfect information game. We compare this with the classical approach for alternating parity tree automata: the Simulation Theorem [START_REF] Muller | Simulating alternating tree automata by nondeterministic automata[END_REF] also combines the above two key ingredients.

Our technique is of interest for at least two reasons: (1) it pushes the algorithmic difficulty to the game solving part, for which antichains representations have recently been developed [START_REF] Berwanger | Alpaga: A tool for solving parity games with imperfect information[END_REF], hence could lead to efficient algorithms, and (2) a "Simulation Theorem"-free technique is required for classes of tree automata for which no (effective) Simulation Theorem exists.

The second contribution illustrates this latter situation. Indeed, we consider an alternation extension of the class of qualitative tree automata as introduced in [START_REF] Carayol | Qualitative tree languages[END_REF]: rather than requiring all branches to be accepting (classical semantics), the qualitative semantics requires almost all branches to be accepting. We apply our technique to check emptiness of an alternating qualitative Büchi tree automaton. Furthermore, we observe that the emptiness problem becomes undecidable for the co-Büchi condition, implying that there is no simulation theorem for alternating qualitative tree co-Büchi automata. For our technique to go through, the key ingredient is a positionality result for stochastic Büchi games over infinite arenas. To the best of our knowledge, very few positionality results are known in the literature that combine both stochastic aspects and infiniteness of the game arena; notable exceptions are [START_REF] Brázdil | Determinacy in stochastic games with unbounded payoff functions[END_REF][START_REF] Kucera | Turn-Based Stochastic Games[END_REF].

The paper is organised as follows. Section 2 gives the key definitions of both perfect/imperfect information games and classical/qualitative alternating tree automata. Section 3 introduces our technique by revisiting the emptiness problem for alternating parity tree automata and compares with the usual approach. Our main contribution is developed in Section 4: we prove that the emptiness problem for alternating qualitative Büchi tree automata is EXPTIME-complete. This is divided into two subsections. The main technical contribution is given in Section 4.1, where we establish a positionality result for stochastic games played on infinite finite out-degree chronological arenas. Finally, we use this positionality result in Section 4.2 to apply our technique to qualitative alternating Büchi tree automata.

Definitions

Let X be a (possibly infinite) alphabet. We denote by X * (resp. X ω ) the set of finite (resp. infinite) words over X and we let ε be the empty word. Let Σ be a finite alphabet. An infinite Σ-labelled binary tree (or simply a tree when Σ is clear from the context) is a map t : {0, 1} * → Σ. In this setting, we shall refer to an element n ∈ {0, 1} * as a node and to ε as the root. For a node n, we call t(n) the label of n in t. A (tree) language is a set of infinite Σ-labelled binary trees.

A graph is a pair G = (V, E) where V is a set of vertices and E ⊆ V × V is a set of edges. For every vertex v we let

E(v) = {w | (v, w) ∈ E}. A dead-end is a vertex v such that E(v) = ∅;
in the rest of the paper, we only consider graphs that have no dead-end, hence this is implicit from now on. The size of a graph is defined to be |V | + |E|.

For a finite set S, a probability distribution on S is a function δ : S → [0, 1] such that s∈S δ(s) = 1. We denote the set of probability distributions on S by D(S) and we write Supp(δ) = {s ∈ S | δ(s) > 0} for the support set of δ.

Perfect Information Stochastic Games

A (turn-based) stochastic arena is a tuple G = (G, V E , V A , V R , δ, v 0 ) where G = (V, E) is a graph, V = V E V A V R
is a partition of the vertices among two players, Éloïse and Abélard, and an extra player Random, δ :

V R → D(V ) is a map such that Supp(δ(v)) = E(v) for all v ∈ V R , and v 0 ∈ V is an initial vertex. In a vertex v ∈ V E (resp. v ∈ V A ) Éloïse (resp.
Abélard) chooses a successor vertex from E(v) and in a random vertex v ∈ V R , a successor vertex is chosen according to the probability distribution δ(v).

A (pure) strategy 1 for Éloïse is a function

ϕ E : V * • V E → V such that for every λ • v ∈ V * • V E one has ϕ E (λ • v) ∈ E(v).
Strategies of Abélard are defined likewise, and usually denoted ϕ A .

Fix a strategy ϕ E for Éloïse and a strategy ϕ A for Abélard. This induces a random walk on G. Indeed, define Plays ϕ E ,ϕ A to be the set of all possible plays when the game starts on v 0 and when Éloïse and Abélard chooses their moves accordingly to ϕ E and ϕ A . Formally, an infinite play

v 0 v 1 v 2 • • • ∈ V ω belongs to Plays ϕ E ,ϕ A if for every i ≥ 0 one has v i ∈ V E ⇒ v i+1 = ϕ E (v 0 • • • v i ), v i ∈ V A ⇒ v i+1 = ϕ A (v 0 • • • v i ) and v i ∈ V R ⇒ v i+1 ∈ E(v i ).
Define a partial play as a prefix of a play in Plays ϕ E ,ϕ A : with any partial play λ, the cone for λ is the set cone(λ) = λ • V ω ∩ Plays ϕ E ,ϕ A of all infinite plays with prefix λ. Denote by Cones the set of all possible cones and let F be the Borel σ-field generated by Cones considered as a set of basic open sets (i.e. F is the smallest set containing Cones and closed under complementation, countable union): then (Plays

ϕ E ,ϕ A , F) is a σ-algebra.
A pair of strategies (ϕ E , ϕ A ) induces a probability space over (Plays ϕ E ,ϕ A , F). Indeed one can define a measure µ ϕ E ,ϕ A : Cones → [0, 1] on cones (this task is easy as a cone is uniquely defined by a finite partial play) and then uniquely extends it to a probability measure on F using the Carathéodory Unique Extension Theorem. For this, one defines µ ϕ E ,ϕ A inductively on cones:

µ ϕ E ,ϕ A (cone(v)) = 1 if v = v 0 , and µ ϕ E ,ϕ A (v) = 0 otherwise. For every partial play λ ending in V E ∪ V A , let µ ϕ E ,ϕ A (cone(λ • v)) = µ ϕ E ,ϕ A (cone(λ)) if v = ϕ E (λ) or v = ϕ A (λ), and µ ϕ E ,ϕ A (cone(λ • v)) = 0 otherwise; For every partial play λ ending in v ∈ V R , let µ ϕ E ,ϕ A (cone(λ • v )) = µ ϕ E ,ϕ A (cone(λ)) • δ(v)(v ). Denote by Pr ϕ E ,ϕ A the unique extension of µ ϕ E ,ϕ A to a probability measure on F. Then (Plays ϕ E ,ϕ A , F, Pr ϕ E ,ϕ A ) is a probability space.
A winning condition is a subset2 Ω ⊆ V ω and a (two-player perfect information) stochastic game is a pair G = (G, Ω). A game is deterministic whenever V R = ∅ (and in this case we omit both V R and δ in the notations).

A strategy ϕ E for Éloïse is surely winning if Plays ϕ E ,ϕ A ⊆ Ω for every strategy ϕ A of Abélard; it is almost-surely winning if Pr ϕ E ,ϕ A (Ω) = 1 for every strategy ϕ A of Abélard. Similar notions for Abélard are defined dually.

A reachability game is one with a winning condition of the form V * F V ω , i.e. winning plays are those that eventually visit a vertex in F (we refer to vertices in F as final ones). We consider the parity winning condition: a colouring function ρ is a mapping ρ : V → Col ⊂ N where Col is a finite set of colours; the parity condition associated with ρ is the set

Ω ρ = {v 0 v 1 • • • ∈ V ω | lim inf(ρ(v i )) i≥0 is even}.
A parity game is a game equipped with a parity winning condition and we shall denote it G = (G, ρ) (i.e. writing ρ instead of Ω ρ ). Büchi games are those where Col = {0, 1} and we refer to vertices v such that ρ(v) = 0 as Büchi vertices. The dual is co-Büchi, for Col = {1, 2}.

A positional strategy ϕ is one that does not require memory, i.e. such that for any two partial plays of the form λ

• v and λ • v, one has ϕ(λ • v) = ϕ(λ • v)
, equivalently ϕ only depends on the current vertex. It is well-known that positional strategies suffice to surely win in deterministic parity games (see e.g. [START_REF] Zielonka | Infinite games on finitely coloured graphs with applications to automata on infinite trees[END_REF]).

Theorem 1 (Positional determinacy). Let G be a deterministic parity game. Then either Éloïse or Abélard has a positional surely winning strategy.

Working with deterministic parity games we only consider positional strategies and see them as maps from V E (or V A depending on the player) to V .

For stochastic games the following result is well-known (see e.g. [START_REF] Gimbert | Perfect information stochastic priority games[END_REF] for a slightly more general result).

Theorem 2. Let G be a stochastic parity game played on a finite arena. If Éloïse almostsurely wins then she can do so using a positional strategy.

To the best of our knowledge, no extension of this result is known when dropping the assumption that the arena is finite. We give such an extension (for Büchi games on so-called chronological arenas of finite out-degree) in Theorem 7.

Alternating Parity Tree Automata

An alternating parity tree automaton is a tuple

A = (Q ∃ , Q ∀ , Σ, ∆, q in , ρ), where Q ∃ is a set of existential states and Q ∀ is a set of universal states such that Q ∃ and Q ∀ are disjoint (we let Q = Q ∃ Q ∀ ), q in ∈ Q is an initial state, Σ is a labelling finite alphabet, ∆ ⊆ Q × Σ × Q × Q is a (finite) transition relation and ρ : Q → N is a colouring function.
We additionally assume without loss of generality that for all (q, σ) ∈ Q × Σ there is at least one (q, σ, q 0 , q 1 ) ∈ ∆. A non-deterministic parity tree automaton is an alternating automaton in which all states are existential (hence, we omit Q ∀ in this case).

In the following, we use tree automata as acceptors for tree languages, and acceptance is defined by means of a perfect information parity game. We will define two semantics for acceptance: classical and qualitative.

Fix an alternating parity tree automaton A = (Q ∃ , Q ∀ , Σ, ∆, q in , ρ) and a Σ-labelled tree t. From A and t, we define two games: G A,t and G =1 A,t . Intuitively, a play in those two games consists in moving a pebble along a branch of t in a top-down manner: the pebble is attached to a state and in a node n with state q Éloïse (if q ∈ Q ∃ ) or Abélard (if q ∈ Q ∀ ) picks a transition (q, t(n), q 0 , q 1 ) ∈ ∆, and then Abélard (in

G A,t ) or Random (in G =1
A,t ) chooses to move down the pebble either to n • 0 (and update the state to q 0 ) or to n • 1 (and update the state to q 1 ).

Formally, one let

G = (V ∃ V ∀ V ∆ , E) with V ∃ = {0, 1} * × Q ∃ , V ∀ = {0, 1} * × Q ∀ and V ∆ = {(n,
q, q 0 , q 1 ) | n ∈ {0, 1} * and (q, t(n), q 0 , q 1 ) ∈ ∆} and

E

= {((n, q), (n, q, q 0 , q 1 )) | (n, q, q 0 , q 1 ) ∈ V ∆ )} ∪ {((n, q, q 0 , q 1 ), (n • x, q x )) | x ∈ {0, 1} and (n, q, q 0 , q 1 ) ∈ V ∆ )} Then let G A,t = (G, V E , V A , (ε, q in )) be the deterministic arena defined by letting

V E = V ∃ and V A = V ∀ ∪ V ∆ and let G =1 A,t = (G, V E , V A , V R , δ, (ε, q in )) be the stochastic arena defined by letting V E = V ∃ , V A = V ∀ , V R = V ∆
and δ((n, q, q 0 , q 1 )) be the distribution (n • 0, q 0 ) → 1 2 and (n • 1, q 1 ) → 1 2 . Extend ρ on V by letting ρ((n, q)) = ρ((n, q, q 0 , q 1 )) = ρ(q). Finally one let G A,t = (G A,t , ρ) and G =1

A,t = (G =1 A,t , ρ). A tree t is accepted (resp. qualitatively accepted) by A if Éloïse has a surely (resp. almost-surely) winning strategy in the game G A,t (resp. G =1 A,t ). Finally, we define the set L(A) as the set of trees accepted by A and the set L =1 (A) as the set of trees qualitatively accepted by A.

The languages of the form L(A), regular tree languages, have many remarkable properties and characterisations (see e.g. [START_REF] Grädel | Automata, Logics, and Infinite Games[END_REF]). The languages of the form L =1 (A) when A is nondeterministic, qualitative tree languages, have been introduced in [START_REF] Carayol | Qualitative tree languages[END_REF] and also enjoy many good properties: for instance they are closed under union and intersection, and their emptiness can be tested in polynomial time.

Example 3. A typical language L =1 (A) with A being non-deterministic is the set of trees that have almost all their branches containing infinitely many a's. An example of a language L =1 (A B ) with A B being alternating is the set of trees such that all subtrees belongs to some L =1 (B) where B is non-deterministic.

Remark. There are several definitions of alternating tree automata, and another popular one is by not distinguishing between existential and universal states but replacing the transition relation by a map δ : Q × Σ → B + (Q × {0, 1}) where B + (X) denotes the positive Boolean formulas over X (see e.g. [START_REF] Kupferman | An automata-theoretic approach to branchingtime model checking[END_REF]). Our model is easily seen to be equi-expressive with that one.

Remark. Any positional strategy for Éloïse in G A,t or G =1

A,t can be described as a function ϕ : {0, 1} * ×Q ∃ → Q×Q that satisfies the following property: ∀n ∈ {0, 1} * , if ϕ(n, q) = (q 0 , q 1 ) then (q, t(n), q 0 , q 1 ) ∈ ∆. Equivalently, in a curryfied form, ϕ is a map {0, 1} * → (Q ∃ → Q × Q). Hence, if one let T be the set of functions from Q ∃ into Q × Q, Éloïse's positional strategies are in bijection with T -labelled binary trees.

Imperfect Information Stochastic Parity Games

In the following we introduce a quite restrictive class of games with imperfect information which is essentially a stochastic version of the model in [START_REF] Chatterjee | Algorithms for omega-regular games with imperfect information[END_REF].

An arena of imperfect information is a tuple G = (S, s 0 , A, T, ∼) where S is a finite set of states, s 0 ∈ S is an initial state, A is the finite alphabet of Éloïse's actions, T ⊆ S × A × D(S) is a (finite) stochastic transition relation and ∼ is an equivalence relation over S. We additionally require that for all (s, a) ∈ S × A there is at least one δ ∈ D(S) such that (s, a, δ) ∈ T . If for all probability distributions in T the support is a singleton, we say that G is an imperfect information deterministic arena and we see T as a subset of S × A × S. An imperfect information stochastic parity game is a pair G = (G, ρ) where G is an arena of imperfect information with set of states S and ρ : S → N is a colouring function defining a parity condition Ω ρ ⊆ S ω . The game is deterministic if its arena is deterministic. A play starts from the initial state s 0 and proceeds as follows: Éloïse plays an action a 0 ∈ A, then Abélard resolves the non-determinism by choosing a distribution δ 0 such that (s 0 , a 0 , δ 0 ) ∈ T and finally a new state is randomly chosen according to δ 0 . Then Éloïse plays a new action, Abélard resolves the non-determinism and a new state is randomly chosen and so on forever. Hence a play is an infinite word s 0 a 0 δ 0 s

1 a 1 δ 1 s 2 • • • ∈ (S × A × D(S)) ω and is won by Éloïse if s 0 s 1 s 2 • • • ∈ Ω ρ . A partial play is a prefix of a play.
Imperfect information is modeled thanks to the equivalence relation ∼ with the meaning that Éloïse cannot distinguish two states that are ∼-equivalent which is important when defining strategies for Éloïse. Intuitively, she should not play differently in two indistinguishable plays, where the indistinguishability of Éloïse is based on perfect recall [START_REF] Fagin | Reasoning about Knowledge[END_REF], that is: Éloïse cannot distinguish two plays s 0 a 0 δ 0 s 1 a 1 δ 1 • • • s and s 0 a 0 δ 0 s 1 a 1 δ 1 • • • s with s i ∼ s i for all i ≤ and a i = a i for all i < . Hence, a strategy for Éloïse is a function ϕ : (S /∼ × A) * • (S /∼ ) → A assigning an action to every set of indistinguishable plays (here S /∼ denotes the set of equivalence classes of ∼ in S, and for every s ∈ S, we shall write [s] ∼ for its ∼-equivalence class). Éloïse respects a strategy ϕ during a play λ = s 0 a 0 δ 0 s

1 a 1 δ 1 • • • if a i+1 = ϕ([s 0 ] ∼ a 0 [s 1 ] ∼ • • • [s i ] ∼ )
, for all i ≥ 0. A strategy ϕ for Éloïse is surely winning if Éloïse wins all plays consistent with ϕ and it is almost-surely winning if Éloïse wins almost all plays3 consistent with ϕ.

Remark. Our model of imperfect information games belongs is quite restrictive compared to general models developed in [START_REF] Gripon | Qualitative concurrent stochastic games with imperfect information[END_REF][START_REF] Bertrand | Qualitative determinacy and decidability of stochastic games with signals[END_REF][START_REF] Chatterjee | Partial-observation stochastic games: How to win when belief fails[END_REF][START_REF] Carayol | Pure strategies in imperfect information stochastic games[END_REF], as here Abélard is perfectly informed. However, our model turns out to be expressive enough for our purpose.

Remark. It is important to note that Éloïse may not observe the colour of the current state in general, as we do not require that s ∼ s ⇒ ρ(s) = ρ(s ). In particular, this has to be taken into account when eventually solving the game.

Revisiting the Emptiness using Imperfect Information Game

In this section, we introduce our technique by revisiting emptiness checking of regular tree languages when described by an alternating parity tree automaton. The standard technique [START_REF] Muller | Simulating alternating tree automata by nondeterministic automata[END_REF] first removes alternation and then reduces emptiness to decide the winner in a finite perfect information game; our technique goes directly to decide the winner in a game but as a drawback imperfect information is needed. Our construction is reminiscent of the notion of blindfold games introduced by Reif in [START_REF] Reif | Universal games of incomplete information[END_REF], and later thoroughly extended [START_REF] Doyen | Antichain algorithms for finite automata[END_REF][START_REF] De Wulf | Antichains: A new algorithm for checking universality of finite automata[END_REF][START_REF] De Wulf | Alaska[END_REF].

We first give our construction and then compare it to the classical one, arguing that rather than being novel our technique is indeed a change of perspective. Later in Section 4 we use this new perspective to design an emptiness test for alternating qualitative tree automata for which the classical perspective was unsuccessful.

Fix an alternating parity tree automaton A = (Q ∃ , Q ∀ , Σ, ∆, q in , ρ). Our goal is to check whether L(A) = ∅ and for this we design an imperfect information deterministic parity game. We first present the game and show how it permits to decide emptiness; then we compare our construction with the standard approach.

An Imperfect Information Emptiness Game

We define an imperfect information deterministic parity game G A that intuitively works as follows. Éloïse describes both a tree t and a positional strategy ϕ t for her in the game G A,t ; the strategy ϕ t is described as a T -labeled tree (where T is the set of functions from

Q ∃ into Q × Q, see Remark 2.2).
As the plays are of ω-length, she actually does not fully describe t and ϕ t but only a branch: this branch is chosen by Abélard, who also takes care of computing the sequence of states along it (either by updating an existential state accordingly to ϕ t or, when the state is universal, by choosing an arbitrary valid transition of the automaton). In this game, Éloïse observes the directions, but not the actual control state of the automaton (indeed, otherwise she could easily "cheat").

Formally, we let G A = (S, s in , A, T, ∼) where S = (Q×{0, 1})∪{(q in , ε)} and s in = (q in , ε); A ⊆ Σ × T is the set of pairs (a, τ ) such that for all q ∈ Q ∃ we have that (q, a, q 0 , q 1 ) ∈ ∆ where τ (q) = (q 0 , q 1 ), (q, i) ∼ (q , i) for all q, q ∈ Q and i ∈ {0, 1}, and T = {((q, i), (a, τ ), (q 0 , 0)), ((q, i), (a, τ ), (q 1 , 1)) | q ∈ Q ∃ and τ (q) = (q 0 , q 1 )} ∪ {((q, i), (a, τ ), (q 0 , 0)), ((q, i), (a, τ ), (q 1 , 1)) | q ∈ Q ∀ and (q, a, q 0 , q 1 ) ∈ ∆} Finally we let G A = (G A , ρ A ) be the imperfect information deterministic parity game obtained by letting ρ A (q, i) = ρ(q) for any (q, i) ∈ S.

Lemma 4. Éloïse has a surely winning strategy in

G A iff L(A) = ∅.
Remark. From the proof of Lemma 4, one can also conclude that if L(A) = ∅ then L(A) contains a regular tree (i.e. the unfolding of a finite graph). Indeed, this is a direct consequence of the fact that if Éloïse has a surely winning strategy in G A , then she has one that uses finite memory [START_REF] Chatterjee | Algorithms for omega-regular games with imperfect information[END_REF].

Lemma 4 provides a reduction of the emptiness problem to deciding the existence of a surely winning strategy in an imperfect information deterministic game. We prove a converse result.

Lemma 5. For any imperfect information deterministic parity game G one can construct an alternating parity tree automaton

A G such that Éloïse surely wins in G iff L(A G ) = ∅.
Moreover in A G all states are universal.

Comparison with the Standard Approach

The usual roadmap to check emptiness of an alternating tree automaton is as follows. First one builds an equivalent non-deterministic automaton thanks to Simulation Theorem (see below) and then one checks emptiness of this latter automaton by solving an associated perfect information game. It is a well-known result that alternating and non-deterministic automata are equi-expressive [START_REF] Muller | Simulating alternating tree automata by nondeterministic automata[END_REF].

Theorem 6 (Simulation Theorem). Let A be an alternating parity tree automaton with n states and using k colours. Then one can effectively construct a non-deterministic parity tree automaton B such that L(A) = L(B). The automaton B has 2 O(nk log(nk)) states and it uses O(nk) colours.

Proof. We do not give a complete proof of this classical result [START_REF] Muller | Simulating alternating tree automata by nondeterministic automata[END_REF] but we rather exhibit the crucial arguments here to later revisit the emptiness problem for alternating parity tree automata.

Fix an alternating parity tree automaton A = (Q ∃ , Q ∀ , Σ, ∆, q in , ρ). For any letter σ ∈ Σ, call a σ-tile any subset τ ⊆ Q × Q × Q such that for all q, q 0 , q 1 ∈ Q, if (q, q 0 , q 1 ) ∈ τ then (q, σ, q 0 , q 1 ) ∈ ∆; for all q ∈ Q ∃ there exists a unique (q 0 , q 1 ) ∈ Q 2 such that (q, q 0 , q 1 ) ∈ τ ; for all q ∈ Q ∀ and for all (q, σ, q 0 , q 1 ) ∈ ∆, (q, q 0 , q 1 ) ∈ τ . Hence, one should think of a σ-tile as a description of the local value of a positional strategy for Éloïse in a node labeled by σ from a tree t in the game G A,t (the case of q ∈ Q ∀ is here to leave all options of Abélard). In the following it is convenient to think of a tile τ as a pair (τ 0 , τ 1 ) of semi-tiles where τ 0 , τ 1 ⊆ Q × Q and (q, q 0 ) ∈ τ 0 (resp (q, q 1 ) ∈ τ 1 ) if and only if there exists p ∈ Q such that (q, q 0 , p) ∈ τ (resp. (q, p, q 1 ) ∈ τ ). See Figure 1a for an example. Now an equivalent non-deterministic automaton A is obtained by choosing as control states the set S of all possible semi-tiles augmented with an extra dummy initial state s in . The transition relation ∆ consists of all those elements of the form (s, σ, τ 0 , τ 1 ) where s is any state and (τ 0 , τ 1 ) is a σ-tile. Acceptance for A is then defined by means of a game G A ,t as previously except that the winning condition is more involved than a parity condition. A play is an element

λ = v 0 v 1 • • • ∈ (({0, 1} * × S) • ({0, 1} * × S × S × S)
) ω to which we can associate a sequence of semi-tiles π(λ) = s 1 s 2 • • • where v 2i = (n i , s i ) for all integer i ≥ 1 (we ignore the dummy initial state). The sequence π(λ) can be seen as a set of infinite paths in an infinite ribbon obtained by gluing together the semi-tiles s 1 , s 2 , . . . (see Figure 1b). An infinite sequence q 1 q 2 • • • is an infinite path in π(λ) if and only if for all i ≥ 1 one has (q i , q i+1 ) ∈ s i ; it is good if lim inf(ρ(q i )) i≥1 is even; and π(λ) is good if all plays in it are good. Finally we define those winning plays for Éloïse as those plays λ such that π(λ) is good.

Then one can easily remark that the set of all λ such that π(λ) is good is an ω-regular language over S, hence is accepted by a deterministic parity ω-word automaton C. Considering a "synchronised" product of C together with A leads B. The desired complexity is achieved by carefully constructing C.

Consider now a non-deterministic parity tree automaton K = (Q, Σ, ∆, q in , ρ). A perfect information emptiness game for K is built as follows. We let G K = (V E V A , E) where V E = Q, V A = ∆ and E = {(q, (q, σ, q 0 , q 1 )), ((q, σ, q 0 , q 1 ), q 0 ), ((q, σ, q 0 , q 1 ), q 1 ) | (q, σ, q 0 , q 1 ) ∈ ∆}. We define G K = (G K , ρ) with G K = (G K , V E , V A , q in ) and where we extend ρ by letting ρ((q, σ, q 0 , q 1 )) = ρ(q). Then one easily has that L(K) = ∅ if and only if Éloïse surely wins in G K . Indeed, strategies for Éloïse in G K are in bijection with pairs made of a tree t and a strategy for Éloïse in G K,t , and this bijection preserves the fact that a strategy is surely winning. Now think of adapting this construction to the automaton A from the proof of the Simulation Theorem and recall that acceptance for A was defined thanks to a game as the classical one except that the winning condition was more involved. Then, the same construction provides a game G A where Éloïse's vertices are semi-tiles and Abélard's vertices are tuple made of a semi-tile, a letter in Σ and a tile, and whose winning condition for a play

λ = v 0 v 1 • • • ∈ ((Σ × S) • (Σ × S × S × S)) ω is that π(λ) = s 1 s 2 • • • is good (in the previous sense) where v 2i = (σ i , s i ) for all integer i ≥ 1.
Now think back to our reduction from A to G A : it makes crucial use of positional determinacy while determinisation of automata on infinite word is implicitly needed when deciding whether Éloïse surely wins in G A . Indeed, one first applies the subset construction of [START_REF] Chatterjee | Algorithms for omega-regular games with imperfect information[END_REF], getting an intermediate perfect information game isomorphic to G A and then, since Éloïse does not observe the colour, one has to embed in the previous subset/tile construction a deterministic parity automaton over infinite words that checks that all plays consistent with the observations fit the parity condition. As this latter automaton is essentially the automaton C one gets a perfect information parity game isomorphic to G B . Figure 2 summarises the previous discussion. We are now coming to the central contributions of this paper. We design an emptiness test for alternating qualitative Büchi tree automata adapting the approach developed in Section 3.

Recall that it relies on two key arguments: a positionality result and a decidability result for games. Hence, we start by proving a positionality result (Theorem 7), and then explain how to obtain a (decidable) emptiness game (Theorem 10).

that for all q ∈ Q ∃ , (q, a, q 0 , q 1 ) ∈ ∆ where τ (q) = (q 0 , q 1 ) and T = {((q, i), (a, τ ), d q0,q1 ) | q ∈ Q ∃ and τ (q) = (q 0 , q 1 )} ∪ {((q, i), (a, τ ), d q0,q1 ) | q ∈ Q ∀ and (q, a, q 0 , q 1 ) ∈ ∆} where d q0,q1 is the probability distribution (q 0 , 0) → 1/2 and (q 1 , 1) → 1/2, and (q, i) ∼ (q , i) for all q, q ∈ Q and i ∈ {0, 1}. Define G =1 A = (G A , ρ A ) with ρ A (q, i) = ρ(q) for any (q, i) ∈ S.

With a proof similar to the one of Lemma 4, we have the following result.

Theorem 10. Éloïse almost-surely wins in G =1

A iff L =1 (A) = ∅.

From [START_REF] Chatterjee | Partial-observation stochastic games: How to win when belief fails[END_REF][START_REF] Carayol | Pure strategies in imperfect information stochastic games[END_REF], one can decide almost-sure winning in imperfect information Büchi games in EXPTIME, hence the same holds for checking emptiness of languages of the form L =1 (A). One can also reduce the emptiness problem for probabilistic ω-words automaton with the almost-sure semantics (in the sense of [START_REF] Baier | Probabilistic ω-automata[END_REF]) to check emptiness of languages of the form L =1 (A) hence, it implies lower bounds as well as undecidability results.

Theorem 11. (1) Deciding whether L =1 (A) = ∅ for a given alternating Büchi tree automaton A is an EXPTIME-complete problem. (2) Deciding whether L =1 (A) = ∅ for a given alternating co-Büchi tree automaton A is an undecidable problem.

Remark. As one can decide whether L =1 (A) = ∅ for non-deterministic tree automata [START_REF] Carayol | Qualitative tree languages[END_REF], Theorem 11 implies that there is no effective simulation theorem for co-Büchi alternating qualitative tree automata. designed so that it contains branches labelled by different ω-words that all behave well with a set of runs of B of measure strictly less than 1.

One can prove the following: a tree t belongs to L =1 (A) if and only if for almost all branch in t the labelling of t (which is the ω-word read along it) belongs to L =1 (B). This can be proved in a similar way as Lemma 9 from [START_REF] Carayol | Qualitative tree languages[END_REF].

As a consequence, it follows that L =1 (B) = ∅ iff L =1 (A) = ∅.

Figure 1

 1 Figure 1 (a) Semi-tiles τ0 and τ1 such that (τ0, τ1) represents the tile {(1, 1, 3), (2, 4, 1), (3, 1, 2), (3, 2, 4), (4, 4, 2), (4, 4, 4)} with Q ∃ = {1, 2} and Q ∀ = {3, 4}. (b) Representation of the sequence of semi-tiles τ0τ0τ1 • • •

AFigure 2

 2 Figure 2 Roadmaps to emptiness checking: the classical one (purple) vs ours (in red).

4

  Checking Emptiness Using an Imperfect Information Game: The Case of L =1 (A) for Büchi Condition

Formally one needs to require that Ω is measurable for all Pr ϕE,ϕA , which will be trivially true for all cases considered here as Ω will always be Borel.

To formally define what it means to win almost all plays one needs to define Abélard's strategies and explain how a pair of strategies for Éloïse and Abélard induces a probabilistic space over plays consistent with those strategies. This is essentially identical to what we did in Section 2.1 for perfect information games.

under grant agreement n°259454 (GALE) and n°239850 (SOSNA).

A Positionality Result for Chronological Games

In this subsection, we prove a positionality result for a subclass of infinite arenas, satisfying the following two conditions:

(finite out-degree) the underlying graph has finite degree, i.e for every v ∈ V there are finitely many outgoing edges from v, and (chronological) there exists a function rank : V → N such that rank -1 (0) = {v 0 } and for (v, v ) ∈ E, rank(v ) = rank(v) + 1. Note that both assumptions hold for G =1

A . Also, observe that for any k, the set rank -1 (k) is finite, and the set V of vertices is countable.

Theorem 7. Let G be a Büchi game whose arena has finite out-degree and is chronological. Then if Éloïse wins almost-surely, then she has a positional winning strategy.

We will use the following result for finite arenas. We state it here in a rather weak form (with the chronological assumption), as it can be easily proved by a backward induction, whereas the proof for general finite arenas is more involved. We refer to [START_REF] Condon | The complexity of stochastic games[END_REF] for the original proof, and to [START_REF] Kucera | Turn-Based Stochastic Games[END_REF] for a nice survey. Lemma 8. Let G be a stochastic reachability game played on a chronological and finite arena. Let W be the set of vertices from which Éloïse has a strategy ensuring to win with probability at least 1 2 . Then there exists a positional strategy which ensures to win with probability at least 1 2 from every vertex in W .

Note that the important point here is that the constructed strategy is uniform, i.e. the same strategy is winning from every vertex. We first sketch the proof. The main idea is to note that if Éloïse can ensure to reach F with probability 1 from some initial vertex, then there exists a bound k such that she can ensure to reach F with probability at least 1 2 within k steps against any strategy of Abélard. This allows to "slice" the arena into infinitely many disjoint finite arenas: in each slice Éloïse plays to reach F with probability at least half. Since each slice forms a finite subarena, optimal positional strategies exist by Lemma 8. The resulting strategy consists in playing in turns the above positional strategies; since each slice gives a probability to reach F of at least half before proceeding to the next, the probability to reach F infinitely often is 1.

Proof. We assume that Éloïse almost-surely wins G. Without loss of generality, we can assume that she wins almost-surely from everywhere, by restricting the arena to vertices reachable by a fixed almost-surely winning strategy.

In the next statement and later on, by a strategy in G from a vertex v we mean a strategy in the game obtained from G by changing the initial vertex of the arena G to be v.

Lemma 9.

Let ϕ E be an almost-surely winning strategy for Éloïse in G from v. There exists an integer k such that for all strategies ϕ A of Abélard, we have

Proof. Toward a contradiction, assume that such a k does not exist. Hence, for each k there exists a strategy ϕ A,k such that Pr ϕ E ,ϕ A,k (V ≤k F V ω ) < 1 2 . Moreover we can assume that the ϕ A,k are positional strategies: indeed, one can pick for ϕ A,k an optimal strategy for Abélard in the finite reachability game obtained by restricting G to the vertices of rank at most k. As this game is finite, by Lemma 8, an optimal strategy can always be chosen to be positional.

From the sequence (ϕ A,k ) k≥0 we can extract a strategy ϕ A,∞ that is consistent, for any k ≥ 0, with infinitely many ϕ A,h on its k first moves. For this, fix an enumeration v 1 , v 2 , • • • of the vertices in V . We will define by induction on i the following objects:

. . , v i and is consistent on these vertices with all those strategies ϕ A,h with h ∈ I i . Let I 0 = N be the set of all positive integers. At step i let us consider the values of ϕ h (v i ) for all h ∈ I i-1 : as G has finite out-degree, there is one v i such that for infinitely many h

Now for k ≥ 0 let i be such that {v j | j ≤ i} contains all vertices of rank at most k: then as required ϕ A,∞ is consistent with infinitely many ϕ A,h -all the ϕ A,h with h ∈ I i -on its k first moves. In particular, for all k, there is some h ≥ k such that

We define inductively a sequence of ranks (k i ) i≥1 together with a sequence of strategies (ϕ E,[ki,ki+1[ ) i≥0 such that for all i ≥ 0, ϕ E,[ki,ki+1[ is a positional strategy, defined on all vertices of rank [k i , k i+1 [, such that from all vertices of rank k i , for all strategies ϕ A , we have

Assume the first i ranks and strategies are defined. For each vertex of rank k i , Lemma 9 shows the existence of a bound; since there are finitely many such vertices, we can consider the maximum of those bounds, and denote it by k i+1 . By construction, from all vertices of rank k i , for all strategies ϕ A , we have Pr ϕ E ,ϕ A (V ≤ F V ω ) ≥ 1 2 , where = k i+1 -k i . In other words, Éloïse wins the chronological and finite reachability game G [ki,ki+1] with probability at least 1 2 , so, thanks to Theorem 2, there exists a uniform positional strategy ensuring to reach F with probability at least 1 2 , denote it ϕ E,[ki,ki+1[ . This concludes the inductive construction. Now define ϕ E,∞ as the disjoint union of the strategies ϕ E,[ki,ki+1[ . This is a positional strategy; we argue that it is almost-surely winning. Indeed, since ϕ E,∞ ensures that going through any slice, a vertex in F will be visited with probability half, the Borel-Cantelli Lemma implies that infinitely many vertices in F will be visited with probability one.

The Reduction

Fix an alternating Büchi tree automaton A = (Q ∃ , Q ∀ , Σ, ∆, q in , ρ). In order to check whether L =1 (A) = ∅, we design an imperfect information stochastic Büchi game G =1

A , in a way similar to the one to decide whether L(A) = ∅ taking advantage the positionality result established in Theorem 7. In the game, Éloïse describes both a tree t and a positional strategy ϕ t for her in the game G =1 A,t ; the strategy ϕ t is described as a T -labeled tree (where T is the set of functions from Q ∃ into Q × Q, see Remark 2.2. As the plays are of ω-length, she actually does not fully describe t and ϕ t but only a branch: this branch is chosen by Random, and Abélard takes care of computing the sequence of states along it (either by updating an existential state accordingly to ϕ t or, when the state is universal, by choosing an arbitrary valid transition of the automaton). Éloïse observes the directions. Formally, we let G =1 A = (S, s in , A, T, ∼) where S = (Q × {0, 1}) ∪ {(q in , ε)} and s in = (q in , ε); A ⊆ Σ × T is the set of pairs (a, τ ) such

), working over infinite A-labelled trees of arity k, that are maps t : {1, . . . , k} * → A. The only difference with the definition of Section 2.2 when considering automata handling such trees is that the transition relation ∆ is a subset of Q × A × Q k . We let ρ ( ) = 0 and ρ (s) = ρ(s) for all s ∈ S and ∆ = {(s, a, s 1 , . . . , s k ) | ∀1 ≤ i ≤ k, (s i ∈ C i and (s, a, s i ) ∈ T ) or s i = }} ∪ {( , a, , . . . , ) | a ∈ A} Note that A-labelled trees of arity k are trivially in bijection with strategies of Éloïse in G. Indeed with a tree t of arity k we associate a strategy ϕ t by letting

Then it is rather immediate to check that the set of plays where Éloïse respects ϕ t in G is isomorphic to the set of plays in the acceptance game G A G ,t (note that in this game all vertices are controlled by Abélard as all states in A G are universal); moreover winning plays are preserved. By noting that one can always encode trees of arity k into binary trees (and modify A accordingly) one concludes the proof.

Proof of Theorem 10

Theorem 10. Éloïse almost-surely wins in

Proof. Due to how ∼ is defined, a strategy for Éloïse in G =1 A can also be viewed as a map ϕ : {0, 1} * → A. As A ⊆ Σ × T , one can see ϕ as a pair (t, ϕ t ) where t is an infinite Σ-labelled binary tree, and ϕ t is a positional strategy for Éloïse in the acceptance game G =1 A,t . Now, once such a strategy ϕ is fixed, the set of plays in G =1

A where Éloïse respects ϕ is in one-to-one correspondence with the set of plays in G =1

A,t where she respects ϕ t , and this correspondence preserves the property of being winning. Therefore, ϕ = (t, ϕ t ) is almost-surely winning iff ϕ t is an almost-surely winning strategy in G =1 A,t iff t ∈ L =1 (A). Now recall that thanks to Theorem 7 we can restrict our attention to positional strategies for Éloïse in G =1 A,t . Hence, Éloïse has an almost-surely winning strategy iff there exists some tree t ∈ L =1 (A).

4

Proof of Theorem 11

Theorem 11.

(1) Deciding whether L =1 (A) = ∅ for a given alternating Büchi tree automaton A is an EXPTIME-complete problem. ( 2) Deciding whether L =1 (A) = ∅ for a given alternating co-Büchi tree automaton A is an undecidable problem.

Proof. Deciding whether L =1 (A) = ∅ for a given alternating Büchi tree automaton A in EXPTIME is simply by using the reduction from Theorem 10 in combination with a result of [START_REF] Chatterjee | Partial-observation stochastic games: How to win when belief fails[END_REF][START_REF] Carayol | Pure strategies in imperfect information stochastic games[END_REF] showing how to decide in EXPTIME whether Éloïse almost-surely wins in an imperfect-information Büchi game. The lower bounds for (1) and the undecidability result for (2) follow from the following lemma Lemma 12. Let B be an ω-word automaton with a Büchi ( resp. co-Büchi) acceptance condition. Deciding whether the language accepted by B under the almost-sure semantics is empty can be polynomially reduced to the emptiness problem for an alternating tree automaton with the qualitative semantics.

Before proving Lemma 12, let us explain how it permits to conclude. First, emptiness of Büchi ω-word automata under the almost-sure semantics has been proved to be EXPTIMEcomplete [START_REF] Baier | Probabilistic ω-automata[END_REF], hence it implies the lower bound in the first case. Second, emptiness of co-Büchi ω-word automaton with the almost-sure semantics is undecidable [START_REF] Baier | Probabilistic ω-automata[END_REF], which implies the undecidability result.

We now sketch how to prove Lemma 12.

We use the notations of [START_REF] Baier | Probabilistic ω-automata[END_REF]. First we can without loss of generality assume that the ω-word automaton B = (Q, Σ, δ, µ 0 , F ) (with either a Büchi or a co-Büchi acceptance condition) is such that the support of µ 0 is a singleton and δ is such that for every (q, σ) ∈ Q × Σ there are exactly two states q 0 and q 1 such that δ(q, σ, q 0 ) = δ(q, σ, q 1 ) = 1 2 . Up to coding we can always reduce the emptiness problem for ω-word automata with the almost-sure semantics to the same question on such a normalised automaton.

We now explain how to construct an alternating tree automaton A such that L =1 (B) = ∅ iff L =1 (A) = ∅. The states of A is Q and the initial state is the unique state q in such that µ 0 (q in ) = 1 and they all belong to Abélard. The labelling alphabet of A is Σ. The colouring function is inherited from B. Finally the transition function is as follows ∆ = {(q, σ, q 0 , q 1 ), (q, σ, q 1 , q 0 ) | δ(q, σ, q 0 ) = δ(q, σ, q 1 ) = 1 2 }

Hence the role of Abélard is to simulate B and to choose to which direction one should send each computation along the branch. This trick permits to prevent the input tree to be


Mathilde Bouteiller
email: mathilde.bouteiller@etu.univ-rouen.fr

M Gallique

A Kosta

J Hardouin

Y Konto-Ghiorghi

C Barbey

X Latour

A Chane

M G J Feuilloley

A Merieau

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

INTRODUCTION

The lack of T6SS formed with Hcp1 disturbs flagella formation.

The lack of T6SS formed with Hcp1 inhibits the sigma factor FliA activity.

The overexpression of fliA gene restores the production of flagella in ∆hcp1/tssC and by the way the "swimming" motility.

Concerning motility, only FliA activity is disturbed by the lack of T6SS formed with Hcp1. The lack of T6SS formed with Hcp1 blocks the secretion of the anti-sigma factor FlgM. FliA is not free in the cytoplasm of ∆hcp1 mutant, and there is no expression of flagellar class IV genes.

Here we show that the deletions of hcp1 or tssC genes induce the loss of flagella and decrease the expression of flagellar class IV genes, that is regulated by the sigma factor FliA. The overexpression of this sigma factor, in ∆hcp1 or ∆tssC strains, restores the wild type phenotype such as flagellin secretion (data not shown), flagella proper assembly and by the way "swimming" motility. By western blot and LC-MS-MS analysis, we show that the anti-sigma factor FlgM is not secreted by ∆hcp1 deletion mutant and could impact free FliA in the cytoplasm. This result may explain the less expression of flagellar class IV genes.

On the first hand, we assume that anti-sigma factor FlgM could be secreted through the T6SS formed with Hcp1 in Pseudomonas fluorescens MFE01. This hypothesis will be checked by analyzing the effect of FlgM overexpression on prey bacteria motility using strains that are immobilized when they are co-cultivated with MFE01 [START_REF] Decoin | A Pseudomonas fluorescens type 6 secretion system is related to mucoidy, motility and bacterial competition[END_REF]. On the other hand, we forecast that the complex "sigma-factor FliA/anti-sigma-factor FlgM" is stabilized by T6SS deletion mutation. In order to test this hypothesis we will study phenotypes of the double mutant ∆hcp1-∆flgM. To identify the toxin that is secreted through T6SS formed by Hcp1 protein, we will perform interactomic studies using translational fusion of flag sequence on hcp1 and flgM genes.

Type 6 Secretion Systems (T6SS) are contractile nanomachines involved in the secretion of effectors directly in prey cells (bacteria or eukaryotic cells). These systems are composed of a membrane complex, a baseplate, and a contractile tail essential for the T6SS effectors/toxin loading . Effectors are transported by a tube with overhead tip that is propelled by a tail contraction. Nowadays, the most studied T6SS effectors exhibit antibacterial activity, by acting on peptidoglycan, lipid membrane or DNA [START_REF] Durand | and beyond: the versatile arsenal of Type VI secretion effectors[END_REF].

Bacterial motility is allowed thanks to an extracellular appendage, the flagella. This complex structure consists of basal body and long filament (polymer of flagellin) connected by a "hook" (Figure 2). The expression of the flagellum filament occurs after the hook reaches a correct length. In this case, the specific sigma factor FliA, is released from FlgM protein, that is secreted throught an incomplete flagellar apparatus. The free FliA protein is able to link the RNA polymerase to permit expression of the flagellar class IV genes including flagellin monomer [START_REF] Dasgupta | A four-tiered transcriptional regulatory circuit controls flagellar biogenesis in Pseudomonas aeruginosa[END_REF].

A.

We have already show that the deletion of hcp1 gene (tube protein) or tssC gene (sheath protein), lead on the first hand, to the loss of swimming motility and flagellin secretion. On the second hand, MFE01 is able to inhibit P. fluorescens MFN1032 target cell motility, thanks to its T6SS formed by Hcp1 [START_REF] Decoin | A Pseudomonas fluorescens type 6 secretion system is related to mucoidy, motility and bacterial competition[END_REF]. This work focuses on identification and characterization of new T6SS effector, associated with Hcp1 (tube protein).

Pseudomonas fluorescens MFE01 is an environmental strain, that possess a functional T6SS. The genes encoding the membrane complex, baseplate and sheath (tssB/C) of this contractile nanomachine are clustered in contrary to genes encoding the tube. There are at least three different orphan genes encoding this tube (hcp1/2 and 3) involved in the formation of different variations of T6SS (Figure 1). Two different hcp genes (hcp2 and hcp3) are involved in antibacterial activity [START_REF] Decoin | A Type VI Secretion System Is Involved in Pseudomonas fluorescens Bacteriam Competition[END_REF]Gallique et al., 2017a), unlike the other one (hcp1) that acts on bacterial motility [START_REF] Decoin | A Pseudomonas fluorescens type 6 secretion system is related to mucoidy, motility and bacterial competition[END_REF].

  flagellar class IV genes is disturbed in MFE01∆hcp1. MFE01, ∆hcp2 and ∆hcp3 possess flagella, contrary to ∆tssC and ∆hcp1

Figure n°1 :

 n°1 Figure n°1 : Schematic representation of P. fluorescens MFE01 T6SS (adapted from Gallique M. et al., 2017b).

Figure n°2 :

 n°2 Figure n°2 : Schematic representation of flagellar class IV genes expression switch (unpublished).

Figure n°3 :

 n°3 Figure n°3 : Electronic microscopy of MFE01 and different T6SS deletion mutants. Red arrows show flagellar filament (Gallique et al., in progress).

Figure n°4 :

 n°4 Figure n°4 : Expression of flagellar genes in MFE01 ∆hcp1 +EV/+hcp1 compared to wild type strain containing empty vector (EV). Data shown represent the mean ± SEM. Significances of differences between mean values were assessed using Mann-Whitney test (n=6) with significance set as *P<0.05; **P<0,005. Red circles represent genes that are expressed by FliA sigma factor. (Gallique et al., in progress).

Figure n°5 :1

 n°5 Figure n°5 : Phenotypes analysis of ∆hcp1 or ∆tssC with or without fliA overexpression. (A.) Electronic microscopy. Red arrows show flagellar filament (B.) Motility on LB 0,3% agar plate (Gallique et al., in progress).

Figure n°6 :

 n°6 Figure n°6 : Western blot on supernatant proteins of MFE01 or ∆hcp1 after a translational fusion of flag sequence with flgM gene. The anti-Flag primary antibody, and a secondary antibody coupled with alkaline phosphatase were used to highlight Flag-FlgM protein. (unpublished).