Margaux Desseigne
email: dr.desseigne@gmail.com

Véronique Madigou

Marie-Vanessa Vanessa Coulet

Olivier Heintz

Virginie Chevallier

Madjid Arab
email: madjid.arab@univ-tln.fr

Au/WO3 nanocomposite based photocatalyst for enhanced solar photocatalytic activity

Keywords: Photocatalyst, Au/WO 3 nanocomposite, Solar photocatalysis, Dyes degradation

Introduction

Water pollution is considered as one of the most prominent issue of global public health challenge with more and more serious situation [1][2][3][4]. Nearly one third of the population around the world cannot access clean drinking water while the more developed countries have to handle new water treatment issues mainly due to pharmaceutical and agricultural wastes [5][START_REF] References Adachi | Controllable Adsorption and Ideal H-Aggregation Behaviors of Phenothiazine Dyes on the Tungsten Oxide Nanocolloid Surface[END_REF][7]. In the past few decades, photocatalytic degradation of pollutants in aqueous solution based on semiconductor-photocatalysts has become an effective approach to address those issues [8][9][10][11][12]. Numerous photocatalysts have been proposed for the decomposition of organic pollutants such as titanium oxide (TiO 2 ) [13][14][15] and zinc oxide (ZnO) [16][17][18], the most studied ones.

However, because of their high band gap energy (> 3.2 eV) corresponding to a maximum wavelength of 392 nm, only 4 % of solar light is effective with these photocatalysts. To meet the challenges of sustainability and green chemistry, the photocatalytic field has to develop new materials capable to absorb visible radiation in order to better harness solar light, a free and clean energy. Different strategies are efficient to extend optical absorption to visible light. One of them consists in doping high band gap photocatalysts such as previously cited TiO 2 or ZnO [19][20][21]; another path is the choice of alternative compounds with a narrower band gap [22][23][24]. In the present work, tungsten trioxide (WO 3 ) has been selected as photocatalyst material to study the degradation of different dyes by photocatalytic reaction. WO 3 is a n-type semiconductor with an indirect band gap ranging between 2.4 and 2.8 eV [25] which endows it a higher solar energy utilization efficiency than TiO 2 or ZnO. The photogenerated holes (h + ) in its valence band (VB) have a strong oxidation ability thanks to a VB potential (E VB ) reaching 2.7-3.4 eV (vs. normal hydrogen electrode, NHE) [26]. Nevertheless, WO 3 has a low photocatalytic activity because its conduction band potential (E CB ) is positive and the recombination of photogenerated electron-hole pairs is greatly facilitated [27]. In order to enhance the photocatalytic efficiency of WO 3 , gold nanoparticles (AuNPs) can be deposited on its surface as metal particles to contribute to the photoelectron-hole separation, prolong the charge carrier lifetime and extend the visible light absorption range to accelerate electron transfer kinetics [28]. Among the different synthesis methods for the deposition of AuNPs on WO 3 , one can cite aerosolassisted chemical vapor deposition [29,30], photochemical deposition [31], cationic adsorption [32], in situ redox reaction [33,34] or ultrasonic method [35]. In this work, we presented a highly efficient photocatalyst based on gold nanoparticles deposition on nanostructured platelet-like tungsten oxide semiconductor. Gold nanoparticles was expected to enhance the photogeneration of charge carrier due to a higher work function than WO 3 and its plasmonic properties. The nanocomposite Au/WO 3 was prepared by a novel and facile method consisting in forming gold nanoparticles onto WO 3 platelets involving a simple impregnationreduction route at room temperature and without any further treatment. The as-synthesized Au/WO 3 nanocomposite is fully characterized in terms of texture, structure and electrical properties. A deep analysis is performed to understand the influence of AuNPs deposition onto the oxide surface. The photocatalytic performance was evaluated on the degradation of three dyes: rhodamine B, methylene blue and methyl orange. Besides, scavengers tests were investigated in order to study the dye decomposition process by oxidative species. Finally, a specific investigation by liquid chromatography coupled with mass spectroscopy was performed in the case of MB degraded by our photocatalysts. This investigation results in a degradation pathway proposition and highlights the interest to associate gold with WO 3 for solar photocatalytic degradation.

Materials and methods

Chemicals

Sodium tungstate dihydrate (NaWO 4 , 2H 2 O; CAS Nb. 10213-10-2), gold (III) chloride trihydrate (HAuCl 4 ,3H 2 O; CAS Nb. 16961-25-4) and sodium borohydride (NaBH 4 ; CAS Nb. 16940-66-2) were purchased from Sigma-Aldrich. Rhodamine B (CAS Nb. 81-88-9), methylene blue (CAS Nb. 61-73-4) and methyl orange (CAS Nb. 547-58-0) were purchased from ChemLab. All reagents were used as received without any further purification. Deionized water with a resistivity of 18 MΩ.cm was used.

Synthesis of Au/WO3 composite

The composite material was obtained in two steps. The first one is the synthesis of a nanostructured semiconductor based on WO 3 subsequently use as a support for the second step consisting in the formation of gold nanoparticles onto the oxide particles.

Preparation of WO3 support

The WO 3 nanoparticles were synthesized in our laboratory following the same method reported in a previous work (Dirany et al., 2016a(Dirany et al., , 2016b)). Firstly, 1 g of the tungsten precursor was dissolved in 20 mL of water and a 2 mol.L -1 HCl solution was added to reduce the pH value to 1. Then, the solution was transferred in a warm bath at 70 °C and stirred until complete evaporation of the solvent is achieved. 60 mL of a 2 mol.L -1 HCl solution was added to the obtained pale yellow powder and the solution was heated at 40 °C during 24 hours under stirring. Secondly, an aging step was applied to the yellow solution in an oven under air flow at 80 °C during 96 hours. At the end, a bright yellow powder was obtained, washed several time with water/ethanol by centrifugation and dried at 60 °C in an oven. A thermal treatment under air at 500 °C lead to WO 3 nanoparticles with an orthorhombic structure and a platelet shape of 60-70 nm thickness size and 300 nm square basal length.

Preparation of Au/WO3 nanocomposite

Gold nanoparticles were formed on the surface of nanostructured tungsten oxide using an impregnationreduction technique at room temperature. First, an amount of previously synthesized WO 3 was dispersed in a 10 -3 mol.L -1 gold precursor solution. The powder concentration was 4 mg.mL -1 . The mixture was stirred in the darkness during 48 hours before to add 0.15 mmol of freshly prepared NaBH 4 solution. The reduction took place and led to the nucleation and growth of gold nanoparticles by the state modification from auric ions to metallic state. After the reductive addition which was executed in an ice-cooled bath, the powder was washed with water/ethanol by centrifugation and dried overnight under air flow at 60 °C in an oven.

Considering the ratio between the gold precursor and the WO 3 suspension, the gold loading on the oxide support was assumed to be 5 wt. %. The as-prepared composite was labelled Au/WO 3 .

Characterizations

The samples were observed by scanning electron microscopy (SEM, SUPRA 40Vp GEMINI Zeiss with inlens detector) and transmission electron microscopy (TEM, JEOL JEM2010 and JEOL JEM3010).

Chemical analyses were performed by inductively coupled plasma (ICP, ICP AES iCAP 6500 DUO -Thermo Scientific and ICP AES iCAP 7400 Radial -Thermo Scientific). Powder X-ray diffraction (XRD) was used to define the crystallinity and the crystallographic structure of samples. Diffraction patterns were acquired using an Empyrean Panalytical diffractometer working with Cu K α radiation in a 2θ range scanning from 20 to 70 degrees (λ = 0.15440 nm, voltage = 45 kV and intensity = 35 mA). The oxidation state of the elements as well as the metal-oxide interaction was monitored using X-ray photoelectron spectroscopy (XPS) measurements. The XPS spectra were acquired with a PHI 5000 Versaprobe apparatus with an Al K α1 radiation source (energy = 1486.7 eV, accelerating voltage = 15 kV, power = 50 W and spot size diameter = 200 µm). Pass energies of 187 eV and 58.7 eV were used for survey spectra and high-resolution windows, respectively. The texture was characterized by gas adsorption. Sorption isotherms were measured at -196 °C using BELSORP Max 1 apparatus. Prior to the measurement, the samples were treated at 150 °C under vacuum for 15 hours in order to remove any adsorbed species. Optical absorbance and UV-visible diffuse reflectance spectra (DRS) were collected with a SHIMADZU 2600 UV-Vis/NIR spectrophotometer. The reflectance (R ∞ ) was recorded with respect to BaSO 4 reference and the band-gap energy was calculated according to the Kubelka-Munk function expressing the relative absorption coefficient by the as-follow equation:

F(R ∞ ) = (1 -R ∞ )²/2R ∞ .
The separation efficiency of the photogenerated charges was determined using photoresistance response (PRR) analysis. Results were collected using a SiO 2 /Si wafer covered with Pt electrodes and the measurements were performed with a Keithley 2611 digital multimeter. The LC-ESI-MS analyses were performed on a UHPLC-HRMS system (Dionex Ultimate 3000 Rapid Separation; Thermo Fisher Scientific) coupled with a QToF Impact II mass spectrometer (Bruker Daltonics, Bremen, Germany) in positive and negative ionization modes. The separations were carried out with an analytical core-shell reversed-phase column (150 × 2.1 mm, 1.7 μm, Kinetex Phenyl-Hexyl; Phenomenex, Le Pecq, France). See supplementary information for more details.

Photocatalytic activity

The photocatalytic performances were evaluated on different model pollutants such as dye molecules.

Rhodamine B (RhB) and methylene blue (MB) were chosen as cationic molecules while methyl orange (MO) was selected as an example of anionic dye. The photocatalytic test device was equipped with an Osram Ultra-Vitalux lamp (300 W, λ > 364 nm) acting as artificial solar light source. Considering all device's parameters (the distance between the lamp and the surface of the solution, the power of the lamp and the dimensions of the used beaker) the irradiance was estimated at 600 W.m -2 .

In a typical test, photocatalytic powder (0.5 mg.mL -1 ) was dispersed in pollutant solution at a concentration equal to 1.10 -3 mol.L -1 . A vigorous stirring in the darkness during one hour was necessary to reach an equilibrium of the adsorption-desorption phenomenon between the particles and the pollutant molecules.

Then, the solar light was switched-on and the mixture was irradiated. 3 mL of the suspension were collected at regular time periods during irradiation. After removal of the powder, the samples were analyzed by UVvisible spectrophotometry. The evolution of the pollutant concentration was estimated by colorimetric method considering the absorbance at 554, 664 and 464 nm for, respectively, RhB, MB and MO.

In parallel, for MB pollutant, the degradation advancement was investigated by qualitative and quantitative determination of the derivatives present in the suspension after different irradiation times, by LC-MS analysis. For this, 3 mL of the suspension were collected just before irradiation (i.e. after adsorption/desorption equilibrium was reached), and after 60, 120 and 180 min of irradiation. They were centrifuged to remove powder and stocked under nitrogen and obscurity at 4 °C until they could be injected in the chromatograph. All experiments for LC-MS analysis were performed in triplicate.

The formation of oxidative radicals in the photocatalytic process was investigated using scavenger coumponds: isopropanol (IPA), ethylenediamine tetraacetic acid disodium salt (EDTA) and benzoquinone (BQ) to trap •OH, h + and •O 2 -, respectively.

Results

Characterization of photocatalysts

The as-prepared Au/WO 3 nanocomposite was firstly characterized by microscopic techniques. XRD analysis were secondly performed to determinate the structure after gold deposition. Figure 3a shows the XRD pattern of WO 3 and Au/WO 3 samples. The patterns are very similar except the presence of three supplementary diffractions lines in the Au/WO 3 pattern. Those lines located at 2θ = 38.27, 44.60 and 64.68 degrees can be well indexed to, respectively, ( 111), ( 200) and ( 220) peaks of cubic gold structure (ICSD card no. 52249). All other diffraction peaks are common with the XRD pattern of bare WO 3 and can be well assigned to WO 3 orthorhombic structure (ICSD card no. 836) which was the platelet's crystalline structure before gold deposition, meaning that the used technique did not modify the bare support structure.

Basically, WO 3 is crystallized in a deformed cubic structure, which can correspond either to a monoclinic phase or to an orthorhombic one. To settle between these two phases, electronic diffraction and Rietveld refinement were necessary and all the calculation details are available in our previous work [START_REF] Desseigne | Shape dependence of photosensitive properties of WO3 oxide for photocatalysis under solar light irradiation[END_REF]. As seen in Figure 4a, the XPS spectrum of Au/WO 3 sample showed the Au, W and O elements coexistence, as expected. The XPS spectrum of bare WO 3 showed residual sodium which can be attributed to impurities coming from the WO 3 platelet synthesis procedure. Figure 4b displays the 4f energy level for pure Au element with the 4f 7/2 peak at 83.97 eV and the 4f 5/2 peak at 87.64 eV. This confirms that gold is well reduced in its metallic state. Figure 4c depicts the binding energy of W 4f 7/2 peak at 35.71 eV and W 4f 5/2 peak at 37.84 eV, in accordance with the energy values found in the literature for W 6+ cation [START_REF] Katrib | The multi-surface structure and catalytic properties of partially reduced WO3, WO2 and WC + O2 or W + O2 as characterized by XPS[END_REF][START_REF] Li | Hydrothermal synthesis of bi-functional nanostructured manganese tungstate catalysts for selective oxidation[END_REF][START_REF] Shpak | XPS studies of active elements surface of gas sensors based on WO3-x nanoparticles[END_REF]. This suggests that W is mainly in the (+VI) state in the Au/WO 3 nanocomposite. Figure 4d represents the 1s energy level of oxygen which was decomposed in three different peaks. The major peak is located at a maximum of 530 eV and corresponds to O 2─ anions of the crystalline network, the peak located at 531 eV corresponds to ─ OH hydroxyl groups [START_REF] Dupin | Systematic XPS studies of metal oxides , hydroxides and peroxides[END_REF] and the part of the peak at 533 eV is attributed to H 2 O water molecules [START_REF] Wagner | Handbook of X-ray Photoelectron Spectroscopy[END_REF]. Moreover, the XPS analysis on the bare WO 3 powder permitted to confirm a ratio of 3 between the atomic concentrations of tungsten and oxygen (see supplementary information) which is in agreement with the expected stoichiometric coefficient. The N 2 sorption isotherm of both WO 3 and Au/WO 3 samples are presented in Figure 5. The inspection of the high-pressure behavior (inset in Figure 5a) evidenced a hysteresis between the adsorption/desorption branches and a small plateau at the saturation pressure. Both isotherms can thus be assigned to type IV isotherm typical of a mesoporous system with relatively large pores considering the location of the sorption branches. The Barret-Joyner-Halenda (BJH) method [START_REF] Barrett | The Determination of Pore Volume and Area Distributions in Porous Substances. I. Computations from Nitrogen Isotherms[END_REF] was applied on the desorption branches and the obtained pore-size distribution is given in Figure 5b. The mean pore size around 60 nm for the bare WO 3 support is characteristic for an inter-granular porosity (between the platelets) and is consistent with the SEM images presented in Figure 2. Addition of AuNPs leads to a strong decrease of the mean pore size that reaches 35 nm. This cannot solely be explained by the presence of the AuNPs whose size and concentration are too small to explain such variation. One hypothesis could be that the AuNPs incorporation procedure (impregnation, reduction and drying) on the WO 3 support modified the agglomeration state of the WO 3 platelets making them more compact, thus reducing the inter-granular porosity. The specific surface area was calculated using the Brunauer, Emmet and Teller (BET) equation.

The obtained values are 12 m 2 .g -1 and 16 m 2 .g -1 for the bare WO 3 support and the Au/WO 3 composite, respectively. The increase of the BET area for the Au/WO 3 composite is directly correlated to the presence of the AuNPs. The total measured BET area a 𝐵𝐵𝐵𝐵𝐵𝐵 𝐴𝐴𝐴𝐴/𝑊𝑊𝑂𝑂 3 can be directly written as in Equ. 1 where x Au and

x WO3 are, respectively, the weight fraction of WO 3 and Au in the composites. Furthermore, the platelet particles thickness was confirmed by applying the method of André et al. [START_REF] André | Morphology and reactivity of aluminium nanocrystalline powders[END_REF] The absorption spectrum of the Au/WO 3 sample (red curve) shown in Figure 6 exhibits two broad edge peaks. The first one centered on 300 nm is also observed in the absorption spectrum of pure WO 3 (Figure 6 blue curve) and corresponds to the optical band gap of the oxide support. The Kubelka-Munk plot in inset made possible the estimation of the band gap energy and the result lead to E g = 2.54 eV. The second peak centered at around 550 nm corresponds to the surface plasmon resonance (SPR) band of gold nanoparticles [START_REF] Hu | Gold/WO3 nanocomposite photoanodes for plasmonic solar water splitting[END_REF]. It is worth noting that the intensity of this peak is quite low compared to the main peak of WO 3 . This is nevertheless consistent with literature where it has been demonstrated that the intensity of the absorbance peak of deposited AuNPs on oxide is strongly dependent on the particle size. Too small gold particles with diameter inferior to 5 nm could not have a SPR effect perceptible in diffuse reflectance spectra [START_REF] Sarina | Photocatalysis on supported gold and silver nanoparticles under ultraviolet and visible light irradiation[END_REF], and in our case, the particles have an average size of 7 ± 3 nm which explains their low absorbance peak intensity. The photoresistance response (PRR) can be an effective method to examine the separation efficiency of photogenerated charges. As it can be seen in Figure 7a and Figure7b, the two samples (WO 3 and Au/WO 3 ) produced different photoresistance responses under an on-off cycle of photoirradiation at λ > 364 nm. First, the intrinsic resistance of the sample must be reached and stabilized, then the irradiation can be started which generates photoelectron-hole pairs and leads to a decrease of the resistance. A plateau was reached when the photogenerated electron rate has stabilized and the irradiation was then switched off. The charge carriers' recombination occurred more or less quickly, depending on the photocatalyst electrical properties.

As expected, the created Schottky barrier at the interface between gold nanoparticles and oxide semiconductor support exhibited the longest recombination period (25 time longer than bare WO 3 ) [START_REF] Liu | Facet engineering of WO3 arrays toward highly efficient and stable photoelectrochemical hydrogen generation from natural seawater[END_REF]. For the nanocomposite sample, the enhancement of charge carriers' lifetime could be explained, on the one hand, by hot electrons which are produced when gold nanoparticles are irradiated due to its gold's SPR property. These hot electrons are transferred in the semiconductor's conduction band provided that their energy is higher than the band gap energy. In our case, we already proved by UV-visible spectroscopy and DRS measurements that our composite is photosensitive at wavelength located in the visible range thanks to E g (WO 3 ) = 2,54 eV. The hot electrons injections lead to an electrons overpopulation which allow a continuous electrons power supply. This results in a lower kinetic of the resistance to reach the equilibrium value hence a better charge carriers' lifetime. Figure 8 illustrates the hot electrons injection phenomenon. E C , E V and E F are respectively the energy level of the conduction, valence and fermi band; eϕ m and eϕ SC are respectively the work function for the metal and for the semiconductor and VL means vacuum level [START_REF] He | Improved photochromism of WO3 thin films by addition of Au nanoparticles[END_REF][START_REF] Hu | Gold/WO3 nanocomposite photoanodes for plasmonic solar water splitting[END_REF][START_REF] Sarina | Photocatalysis on supported gold and silver nanoparticles under ultraviolet and visible light irradiation[END_REF]. On the other hand, under irradiation, the photons' electric field intensity at the surface of plasmonic nanoparticle is exacerbated which induce a localized SPR effect. This results in an important slowdown in the diffusion of photogenerated holes in the semiconductor which increase the return time at the equilibrium state of the charge carriers [START_REF] Christopher | Visible-light-enhanced catalytic oxidation reactions on plasmonic silver nanostructures[END_REF][START_REF] Link | Optical Properties and Ultrafast Dynamics of Metallic Nanocrystals[END_REF].

Efficiency of photocatalytic activity

The photocatalytic activity of the Au/WO 3 nanocomposite was studied by the degradation under solar light irradiation of three model dyes like: rhodamine B (RhB), methylene blue (MB) and methyl orange (MO).

The degradation efficiency depends on two main phenomena, the first one is the adsorption rate of the organic molecule onto the photocatalyst surface and the second one is due to the photoexcitation reaction occurring under irradiation.

Adsorption phenomenon

The adsorption rate was estimated by comparing the UV-visible spectra of the initial dye solution and the solution after reaching adsorption/desorption equilibrium. In general, the adsorption phenomenon depends on numerous factors such as the specific surface area, the steric hindrance related to organic molecules' interactions between adsorbent/adsorbate and the surface charge. As it can be seen in Figure 9, the bare oxide photocatalyst showed a selective adsorption depending on the charge and on the nature of the dye molecule. The zeta potential of the WO 3 powder dispersed in water was found to be -41 mV [55] which indicates that the surface of the compound is highly negatively charged at natural pH. This creates suitable conditions for an electrostatic interaction with positively charged molecules. For MO, as expected for an anionic molecule, there was no adsorption for both bare WO 3 and Au/WO 3 nanocomposite. Interestingly, the adsorption behavior of WO 3 showed a huge difference between RhB and MB while both of them are cationic molecules; there is no adsorption for RhB whereas MB is adsorbed almost at 90 %. The strong attraction between MB and WO 3 might be favored by the high sulfur-oxygen affinity and the low steric hindrance around the cationic charge. On the contrary, the steric repulsion of the carboxylate anions in RhB might inhibits the extent of adsorption [56] on the WO 3 surface. The ca. 20 % decrease in MB adsorption rate in presence of the Au/WO 3 sample might be explained by the reduction of the porosity (change from 60 nm to 30 nm), due to the formation of gold nanoparticles which decrease adsorption site number.

Figure 9: Dye adsorptipn ratio onto the photocatalyst's surface

Photocatalysis process

The photocatalytic efficiency results were determined from UV-visible spectra corresponding to different samples collected at periodic time during the irradiation time. with a concentration loss of 30 % in 180 min. The photodegradation efficiencies are presented by empty square plot for pure WO 3 photocatalyst and full square plot for the gold decorated photocatalyst. The concentration at the initial irradiation point t 0 corresponds to the concentration after adsorption (C 0 ), in that respect, the concentration evolution (C t ) is only due to the photosensitive effect. RhB and MO dyes are only degraded in presence of the Au/WO 3 nanocomposite. The degradation under solar light irradiation reaches 100 % after 90 min for RhB and almost 50 % after 180 min for MO. Thus, a twice higher degradation rate can be reached in a twice shorter time for RhB than for MO. These differences might be associated with the charge of the molecules. The photocatalysis being a surface reaction, it might be expected that an attractive interaction will promote the photocatalytic efficiency while a repulsive interaction will hinder the degradation process. The higher reactivity of Au/WO 3 photocatalyst with RhB pollutant is confirmed by the pseudo-first order plots presented in supplementary information from which the kinetic constant rate was calculated to be about 33.10 -3 min 1 which is 3.3 times faster than for MB and 11 times faster than for MO. Although, MO has a lower degradation rate than the other two dyes, the efficiency of our nanocomposite photocatalyst towards the photodegradation of this specific dye noteworthy compared to some results in the literature where no degradation occurred with a similar Au/WO 3 material [START_REF] Qamar | Synthesis and comparative photocatalytic activity of Pt/WO3 and Au/WO3 nanocomposites under sunlight-type excitation[END_REF]. Due to a high adsorption of MB onto the pure WO 3 photocatalyst's surface before irradiation, a screening effect appeared which restricted the reactive oxygen species (ROS) production. As a result, the degradation started only after one hour of irradiation and reached 65 % after 180 min. In the case of gold decorated photocatalyst, the degradation started as soon as irradiation begins and no screening effect was observed leading to a better degradation rate which reached 81 % at the end of the test. From those observations, it can be concluded that AuNPs onto WO 3 nanoplatelets enhanced the efficiency of the photocatalyst whatever the dye's ionic charge. Generally, the photodegradation mechanism starts when the semiconductor absorbs photons from the irradiation source generating pairs of electron -hole (Equ. 2). Then, three main species can lead to an efficient degradation in this system: (i) hydroxyl radicals •OH produced by WO 3 (Equ. ). Yet for MB and MO, this reduction cannot straightly be ruled out because of the hot electrons generated in AuNPs by SPR effect. Nevertheless, there is evidence that potential MB photobleaching was followed by a real decomposition process like a gradual blueshift of the MB peak absorbance at 664 nm (Figure 10b) as expected in an oxidative demethylation of the dye molecule [START_REF] Zang | Photochemistry of semiconductor particles 3. Effects of surface charge on reduction rate of methyl orange photosensitized by ZnS sols[END_REF]. Moreover, this demethylation will be demonstrated and confirmed hereafter with LC-MS analysis.

Equ the leuco methylene blue (LMB), by holes is highly thermodynamically favored. This would lead to a recoloration of the solution and distort the estimated concentration. This kind of observation was already observed in the case of TiO 2 based photocatalysts exposed to aerated conditions [START_REF] Lee | Novel UV-Activated Colorimetric Oxygen Indicator[END_REF] or visible light irradiation [START_REF] Wang | Nanocrystalline TiO 2 -Catalyzed Photoreversible Color Switching[END_REF]. In order to confirm a "real" degradation of MB by our photocatalyst, we performed liquid chromatography coupled with mass-spectrometry analyses. The concentration evolution throughout the irradiation was evaluated by the area of the chromatogram pic relevant to MB molecule (i.e. pic corresponding to mass and charge ratio m/z = 284). The relative concentration vs the irradiation time is presented in Figure 13 and compared with UV-visible spectroscopy results.

A huge difference between the concentration evolution of MB, during photolysis and photocatalysis with pure WO 3 , respectively determined from UV-vis. spectra and LC-MS chromatograms appeared. Instead to have a continuous decrease as observed with UV-visible spectroscopy method, the observed degradation by chromatography method started after a plateau until 120 min and 60 min for photolysis and photocatalysis, respectively. This highlights that the first degradation part of MB is not really a degradation but the formation of colorless LMB molecule. It also highlights the limit of UV-visible spectroscopy method and the importance to use a more sensitive technique to quantify the dye degradation yield. In contrast, similar results between the two analytical methods were obtained in presence of Au/WO 3 photocatalyst meaning gold decoration of the material is an efficient way to promote its activity under visible light and induce the decomposition of MB dye. 193,217,229) in only 180 min of irradiation. Because of the detection limit of the LC-MS device, it was not possible to observed lower fragments but, according to the literature, when the ring-opening is initiated for MB dye, then the mineralization is easy to reach. This conclude on the high efficiency of our nanocomposite photocatalyst for the MB degradation under solar light [START_REF] References Adachi | Controllable Adsorption and Ideal H-Aggregation Behaviors of Phenothiazine Dyes on the Tungsten Oxide Nanocolloid Surface[END_REF][START_REF] Cohen | Tracking the degradation pathway of three model aqueous pollutants in a heterogeneous Fenton process[END_REF][START_REF] Depuccio | Degradation of Methylene Blue Using Porous WO3, SiO2-WO3, and Their Au-Loaded Analogs: Adsorption and Photocatalytic Studies[END_REF][START_REF] Guo | Photo-Fenton degradation of methylene blue by synergistic action of oxalic acid and hydrogen peroxide with NiFe2O4 hollow nanospheres catalyst[END_REF][START_REF] Houas | Photocatalytic degradation pathway of methylene blue in water[END_REF][START_REF] Matsunami | Comparison of photodegradation of methylene blue using various TiO2 films and WO3 powders under ultraviolet and visible-light irradiation[END_REF][START_REF] Nguyen | Activation of persulfate by CoO nanoparticles loaded on 3D mesoporous carbon nitride (CoO@meso-CN) for the degradation of methylene blue (MB)[END_REF][START_REF] Su | Transformation pathway and degradation mechanism of methylene blue through β-FeOOH@GO catalyzed photo-Fenton-like system[END_REF][START_REF] Wolski | Formation of reactive oxygen species upon interaction of Au/ZnO with H2O2 and their activity in methylene blue degradation[END_REF][START_REF] Zang | Photochemistry of semiconductor particles 3. Effects of surface charge on reduction rate of methyl orange photosensitized by ZnS sols[END_REF].

  As a representative example of the distribution in gold nanoparticles (AuNPs) on the surface oxide catalyst, the SEM image of the WO 3 sample after Au deposition is given in Figure 1. It shows a rather dense collection of well distributed AuNPs on the basal facets of the support. The size distribution of gold nanoparticles, obtained by counting 1 000 particles, is given in inset. It shows a polydisperse size with a mean diameter of 7 ± 3 nm.

Figure 1 :

 1 Figure 1: SEM image of Au/WO 3 nanocomposite. The inset represents the size distribution of gold particles performed on 1 000 particles.TEM images, presented in Figure2aand Figure2b, show that AuNPs are essentially hemispherical thus optimizing the interfacial contact between the metal and the semiconductor. Interestingly, it is also observed that AuNPs preferentially decorate the basal flat facets of WO 3 nanoplatelets rather than lateral facets. On the Figure2b, which shows a WO 3 platelet edge-on, no AuNP is observed on the lateral facet. Fast Fourier transforms (FFT) of the HR-TEM images were carried out (insert in Figures2a and 2b), they showed that the platelets are a single crystal and all diffracted planes match with an orthorhombic phase, in agreement with XRD results presented in the next paragraph. Figure2acorresponds to a platelet viewed along the

Figure 2 :

 2 Figure 2: Images of gold nanoparticles deposited on WO 3 platelet:(a) platelet lying flat, the associated FFT corresponding to a [010] zone axis in insert; (b) platelet edge on with the (020) planes imaged; (c) defects like pores are observed on the (020) basal surface and (d) HREM of platelet oriented along the [100] direction, the circles corresponds to the selected areas of the FFT presented in inserts The gold content was determined by ICP-AES. The results showed a concentration of 3.5 wt.% in gold for the composite sample while the assumed gold loading was 5 wt. %. This indicates a gold loading yield success of 70 % by the impregnation-reduction route.

Figure 3 :

 3 Figure 3: XRD patterns of bare WO 3 (blue) and Au/WO 3 nanocomposite (red)

Figure 4 :

 4 Figure 4: (a) XPS pattern of all elements for bare WO 3 and Au/WO 3 ; (b-d) High-resolution measurements on 4f levels of Au (b), W (c) and 1s level of O (d) for the Au/WO 3 composite.

  Figure 5: (a) N 2 sorption-desorption isotherms of bare WO 3 in blue and Au/WO 3 nanocomposite in red; (b) Distribution of the pore-size (BJH method)

Figure 6 :

 6 Figure 6: Absorbance spectra of bare WO 3 (blue curve) and Au/WO 3 composite (red curve). The inset corresponds to Kubelka-Munk plot used to determine the band gap energy

Figure 7 :

 7 Figure 7: Photoresistance response after solar light irradiation of (a) WO 3 and (b) Au/WO 3 samples

  Figure 10d, e and f for respectively RhB, MB and MO. Only MB is significantly sensitive to irradiation

Figure 10 :

 10 Figure 10: (a, b, c) Evolution of dye UV-vis. spectra during irradiation time with Au/WO 3 photocatalyst and (c, d, e) Evolution of relative dye concentration vs irradiation time for RhB (pink), MO (blue) and MO (orange). C 0 and C t correspond to the initial dye concentration and the one at t time of irradiation, respectively.

  3 and 4), which are well known to have a high oxidative power at the conduction band level; (ii) superoxide radicals •O 2 ─ allowed by the presence of gold particles (Equ. 5 to 7) which can produce other ROS through reactions with water (Equ. 8 to 10) and, (iii) holes h + which react directly with the organic molecule at the catalyst surface.In addition, the photoexcited electrons within the photocatalyst might transform blue MB and pink RHB molecules into their colorless leuco form (LMB and LRhB respectively), as well as orange MO molecules into their colorless reduced form (MOH 2 ) , resulting in the photobleaching of their respective solution. With the Au/WO 3 photocatalyst, the conduction band energy level (E CB = +0.82 V/NHE) only provide RhB to be directly reduced (E RhB/LRhB = +0.95 V/NHE, E MB/LMB = +0.53 V/NHE [58], E MO/MOH2 = +0.24 V/NHE (pH=0)[59]

  degradation is mainly due to •OH. Only •OH trapping solution had an influence on the MB degradation while all scavengers impacted the efficiency of MO decomposition. Indeed, on the one hand, a degradation was observed when •OH and •O 2 ─ were trapped in MO solution which indicates that both oxygen radicals play a major role in the photoreaction mechanism; on the other hand, photogenerated h + seem to also play a role but minor than other species. In sum, the degradation with the Au/WO 3 nanocomposite under solar light irradiation is due to all created ROS for MO and only due to •OH for MB and RhB with a better degradation kinetic for RhB thanks to a direct oxidation with the photocatalyst.

Figure 11 :

 11 Figure 11: Results of trapping tests for nanocomposite with all dyes under solar light irradiation Thanks to all results, the interactions between the solar light, nanocomposite photocatalyst and dye molecules can be summarized by the illustration in Figure 12.

Figure 12 :

 12 Figure 12: Illustration of dyes degradation mechanism in presence of Au/WO 3 under solar light irradiation As MB is the only dye undergoing a degradation by photolysis, we performed further investigation in order to confirm the efficiency of our photocatalyst to really decompose it (thus eliminating the hypothesis of simple photobleaching) and to give an idea of the degradation pathway. In fact, in taking into account the valence band position of WO 3 (E VB = +3.36 V/NHE), re-oxidation of the colorless reduced form of MB,

Figure 13 :

 13 Figure 13: Evolution of relative concentration of MB during photolysis test (λ = 664 nm) determined from UVvisible spectra and LC-MS chromatographs (m/z = 284). S and C mean spectroscopy and chromatography method, respectively

Figure 14 :

 14 Figure 14: Chromatograms of MB degradation products obtained withou photocatalyst (black line), with bare WO 3 (dark blue line), and with Au/WO 3 photocatalyst (light blue line) at (a) 60, (b) 120 and (c) 180 min of irradiation

ACKNOWLEDGMENTS

The authors gratefully acknowledge the Regional Council of Provence-Alpes-Côte d'Azur, General Council of Var, the urban community of Toulon Provence Mediterranean and University of Toulon for their financial support in the framework of the "NanoCat" project. The authors also wish to thank Professor Gerald CULIOLI and Bruno VIGUIER for allowing us to perform LC-MS analysis and for scientific discussions and advice.

Table 1 : Decomposition products detected by LC-MS analysis after 60, 120 and 180 min of irradiation by (a) photolysis and photocatalysis asssisted by (b) bare WO 3 and (c) Au/WO 3 nanocomposite. i, ii, iii means products from one of the three degradation pathway illustrated in Figure 15


Antonio Al Serhali

Joachim Niehren

Subhedge Projection for Stepwise Hedge Automata

We show how to evaluate stepwise hedge automata (Shas) with subhedge projection. Since this requires passing finite state information top-down, we introduce the notion of downward stepwise hedge automata. We use them to define an in-memory and a streaming evaluator with subhedge projection for Shas. We then tune the streaming evaluator so that it can decide membership at the earliest time point. We apply our algorithms to the problem of answering regular XPath queries on Xml streams. Our experiments show that subhedge projection of Shas can indeed speed up earliest query answering on Xml streams.

Introduction

Projection is necessary for running automata on words, trees, hedges or nested words efficiently without having to evaluate irrelevant parts of the input structure. Projection is most relevant for Xml processing as already noticed by [START_REF] Marian | Projecting XML documents[END_REF][START_REF] Frisch | Regular tree language recognition with static information[END_REF][START_REF] Maneth | XPath whole query optimization[END_REF]]. Saxon's in-memory evaluator, for instance, projects input Xml document relative to an Xslt program, which contains a collection of XPath queries to be answered simultaneously [START_REF] Kay | The saxon xslt and xquery processor[END_REF]. When it comes to processing Xml streams, quite some algorithms [START_REF] Madhusudan | Query automata for nested words[END_REF][START_REF] Mozafari | High-performance complex event processing over XML streams[END_REF][START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF][START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF] are based on nested word automata (Nwas), for which an efficient projection algorithm exists [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF].

More recently, it was noticed that stepwise hedge automata (Sha) [START_REF] Niehren | Determinization and minimization of automata for nested words revisited[END_REF] have important advantages over Nwas when it comes to determinization and earliest query answering [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF]. Shas are a recent variant of standard hedge automata that go back to the sixties [START_REF] Comon | Tree automata techniques and applications[END_REF][START_REF] Thatcher | Characterizing derivation trees of context-free grammars through a generalization of automata theory[END_REF]. They mix up bottom-up processing of standard tree automata with the left-to-right processing of finite word automata (Nfas), but do neither support top-down processing nor have an explicit stack in contrast to Nwas. In particular, it could be shown that earliest query answering for regular queries defined by deterministic Shas [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF] has a lower worst case complexity than for deterministic Nwas [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF]. Shas have the advantage that the set of states that are accessible over some hedge from a given set of start states can be computed in linear time, while for Nwas this requires cubic time.

Based on deterministic Shas, earliest query answering for regular queries became feasible in practice [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF], as shown for a collection of deterministic Shas for real word regular XPath queries on Xml documents [START_REF] Serhali | A Benchmark Collection of Deterministic Automata for XPath Queries[END_REF]. On the other hand side, it is still experimentally slower than the best non-earliest approaches [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF]. We believe that this is due to the fact that projection algorithms for Sha evaluation are missing. Projecting in-memory evaluation assumes that the full graph of the input hedge is constructed at beforehand. Nevertheless, projection may still save time, if one has to run several queries on the same input hedge, or, if the graph got constructed for different reasons anyway. In the streaming case with subhedge projection, the situation is similar: the whole input hedge on the stream needs to be parsed. But only for the nodes that are not projected away, the automaton transitions need to be computed. Given that pure parsing is by two or three orders of magnitude faster, one can save considerable time as noticed in [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF].

Consider the example of the XPath filter [self::list][child::item] that is satisfied by an Xml document if its root is an list element that has some item child. When evaluating this filter on an Xml document, it is sufficient to inspect its roots for having label list and then all its children until some item is found. The subhedges of these children can be projected away. However, one must memoize whether the level of the current node is 0, 1, or greater. This level information can be naturally updated in a top-down manner. The evaluators of Shas, however, operate bottom-up and left-to-right exclusively. Therefore, projecting evaluators for Shas need to be based on more general machines. It would not be sufficient to map Shas to Nwas and use their projecting evaluators [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF]. The Nwas obtained by compilation from Shas do not push any information top-down, so no projection is enabled. Thus, the objective of the present paper is to develop evaluators with subhedge projection for Shas.

As more general machines we propose downward stepwise hedge automata (Sha ↓ s), a variant of Shas that support top-down processing in addition. They are basically Neumann and Seidl's pushdown forest automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF], except that they apply to unlabeled hedges instead of labeled forests. Nwas are known to operate similarly on nested words [START_REF] Gauwin | Streaming tree automata[END_REF], while allowing for more general visible pushdowns. We then distinguish subhedge projection states for Sha ↓ s, and show how to use them to evaluate Shas with subhedge projection both in-memory and in streaming mode. Alternatively, subtree projecting evaluators for Sha ↓ s could be obtained by compiling them to Nwas, distinguishing irrelevant subtrees there [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF], and using them for subtree projecting evaluation via projecting Nwas.

As a first and main contribution, we show how to compile Shas to Sha ↓ s so that one can distinguish appropriate subhedge projection states. The idea is to distinguish contexts in which states of the Sha will safely not change. For instance, the XPath filter [self::list][child::item] can be defined by the deterministic Sha in Fig. 1, which our compiler maps to the Sha ↓ in Fig. 2 (up to renaming of states). The context information made explicit is about the levels of the states. This permits us to distinguish a projection state Π taken from level 2 on in which subhedges can be ignored.

We prove the soundness of our compiler given in the appendix. The proof is based on an nontrivial invariant, that we establish for a slight adaptation of the original projection algorithm published at FCT [START_REF] Nagy | Subhedge projection for stepwise hedge automata[END_REF]. We also note that our compiler may in the worst case increase the size of the automata exponentially. Therefore, we avoid constructing the Sha ↓ s statically but rather construct only the needed part of the Sha ↓ s dynamically on the fly when using it to evaluate some hedge with subhedge projection.

Our second contribution is a refinement of the compiler from Shas to Sha ↓ s for distinguishing safe states for rejection and selection. In this way, we obtain an earliest membership tester for deterministic Shas in streaming mode which improves the recent earliest membership tester of [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF] with subhedge projection. The property of being earliest carries over from there. We lifted this earliest membership tester to an earliest query answering algorithm with subhedge projection for monadic queries defined by deterministic Shas but omit the details.

Our third contribution is an implementation and experimental evaluation of an earliest query answering algorithm for dShas with subhedge projection (not only of earliest membership testing), by introducing subhedge projection into the AStream tool [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF]. For the evaluation, we consider the deterministic Shas constructed with the compiler from [START_REF] Niehren | Determinization and minimization of automata for nested words revisited[END_REF] for the forward regular XPath queries of the XPathMark benchmark [START_REF] Franceschet | Xpathmark performance test[END_REF] and real-world XPath queries [START_REF] Serhali | A Benchmark Collection of Deterministic Automata for XPath Queries[END_REF]. It turns out that we can reduce the running time for all regular XPath queries that contain only child axes considerably since large parts of the input hedges can be projected away. For such XPath queries, the earliest query answering algorithm of AStream with projection becomes competitive in efficiency with the best existing streaming algorithm from QuiXPath [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF] (which is non-earliest on some queries though). The win is smaller for XPath queries with descendant axis, where only few subhedge projection is possible. Outline. After some preliminaries in Section 2 and 3. In Section 4 we introduce Sha ↓ s and show that they enable in-memory evaluation with subhedge projection. In Section 5 we show how to compile Shas to Sha ↓ s with subhedge projection states. Streaming evaluators for Sha ↓ s with subhedge projection follow in Section 6. Section 7 improves the compiler from Shas to Sha ↓ s for obtaining an earliest membership tester. Section 8 discusses our practical experiments.

Publication Comments. This orignial version of this paper paper was published at FCT [START_REF] Nagy | Subhedge projection for stepwise hedge automata[END_REF] without appendix. The appendix of the present longer version [START_REF] Niehren | Subhedge projection for stepwise hedge automata[END_REF] contains supplementary material including in particular the soundness proof of the safe-no-change subhedge projection algorithm. It also contains further discussion on related work.

Preliminaries

Let A and B be sets and r ⊆ A × B a binary relation. The domain of r is

dom(r) = {a ∈ A | ∃b ∈ B. (a, b) ∈ r}. We call r total if dom(r) = A. A partial function f : A → B is a relation f ⊆ A × B that is functional. A total function f : A → B is a partial function f : A → B that is total.
Words. Let N be the set of natural numbers including 0. Let the alphabet Σ be a set. The set of words over

Σ is Σ * = ∪ n∈N Σ n . A word (a 1 , . . . , a n ) ∈ Σ n
where n ∈ N is written as a 1 . . . a n . We denote the empty word of length 0 by ε ∈ Σ 0 and by

v 1 • v 2 ∈ Σ * the concatenation of two words v 1 , v 2 ∈ Σ * .
Hedges. Hedges are sequences of letters and trees ⟨h⟩ with some hedge h. More formally, a hedge h ∈ H Σ has the following abstract syntax:

h, h ′ ∈ H Σ ::= ε | a | ⟨h⟩ | h • h ′ where a ∈ Σ We assume ε • h = h • ε = h and (h • h 1 ) • h 2 = h • (h 1 • h 2 )
. Therefore, we consider any word in Σ * as a hedge in H Σ , i.e.,

Σ * ∋ aab = a • a • b ∈ H Σ .
Nested Words. Hedges can be identified with nested words, i.e., words over the alphabet Σ = Σ ∪ {⟨, ⟩} in which all parentheses are well-nested. This is done by the function nw (h) :

H Σ → (Σ ∪ {⟨, ⟩}) * such that: nw (ε) = ε, nw (⟨h⟩) = ⟨ • nw (h) • ⟩, nw (a) = a, and nw (h • h ′ ) = nw (h) • nw (h ′ ).
3 Stepwise Hedge Automata (SHAs)

Stepwise hedge automata (Shas) are automata for hedges mixing up bottom-up tree automata and left-to-right word automata.

Definition 1. A stepwise hedge automaton ( Sha) is a tuple A = (Σ, Q, ∆, I, F )
where Σ and Q are finite sets, I, F ⊆ Q, and ∆ = ((a ∆ ) a∈Σ , ⟨⟩ ∆ , @ ∆ ) where:

a ∆ ⊆ Q × Q, ⟨⟩ ∆ ⊆ Q, and @ ∆ : (Q × Q) × Q.
A Sha is deterministic or equivalently a d Sha if I and ⟨⟩ ∆ contain at most one element, and all relations (a ∆ ) a∈Σ and @ ∆ are partial functions.

The set of state q ∈ Q, subsumes a subset I of initial state, a subset F of final states, and a subset ⟨⟩ ∆ of tree initial states. The transition rules in ∆ have three forms: If (q, q ′ ) ∈ a ∆ then we have a letter rule that we write as q a -→ q ′ in ∆. If (q, p, q ′ ) ∈ @ ∆ then we have an apply rule that we write as: q@p → q ′ in ∆.

And if q ∈ ⟨⟩ ∆ ∈ Q then we have a tree initial rule that we denote as ⟨⟩ -→ q in ∆. For any hedge h ∈ H Σ we define the transition relation h -→ wrt ∆ such that for all q, q ′ , p, p ′ ∈ Q, a ∈ Σ, and h, h ′ ∈ H Σ :

true q ε -→ q wrt ∆ q a -→ q ′ in ∆ q a -→ q ′ wrt ∆ q h -→ q ′ wrt ∆ q ′ h ′ -→ q ′′ wrt ∆ q h•h ′ --→ q ′′ wrt ∆ ⟨⟩ -→ p in ∆ p h -→ p ′ q@p ′ → q ′ in ∆ q ⟨h⟩ --→ q ′ wrt ∆
A run of the dSha in Fig. 1 on the tree ⟨h⟩ with subhedge h = list • ⟨item⟩ is illustrated graphically in Fig. 2. It justifies the transition 0 ⟨h⟩ --→ 4 wrt ∆. The run starts on the top-most level of ⟨h⟩ in the initial state 0 of the automaton. The run on the topmost level is suspended immediately. Instead, a run on the tree's subhedge h on the level below is started in the tree initial state, which is 0 since ⟨⟩ -→ 0 in ∆. This run eventually ends up in state 3 justifying the transition 0 h -→ 3 wrt ∆. The run of the upper level is then resumed from state 0. Given that 0@3 → 4 in ∆ it continues in state 4. In the graph, this instance of the suspension/resumption mechanism is illustrated by the box in the edge 0 4. The box stands for a future value. Eventually, the box is filled by state 3, as illustrated by 3 so that the computation can continue. But in state 4, the upper hedge ends. Since state 4 is final the run ends successfully. The run on the subhedge justifying 0 h -→ 3 wrt ∆ works in analogy. A hedge is accepted if its transition started in some initial state reaches some final state. The language L(A) is the set of all accepted hedges:

L(A) = {h ∈ H Σ | q h -→ q ′ wrt ∆, q ∈ I, q ′ ∈ F }
For any subset Q ⊆ Q and hedge h ∈ H Σ we define the in-memory evaluation:

h (Q) = {q ′ | q h -→ q ′ wrt
∆, q ∈ Q}. An in-memory membership tester for h ∈ L(A) can be obtained by computing h (I) by applying the transition relation to all elements recursively and testing whether it contains some final state in F .

0 0' 1' 0" 1 ′′ h2 h1 Π 1 ′′ 1' 0" 2" Π 2" 3' 4 list ⟨⟩ ⟨⟩ list ⟨⟩ item
Fig. 4: A run of the Sha ↓ in Fig. 2 on ⟨list

• ⟨list • h 1 ⟩ • ⟨item • h 2 ⟩⟩.
4 Downward Stepwise Hedge Automata (SHA ↓ s)

Shas process information bottom-up and left-to-right exclusively. We next propose an extension to downward stepwise hedge automata with the ability to pass finite state information top-down. These can also be seen as an extension of Neumann and Seidl's pushdown forest automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF] from (labeled) forests to (unlabeled) hedges.

Definition 2. A downward stepwise hedge automaton (Sha ↓ ) is a tuple A = (Σ, Q, ∆, I, F ) where Σ and Q are finite sets, I, F ⊆ Q, and ∆ = ((a ∆ ) a∈Σ , ⟨⟩ ∆ , @ ∆ ). Furthermore,

a ∆ ⊆ Q × Q, ⟨⟩ ∆ ⊆ Q × Q, and @ ∆ : (Q × Q) × Q. A Sha ↓
is deterministic or equivalently a dSha ↓ if I contains at most one element, and all relations ⟨⟩ ∆ , a ∆ , and @ ∆ are partial functions.

The only difference to Shas is the form of the tree opening rules. If (q, q ′ ) ∈ ⟨⟩ ∆ ∈ Q then we have a tree initial rule that we denote as: q ⟨⟩ -→ q ′ in ∆. So here the state q ′ where the evaluation of a subhedge starts depends on the state q of the parent. The definition of the transition relation and thus the evaluator of a Sha ↓ differs from that of a Sha by the following equation:

q ⟨⟩ -→ p in ∆ p h -→ p ′ wrt ∆ q@p ′ → q ′ in ∆ q ⟨h⟩ --→ q ′ wrt ∆
This means that the evaluation of the subhedge h starts in some state p such that q ⟨⟩ -→ p in ∆. So the restart state p now depends on the state q above. This is how finite state information is passed top-down by Sha ↓ s. Shas in contrast operate purely bottom-up and left-to-right.

An example of an in-memory evaluation on the dSha ↓ in Fig. 2 for the filter [self::list][child::item] is shown in Fig. 4. The run of Sha ↓ s works quite similarly to the runs of Shas, just that when restarting a computation in the subhedge of some tree in state q, then it will start in some state p such that q ⟨⟩ -→ p (rather than in some tree initial state that is independent of q). This Fig. 5: The Sha ↓ A down for the dSha A in Fig. 1. can be noticed for example when opening the first subtree labeled with item where a transition rule 1 ′ ⟨⟩ -→ 0 ′′ is applied. One can see that all nodes of the subtrees h 1 and h 2 are evaluated to the projection state Π, which holds finitestate information on the current level that was passed top-down.

Any Sha A = (Σ, Q, ∆, I, F ) can be mapped to a Sha ↓ A down = (Σ, Q, ∆ down , I, F ) with the same runs and language. The only change is described by the following rule.

⟨⟩

-→ p in ∆ q ∈ Q q ⟨⟩ -→ p in ∆ down
Independently of the current state q ∈ Q, the Sha ↓ A down can start the evaluation of the subhedge of a subtree in any open tree state p ∈ ∆. Note that the conversion preserves determinism. For illustration, the dSha ↓ for dSha from Fig. 1 of the introduction is given in Fig. 5. As for other kinds of automata, making them multi-way does not add expressiveness. So we can convert any dSha ↓ A into an equivalent Sha by introducing nondeterminism . Since Shas can be determinized in at most exponential time, the same holds for Sha ↓ s. It is sufficient to convert it to a Sha, determinize it, and identify the resulting dSha with a dSha ↓ .

We next show how to get subhedge projection for Sha ↓ s. Two notions will be relevant here, automata completeness and subhedge projection states.

So let A = (Σ, Q, ∆, I, F ) be a Sha ↓ . We call ∆ complete if all its relations (a ∆ ) a∈Σ , ⟨⟩ ∆ and @ ∆ are total. We call A complete if ∆ is complete and I ̸ = ∅. Definition 3. We call a state q ∈ Q a subhedge projection state of ∆ if there exists q ′ ∈ Q called the witness of q such that the set of transition rules of ∆ containing q ′ or with q on the leftmost position is included in:

{q ⟨⟩ -→ q ′ , q@q ′ → q, q ′ ⟨⟩ -→ q ′ , q ′ @q ′ → q ′ } ∪{q ′ a -→ q ′ , q a -→ q | a ∈ Σ} q q ′ ⟨⟩ ⟨⟩ a ∈ Σ q ′ q ′ a ∈ Σ
In the example Sha ↓ in Fig. 2 Π is a subhedge projection state with witness Π, but also the states 3 ′ , 4, and 2 ′′ are subhedge projection states with witness Π. Note that only inclusion holds for the latter but not equality since this automaton is not complete.

For complete Sha ↓ s A, the above set must be equal to the set of transition rules of ∆ with q or q ′ on the leftmost position. In the soundness expressed in Proposition 4, completeness will be assumed and the proof relies on it. In the examples, however, we will consider automata that are not complete. Still they are "sufficiently complete" to illustrate the constructions.

Note that a subhedge projection state q may be equal to its witness q ′ . Therefore the witness q ′ of any subhedge projection state is itself a subhedge projection state with witness q ′ . Let P ⊆ Q be a subset of subhedge projection states of ∆. We define the transition relation with projection h -→ P ⊆ Q × Q with respect to ∆ such that for all hedges h, h ′ ∈ H Σ and letters a ∈ Σ:

q ∈ P q h -→ P q wrt ∆ q ̸ ∈ P q a -→ q ′ in ∆ q a -→ P q ′ wrt ∆ q ̸ ∈ P q ε -→ P q wrt ∆ q ̸ ∈ P q h -→ P q ′ wrt ∆ q ′ h ′ -→ P q ′′ wrt ∆ q h•h ′ --→ P q ′′ wrt ∆ q ̸ ∈ P q ⟨⟩ -→ p in ∆ p h -→ P p ′ q@p ′ → q ′ in ∆ q ⟨h⟩ --→ P q ′′ wrt ∆
Transitions with respect to P stay in states q ∈ P until the end of the current subhedge is reached. This is correct if p is a subhedge projection state since transitions without subhedge projection don't change state p nor if the run is not blocking.

Proposition 4. Let A = (Σ, Q, ∆, I, F ) be a complete Sha ↓ and P a subset of subhedge projection states for ∆. Then for all hedges h ∈ H Σ and states q, q ′ ∈ Q:

q h -→ q ′ wrt ∆ iff q h -→ P q ′ wrt ∆.
For any subset Q ⊆ Q and hedge h ∈ H Σ , we define the in-memory evaluation with subhedge projection:

h P (Q) = {q ′ ∈ Q | q h -→ P q ′ wrt
∆, q ∈ Q}. An inmemory membership tester for h ∈ L(A) with subtree projection can be obtained by computing h P (I) and testing whether it contains some state in F .

Compiling SHAs to SHA ↓ s with Projection States

We show how to compile any Sha to some Sha ↓ with subhedge projection states, yielding an evaluator with appropriate subhedge projection for the Sha via the Sha ↓ . This compiler is the most original contribution of the paper.

Let A = (Σ, Q, ∆, I, F ) be a Sha. For any set Q ⊆ Q we define the set

acc ∆ (Q) = {q ′ ∈ Q | ∃ q ∈ Q, h ∈ H Σ . q h -→ q ′ wrt
∆}. We note that acc ∆ (Q) can be computed in linear time in the size of ∆. We define:

safe ∆ (Q) = {q ∈ Q | acc ∆ ({q}) ⊆ Q}
If A is complete and deterministic then safety can be used to characterize universal states, since for all q ∈ Q: L(A[I/{q}]) = H Σ if and only if q ∈ safe ∆ (F ). See Lemma 5 of [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF]. Note that safe ∆ (Q) can be computed in linear time in the size of ∆. We define the set of states that may no more change by:

no-change ∆ = {q | q ∈ safe ∆ ({q})}
Note that q ∈ no-change ∆ if and only if acc ∆ ({q}) ⊆ {q}. In the example automaton from Fig. 1 we have no-change ∆ = {2, 3, 4}. For any state q ∈ Q and subset of states Q ⊆ Q we define:

s-down ∆ (q, Q) = safe ∆ ({p ∈ Q | q@ ∆ p ⊆ Q}) s-no-change ∆ (q) = s-down ∆ (q, {q})
A state belongs to s-down ∆ (q, Q) if it can either no more change or if all accessible states p satisfy that q@ ∆ p ⊆ Q.

We next compile the Sha A to a

Sha ↓ A π = (Σ, Q π , ∆ π , I π , F π ).
For this let Π be a fresh symbol and consider the state set:

Q π = {Π} ⊎ (Q × 2 Q )
A pair (q, P ) means that the evaluator in state q may project subhedges if q ∈ P since these will no more lead to any relevant change. The sets of initial and final states are defined as follows:

I π = {(q, ∅) | q ∈ I} F π = {(q, ∅) | q ∈ F }
How to generated the transition rules of A π from those of A is described in Fig. 6. When applied to the Sha in Fig. 1 for [self::list][child::item], the construction yields the Sha ↓ in Fig. 7 which is indeed equal to the Sha ↓ from Fig. 2 up to state renaming. When run on the hedge ⟨list

• ⟨list • h 1 ⟩ • ⟨item • h 2 ⟩⟩
as shown in Fig. 4, it does not have to visit the subhedges h 1 nor h 2 , since all of them will be reached starting from the projection state Π.

Proposition 5 (Soundness). L(A π ) = L(A) for any complete Sha A.

We have to prove that no more changing states q ∈ P ∪ no-change ∆ is sound. If q ∈ no-change ∆ this follows from the completeness of ∆, so that one can neither block nor change the state. In the case q ∈ P , the intuition is that the state on level above -say r -can no more change, since then P = s-no-change ∆ (r). Neither can the automaton block by completeness. The projecting in-memory evaluator of A π will be more efficient than that the nonprojecting evaluator of A. Note, however, that the size of A π may be exponentially bigger than that of A. Therefore, for evaluating a dSha A with subhedge projection on a given hedge h, we create only the needed part of A π on the fly. This part has size O(|h|) and can be computed in time O(|A| |h|), so the exponential preprocessing time is avoid. Example 6. In order to see how the exponential worst case may happen, we consider a family of regular languages, for which the minimal left-to-right Dfa is exponentially bigger than the minimal right-to-left Dfa. The classical example languages with this property are L n = Σ * .a.Σ n where n ∈ N and Σ = {a, b}. Intuitively, a word in Σ * belongs to L n if and only its n + 1-th letter from the end is equal to "a". The minimal left-to-right Dfa for L n has 2 n+1 many states, since needs to memoize a window of n + 1-letters. In contrast, its minimal rightto-left Dfa has only n + 1 states; in this direction, it is sufficient to memoize the distance from the end modulo n + 1.

q a -→ q ′ in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P ) a -→ (q ′ , P ) in ∆ π q ∈ P ∪ no-change ∆ (q, P ) a -→ (q, P ) in ∆ π ⟨⟩ -→ q ′ in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P ) ⟨⟩ -→ (q ′ , s-no-change ∆ (q)) in ∆ π q ∈ P ∪ no-change ∆ (q, P ) ⟨⟩ -→ Π in ∆ π q@p → q ′ in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P )@(p, s-no-change ∆ (q)) → (q ′ , P ) in ∆ π q ∈ P ∪ no-change ∆ (q, P )@Π → (q, P ) in ∆ π a ∈ Σ Π a -→ Π in ∆ π true Π@Π → Π in ∆ π true Π ⟨⟩ -→ Π in ∆ π
We next consider the family of hedge languages H n ∈ H Σ such that each node of h ∈ H n is labeled by one symbol in Σ and so that the sequence of labels of some root-to-leave path of h n belongs to L n . Note that H n can be recognized in a bottom-up manner by the dSha A n with O(n + 1) states, which simulates the minimal deterministic Dfa of L n on all paths of the input hedge. For an evaluator with subhedge projection the situation is different. When moving topdown, it needs to memoize the sequence of labels of the n + 1-last ancestors, possibly filled with b ′ s, and there a 2 n+1 such sequences. If for some leaf, its sequence starts with an "a" then the following subhedges with the following leaves can be projected away. As a consequence, there cannot be any Sha ↓ recognizing H n that projects away all irrelevant subhedges with less than 2 n+1 states. In particular, the size of A π n must be exponential in the size of A n . 6 Streaming Evaluators for SHA ↓ s

Any Sha ↓ yields a visibly pushdown machine [START_REF] Kumar | Visibly pushdown automata for streaming XML[END_REF] that evaluates nested words in a streaming manner. The same property was already noticed for Neumann and Seidl's pushdown forest automata [START_REF] Gauwin | Streaming tree automata[END_REF]. Let A = (Σ, Q, ∆, q init , F ) be a Sha ↓ . A configuration of the corresponding visibly pushdown machine is a pair in K = Q×Q * containing a state and a stack of states. For any word v ∈ Σ * we define the transition relation of the visibly pushdown machine v -→ str ⊆ K × K such that for all q, q ′ ∈ Q and σ ∈ Q * : true

(q, σ) ε -→ str (q, σ) wrt ∆ (q, σ) v -→ str (q ′ , σ) (q ′ , σ) v ′ -→ str (q ′′ , σ) wrt ∆ (q, σ) v•v ′ --→ str (q ′′ , σ) wrt ∆ q a -→ q ′ in ∆ q a -→ str q ′ wrt ∆ q ⟨⟩ -→ q ′ in ∆ (q, σ) ⟨ - → str (q ′ , σ • q) wrt ∆ q@p → q ′ in ∆ (p, σ • q) ⟩ - → str (q ′ , σ) wrt ∆
The same visibly pushdown machine can be obtained by compiling the Sha to an Nwa. In analogy to Theorem 4 of [START_REF] Gauwin | Streaming tree automata[END_REF], we can show for any hedge h that the streaming transition relation

nw (h) ----→ str wrt ∆ is correct for its in-memory transition relation h -→ wrt ∆: Proposition 7. L(A) = {h ∈ H Σ | (q, ε) nw (h) ----→ str (q ′ , ε) wrt ∆, q ∈ I, q ′ ∈ F }.
Any nested word v ∈ Σ * can be evaluated in streaming mode on any subset of configurations K ⊆ K: v str (K) = {(q ′ , σ ′ ) | (q, σ) v -→ str (q ′ , σ ′ ) wrt ∆, (q, σ) ∈ K}. So any hedge can be evaluated in streaming mode by computing nw (h) str (I× {ε}). The hedge is accepted if it can reach some final configuration in F × {ε}.

Going one step further, we show how to enhance the streaming evaluator of an Sha ↓ with subhedge projection, in analogy to the in-memory evaluator. This approach yields a similar result in a more direct manner, as obtained by mapping Sha ↓ s to Nwas, identifying subtree projection states there, and mapping Nwas with subtree projection states to projecting Nwas [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF].

Let P ⊆ Q be the subset of subhedge projection states of ∆. We define a transition relation with subhedge projection h -→ str P ⊆ K × K with respect to ∆ such that for all nested words v, v ′ ∈ N Σ , letters a ∈ Σ, states p, q, q ′ , q ′′ ∈ Q and stacks σ, σ ′ , σ ′′ ∈ Q * :

q ∈ P (q, σ) v -→ str P (q, σ) wrt ∆ q ̸ ∈ P q a -→ q ′ in ∆ (q, σ) a -→ str P (q ′ , σ) wrt ∆ q ̸ ∈ P q ε -→ str P q wrt ∆ q ̸ ∈ P (q, σ) v -→ str P (q ′ , σ ′ ) wrt ∆ (q ′ , σ ′ ) v ′ -→ str P (q ′′ , σ ′′ ) wrt ∆ (q, σ) v•v ′ --→ str P (q ′′ , σ ′′ ) wrt ∆ q ̸ ∈ P q ⟨⟩ -→ q ′ in ∆ (q, σ) ⟨ - → str P (q ′ , σ • q) wrt ∆ p ̸ ∈ P q@p → q ′ in ∆ (p, σ • q) ⟩ - → str P (q ′ , σ) wrt ∆
The projecting transition relation stays in a configuration with a projection state until the end of the current subhedge is reached. This is correct since the state of the non-projecting transition relation would not change the state either, while the visible stack comes back to its original value after the evaluation of a nested word (that by definition is well-nested).

Proposition 8. Let v be a word in Σ * , ∆ a set of transition rules of a complete Sha ↓ with state set Q, q ∈ Q a state and σ ∈ Q * a stack. For any subset P ⊆ Q of subhedge projection states of ∆:

(q, σ) v -→ str (q ′ , σ ′ ) wrt ∆ iff (q, σ) v -→ str P (q ′ , σ ′ ) wrt ∆.
For any subset K ⊆ K and nested word v ∈ N Σ we define the streaming evaluation with subhedge projection:

v str P (K) = {(q ′ , σ ′ ) | (q, σ) v -→ str P (q ′ , σ ′ ) wrt ∆, (q, σ) ∈ K}
A streaming membership tester for h ∈ L(A) with subtree projection can be obtained by computing nw (h) str P (I ×{ε}) and testing whether it contains some state in F × {ε}.

Earliest Membership with Subhedge Projection

We next enhance our compiler from Shas to Sha ↓ s for introducing subtree projection such that it can take safe rejection and safe selection into account. The streaming version for deterministic Shas leads us to an earliest membership tester, which enhances the previous earliest membership tester for dShas from [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF] with subtree projection.

The idea is as follows: A state is called safe for rejection if whenever the evaluator reaches this state on some subhedge then it can safely reject the hedge independently of the parts that were not yet evaluated. In analogy, a state is safe for selection if whenever the evaluator reaches this state for some subhedge, the full hedge will be accepted.

Consider a dSha A = (Σ, Q, ∆, I, F ). The states of our dSha ↓ will contain tuples (q, Q, R, S) stating that the evaluator is in state q, that the states in Q are safe no-changes, the states in R are safe for rejection, and the states in S safe for selection. State changes are relevant only if they are not safe for no-change, rejection or selection. Let sel be a fresh symbols beside of Π.

We next compile the given Sha A to a Sha ↓ A π e = (Σ, Q π e , ∆ π e , I π e , F π e ). We start with set set of states that are safe for selection S 0 = safe ∆ (F ) and respectively safe for rejection R 0 = safe ∆ (Q \ F ). The state sets of A π e are then:

Q π e = (Q × 2 Q × 2 Q × 2 Q ) ∪ {Π, sel } I π e = {(q, ∅, R 0 , S 0 ) | q ∈ I, q ̸ ∈ R 0 ∪ S 0 } ∪ {sel | I ∩ S 0 ̸ = ∅} F π e = {(q, ∅, R 0 , S 0 ) | q ∈ F } ∪ {sel }
The transition rules in ∆ π e are given by the in Fig. 8. For illustration, reconsider the dSha from Fig. 1. However, it is not sufficiently complete to obtain the expected results. The problem is that s-down ∆ (0, {4}) = {0, 1, 2, 3, 4} there, but only the states 3 is really safe for selection one level down. We therefore add a sink state to it -that we call 5 -yielding the dSha ↓ in Fig. ??. For this dSha, which is still not complete but complete for the intended schema µX.⟨(item+list)•X * ⟩ * . We then get s-down ∆ (0, {4}) = {3, 4}. I may seem counter intuitive that note only state 3 but also state 4 down remains safe for selection. This reflects the fact that no proper subhedge of any hedge satisfying the intended schema may ever get into state 4. Applying the earliest construction with safe-no-change projection to dSha in Fig. ?? yields the dSha ↓ in Fig. 9. This automaton is the best dSha ↓ that we could hope for the XPath filter [self::list][child::item], enabling earliest query answering with earliest rejection and perfect subhedge projection.

Running the Sha ↓ s A π e in streaming mode with subtree projection yields an earliest membership tester for dShas with subtree projection. A single adaptations are in order. Whenever the safe selection state sel is reached, the evaluation can be stopped and the input hedge on the stream is accepted. Theorem 1. Let A = (Σ, Q, ∆, I, F ) and P the set of its projection states of ∆ π e with witness either sel or Π. For any hedge h ∈ H Σ with h (I) ̸ = ∅ wrt ∆ (q, P ) a -→ (q ′ , P ) in ∆ π q ′ ̸ ∈ S ∪ R (q, P, S, R) a -→ (q ′ , P, S, R) in ∆ π e (q, P ) ⟨⟩ -→ (q ′ , P ′ ) in ∆ π q ′ ̸ ∈ S ∪ R (q, P, S, R) ⟨⟩ -→ (q ′ , P ′ , s-down ∆ (q, S), s-down ∆ (q, R)) in ∆ π e (q, P )@(p, P ′ ) → (q ′ , P ) in ∆ π q ′ ̸ ∈ S ∪ R (q, P, S, R)@(p, P ′ , s-down ∆ (q, S), s-down ∆ (q, R)) → (q ′ , P, S, R) in ∆ π e (q, P )@Π → (q, P ) in ∆ π q ′ ̸ ∈ S ∪ R (q, P, S, R)@Π → (q, P, S, R) in ∆ π e (q, P ) a -→ (q ′ , P ) in ∆ π q ′ ∈ S (q, P, S, R)

a -→ sel in ∆ π e (q, P ) ⟨⟩ -→ (q ′ , P ) in ∆ π q ′ ∈ S (q, P, S, R) ⟨⟩ -→ sel in ∆ π e
(q, P )@(p, P ′ ) → (q ′ , P ) in ∆ π q ′ ∈ S (q, P, S, R)@(p, P ′ , s-down ∆ (q, S), s-down ∆ (q, R)) → sel in ∆ π e (q, P )@Π → (q, P ) in

∆ π q ′ ∈ S (q, P, S, R)@Π → sel in ∆ π e a ∈ Σ Π a -→ Π in ∆ π e true Π@Π → Π in ∆ π e true Π ⟨⟩ -→ Π in ∆ π e a ∈ Σ sel a -→ sel in ∆ π e µ ∈ Q π e sel @µ → sel in ∆ π e µ ∈ Q π e µ@sel → sel in ∆ π e true sel ⟨⟩ -→ sel in ∆ π e
Fig. 8: The transition rules of the Sha ↓ A π e inferred from those of the Sha A.

the streaming evaluation nw (h) str P (I π e ) with respect to ∆ π e checks membership h ∈ L(A) at the earliest event when streaming nw (h).

The hedge h is accepted once the evaluator reaches state sel . It this doesn't happend online, the truth value of q ∈ F is returned where q is the state in the final tuple.

Proof (sketch). Let P ′ be the set of projection states of A that use state sel as witness (but not state Π). We obtain an streaming membership tester with earliest selection and earliest rejection (but no safe-no-change subhedge projection) by computing: h str P ′ (I π e ) wrt. ∆ π e Earliest selection is detected by reaching the state sel , while earliest rejection happens when the run fails. We notice that this algorithm is basically the same as the earliest membership tester from Proposition 6 of [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF], except that it also check for safe rejection. The fact that nested word automata are used there instead of Sha ↓ s here is not essential. So we can rely on the definitions of earliest membership testing and the result given there. In order to add safe-no-change subtree projection, we consider the set of all projection state P of ∆ π e whose witnesses are either Π or sel . We then compute: h str P (I π e ) wrt. ∆ π e . The difference is that the evaluator based on P does also ignore subtrees that go to safe-no-change projection states. Clearly, this does not affect earliest selection nor earliest rejection, so we still have an earliest membership tester, but now safe-no-change subtree projection is added.

Experimental Evaluation

We integrated subhedge projection into the earliest query answering tool AStream [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF]. It is implemented in Scala while computing safety with ABC Datalog.

In order to benchmark AStream 2.01 with subhedge projection for efficiency, and to compare it to AStream 1.01 without projection, we considered the regular XPath queries from the XPathMark [START_REF] Franceschet | Xpathmark performance test[END_REF] A1-A8. We used the deterministic Shas for all these XPath queries constructed by the compiler from [START_REF] Niehren | Determinization and minimization of automata for nested words revisited[END_REF]. These were evaluated on Xml documents of variable size created by the XPathMark generator. We did further experiments on a sub-corpus of 79 regular XPath queries extracted by Lick and Schmitz from real-world Xslt and XQuery programs, for which dShas are available [START_REF] Serhali | A Benchmark Collection of Deterministic Automata for XPath Queries[END_REF]. These experiments confirm the results presented here, so we don't describe them in detail.

The XPath queries of the XPathMark without descendant axis are A1,A4 and A6-A8. The evaluation time on these queries a 1.2 GB document are reduced between 88 -97%. In average, it is 92.5%, so the overall time is divided by 12. While the parsing time remains unchanged the gain on the automaton evaluation time is proportional to the percentage of subhedge projection for the respective query. This remains true for the other queries with the descendant axis, just that the projection percentage is much lower.

Finally, we compared AStream with for QuiXPath [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF], the best previous streaming tool that can answer A1-A8 in an earliest manner. QuiXPath compiles regular XPath queries to possibly nondeterministic early Nwas, and evaluates them with subtree and descendant projection [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF]. QuiXPath is not generally earliest though. On the queries without descendant axis, AStream 1.01 without projection is by a factor of 60 slower than QuiXPath [START_REF] Serhali | Earliest query answering for deterministic stepwise hedge automata[END_REF]. With subhedge projection in version 2.01, the overhead goes down to a factor of 5 = 60/12. So our current implementation is close to becoming competitive with the best existing streaming tool while guaranteeing earliest query answering in addition.

Conclusion and Future Work

We developed evaluators with subhedge projection for Shas in in-memory mode and in streaming mode. One difficulty was how to push the needed finite state information for subtree projection top-down given that Shas operate bottom-up. We solved it based on a compiler from Shas to downward Shas. This compiler propagates safety information about non-changing states, similar to the propagation of safety information proposed for earliest query answering for dSha queries on nested word streams. We confirmed the usefulness of our novel subhedge projection algorithm for Shas experimentally. We showed that it can indeed speed up the best previously existing earliest query answering algorithm for dSha queries on nested word streams, as needed for answering regular XPath queries on Xml streams. In future work, we plan to improve on subhedge projection for Shas with descendant projection for Shas and to use it for efficient stream processing. Another question is whether and how to obtain completeness results for subhedge projection.

A Proofs for Section 4 (Downward Stepwise Hedge

Automata (SHA ↓ s))

Proposition 4. Let A = (Σ, Q, ∆, I, F ) be a complete Sha ↓ and P a subset of subhedge projection states for ∆. Then for all hedges h ∈ H Σ and states q, q ′ ∈ Q:

q h -→ q ′ wrt ∆ iff q h -→ P q ′ wrt ∆.
Proof. If q ̸ ∈ P, then for any p ∈ Q, q h -→ p wrt ∆ iff q h -→ P p wrt ∆ by definition of the projecting transition relation. If q ∈ P then p is a subhedge projection state of ∆, so the set of transition rules of ∆ containing q ′ or with q on the leftmost position are included in the following:

q q ′ ⟨⟩ ⟨⟩ a ∈ Σ q ′ q ′ a ∈ Σ
Since ∆ is complete, equality holds. Hence for any hedge h ∈ H Σ it holds that q h -→ q wrt ∆ while q ̸ h -→ p wrt ∆ for all p ̸ = q. The projecting transition relation does the same: q h -→ P q wrt ∆ while q ̸ h -→ P p wrt ∆ for all p ̸ = q. Related Work. We can convert any dSha ↓ A into an equivalent Sha elim ↓ (A) as follows.

I elim ↓ = Q × I F elim ↓ = Q × F q ⟨⟩ -→ q ′ in ∆ ⟨⟩ -→ (q, q ′ ) in ∆ elim ↓ q a -→ q ′ in ∆ r ∈ Q (q, r) a -→ (q ′ , r) in ∆ elim ↓ q@p → q ′ in ∆ r ∈ Q (q, r)@(p, q) → (q ′ , r) in ∆ elim ↓ Proposition 9. L(A) = L(elim ↓ (A)).
Proof. The construction is analogous to the conversion of Nwas to Shas [START_REF] Niehren | Determinization and minimization of automata for nested words revisited[END_REF] or to hedge automata [START_REF] Gauwin | Streaming tree automata[END_REF]. The correctness proofs for these compilers are standard.

It should be noticed that unique minimization fails for Sha ↓ , as usual for deterministic multiway automata. This even happens for deterministic two-way finite state automata on words. In contrast, the class of dShas with the same initial and tree initial state enjoys unique minimization.

Standard hedge automata [21,5,?,?] have the same expressiveness as Neumann and Seidl's pushdown forest automata [START_REF] Neumann | Locating matches of tree patterns in forests[END_REF] and also as Bojanczyk's forest automata (see Section 3.3 of [?]). Note, however, that there is an exponential difference in succinctness between Shas and Bojanczyk's forest automata. Therefore, these forest automata are of quite different nature from those of Neumann and Seidl.

B Proofs for Section 5 (Compiling SHAs to SHA ↓ s with Projection States)

Proposition 5 (Soundness). L(A π ) = L(A) for any complete Sha A.

Proof. We have to prove that no more changing states q ∈ P ∪ no-change ∆ is sound. If q ∈ no-change ∆ this follows from the completeness of ∆, so that one can neither block nor change the state. In the case q ∈ P , the intuition is that the state on level above -say r -can no more change, since then P = s-no-change ∆ (r). Neither can the automaton block by completeness. We prove the first inclusion L(A) ⊆ L(A π ) based on the following three Claims 5.1a, 5.2a, and 5.3a:

Claim 5.1a. Π h -→ Π wrt ∆ π for all hedges h ∈ H Σ .
The proof is straightforward by induction on the structure of h. It uses the last three transition rules of ∆ π in Fig. 6 permitting to always stay in Π for whatever hedge follows.

Claim 5.2a. For all h ∈ H Σ , q ∈ Q, and P ⊆ Q such that q ∈ P ∪ no-change ∆ :

(q, P ) h -→ (q, P ) wrt ∆ π
We prove Claim 5.2a by induction on the structure of h. Note that the completeness of ∆ will be needed.

Case h = ⟨h ′ ⟩. In this case, we can use Claim 5.1a to show Π h ′ -→ Π wrt ∆ π and the inference rules

q ∈ P ∪ no-change ∆ (q, P ) ⟨⟩ -→ Π in ∆ π
q ∈ P ∪ no-change ∆ (q, P )@Π → (q, P ) in ∆ π in order to close the following diagram with respect to ∆ π :

(q, P ) Π h ′ Π (q, P ) ⟨⟩
This proves (q, P ) h -→ (q, P ) wrt ∆ π as required by the claim. Case h = a. By completeness of ∆ there exists some state q ′ such that q a -→ q ′ in ∆. Since q ∈ P ∪ no-change ∆ we can apply the inference rule:

q ∈ P ∪ no-change ∆ (q, P ) a -→ (q, P ) in ∆ π
This proves this case of the claim.

Case h = ε. We trivially have (q, P ) ε -→ (q, P ) wrt ∆ π .

Case h = h ′ • h ′′ . By induction hypothesis applied to h ′ and h ′′ we have: (q, P ) h ′ -→ (q, P ) and (q, P ) h ′′ --→ (q, P ). Hence (q, P )

h ′ •h ′′ ---→ (q, P ).
This ends the proof of Claim 5.2. The next claim, in which the induction step is a little more tedious to prove, is the key of the soundness proof.

Claim 5.3a. Let h ∈ H Σ a hedge, q, q ′ ∈ Q states and P ⊆ Q a subset of states such that acc ∆ (P ) ⊆ P and q ̸ ∈ P ∪ no-change ∆ . If q h -→ q ′ wrt ∆ then there exists q ′′ such that (q, P ) h -→ (q ′′ , P ) wrt ∆ π and (q ′ = q ′′ or q ′ , q ′′ ∈ P ).

Proof. By induction on the structure of h.

Case h = ⟨h ′ ⟩. The assumption q h -→ q ′ wrt ∆ shows that there exists some state p ∈ Q closing the following diagram:

q ⟨⟩ ∆ h ′ p q ′

⟨⟩

Let P ′ = s-no-change ∆ (q) and note that acc ∆ (P ′ ) ⊆ P ′ . Since q ̸ ∈ P ∪ no-change ∆ we can infer:

⟨⟩ -→ ⟨⟩ ∆ in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P ) ⟨⟩ -→ (⟨⟩ ∆ , P ′ ) in ∆ π q@p → q ′ in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P )@(p, P ′ ) → (q ′ , P ) in ∆ π Subcase ⟨⟩ ∆ ̸ ∈ P ′ ∪ no-change ∆ . The induction hypothesis applies to h ′ yielding that shows that there exists p ′ such that (⟨⟩ ∆ , P ′ ) h ′ -→ (p, P ′ ) wrt ∆ π and p = p ′ ∨ p, p ′ ∈ P . We distinguish the latter two cases: Subsubcase (⟨⟩ ∆ , P ′ ) h ′ -→ (p, P ′ ) wrt ∆ π . We can close the diagram as follows:

(q, P )

(⟨⟩ ∆ , P ′ ) h ′ (p, P ′ ) (q ′ , P ) ⟨⟩
This shows that (q, P ) h -→ (q ′ , P ) wrt ∆ π , so the first disjunct of the claim holds for h. Subsubcase p ∈ P ′ ∧ ∃p ′ ∈ P ′ . (⟨⟩ ∆ , P ′ ) h ′ -→ (p ′ , P ′ ) wrt ∆ π . Since ∆ is complete, there exists a state q ′′ such that q ′′ ∈ q@ ∆ p ′ . Since both p, p ′ ∈ P ′ we have q ′ = q = q ′′ by definition of P ′ = s-no-change ∆ (q). Hence we can close the diagram as follows:

(q, P ) (⟨⟩ ∆ , P ′ ) h ′ (p ′ , P ′ ) (q ′′ , P )

⟨⟩

Since q ′′ = q ′ this shows that (q, P ) h -→ (q ′ , P ) wrt ∆ π , so the first disjunct of the claim holds again.

Subcase ⟨⟩ ∆ ∈ P ′ ∪ no-change ∆ . Claim 5.2a then shows that (⟨⟩ ∆ , P ′ )

h ′ -→ (⟨⟩ ∆ , P ′ ) wrt ∆ π .
Subsubcase ⟨⟩ ∆ ∈ P ′ . Since p ∈ acc ∆ (⟨⟩ ∆ ) and acc ∆ (P ′ ) ⊆ P ′ it follows that p ∈ P ′ too. By definition P ′ = s-no-change ∆ (q) and the completeness of ∆, the memberships ⟨⟩ ∆ ∈ P ′ and p ∈ P ′ imply that q@ ∆ ⟨⟩ ∆ = {q} = q@ ∆ p. We can now close the diagram below as follows:

(q, P )

(⟨⟩ ∆ , P ′ ) h ′ (⟨⟩ ∆ , P ′ ) (q, P ) ⟨⟩ Subsubcase ⟨⟩ ∆ ∈ no-change ∆ .
In this case ⟨⟩ ∆ = p so that q ′ ∈ q@ ∆ ⟨⟩ ∆ . Hence:

(q, P ) (⟨⟩ ∆ , P ′ ) h ′ (p, P ′ ) (q ′ , P )

⟨⟩

Case h = a. Since q ̸ ∈ P ∪ no-change ∆ we can apply the inference rule:

q a -→ q ′ in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P ) a -→ (q ′ , P ) in ∆ π
This shows that (q, P ) h -→ (q ′ , P ), so claim is valid with the first disjunct. Case h = ε. In this case we have q = q ′ and (q, P ) ε -→ (q, P ) so the first property required by the claim holds. Case h = h 1 • h 2 . Since q h -→ q ′ wrt ∆, there exists q 1 ∈ Q such that q h1 -→ q 1 wrt ∆ and q 1 h2 -→ q ′ wrt ∆. Since q ̸ ∈ P ∪no-change ∆ , we apply the induction hypothesis on h 1 . This implies that there exists q ′ 1 such that:

(q, P )

h1 -→ (q ′ 1 , P ) wrt ∆ π ∧ (q 1 = q ′ 1 ∨ q 1 , q ′ 1 ∈ P )
We distinguish the two cases of the disjunction: Subcase q 1 = q ′ 1 . We also distinguish two subcases here:

(q, P )

µ1 h ′ µ ′ 1 µ ⟨⟩
Since q ∈ P ∪ no-change ∆ , the following rule must have been applied to infer (q, P )

⟨⟩ -→ µ 1 wrt ∆ π : q ∈ P ∪ no-change ∆ (q, P ) ⟨⟩ -→ Π in ∆ π
Therefore µ 1 = Π. Claim 5.1b shows that µ ′ 1 = Π too. So µ must have been infered by applying the rule: q ∈ P ∪ no-change ∆ (q, P )@Π → (q, P ) in ∆ π So µ = (q, P ) as required.

Case h = a. The following rule must have been applied:

q ∈ P ∪ no-change ∆ (q, P ) a -→ (q, P ) in ∆ π
Hence, µ = (q, P ). Case h = ε. Obvious. Case h = h 1 • h 2 . There must exist µ 1 such that (q, P )

h1 -→ µ 1 h2 -→ µ wrt ∆ π .
By induction hypothesis applied to h 1 , we have µ 1 = (q, P ). We can thus apply the induction hypothesis to h 2 to obtain µ 2 = (q, P ). This ends the proof of Claim 5.2b. We next need an inverse of Claim 5.3a. Claim 5.3b. Let h ∈ H Σ a hedge, q ∈ Q states and P ⊆ Q a subset of states such that acc ∆ (P ) ⊆ P and q ̸ ∈ P ∪ no-change ∆ . If (q, P ) h -→ µ wrt ∆ π then there exists q ′ , q ′′ such that µ = (q ′ , P ), q h -→ q ′′ wrt ∆ and (q ′ = q ′′ or q ′ , q ′′ ∈ P ).

Proof. Let P ⊆ Q and q ∈ Q such that acc ∆ (P ) ⊆ P and q ̸ ∈ P ∪ no-change ∆ . Assume that (q, P ) h -→ µ wrt ∆ π . We prove by induction on h that there exists q ′ such that µ = (q ′ , P ) and ∃q ′′ . (q ′ = q ′′ ∨ q ′ , q ′′ ∈ P ) ∧ q h -→ q ′′ wrt ∆.

Case h = ⟨h ′ ⟩. By definition of (q, P ) h -→ µ wrt ∆ π there must exist µ 1 , µ ′ 1 ∈ Q π such that the following diagram can be closed:

(q, P ) µ1 h ′ µ ′ 1 µ ⟨⟩
Since q ̸ ∈ P ∪ no-change ∆ , the following inference rule got applied:

⟨⟩ -→ p in ∆ q ̸ ∈ P ∪ no-change ∆ (q, P ) ⟨⟩ -→ (p, s-no-change ∆ (q)) in ∆ π
Let P ′ = s-no-change ∆ (q). Hence there exists p ∈ ⟨⟩ ∆ such that µ 1 = (p, P ′ ). Subcase p ∈ P ′ ∪ no-change ∆ . Subsubcase p ∈ P ′ . Since p ∈ acc ∆ ({p}) and P ′ = s-no-change ∆ (q) we have q@p = {q}. So q = q ′ . Furthermore, by completeness of ∆ there exists p ′ such that p h ′ -→ p ′ wrt ∆. In particular p ′ ∈ acc ∆ ({p}) so by definition of P ′ , it follows that q@p ′ → q wrt ∆. Hence, we can close the following diagram:

q p h ′ p ′ q ⟨⟩ Since q = q ′ this shows that q ⟨h ′ ⟩ --→ q ′ wrt ∆. Subsubcase p ∈ no-change ∆ . By completeness of ∆ there exists p ′ such that p h ′ -→ p ′ wrt ∆. Since p ∈ no-change ∆ it follows that p ′ = p.
Hence, we can close the following diagram:

q p h ′ p q ′ ⟨⟩
This shows that q ⟨h ′ ⟩ --→ q ′ wrt ∆. Subcase p ̸ ∈ P ′ ∪ no-change ∆ . By induction hypothesis, there exists p ′ , p ′′ such that µ ′ 1 = (p ′ , P ′ ), p h ′ -→ p ′′ wrt ∆, and (p ′ = p ′′ or p ′ , p ′′ ∈ P ′ . By completeness of ∆ there exist q ′′ ∈ q@ ∆ p ′′ and q ′ ∈ q@ ∆ p ′ . Subsubcase p ′ = p ′′ . Hence, we have:

q p h ′ p ′ q ′ ⟨⟩ This shows q ⟨h ′ ⟩
--→ q ′ wrt ∆. Subsubcase p ′ , p ′′ ∈ P . By definition of P ′ it follows that q ′ = q = q ′′ . Hence:

q p h ′ p ′′ q ⟨⟩ h2
-→ µ wrt ∆ π and q ′′ 1 ∈ P . Claim 5.2b shows that µ = (q ′′ 1 , P ) wrt ∆ π . We also have q h1 -→ q ′′ 1 wrt ∆. By completeness of ∆, there exist a state q ′′ such that q ′′ 1 h -→ q ′′ wrt ∆. Since q ′ 1 ∈ P and P is closed by accessibility, we have q ′′ ∈ acc({q ′′ 1 }) ⊆ acc(P ) ⊆ P . From q h1 -→ q ′′ 1 wrt ∆, we get q h -→ q ′′ wrt ∆. The claim follows since q ′′ 1 , q ′′ ∈ P . This ends the proof of Claim 5.3b.

Proof of inclusion L(A π ) ⊆ L(A).

Let h ∈ L(A π ). Then there exists q 0 ∈ I and q ∈ F such that (q 0 , ∅) h -→ (q, ∅) wrt ∆ π . We distinguish two cases:

Case q 0 ∈ no-change ∆ . Claim 5.2b shows that q = q 0 . Claim 5.2a proves that q 0 h -→ q 0 wrt ∆. Hence q 0 h -→ q wrt ∆ and thus h ∈ L(A). Case q 0 ̸ ∈ no-change ∆ . Claim 5.3b with P = ∅ shows that q 0 h -→ q wrt ∆ π and hence h ∈ L(A π ). This end the proof of the inverse inclusion, and thus of L(A) = L(A π ).

C Proofs for Section 6 (Streaming Evaluators for SHA ↓ s)

Proposition 7. L(A) = {h ∈ H Σ | (q, ε) nw (h) ----→ str (q ′ , ε) wrt ∆, q ∈ I, q ′ ∈ F }.
Proof. Straightforward. Proposition 8. Let v be a word in Σ * , ∆ a set of transition rules of a complete Sha ↓ with state set Q, q ∈ Q a state and σ ∈ Q * a stack. For any subset P ⊆ Q of subhedge projection states of ∆:

(q, σ) v -→ str (q ′ , σ ′ ) wrt ∆ iff (q, σ) v -→ str P (q ′ , σ ′ ) wrt ∆.
Proof. Analogous to the proof of Proposition 4, i.e., the soundness of the inmemory evaluator with projection for complete Sha ↓ s. Related Work. A streaming evaluator for Sha ↓ s via a visibly pushdown machine can also be obtained by compiling a Sha ↓ to a nested word automaton (Nwa) [?], whose streaming evaluator is given by a visibly pushdown machine [?], previously known as input driven automata [?,?,?]. Definition 10. A nested word automata ( Nwa) is a tuple (Σ, Q, Γ, ∆, I, F ), where Σ, Γ and Q are sets, I, F ⊆ Q, and

∆ = ((a ∆ ) a∈Σ , ⟨ ∆ , ⟩ ∆ ) contains relations: a ∆ ⊆ Q × Q, ⟨ ∆ ⊆ Q × (Γ × Q) and ⟩ ∆ : Q × Γ × Q.
A Nwa is deterministic or equivalently a d Nwa if I contains at most one element and all above relations are partial functions.

The elements of Γ are called stack symbols. The transition rules in ∆ again have three forms: Internal rules q a -→ q ′ as for Shas, opening rules q ⟨↓γ --→ q ′ if ⟨ ∆ (q) = (q ′ , γ) and closing rules q ⟩↑γ --→ q ′ if ⟩ ∆ (q, γ) = q ′ . The streaming evaluator for Nwas can be seen as pushdown machines for evaluating the nested words of hedges in streaming manner. A configuration of the pushdown machine is a pair in K = Q × Γ * containing a state and a stack. For any word v ∈ Σ * we define a streaming transition relation v -→ str ⊆ K × K such that for all q, q ′ ∈ Q and S ∈ Γ * : true (q, S) ε -→ str (q, S) wrt ∆ (q, S) v -→ str (q ′ , S) (q ′ , S) v ′ -→ str (q ′′ , S) wrt ∆ (q, S)

v•v ′ --→ str (q ′′ , S) wrt ∆ q a -→ q ′ in ∆ q a -→ str q ′ wrt ∆ q ⟨↓γ --→ q ′ in ∆ (q, S) ⟨ - → str (q ′ , S) wrt ∆ q ⟩↑γ --→ q ′ in ∆ (q, S • γ) ⟩ - → str (q ′ , S) wrt ∆
For any dSha ↓ A = (Σ, Q, ∆, I, F ) we can define the dNwa A nwa = (Σ, Q, Γ, ∆ nwa , I nwa , F nwa ) such that Γ = Q, while ∆ nwa contains for all a ∈ Σ and q, p ∈ Q the transition rules: q a -→ q ′ in ∆ q a -→ q ′ in ∆ nwa q ⟨⟩ -→ q ′ in ∆ q ⟨↓q --→ q in ∆ nwa p@q → q ′ in ∆ q ⟩↑p --→ q ′ in ∆ nwa Lemma 11. L(A nwa ) = L(A).

The runs of Sha ↓ s A and Nwas A nwa can be identified. Projecting evaluators for Nwas were proposed in the context of projecting Nwas [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF]. They are based on the following notion of states of irrelevant subtrees for Nwas.

Definition 12 (Variant of Definition 3 of [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF]). We call a state q of an Nwa a state of irrelevant subtrees if there exist two different stack symbols γ, γ ′ and a state q ′ such that the transitions shown on the right exist, but no further opening transitions with γ, no further transitions with γ ′ , and no further closing transition in q popping γ. In this case, we write q ∈ i-tree Σ\∅ .

q q ′ ⟨ ↓ γ ⟩ ↑ γ ⟨ ↓ γ ′ ⟩ ↑ γ ′ a ∈ Σ
Lemma 13. Any subhedge projection state of a complete Sha ↓ A is a state of irrelevant subtrees of A nwa .

It was then shown in [START_REF] Sebastian | Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams[END_REF] how to map an Nwa with a subset P of states of irrelevant subtrees to a projecting Nwa, whose streaming semantics yields a streaming evaluator with subhedge projection. The presentation of subhedge projection for Sha ↓ s without passing via Nwas yields the same result in a more direct manner.

It should also be notice that projecting Nwas support descendant projection beside of subhedge projection. For Shas this is left to future research.

D Proofs for Section 7 (Earliest Membership with

Subhedge Projection) Lemma 14. Let P be a subset of projection states of ∆ π e . For any hedge h and prefix v of nw (h), state q ∈ Q, state sets Q, R, S ⊆ Q, and stack σ ∈ Q * : if (I π e , ε) π e v -→ str P ((q, Q, R, S), σ) wrt. ∆ π e and q ∈ S then h ∈ L(A).

E Proofs for Section 8 (Experimental Evaluation)

Fig. 1 :

 1 Fig. 1: A unique minimal deterministic Sha (with initial state equal tree initial state) for the XPath filter [self::list][child::item].

Fig. 2 :

 2 Fig. 2: The deterministic Sha ↓ with subhedge projection state Π obtained by our compiler.

Fig. 3 :

 3 Fig. 3: A successful run of the Sha in Fig. 1 on ⟨list • ⟨item⟩⟩.

Fig. 6 :

 6 Fig.6: The transition rules of the Sha ↓ A π inferred from those of the Sha A.

Fig. 7 :

 7 Fig. 7: The dSha ↓ A π constructed from the dSha A in Fig. 1 except for useless state transitions leading out of the schema of our application. Note that no-change ∆ = {2, 3, 4}. It is equal to the Sha ↓ in Fig. 2 up to the state renaming 0 = (0, {}), 0 ′ = (0, {2, 4}), 0 ′′ = (0, {1, 3, 4}), 1 ′ = (1, {2, 4}), 1 ′′ = (1, {1, 3, 4}), 2 ′ = (2, {2, 4}), 2 ′′ = (2, {1, 3, 4}), 3 ′ = (3, {2, 4}), 4 = (4, {}).

Fig. 9 :

 9 Fig. 9: The earliest dSha ↓ A π e with safe-no-change subhedge projection for the the Sha A in Fig. 10 adding sink 5 to the dSha in Fig. 1. The states of A π e correspond to the following tuples: 0 = (0, ∅, {1, 2, 3, 5}, {4}), 0 ′ = (0, ∅, {2, 4, 5}, {3, 4}), 1 ′ = (1, ∅, {2, 4, 5}, {3, 4}), 0 ′′ = (0, {1, 3, 4, 5}, ∅, {2, 4, 5}), and 1 ′′ = (1, {1, 3, 4, 5}, ∅, {2, 4, 5}).

Fig. 10 :

 10 Fig. 10: Adding a sink 5 to the dSha from Fig. 1 for the XPath filter [self::list][child::item].

Table 1 :

 1 XPathMark list of queries.

	Id	XPath Query
	A1:	/site/closed auctions/closed auction/annotation/
		description/text/keyword
	A2:	//closed auction//keyword
	A3:	/site/closed auctions/closed auction//keyword
	A4:	/site/closed auctions/closed auction[annotation/description/
		text/keyword]/date

Table 2 :

 2 Timings in seconds for XPathMark queries that have child axis exclusively with QuiXPath and the two versions of our tool.

		QuiXPath Astream Astream	Gain:	Factor:
			1.01	2.01 Astream2.01 vs QuiXPath/
			nonproj. proj.	Astream1.01 Astream2.01
	A1	11	644.67 72.83	88.7%	*6.62
	A4	11.6	723.03	78.5	89.14%	*6.77
	A6	10.7	780.78 65.26	91.64%	*6.1
	A7	8.6	601.26 24.64	95.9 %	*2.87
	A8	8.8	801.96 24.85	96.9%	*2.82
	average 10.14	710.34	53.2	92.45%	*5.036

Table 3 :

 3 Timings in seconds for XPathMark queries that have descendant axis with QuiXPath and the two versions of our tool.

		QuiXPath Astream Astream	Gain:	Factor:
			1.01	2.01 Astream2.01 vs QuiXPath/
			nonproj. proj.	Astream1.01 Astream2.01
	A2	11.4	569.0112 664.6	-16.8%	*58.3
	A3	11.5	673.716 666.124	1.13%	*57.92
	A5	12	593.4648 77.785	86.89%	*6.48

Subsubcase q 1 ̸ ∈ P . The induction hypothesis applied to h 2 yields: ∃q ′′ .(q 1 , P ) h2 -→ (q ′′ , P ) wrt ∆ π ∧ (q ′ = q ′′ ∨ q ′ , q ′′ ∈ P ) Hence ∃q ′′ . (q, P ) h -→ (q ′′ , P ) wrt ∆ π ∧ (q ′ = q ′′ ∨ q ′ , q ′′ ∈ P ) Subsubcase q 1 ∈ P . By Claim 5.2a, we have (q 1 , P ) h2 -→ (q 1 , P ). We also have q ′ ∈ acc({q 1 }) and since we assume acc(P ) ⊆ P , this implies q ′ ∈ P . Hence (q, P ) h -→ (q 1 , P ) and q ′ , q 1 ∈ P implying the claim with the second disjunct valid. Subcase q 1 , q ′ 1 ∈ P . Since q ′ 1 ∈ P , Claim 5.2a, implies (q ′ 1 , P ) h2 -→ (q ′ 1 , P ) wrt ∆ π . Thus (q, P ) h -→ (q ′ 1 , P ) wrt ∆ π . Since q ′ ∈ acc ∆ ({q 1 }) and q 1 ∈ P it follows that q ′ ∈ acc ∆ (P ) ⊆ P . Here we used as in the previous subsubcase that acc(P ) ⊆ P is assumed by the claim. Let q ′′ = q ′ 1 . Then we have (q, P ) h -→ (q ′′ , P ) wrt ∆ π and q ′ , q ′′ ∈ P showing the claim. This ends the proof of Claim 5.3a.

Proof of inclusion L(A) ⊆ L(A π ). Let h ∈ L(A).

Then there exists q 0 ∈ I and q ∈ F such that q 0 h -→ q. We distinguish two cases:

Case q 0 ∈ no-change ∆ . By definition of no-change ∆ and since q ∈ acc ∆ (q 0 ) we have q 0 = q. Claim 5.2a shows that (q 0 , ∅) h -→ (q 0 , ∅) wrt ∆ π and thus (q 0 , ∅) h -→ (q, ∅) so that h ∈ L(A π ).

Case q 0 ̸ ∈ no-change ∆ . Claim 5.3a with P = ∅ shows that (q 0 , ∅)

This ends the proof of the first inclusion. We next want to show the inverse inclusion L(A π ) ⊆ L(A). It will eventually follow from the following three Claims 5.1b., 5.2b, and 5.3b.

Claim 5.1b. For any hedge h and state

The proof is straightforward by induction on the structure of h: the only transitions rules of ∆ π with Π on the left hand side are inferred by the last three rules in Fig. 6. These require to stay in Π whatever hedge follows.

Claim 5.2b. For any hedge h, set P ⊆ Q, state q ∈ P ∪ no-change ∆ , and state

Proof. By induction on the structure of h. Suppose that (q, P )

This shows q ⟨h ′ ⟩ --→ q wrt ∆. Case h = a. Since q ̸ ∈ P ∪ no-change ∆ , the following inference rule must be used:

-→ µ wrt ∆ π . Since q ̸ ∈ P ∪ no-change ∆ , we can apply the induction hypothesis to h 1 . It shows that there exists q ′ 1 and q ′′ 1 such that µ 1 = (q ′ 1 , P ) and

In this case, we can apply the induction hypothesis to (q ′ 1 , P ) h2 -→ µ wrt ∆ π showing the existence of q ′ such that µ = (q ′ , P ) and ∃q ′′ . q ′ 1 h2 -→ q ′′ ∧ (q ′ = q ′′ ∨ q ′ , q ′′ ∈ P ).

Hence ∃q ′′ . q h -→ q ′′ wrt ∆ ∧ (q ′ = q ′′ ∨ q ′ , q ′′ ∈ P ), so the claim holds.

Subsubcase q ′ 1 ∈ P ∪ no-change ∆ . Claim 5.2b applied to (q ′ 1 , P ) h2 -→ µ wrt ∆ π shows that µ = (q ′ 1 , P ). Subcase q ′ 1 , q ′′ 1 ∈ P . Recall that (q ′′ 1 , P )