Pierre Hellier
email: pierre.hellier@irisa.fr

Pierrick Coupé

Xavier Morandi

D Louis Collins

An automatic geometrical and statistical method to detect acoustic shadows in intraoperative ultrasound brain images

Keywords: 3D ultrasound, acoustic shadows, reconstruction, registration

In ultrasound images, acoustic shadows appear as regions of low signal intensity linked to boundaries with very high acoustic impedance differences. Acoustic shadows can be viewed either as informative features to detect lesions or calcifications, or as damageable artifacts for image processing tasks such as segmentation, registration or 3D reconstruction. In both cases, the detection of these acoustic shadows is useful. This paper proposes a new method to detect these shadows that combines a geometrical approach to estimate the B-scans shape, followed by a statistical test based on a dedicated modeling of ultrasound image statistics. Results demonstrate that the combined geometrical-statistical technique is more robust and yields better results than the previous statistical technique. Integration of regularization over time further improves robustness. Application of the procedure results in 1) improved 3D reconstructions with fewer artifacts, and 2) reduced mean registration error of tracked intraoperative brain ultrasound images.

Introduction

The image formation process of ultrasound images is bound to the propagation and interaction of waves in tissues of various acoustic impedances [START_REF] Steel | Origins of the edge shadowing artefact in medical ultrasound imaging[END_REF]. More precisely, at the boundary of two materials, the wave energy is transmitted, reflected, dispersed and/or diffracted. If the wave energy is almost totally reflected, this will result in an acoustic shadow in the region of the image beyond the boundary. The motivation for detecting acoustic shadows is twofold. First, the presence of an acoustic shadow reflects the presence of an interface where the acoustic energy was almost completely lost. This is typically an interface tissue/air or tissue/bone. Therefore, acoustic shadows are useful to detect calcifications, gallstones or bone structures, detect lesions [START_REF] Drukker | Computerized analysis of shadowing on breast ultrasound for improved lesion detection[END_REF], discriminate benign tumors [START_REF] Timmerman | Simple ultrasound-based rules for the diagnosis of ovarian cancer[END_REF], predict stability of Peyronie's disease [START_REF] Bekos | The natural history of peyronie's disease: An ultrasonographybased study[END_REF] or diagnosis leiomyoma [START_REF] Caoili | Refractory shadowing from pelvic masses on sonography: A useful diagnostic sign for uterine leiomyomas[END_REF]. Secondly, acoustic shadows might limit the efficiency of image processing techniques like segmentation, registration [START_REF] Leroy | Rigid registration of freehand 3d ultrasound and ct-scan kidney images[END_REF][START_REF] Penney | Registration of freehand 3d ultrasound and magnetic resonance liver images[END_REF] or 3D reconstruction. The automatic processing of ultrasound in a quantitative analysis workflow requires to detect and account for acoustic shadows. This paper will focus on the impact of shadow estimation on image processing tasks and more precisely on 3D reconstruction and 3D registration of ultrasound intraoperative data.

Related work

Only a few papers have presented automatic methods to detect acoustic shadows. Methods can be broadly sorted in two groups: intensity-based methods [START_REF] Drukker | Computerized analysis of shadowing on breast ultrasound for improved lesion detection[END_REF][START_REF] Madabhushi | Distinguishing Lesions from Posterior Acoustic Shadowing in Breast Ultrasound via Non-Linear Dimensionality Reduction[END_REF] and geometric methods [START_REF] Leroy | Rigid registration of freehand 3d ultrasound and ct-scan kidney images[END_REF][START_REF] Penney | Registration of freehand 3d ultrasound and magnetic resonance liver images[END_REF]. Intensity-based methods rely on a direct analysis of the intensities to detect dark regions. Madabhusi et al. [START_REF] Madabhushi | Distinguishing Lesions from Posterior Acoustic Shadowing in Breast Ultrasound via Non-Linear Dimensionality Reduction[END_REF] describe a method that combines a feature space extraction, manual training and classification to discriminate lesions from posterior acoustic shadowing. Drukker et al. [START_REF] Drukker | Computerized analysis of shadowing on breast ultrasound for improved lesion detection[END_REF] use a threshold on a local skewness map to detect shadows. Geometric methods take into account the probe's geometry and analyze intensity profiles along the lines that compose the B-scan. Leroy et al. [START_REF] Leroy | Rigid registration of freehand 3d ultrasound and ct-scan kidney images[END_REF] fit an heuristic exponential function to determine whether a shadow occurred, while Penney et al. [START_REF] Penney | Registration of freehand 3d ultrasound and magnetic resonance liver images[END_REF] manually estimate the image mask to determine dark areas.

The method proposed in this paper is a hybrid method combining a geometrical approach with a modeling of ultrasound image statistics. Contrary to previous papers, the image mask, the probe geometry and the statistical detection threshold are estimated automatically. Rather than fitting heuristic function to detect shadows, a statistical analysis is performed along each transducer line to detect potential shadows regions. These ruptures (or breaks) along the intensity profiles are tested as potential shadow boundary with a statistical test based on a noise model estimation.

Method

Overview

The shadow detection procedure consists of two phases. Since the presence of acoustic shadows is bound to the geometry of the probe and to the propagation of the signal along the lines that compose the B-scan, it is necessary to estimate the probe's shape in the first phase. The probe's shape is related to the probe geometry (linear, curvilinear) and corresponds to the image mask in the Bscans (see figure 1-a). Then, in a second phase, a signal analysis is performed along the lines that compose the B-scan. An acoustic shadow is detected along a line when two criteria are met:

(1) A rupture along a line exists and (2) The signal distribution after the rupture is statistically compliant with an estimated noise model.

B-scan geometry extraction

Given a sequence of 2D ultrasound images (see a typical image in figure 1-(a)), it is necessary to separate the image and the background. In many cases, the geometry (e.g., fan vs linear) will be known a priori, it will be possible to use a precomputed mask and this step of the procedure can be skipped. However, when this is not the case, estimating the mask amount to computing a 2D mask given the 2D + t sequence. To do so, maps of longitudinal mean and variance are computed, and multiplied pixelwise to compute a feature map. For a given point, the longitudinal mean (respectively variance) is defined as the mean (respectively variance) of a 2D pixel location over time. Background pixels are dark and have low (or zero) variance. Points in the image foreground have the highest values of the feature map (compared to the background). Then, points with the highest values of the feature map are retained (see figure 1-(b)). Some false detections exist, mainly due to textual data and complementary image information presented on the ultrasound machine display. Therefore, a morphological closing and opening are performed to clean the input mask (see figure 1-(c)). To estimate the probe geometry, a trapezoid model is fitted to the input mask. The trapezoid model is the simplest model capable of capturing the geometry of a linear or curvilinear probe. The 5 parameters of the model are estimated by optimizing the total performance measure φ (see figure 1-(d)) that is defined as:

φ = T P + T N T P + T N + F P + F N ′ (1)
where T P is the number of true positives (point being in the mask and in the trapezoid), T N the number of true negatives (point being neither the mask nor in the trapezoid), F P the number of false positives (point not being in the mask but in the trapezoid) and F N the number of false negatives (point being in the mask but not in the trapezoid). With the symmetry hypothesis, the number of parameters is reduced to 4 and they are estimated within a simplex optimization. Thus the final shape will share as many points as possible with the mask, while maintaining the trapezoidal constraint.

For the model estimation, accuracy is needed for the extremal lines of the trapezoid. The extremal lines are the extreme right and extreme left lines that encompass the B-scans. Actually, these extremal lines are the most important features in the method, since they define the line profiles that will be triggered. Several experiments were conducted with three different acquisition systems (various video acquisition cards and echographic machines) and demonstrated that the method performs robustly in all tested cases. The mask in 1-(c) is used to determine which data will be analyzed for possible shadows, while the trapezoid in 1-(d) is used to determine the geometry of the US transducer lines (rays).

Line rupture detection

Once the probe's geometry is estimated, it is possible to know whether the direction of scanning is top-down or bottom-up when a curvilinear probe is used. For a linear probe, the user must specify the direction of scanning (it is generally top-down except if the video grabber flipped the image). Afterwards, it is necessary to sample line profiles corresponding to the transducer lines. For each B-scan, an arbitrary number of lines can be drawn and for each line, k samples are computed by trilinear interpolation in the corresponding B-scan. As mentioned previously, the shadow is defined as a signal rupture along the line, followed by a low signal afterwards. Therefore, signal ruptures are detected first. To do so, the line signal is smoothed with a low-pass filter. Then, a local symmetric entropy criterion is computed. For each point p of the line signal S, a sliding window of size n is used to compute the rupture criterion R:

R = i=n i=1 S(p -i) log S(p -i) S(p + i) + S(p + i) log S(p + i) S(p -i)
The first term is the relative entropy of the "past" (the signal before the rupture) knowing the "future" (the signal after the rupture) which can also be viewed as the Kullback-Leibler divergence of the past distribution given a reference signal (the future). In order to symmetrize the criterion, the second term is added and expresses the relative entropy of the future knowing the past.

The loci where R is maximal indicate a signal rupture. The rupture criterion R is quite general since it relies on the statistical dependency between the future and the past samples in a sliding window. Rupture positions are determined as zero-crossings of the gradient of R. Figure 2 illustrates the rupture detection on a synthetic example. 3.4 Noise model and shadow detection

! "! #!! #"! $!! $"! %!! ! $! &! '! (! #!! #$! #&! ! "! #!! #"! $!! $"! %!! $! &! '! (! ! "! #!! #"! $!! $"! %!! ! "!! #!!! #"!! $!!! $"!! (a) Input signal (b) Attenuation (c) Added noise ! "! #!! #"! $!! $"! %!! $!! &!! '!! (!! #!!! #$!! #&!! ! "! #!! #"! $!! $"! %!! ! #!!! $!!! %!!! &!!! ! "! #!! #"! $!! $"! %!! &$!! &#!! ! #!! $!! (d) Filtered signal (e) Rupture detection (f ) Rupture gradient

Noise model

Each detected rupture is tested as a possible candidate for an acoustic shadow.

To design the detection test, we rely on a modeling of the ultrasound image statistics. Because of the difficulty to model the ultrasound image formation process, several models have been introduced so far. We use here a general model that has been successfully used for ultrasound images [START_REF] Hao | A novel multiscale nonlinear thresholding method for ultrasonic speckle suppressing[END_REF][START_REF] Krissian | Speckle-contrained anisotropic diffusion for ultrasound images[END_REF][START_REF] Coupé | NonLocal Means-based Speckle Filtering for Ultrasound Images[END_REF][START_REF] Loupas | An adaptive weighted median filter for speckle suppression in medical ultrasonic images[END_REF]. This model reads as:

u(x) = v(x) + v(x) • µ(x) with µ(x) ∼ N (0, σ 2 ), ( 2
)
where u is the observed image and v the "ideal" signal. In this model, the noise depends on the signal intensity. In other words, the noise is higher in bright areas. Equation 2 leads to:

u(x)|v(x) ∼ N (v(x), v(x)σ 2 ) (3)
The meaning of parameter σ is the following: on a local neighborhood, the in-tensity variance is proportional to the intensity mean, and the linear regression parameter is σ 2 .

Shadow detection test

It is generally assumed that acoustic shadows are areas where the signal is relatively low. In this paper, we assume that acoustic shadows are areas where the noise is low. Since noise is modulated by signal intensity in ultrasound images, this is not a strong assumption. When a rupture is detected and tested as a candidate for a shadow, let us denote E(u f ) (respectively V(u f )) the mean (respectively the variance) of the signal after the rupture. The shadow detection test states that the intensity noise after the rupture is low and not compliant with the noise modeling of equation 2. Therefore, the test reads as:

V(u f ) < E(u f ) • σ 2 . ( 4
)
Thus it is necessary to estimate the parameter σ. To do so, we follow the approach described in [START_REF] Hirakawa | Image denoising using total least squares[END_REF]. On local square patches that intersect the B-scan mask, the local mean µ and variance ϑ are computed. The parameter σ 2 can be interpreted as the linear regression parameter of the variance versus the mean:

ϑ = σ 2 • µ.
This computation relies on the hypothesis that the patch contains only one tissue type. This cannot be ensured in practice as illustrated in figure 3-(a) where two regions R 1 and R 2 intersect the patch. Therefore, a robust Leclerc M-estimators (with parameter σ = 20) is used to compute a robust mean and variance. Let us note x i the samples that compose the patch, then the robust mean is computed as µ = i λ i x i i λ i . The robust estimator iterates between the computation of the weights λ and the weighted mean µ until convergence. After convergence, the weights λ are used to compute the robust variance as 3-(b) shows a plot of variance versus mean of all image patches using a classical computation, while figure 3-(c) show the same plot with a robust computation of mean and variance. These figures show that the robust computation leads to a better constrained linear regression.

V r (x) = i λ 2 i (x i -x) 2 i λ i . Figure
The remaining issue is the size of the square patch used to compute the regression parameter σ. One may expect that using small patches will bias the computation of mean variance, while using large patches will lead to inconsistent results, since a patch will contain several tissue classes, as illustrated in figure 3-(a). Figure 4 shows the results of the regression parameter when the patch size varies, with a classic computation of statistics 4-(a) and a robust computation of statistics 4-(b). This shows that the classical computation leads to a biased estimation of σ. When the patch size increases, the patch is composed of different tissue classes and the observed variance is the sum of the noise variance and the inter-tissue variance. On the opposite, the use of robust statistics leads to a consistent and reliable estimation of σ over a wide range of patch sizes.

Regularization

Since acoustic shadows are due to an anatomical structure that reflects the wave energy (which more precisely depends on the angle between the beam and the interface), the detection of acoustic shadows should vary smoothly between two consecutive lines. A simple regularization scheme is therefore adopted: for each line, the detection index is defined as the position of the detected shadow along the line. A 2D median filtering of the detection indexes was first performed on a local neighborhood of adjacent lines to regularize the solution.

When the acquisition is continuous, the variations of acoustic shadow profiles should also vary smoothly between consecutive slices, since the frame rate of the imaging system is usually above 10Hz and the movement of the probe is relatively slow. Thus, a longitudinal regularization is performed by taking into account adjacent lines from the 2 neighboring B-scans, achieving an anisotropic 2D + t median filtering.

Results

Material

The method was tested with 2D tracked freehand ultrasound images. The sequences were acquired on patients who underwent surgery for tumor resection. The Sonosite cranial 4 -7M Hz probe was tracked by the Medtronic StealthStation© neuronavigation system using a Polaris infrared stereoscopic camera. Ultrasound data were thus registered with the coordinate system of the preoperative MRI.

Comparison between geometrical and statistical approaches

In figure 5, two methods were first compared. The first one is the solely statistical approach: after the estimation of the noise model (parameter σ), each point x is tested as a shadow candidate by performing the test in equation 4 on a local square neighborhood of size 5 × 5 around x. The result of this statistical approach is shown in figure 5-(b) and demonstrates that the statistical test is able to capture acoustic shadows, as well as hypoechogeneic areas. The combination of the geometrical method with the statistical test of eq. 4 applied to Fig. 5-(a) leads to a more consistent detection of acoustic shadows as seen in Fig. 5-(c). Due to the line sampling according to the probe's geometry, only deep areas corresponding to shadows are detected.

Detection of acoustic shadows

The regularization effect is illustrated on intraoperative brain ultrasound images, with 4 B-scans taken at 4 consecutive time stamps (figures 6-a-d). Different results were obtained with these four consecutive B-scans: without regularization in figures 6-(e-h), with 2D regularization (see figures 6-i-l) and with 2D + t regularization (see figures 6-m-p). For legibility purposes, only a few sampling lines were drawn.

The 2D regularization removed aberrant false positive detections like the dark red area on Figure 6-(m) corresponding to anatomical structures and smoothed the shape of the detected shadows. With the 2D+t regularization, the smoothing effect is stronger and there is more consistency from slice to slice. Regions of acoustic shadow and strong signal attenuation were detected by the method.

Typically, 400 scan lines were triggered for each image. The number of detected ruptures varies depending on some parameters. In our experience, we have found that it is better to detect and test many ruptures. Depending on the data, there is usually more than 50 ruptures tested per scan line. With the current sub-optimal implementation, the computation time is around 1 minute for a sequence of 50 B-scans.

Comparison with manually delineated ROI

Since the automatic method detects both the B-scan geometry and the shadows as shown in figure 5-c, the image ROI (i.e., the B-scan mask without the detected shadows) was compared to a manual delineation of this area. Three real intraoperative sequences were chosen for this experiment, with depth varying from superficial acquisition 7-(a) to deep acquisition 7-(c). The extent of the acoustic shadows and signal attenuation increases with the acquisition depth.

Four experts manually delineated the areas using the ITKsnap software [START_REF] Yushkevich | User-guided 3D active contour segmentation of anatomical structures: Significantly improved efficiency and reliability[END_REF]. The corresponding segmentations are presented in Fig. 8. Visually, the experts segmentations exhibit very large differences. This fact supports the use of an objective automatic process to delinetate these areas. As an evaluation criterion, the Dice coefficient, as well as the specificity and sensitivity were compared between the automatic method and the manual raters. Results are given in Ta-bles 1, 2 and 3. Results show that the automatic method is very consistent with respect to the raters segmentations. 1 Comparison between the various segmentations (manual raters, and automatic method) for the superficial dataset (7-(a)). For each comparison, the first figure is the Dice coefficient, followed the sensitivity and specificity into brackets. The automatic method leads to results as consistent as the manual raters with an excellent detection rate. 3 Comparison between the various segmentations for the large depth dataset (7-(c)) as in Table 1. The Dice coefficient decreases compared to superficial acquisitions, since the relative size of the ROI compared to the image size decreases.

Impact on Reconstruction

The reconstruction of the non uniformly distributed set of B scans into a regular 3D array of voxels is necessary for the successive processing steps like registration and segmentation. Therefore reconstruction artifacts and image distortions must be avoided to ensure optimal image quality. To solve this problem, the reconstruction method presented in [START_REF] Coupé | Probe trajectory interpolation for 3d reconstruction of freehand ultrasound[END_REF] was used. In this experiment, the data were composed of two sweeps from two view points that differ mostly by a translation. After application of the processing described above, areas detected as shadows regions were ignored in the distance-weighted interpolation step.

Figure 9-(a) shows a slice of the initial reconstruction and 9-(b) is the reconstructed slice when taking into account the detection of acoustic shadows. Figure 9-(c) shows the corresponding pre-operative MR slice. Artifacts are visible, not only at the border between the two views, but also in deep regions. For instance, deep cerebral structures previously difficult to make out (lenticular nucleus and choroid plexus, see arrows) are clearly visible on the reconstructed US image when taking into account acoustic shadows. As a numerical assessment, the correlation ratio [START_REF] Roche | Unifying maximum likelihood approaches in medical image registration[END_REF] was computed between the reconstructed US and the pre-operative MR. The correlation ratio increases from 0.15312 to 0.173996 when taking into account shadows, indicating objectively that the 3D reconstruction was improved.

Impact on registration

Registration of 3D ultrasound volumes is mandatory for quantitative image analysis and guidance [START_REF] Coupé | A probabilistic objective function for 3d rigid registration of intraoperative us and preoperative mr brain images[END_REF][START_REF] Pratikakis | Robust multiscale deformable registration of 3D ultrasound images[END_REF]. Registering ultrasound data is particularly needed in various situations: rigid registration of ultrasound data acquired at different surgical steps (e.g., before and after dura opening), registration of data for compounding purposes acquired from different view points or at different depths. It is expected that imaging artifacts such as acoustic shadows might adversely affect the registration process. Therefore, the benefit of removing detected acoustic shadows from the registration similarity is investigated in this section. Using masks to select relevant voxels, the similarity based on the SSD (sum of square differences) for a given transformation T reads as:

SSD(T ) =    (I M ask -J M ask • T ) 2 if I M ask ∩ J M ask • T = ∅ +∞ if I M ask ∩ J M ask • T = ∅ (5)
where I M ask and J M ask • T denote the reference masked image and the transformed masked floating image. The registration similarity is based on the sum of square differences with a simplex optimization within a multiresolution scheme. A barrier cost is included in the cost function in order to remove divergent solutions presenting no mask overlap.

In this section, three registration methods will be compared:

Method R : This registration is the standard registration with the SSD criterion on the entire image. Method RG : This registration method accounts for the B-scan geometry and uses the B-scan mask as explained in equation ( 5). Method RGASD : This registration method accounts for both the B-scan geometry and the acoustic shadows detection. The total mask is then used with the modified SSD criterion of equation [START_REF] Caoili | Refractory shadowing from pelvic masses on sonography: A useful diagnostic sign for uterine leiomyomas[END_REF].

To register two intraoperative sequences (i.e., to acquisitions at two depths), the transformation provided by the neuronavigation system can be used to assess registration methods. This transformation was used as a ground truth to assess the transformation resulting from the methods R, RG and RGASD.

Here it was assumed that the coordinates given by the neuronavigation system were reliable: that was checked by visual inspection on salient structures. We considered two US sequences I ref and I f lo registered together with the transformation from the neuronavigation system T neuro . To gather registration performance over a large number of samples and compute statistics, 100 random transformations T n were applied to I ref . I f lo was then registered and the resulting transformation was then compared to the reference T n • T neuro with the Frobenius matrix norm (||A|| F = T r(AA H ))).

A set of 100 random rigid transformations was used in this framework, with translation and rotation parameters uniformly distributed in [-20;20]mm and [-20;20]°respectively. Two acquisitions from the same patient taken at the same surgical time (before dura opening) but at two different depths were selected as shown in The Frobenius norm threshold used for the convergence rate estimation was set to 50. Above this value, all the registrations were showing visually aberrant results. The three methods are similar in terms of convergence for the first set of transformations as shown in Table 5. However, with the set of larger transformations, we notice an accuracy improvement when using the acoustic shadow information. The median and the upper bound of the distribution of registrations are very close, but there is a difference in the lower part of the box plot in Figure 11 for the registration RGASD. This difference is confirmed by the computation of the mean of the distribution : the improvement is about 2mm and 2°closer to the ground truth on each parameter.

Conclusion

In this paper, an automatic method to detect shadows in ultrasound images that uses image statistics and regularization for accurate detection of shadow borders was presented. The method was successfully tested on real intraoperative brain images, exhibiting a robust and reliable detection of acoustic shadows when compared to a manual delineation of these shadows. It was shown that the incorporation of acoustic shadows in the reconstruction process improves the quality of the reconstruction. Thanks to a modified similarity criterion that incorporates the detected mask, the benefit of accounting for acoustic shadows in a registration task was assessed: it was shown that incorporating acoustic shadows in the process enables more successful registrations, down to sub-voxel accuracy. Therefore, we advocate that accounting for shadows and attenuation is important for accurate registration of intraoperative brain images. Incorporating acoustic shadows into the registration process leads to a slight increase in computational time that can be neglected compared to that required for the registration process. Finally, the inter-rater variability of the manually defined masks sen in Fig. 8 demonstrates the need for an objective automatic procedure to detect acoustic shadows as that presented here.

In this paper, only a subset of acoustic shadows are detected corresponding to deep areas. Further work should focus on acoustic shadows that do not occur in deep zones, but revealing a reflectance interface like a gallstone. The framework presented here would need to be adapted to this case. For instance, the statistical detection test could be done after each rupture and between all following ruptures. In addition, more regularization constraints are needed to address concerns of minimum size and shape regularity. Further work should focus on the validation of such methods on various data including various types of shadows: air interfaces, bone interfaces, gallstones. For instance, the detection of bone interfaces in ultrasound images may be of interest for the registration of such data to CT images.

(a )

 ) Typical image (b) First mask (c) Cleaned mask (d) Trapezoid estimation

Fig. 1 .

 1 Fig. 1. Illustration of the automatic mask extraction. (a) shows a typical image of the acquired sequence. (b) shows the first mask obtained after selecting the highest values of the longitudinal statistics. (c) shows the mask after morphological operators were applied to remove patient information. (d) shows the final trapezoid model estimation.

Fig. 2 .

 2 Fig. 2. Illustration of the line processing on a synthetic signal. (a) : a synthetic "hat" signal is used as an input. (b) : an exponential attenuation is applied. (c) : multiplicative Rayleigh noise is added with σ = 10. (d) : the signal is smoothed with a low-pass filter, a Gaussian filter with standard deviation 3.. (e) : the local rupture criterion R is computed, as well as its gradient in (f). All loci of a gradient zero-crossing are tested as possible candidates for a shadow detection.

Fig. 3 .

 3 Fig. 3. Estimation of parameter σ of the noise model 2. On square patches, local statistics are computed to determine the parameter σ. Each dot represents the local statistic (variance on vertical axis versus mean on horizontal axis) of a single patch computed from a real intraoperative image. Since a square patch may not contain only one tissue, as illustrated on the left, robust statistics are used to compute the mean and variance. As a matter of fact, when a patch is composed of two tissue types, the variance increases and this is visible in figure (b). On the contrary, the use of robust statistics (c) enables a more accurate regression and estimation of σ compared to the regression using standard statistics (b).

Fig. 4 .

 4 Fig.4. Influence of patch size on parameter σ 2 computed with classical statistics (a,) and robust statistics (b). The use of robust statistics leads to a consistent and reliable estimation of the regression parameter. When the size patch increases, a patch contains several tissue classes and the observed variance is the sum of the noise variance and the inter-tissue intensity variance. Therefore, the regression parameter increases.

Fig. 5 .

 5 Fig. 5. Effects of the statistical test and the geometrical constraint. (a): Intraoperative 2D US of a left frontal glioma. In (b), black pixels represent the centers of patches detected as shadows with the statistical test only.Figure (c) presents the result obtained when combining the statistical and geometrical method. The introduction of a geometrical constraint leads to a more accurate and consistent detection of shadows.

  2D + t (n) 2D + t (o) 2D + t (p) 2D + t (m) at time t (n) at time t + 1 (o) at time t + 2 (p) at time t + 3

Fig. 6 .

 6 Fig. 6. Example of shadow estimation on intraoperative brain ultrasound images. For legibility, only a few lines were sampled in this case. Figures (a-d) show the initial B-scans, different results were obtained: without regularization (e-h), with 2D regularization (i-l) and with 2D + t regularization (m-p). The 2D regularized lines in red are overlaid on the 2D + t regularized lines in white for comparison. The 2D regularization removes outliers and smoothes the profile of the shadow boundaries. With the 2D + t regularization the smoothing is stronger and the detected area fits better in acoustic shadow. False detections, like the dark red lines in figure (m) are avoided thanks to the temporal regularization that anticipates anatomical structures present in neighboring slices.

Fig. 7 .Fig. 8 .Fig. 9 .

 789 Fig. 7. Left: Real intraoperative data used for the comparison with manual delineation. Data was chosen so as to represent three different depth acquisition: superficial, medium and deep. Right: the corresponding ROI detected with the automatic method.

(a) Sequence 1 -Fig. 10 .Fig. 11 .

 11011 Fig. 10. 2D slices of the ultrasound sequences selected for the validation, after 3D reconstruction. An important acoustic shadow area can be observed at the bottom of the B-scan of Figure (b), due to the shadowing effect of the tumor and the cerebral falx.

Table 2

 2 Comparison between the various segmentations for the medium depth dataset (7-(b)) as in Table1. The automatic method leads to results as consistent as the manual raters with an excellent detection rate.

	Rater 2	Rater 3	Rater 4	Automatic method
	Rater 1 0.964 (0.96/0.97) 0.936 (0.88/0.99) 0.958 (0.95/0.96)	0.933 (0.87/0.99)
	Rater 2	0.943 (0.89/0.99) 0.977 (0.97/0.97)	0.939 (0.88/0.99)
	Rater 3		0.945 (0.99/0.86)	0.976 (0.97/0.96)
	Rater 4			0.942 (0.99/0.86)
	Rater 2	Rater 3	Rater 4	Automatic method
	Rater 1 0.855 (0.77/0.99) 0.781 (0.56/0.99) 0.819 (0.78/0.96)	0.817 (0.69/0.99)
	Rater 2	0.822 (0.70/0.99) 0.848 (0.91/0.94)	0.897 (0.83/0.98)
	Rater 3		0.752 (0.99/0.84)	0.879 (0.98/0.91)
	Rater 4			0.840 (0.73/0.99)
	Table

Table 4 :

 4 deep (8cm) and middle deep (6cm) sequences were selected for I ref and I f lo to get relevant areas of acoustic shadow. Ultrasound sequence characteristics : deep (8cm) and middle deep (6cm) sequences were selected for I ref and I f lo with acoustic shadow ratio of 31% and 13% respectively.

	Acquisition	Sequence 1 -I f lo	Sequence 2 -I ref
	Depth	6cm	8cm
	Acoustic Shadow Ratio	13%	31%
	Table 4

Table 5 Convergence

 5 Rate and Mean Errors computed with the Frobenius matrix norm. The introduction of acoustic shadows improves the registration accuracy.

	Registration method	R	RG	RGASD
	Convergence Rate	13%	12%	12%
	Mean Error (Frobe-	36	36	33,2
	nius norm)


Hédi Zeghidi

Carlos F Crispim-Junior
email: carlos.crispim-junior@liris.cnrs.fr

Iuliia Tkachenko
email: iuliia.tkachenko@liris.cnrs.fr

CDP-Sim: Similarity metric learning to identify the fake Copy Detection Patterns

Keywords: detection pattern, similarity metric learning, fake detection

I. INTRODUCTION

The number of counterfeits increases each year due to the accessibility of editing software and printing and digitization devices. Counterfeits have a significant impact on our health or safety and due to growing number of fakes, people lose the trust on medicines and product quality. The majority of existing security elements (holograms, watermarks, sticky labels, specific inks) cannot be easily verified by the common users. One of the promising solutions is the use of printable unclonable codes [START_REF] Picard | Digital authentication with copy-detection patterns[END_REF], [START_REF] Tkachenko | Two-level QR code for private message sharing and document authentication[END_REF] that has easy integration and verification processes. Copy Detection Pattern (CDP) [START_REF] Picard | Digital authentication with copy-detection patterns[END_REF] is the most commonly used printable unclonable code. It is a black-andwhite maximum entropy image generated with a secret key, illustrated in Fig. 1 The security of CDP is based on the information loss principle [START_REF] Picard | Digital authentication with copy-detection patterns[END_REF], which applies to each printing and digitization process.

The stochastic nature of Print-and-Digitization (P&D) process [START_REF] Phan Ho | Document authentication using graphical codes: Reliable performance analysis and channel optimization[END_REF] impacts both the structure and the image quality of any CDP as illustrated in Fig. 1.b. Thanks to the stochastic nature of P&D process, the CDP was supposed to be unclonable. Nevertheless, recently high quality fakes, known as estimation attacks, were generated using neural networks [START_REF] Taran | Clonability of anticounterfeiting printable graphical codes: a machine learning approach[END_REF], [START_REF] Yadav | Copy sensitive graphical code estimation: Physical vs numerical resolution[END_REF], [START_REF] Yadav | Estimation of copy-sensitive codes using a neuronal approach[END_REF].

The classical detectors based on Pearson correlation have become ineffective against estimation attack. It was shown that the detector can be improved using some pre-processing techniques [START_REF] Khermaza | Can copy detection patterns be copied? evaluating the performance of attacks and highlighting the role of the detector[END_REF]. However, more recent estimation attacks [START_REF] Chaban | Machine learning attack on copy detection patterns: are 1x1 patterns cloneable?[END_REF] are very precise and the known similarity metrics (Pearson correlation, Hamming distance and Jaccard metric) cannot separate them from original CDP, even with pre-processing techniques.

As shown in [START_REF] Picard | On the security of copy detectable images[END_REF], the noise altering a CDP is difficult to characterize as each printer and scanner has its own characteristics [START_REF] Ferreira | Data-driven feature characterization techniques for laser printer attribution[END_REF], [START_REF] Navarro | Connecting the dots: Toward accountable machine-learning printer attribution methods[END_REF]. Therefore, in this paper, we explore the possibility to detect the fakes using the differences of printer signatures and the metric learning approach [START_REF] Ferreira | Ensembling shallow siamese neural network architectures for printed documents verification in datascarcity scenarios[END_REF]. The contributions of this paper are the following:

• We propose the metric learning approach based on Siamese neural network to identify the printer used for CDP production. The idea behind this task is to extract printer forensic features that can precisely separate the original CDP (printed using a known printer) from counterfeits (printed by unknown printer). • We explore the different configurations of input and outputs layers for similarity metric learning. • We propose a similarity based detector that can efficiently distinguish the originals from seen and unseen fakes. The rest of the paper is organized as follows. We start by describing the related work on estimation attacks and detectors in Section II. The proposed similarity metric learning approach (CDP-Sim), as well as the proposed detector are presented in Section II. The experimental results are shown in Section IV. Finally, in Section V we summarize our conclusions and discuss the future work.

II. SECURITY ASPECTS OF CDP

In this section, we discuss the CDP security aspects focusing both on new challenges brought by the deep learning based attacks and on the proposed countermeasures to detect the fake CDP produced by these estimation attacks.

A. Estimation attacks

The CDP authentication systems based on Pearson correlation were robust against duplication attack and naive image processing (Otsu thresholding, unsharp masking) attacks [START_REF] Tkachenko | Exploitation of redundancy for pattern estimation of copy-sensitive two level qr code[END_REF], [START_REF] Tkachenko | Sensitivity of different correlation measures to print-and-scan process[END_REF]. Nevertheless, the estimation attacks based on deep learning approach have shaken up the CDP based authentication systems. During the last 4 years a big amount of estimation attacks have been developed using different deep learning architectures. The first architectures used for estimation attacks were bottleneck deep neural network [START_REF] Taran | Clonability of anticounterfeiting printable graphical codes: a machine learning approach[END_REF], selectional autoencoders [START_REF] Yadav | Estimation of copy-sensitive codes using a neural approach[END_REF], super resolution generative adversarial network [START_REF] Yadav | Copy sensitive graphical code estimation: Physical vs numerical resolution[END_REF], among others. The majority of fakes produced by these estimations attacks can be detected using image processing techniques that improve the detector based on Pearson correlation values [START_REF] Khermaza | Can copy detection patterns be copied? evaluating the performance of attacks and highlighting the role of the detector[END_REF]. However, a novel publicly available dataset, named Indigo [START_REF] Chaban | Machine learning attack on copy detection patterns: are 1x1 patterns cloneable?[END_REF], was published recently. On this dataset, the classical similarity metrics underperform. Fig. 2 illustrates the distribution of normalized correlation values calculated between the template CDP and printed version of CDP (both originals and fakes). One can note that it is impossible to identify an authentication threshold that can efficiently separate the original CDP (red and blue curves in Fig. 2) from fake CDP (illustrated using magenta, yellow, cyan and green curves in Fig. 2). Therefore, it is urgent to find novel detectors to counter high quality fakes.

B. Authentication detectors

The high accessibility of deep learning models adds new challenges to CDP security system as the classical detectors that were used to identify the duplicated CDP [START_REF] Picard | Digital authentication with copy-detection patterns[END_REF] are inefficient against estimation attacks. Therefore, novel detectors were proposed [START_REF] Belousov | Digital twins of physical printing-imaging channel[END_REF], [START_REF] Pulfer | Anomaly localization for copy detection patterns through print estimations[END_REF], [START_REF] Tutt | Mathematical model of printing-imaging channel for blind detection of fake copy detection patterns[END_REF]. In the first approach, the authors [START_REF] Pulfer | Anomaly localization for copy detection patterns through print estimations[END_REF] proposed a machine learning based authentication system that uses only the CDP templates. It can identify the originals and accurately locate the anomalies in the fake CDP. The second detector uses a mathematical model of P&D process based on local statistics to train a one-class classifier to identify the originals and reject the fakes [START_REF] Tutt | Mathematical model of printing-imaging channel for blind detection of fake copy detection patterns[END_REF]. The proposed detector works well while using for authentication uniquely the symbols with low probability of bit-error on the training set. Another approach consists to simulate the P&D process using an encoder-decoder architecture [START_REF] Belousov | Digital twins of physical printing-imaging channel[END_REF]. The authors believe that these synthetic CDP generated using the proposed model can allow them to build a new classifier capable of detecting unseen fakes. These results show us that the construction of powerful detector is a challenging problem that is still an open issue. In this paper, we want to explore another approach for detector construction trying to characterize the printer used to produce authentic CDP samples.

III. PROPOSED AUTHENTICATION APPROACH

The studied pipeline is illustrated in Fig. 3. The manufacture produces a genuine physical object with CDP. Some printed samples are fed to the detector to learn the printer characteristics (the deep learning model and detector are detailed bellow). This detector is accessible to a final user to authenticate the physical object. The verification stage consists in digitization of physical object and calculation of the similarity between captured image and reference detector dataset (a set of images used as reference for similarity comparison). All the forgeries are created between printing and digitization processes. An opponent has access to the printed genuine physical object. He should digitize the object and forge the CDP using estimation attack. After the forging process, the fake CDP is printed by opponent device and sent to the market. The forged and authentic physical objects will be analyzed by the same verification system. The aim of authentication detector is to identify the difference between genuine and fake physical objects and reject the fakes. In this paper, we propose CDP-Sim, a method to learn a nonlinear, similarity metric learning distance that can separate original and fake examples of CDP. The proposed method is composed of a Siamese neural network (SNN) and a CDP

A. Siamese neural network

An SNN architecture can be viewed as two identical, parallel models sharing the same weight set [START_REF] Duffner | Similarity Metric Learning[END_REF]. The SNN models project each input into a feature vector of fixed length. The feature vectors can be then compared using a distance metric to measure their similarity using as a basis the projected space learned by the SNN. In practice, we may use the same neural network model for both inputs, hence enforcing the shared weights aspect. The CDP-SIM method follows the described approach and adopts the architecture [START_REF] Rao | A deep siamese neural network learns the human-perceived similarity structure of facial expressions without explicit categories[END_REF] as its basis. The adopted architecture is the following (Fig. 4): The first convolution layer is composed of 96 squared kernels of 11x11 with a stride of 4. This layer is followed by a ReLU (Rectified Linear Unit) activation function and max pooling layer (kernel size of 2, stride of 2). The second convolution layer is composed of 256 squared kernels of size 5 and stride of 1, and it is also followed by a ReLU activation layer and max pooling layer with the same hyperparameters as the previous max pooling layer. The third convolution layer adopts 384 squared kernels of size 8, with a stride of 1, and it is also followed by a ReLU activation layer. The next layers are fully connected layers of dimensions 1024, 256, and m, respectively. The term m defines the size of the output feature vector. We study the influence of this therm in the experimental section. Fig. 4 illustrates the overall architecture of the deep neural network adopted and the dimensions of the output volume of each layer. We adopted the contrastive divergence loss [START_REF] Duffner | Similarity Metric Learning[END_REF], as the pair-wise loss function to train CDP-Sim.

B. Detector

The SNN architecture described measures the distance between two samples of CDP. In this section, we describe During test time, we compute the distance between a tested example I and all examples D i , i = 1, . . . N in the reference set using the learned SNN model. Each reference example classifies the new example as true/fake, using a pre-defined threshold th. The new example I is considered authentic if more than N/2 reference examples vote as such. Otherwise, the test CDP image I is rejected as a fake.

IV. EXPERIMENTAL RESULTS

In this section we will discuss the dataset preparation, the accuracy of the CDP-Sim as well as the detector results in the simulated real-world use case.

A. Dataset preparation

In this work, we use the most recent publicly available dataset -Indigo 1x1 [START_REF] Chaban | Machine learning attack on copy detection patterns: are 1x1 patterns cloneable?[END_REF], that contains originals and fake CDP patterns. The fake CDP were obtained using machine learning based estimation attack which has an accuracy score of 94% [START_REF] Chaban | Machine learning attack on copy detection patterns: are 1x1 patterns cloneable?[END_REF]. Indigo dataset consists of 720 CDP templates of size 684×684 pixels that were printed by two printers (HP55 and HP76) and digitized by the same scanner. Then the printed CDP were used for estimation attack. The estimated CDP were printed again by the same printers, that gives 4 types of fakes (F55/55, F55/76, F76/55, F76/76). In this work, we use only a subset from the Indigo dataset: 719 images per printer (HP55 and HP76), 719 fakes F55/55 and 719 fakes F55/76. This subset is used for two use cases: known-fakes use case and real-world use case, as illustrated in Table I. The known-fake use case simulates the situation when the manufacture has information about the originals and the fakes that could be found in the market. We will use this use case in Section IV-C to identify best configuration of the adopted architecture. The real-world use case is used in the CDP-Sim detector evaluation. We simulate the scenario, when a manufacture train the detector using original CDP and possible fakes that s/he creates by himself. Nevertheless, the tests are done using the known and unknown fakes as in real life the manufacture cannot predict all the possible fake types. The dataset is split into training (60%), validation (20%) and testing (20%) sets: 431 originals and 431 fakes for training, 144 originals and 144 fakes for validation and the same quantity for test.

To train the SNN model, we construct pairs of images to maximize the distance between original and fakes examples (dissimilar images), and to minimize the distance between the examples of the original class (similar images). We constructed the CDP pairs for training and validation using the following rules:

• the first image of the pair is always randomly picked from the original class, • the second image is 50% of the time randomly selected from the class of originals (but cannot be the same CDP), and the 50% of the time from class of fakes. For CDP-Sim accuracy evaluation (see Section IV-C), the CDP pairs used during testing were created following the same rules.

In the case of real-world use case (see Section IV-D), for each CDP image in the test set we create N pairs with images from the detector dataset.

B. Model training and evaluation

All model weights have been initialized randomly using Xavier uniform distribution. We used Adam algorithm for model weights optimization with a learning rate of 5 × 10 -4 . All SNN models are trained for 100 epochs on the training set.

To evaluate the variation of model accuracy across training, we have used a fixed threshold, set to 0.5. By the end of the training we have computed the best threshold using the validation set, and defined it as the authentication threshold th.

C. SNN evaluation

To evaluate the proposed network, we have used the knownfake use case dataset. We have tested the network models with different input and output sizes to identify the best configuration for our problem. Table II One can note that the best accuracy is obtained while the input is of size 684 × 684 × 3. We use this input configuration for the detector implementation. The results for different sizes of output are quite similar, thus, we have decided to keep the smallest output size. The authentication threshold is defined on the validation set. We can note in Fig. 5 that the best authentication threshold for our dataset is nearly 1. We will use this authentication threshold value in the detector implementation.

D. Proposed detector

We evaluate the performance of the proposed detector on real-world use case. The detector is trained uniquely on originals (HP55) and fakes produced using these originals (F55/55).

This scenario simulates the situation where a manufacturer tries to produce the fakes using known estimation attacks, but using the known production devices (printer and scanner), which is the hardest case for detector. During the test phase, the CDP images may come from 4 different sets:

• Originals -Known HP Indigo printer (HP55) • Fakes -Known fakes used to train the detector (F55/55) • Fakes -Unknown fakes (F55/76) • Fakes -Unknown HP Indigo printer (HP76) In the studied scenario, the CDP printed using HP76 are considered as fakes, as they were printed using unknown (nonauthorized) printer. This real-world use case is a challenging task for the detector based on Pearson correlation. As shown in Fig. 6, the distributions of correlation values overlaps, what complicates the choice of an authentication threshold. We have simulated the detector based on the correlation: the training and validation dataset were used to find the threshold that separates optimally the originals (HP55) from fakes (F55/55). Than, this threshold was used for test dataset to detect the originals and fakes. The confusion matrix in Table III illustrates the results of this state-of-the-art detector. We note that this detector can identify fakes that come from estimation attacks, but it accepts nearly 15% of fake samples. We can also observe that the majority of CDP printed by unknown printer are detected as original CDP, even though we would expect them to be detected as fakes. This observation indicates that if the opponent guesses the CDP structure, the fake codes will be accepted as originals. We can note that 18% of originals (HP55) are considered as fakes. This value of false positives is quite high for a CDP detector.

To address this limitation we propose to use the CDP-Sim detector to better separate the seen originals (printed using known printer) from unseen originals and fakes. The training process was performed as described in Section IV-A. In test phase, we evaluated three setups with N = {5, 15, 25}. It is worth to mention that in all three setups the results are very similar. We have hence chosen to comment only on the results obtained for N = 5. Fig. 7 illustrates the distribution of mean Euclidean distances calculated between the feature vector of CDP images from the detector dataset and the feature vector of test CDP samples. We can note an almost perfect separation between the originals (represent the similar pairs) and fakes (represent dissimilar pairs). For the calculation of CDP-Sim accuracy, we have used the optimal authentication threshold defined on the validation set. In this particular test, the optimal authentication threshold is equal to th = 1.009. The detection results are presented in Table IV. We note that the optimal threshold choice allows us to accurately separate the samples between original and fake classes. The accuracy of the proposed CDP-Sim detector is 99%, which means that the proposed detector can be a good solution to detect fakes created by estimation attacks. It is worth to mention that the presented results are obtained for one particular use case. The main drawback of the proposed solution is that we do not consider the CDP template in the authentication stage. By consequence, any CDP printed on the same printer will be considered as authentic by our CDP-Sim detector. Nevertheless, it is quite unreal that the opponent will have the possibility to print the fake CDP in the same printing company. Another direction of work will be to acquire another dataset that is larger and depicts real-world condition such as CDP captured by smartphones.

V. CONCLUSIONS

In this paper, we investigated a similarity metric learning approach on the printer forensic task to separate the profiles of authentic and counterfeited printing devices. We proposed a novel authentication method named CDP-Sim that is able to distinguish the fake CDP produced by high quality estimation attacks. We have simulated a real-world use case, and the proposed detector can successfully detect all the fakes produced by estimation attacks, and even CDP printed by an unknown printer.

In future work, we plan to evaluate the performance of proposed detector in other datasets and to consider the CDP templates training stage of the proposed model to increase its robustness in less favorable setting. For instance, the situation where the forger has an access to the known printer.

Fig. 1 .

 1 Fig. 1. Example of CDP from Indigo dataset [3]: a) an original random binary image before printing and b) its degraded version by P&D.

Fig. 2 .

 2 Fig. 2. Correlation values calculated to whole samples of Indigo dataset.

Fig. 3 .

 3 Fig. 3. Studied pipeline depicting an authentic and an opponent production channel.

Fig. 4 .

 4 Fig. 4. Adopted Siamese Neural Network architecture [13].

  the detection algorithm we adopt to classify CDP examples in true or false class. The proposed detection algorithm is inspired on nearest neighbor algorithm. During training phase, we randomly choose N positive examples of CDP from our training dataset. The selected examples constitute the reference subset D.

Fig. 5 .

 5 Fig. 5. Optimization of authentication threshold th in validation dataset.

Fig. 6 .

 6 Fig. 6. Distribution of correlation values of 4 labels data set.

Fig. 7 .

 7 Fig. 7. Distribution of Euclidean distances on test dataset.

  presents the accuracy of the SNN models for different input and output sizes.

		Input size
	Output size 171 × 171 × 16 684 × 684 × 3 171 × 171 × 3
	2 × 1	64%	94%	89%
	32 × 1	61%	95%	90%
	64 × 1	68%	96%	89%
	128 × 1	62%	91%	86%
		TABLE II
	SNN ACCURACY FOR DIFFERENT INPUT AND OUTPUT SIZES.

ACKNOWLEDGMENT

This work was funded by the project FakeNets supported by the Computer Science Federation of Lyon (Féderation d'Informatique de Lyon).


Olivier Finkel
email: finkel@logique.jussieu.fr

On some sets of dictionaries whose ω-powers have a given complexity

Keywords: powers, sets of languages, descriptive set theory, Cantor topology, topological complexity, Borel sets, Borel hierarchy, Borel ranks. MSC (2000) 03E15, 03B70, 54H05, 68Q15, 68Q45

A dictionary is a set of finite words over some finite alphabet X. The ω-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V . Lecomte studied in [1] the complexity of the set of dictionaries whose associated ω-powers have a given complexity. In particular, he considered the sets

In this paper we first establish a new relation between the sets W(Σ 0 2 ) and W(∆ 1 1 ), showing that the set W(∆ 1 1 ) is "more complex" than the set W(Σ 0 2 ). As an application we improve the lower bound on the complexity of W(∆ 1 1 ) given by Lecomte, showing that

Then we prove that, for every integer k ≥ 2, (respectively, k ≥ 3) the set of dictionaries W(Π 0 k+1 ) (respectively, W(Σ 0 k+1 )) is "more complex" than the set of dictionaries W(Π 0 k ) (respectively, W(Σ 0 k )) .

Introduction

A finitary language, called here also a dictionary as in [1], is a set of finite words over some finite alphabet X. The ω-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V . The ω-powers appear very naturally in Theoretical Computer Science and in Formal Language Theory, in the characterization of the classes of languages of infinite words accepted by finite automata or by pushdown automata, [START_REF] Staiger | ω-languages[END_REF].

Since the set of infinite words over a finite alphabet X is usually equipped with the Cantor topology, the question of the topological complexity of the ω-powers of finitary languages naturally arises. It has been posed by Niwinski [START_REF] Niwinski | A problem on ω-powers[END_REF], Simonnet [START_REF] Simonnet | Automates et théorie descriptive[END_REF] and Staiger [START_REF] Staiger | On ω-power languages[END_REF]. Firstly it is easy to see that the ω-power of a finitary language V is always an analytic set because it is the continuous image of either a compact set {1, . . . , n} ω for n ≥ 0, or the Baire space ω ω . The first example of a finitary language L such that the ω-power L ω is analytic but not Borel, and even Σ 1 1complete, was obtained in [6]. Amazingly the language L has a very simple description and was obtained via a coding of the infinite labelled binary trees. The construction will be recalled below. For the Borel ω-powers, after some partial results obtained in [7][8][START_REF] Duparc | An ω-power of a context free language which is Borel above ∆ 0 ω[END_REF], the question of the Borel hierarchy of ω-powers of finitary languages has been solved recently by Finkel and Lecomte in [START_REF] Finkel | There exist some ω-powers of any Borel rank[END_REF], where a very surprising result is proved, showing that actually ω-powers exhibit a great topological complexity. For every non-null countable ordinal α there exist some Σ 0 α -complete ω-powers and also some Π 0 α -complete ω-powers.

Another question naturally arises about ω-powers and descriptive set theory. It has been firstly studied by Lecomte in [1]. He asked about the complexity of the set of dictionaries whose associated ω-powers have a given complexity. The set W(Σ 0 ξ ) (respectively, W(Π 0 ξ ), W(∆ 1 1 )) is the set of dictionaries over the alphabet 2 = {0, 1} whose ω-powers are Σ 0 ξ -sets (respectively, Π 0 ξ -sets, Borel sets). The set of dictionaries over the alphabet 2 = {0, 1} can be naturally equipped with the Cantor topology. Then Lecomte proved that W(Σ 0 2 ) is in Σ 1 2 (2 2 ⋆ )\ Π 0 2 and that all the other sets W(Σ 0 ξ ), W(Π 0 ξ ), and W(∆ 1 1 ) are in Σ 1 2 (2 2 ⋆ ) \ D 2 (Σ 0 1 ), where D 2 (Σ 0 1 ) is the class of 2-differences of open sets, that is, the class of sets which are intersections of an open set and of a closed set. It is proved in [11] that for each countable ordinal ξ ≥ 3 the sets W(Σ 0 ξ ) and W(Π 0 ξ ) are actually Π 1 1 -hard. In this paper we obtain first a new relation between the sets W(Σ 0

2 ) and W(∆ 1 1 ), showing that W(Σ 0 2 ) is continuously reducible to W(∆ 1 1 ), which means that the set W(∆ 1 1 ) is "more complex" than the set W(Σ 0 2 ). As an application we improve the lower bound on the complexity of W(∆ 1 1 ) given by Lecomte, showing that

W(∆ 1 1 ) is in Σ 1 2 (2 2 ⋆ )\ Π 0 2 .
Then we prove that, for every integer k ≥ 2, (respectively

, k ≥ 3) the set of dictionaries W(Π 0 k+1 ) (respectively, W(Σ 0 k+1 )) is "more complex" than the set of dictionaries W(Π 0 k ) (respectively, W(Σ 0 k )) .
The paper is organized as follows. In Section 2 we recall some notations of formal language theory and some notions of topology. We prove our results in Section 3. Some concluding remarks are given in Section 4.

Borel and projective hierarchies

We use usual notations of formal language theory which may be found for instance in [START_REF] Staiger | ω-languages[END_REF][START_REF] Thomas | Automata on infinite objects[END_REF]. When X is a finite alphabet, a non-empty finite word over X is any sequence x = a 1 . . . a k , where a i ∈ X for i = 1, . . . , k , and k is an integer ≥ 1. The length of x is k, denoted by |x|. The empty word has no letter and is denoted by λ; its length is 0. X ⋆ is the set of finite words (including the empty word) over X, and X + = X ⋆ \{λ} is the set of non-empty finite words. A finitary language, called here also a dictionary, over the alphabet X is a subset of X ⋆ .

An ω-word over X is an ω -sequence a 1 . . . a n . . ., where for all integers i ≥ 1, a i ∈ X. When σ is an ω-word over X, we write σ = σ(1)σ(2) . . . σ(n) . . ., where for all i, σ(i) ∈ X, and σ[n] = σ(1)σ(2) . . . σ(n) for all n ≥ 1 and σ[0] = λ.

The usual concatenation product of two finite words u and v is denoted u • v (and sometimes just uv). This product is extended to the product of a finite word u and an ω-word v: the infinite word u • v is then the ω-word such that:

(u • v)(k) = u(k) if k ≤ |u| , and (u • v)(k) = v(k -|u|) if k > |u|.
The prefix relation is denoted ⊑: a finite word u is a prefix of a finite word v (respectively, an infinite word v), denoted u ⊑ v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u • w.

The set of ω-words over the alphabet X is denoted by X ω . An ω-language over an alphabet X is a subset of X ω . We shall denote X ≤ω = X ⋆ ∪ X ω the set of finite or infinite words over the alphabet X.

We assume the reader to be familiar with basic notions of topology which may be found in [START_REF] Staiger | ω-languages[END_REF][START_REF] Moschovakis | Descriptive set theory[END_REF][START_REF] Lescow | Logical specifications of infinite computations[END_REF][START_REF] Kechris | Classical descriptive set theory[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. There is a natural metric on the set X ω of infinite words over a finite alphabet X containing at least two letters. It is called the prefix metric and is defined as follows. For u, v ∈ X ω and u = v let δ(u, v) = 2 -l pref(u,v) where l pref(u,v) is the first integer n such that the (n + 1) st letter of u is different from the (n + 1) st letter of v. This metric induces on X ω the usual Cantor topology for which the open subsets of X ω are of the form W • X ω , where W ⊆ X ⋆ . A set L ⊆ X ω is a closed set iff its complement X ω \ L is an open set. Define now the Borel Hierarchy of subsets of X ω : Definition 2.1 For a non-null countable ordinal α, the classes Σ 0 α and Π 0 α of the Borel Hierarchy on the topological space X ω are defined as follows: Σ 0 1 is the class of open subsets of X ω , Π 0 1 is the class of closed subsets of X ω , and for any countable ordinal α ≥ 2: Σ 0 α is the class of countable unions of subsets of X ω in γ<α Π 0 γ . Π 0 α is the class of countable intersections of subsets of X ω in γ<α Σ 0 γ .

For a countable ordinal α, a subset of

Σ ω is a Borel set of rank α iff it is in Σ 0 α ∪ Π 0 α but not in γ<α (Σ 0 γ ∪ Π 0 γ ).
There exists another hierarchy beyond the Borel hierarchy, which is called the projective hierarchy. The classes Σ 1 n and Π 1 n , for integers n ≥ 1, of the projective hierarchy are obtained from the Borel hierarchy by successive applications of operations of projection and complementation. The first level of the projective hierarchy consists of the class of analytic sets, and the class of co-analytic sets which are complements of analytic sets. In particular, the class of Borel subsets of X ω is strictly included in the class Σ 1 1 of analytic sets. The class of analytic sets is also the class of the continuous images of Borel sets.

We now recall the notion of Wadge reducibility, which will be fundamental in the sequel. Definition 2.2 (Wadge [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF]) Let X, Y be two finite alphabets. For L ⊆ X ω and L ′ ⊆ Y ω , L is said to be Wadge reducible to L ′ (L ≤ W L ′ ) iff there exists a continuous function f :

X ω -→ Y ω , such that L = f -1 (L ′ ). L and L ′ are Wadge equivalent iff L ≤ W L ′ and L ′ ≤ W L. This is denoted by L ≡ W L ′ .
The relation ≤ W is reflexive and transitive, and ≡ W is an equivalence relation. The equivalence classes of ≡ W are called Wadge degrees.

For L ⊆ X ω and L ′ ⊆ Y ω , if L ≤ W L ′ and f is a continuous function from X ω into Y ω with L = f -1 (L ′ ), then f is called a continuous reduction of L to L ′ .
Intuitively it means that L is less complicated than L ′ because to check whether x ∈ L it suffices to check whether f (x) ∈ L ′ where f is a continuous function.

Recall that each Borel class Σ 0 α and Π 0 α is closed under inverse images by continuous functions and that a set

L ⊆ X ω is a Σ 0 α (respectively Π 0 α )-complete set iff for any set L ′ ⊆ Y ω , L ′ is in Σ 0 α (respectively Π 0 α ) iff L ′ ≤ W L.
There is a close relationship between Wadge reducibility and games that we now introduce.

Definition 2.3 Let L ⊆ X ω and L ′ ⊆ Y ω . The Wadge game W (L, L ′
) is a game with perfect information between two players. Player 1 is in charge of L and Player 2 is in charge of L ′ . Player 1 first writes a letter a 1 ∈ X, then Player 2 writes a letter b 1 ∈ Y , then Player 1 writes a letter a 2 ∈ X, and so on. The two players alternatively write letters a n of X for Player 1 and b n of Y for Player 2. After ω steps, Player 1 has written an ω-word a ∈ X ω and Player 2 has written an ω-word b ∈ Y ω . Player 2 is allowed to skip, even infinitely often, provided he really writes an ω-word in ω steps. Player 2 wins the play iff

[a ∈ L ↔ b ∈ L ′ ], i.e. iff : [(a ∈ L and b ∈ L ′ ) or (a / ∈ L and b / ∈ L ′ and b is infinite)].
Recall that a strategy for Player 1 is a function σ : (Y ∪ {s}) ⋆ -→ X. And a strategy for Player 2 is a function

f : X + -→ Y ∪ {s}.
A strategy σ is a winning stategy for Player 1 iff he always wins the play when he uses the strategy σ, i.e. when the n th letter he writes is given by

a n = σ(b 1 • • • b n-1 )
, where b i is the letter written by Player 2 at the step i and b i = s if Player 2 skips at the step i. A winning strategy for Player 2 is defined in a similar manner.

Martin's Theorem states that every Gale-Stewart game G(B), where B is a Borel set, is determined, see [START_REF] Kechris | Classical descriptive set theory[END_REF]. This implies the following determinacy result:

Theorem 2.4 (Wadge) Let L ⊆ X ω and L ′ ⊆ Y ω be two Borel sets, where X and Y are finite alphabets. Then the Wadge game W (L, L ′ ) is determined: one of the two players has a winning strategy. And L ≤ W L ′ iff Player 2 has a winning strategy in the game W (L, L ′ ).

ω-powers and sets of dictionaries

Recall that, for V ⊆ X ⋆ , the ω-language

V ω = {u 1 • u 2 • • • u n • • • | ∀i ≥ 1 u i ∈ V \ {λ}}
is the ω-power of the language, or dictionary, V .

A dictionary over the alphabet X may be seen as an element of the space 2 X ⋆ , i.e. the set of functions from X ⋆ into 2, where 2 = {0, 1} is a two letter alphabet. The space 2 X ⋆ is naturally equipped with the product topology of the discrete topology on 2 = {0, 1}. The set X ⋆ of finite words over the alphabet X is countable so there is a bijection between X ⋆ and ω and the topological space 2 X ⋆ is in fact homeomorphic to the Cantor space 2 ω . The notions of Borel and projective hierarchies on the space 2 X ⋆ are obtained in the same way as above in the case of the Cantor space X ω . Lecomte introduced in [1] the following sets of dictionaries. For a non null countable ordinal ξ, we set

W(Σ 0 ξ ) := {A ⊆ 2 ⋆ | A ω is a Σ 0 ξ -set }, W(Π 0 ξ ) := {A ⊆ 2 ⋆ | A ω is a Π 0 ξ -set }, W(∆ 1 1 ) := {A ⊆ 2 ⋆ | A ω is a Borel set }. Lecomte proved in [1] that W(Σ 0 2 ) is in Σ 1 2 (2 2 ⋆ )\ Π 0 2
and that all the other sets W(Σ 0 ξ ), W(Π 0 ξ ), and

W(∆ 1 1 ) are in Σ 1 2 (2 2 ⋆ )\D 2 (Σ 0 1 ), where D 2 (Σ 0 1 )
is the class of 2-differences of open sets, that is, the class of sets which are intersections of an open set and of a closed set. Finkel and Lecomte showed in [11] that for each countable ordinal ξ ≥ 3 the sets W(Σ 0 ξ ) and W(Π 0 ξ ) are actually Π 1 1 -hard. This gives a much better lower bound on the complexity of these sets, but their complexity is not completely determined.

Staiger gave in [START_REF] Staiger | On ω-power languages[END_REF] a characterization of the set W(Σ 0 1 ) (respectively, W(Π 0 1 )). He gave in [START_REF] Staiger | On ω-power languages[END_REF] an example of a dictionary V ∈ W(Σ 0 1 \ Π 0 1 ), and also an example of a W ∈ W(∆ 0 2 ) \ W(Σ 0 1 ∪ Π 0 1 ). We refer the reader to [START_REF] Finkel | There exist some ω-powers of any Borel rank[END_REF]11] for an example of a W ∈ W(Σ 0 2 \ Π 0 2 ).

In this paper we show that the set W(∆ 1 1 ) is more complex than the set W(Σ 0 2 ). As an application we improve the lower bound on the complexity of the set W(∆ 1 1 ).

We have already mentioned in the introduction the existence of a dictionary L such that L ω is Σ 1 1 -complete, and hence non Borel. We now give a simple construction of such a language L using the notion of substitution that we now recall, (see [6] for more details).

A substitution is defined by a mapping f : X -→ P(Y ⋆ ), where X = {a 1 , . . . , a n } and Y are two finite alphabets. For each integer i ∈ [1; n], f (a i ) = L i is a finitary language over the alphabet Y . Now this mapping is extended in the usual manner to finite words:

f (a i1 • • • a in ) = L i1 • • • L in , and to finitary languages L ⊆ X ⋆ : f (L) = ∪ x∈L f (x).
If for each integer i ∈ [1; n] the language L i does not contain the empty word, then the mapping f may be extended to ω-words:

f (x(1) • • • x(n) • • • ) = {u 1 • • • u n • • • | ∀i ≥ 1 u i ∈ f (x(i))} and to ω-languages L ⊆ X ω by setting f (L) = ∪ x∈L f (x).
Now let X = {0, 1}, d be a new letter not in X, and

D = {u • d • v | u, v ∈ X ⋆ and [(|v| = 2|u|) or (|v| = 2|u| + 1)] }
Let g : X -→ P((X ∪ {d}) ⋆ ) be the substitution defined by g(a) = a • D.

Notice that if V ω is an ω-power then g(V ω ) = (g(V )) ω is also an ω-power.

If W = 0 ⋆ • 1 then W ω = (0 ⋆ • 1)
ω is the set of ω-words over the alphabet X containing infinitely many occcurrences of the letter 1. It is a well known example of an ω-language which is a Π 0 2 -complete subset of X ω . One can prove that (g(W )) ω is Σ 1 1 -complete, and hence a non Borel set. This is done by reducing to this ωlanguage a well-known example of a Σ 1 1 -complete set: the set of infinite binary trees labelled in the alphabet {0, 1} having an infinite branch in the Π 0 2 -complete set (0 ⋆ .1) ω . More generally it is proved in [6, proof of Theorem 4.5 and Section 5] that if W ω ⊆ X ω is an ω-power which is Π 0 2 -hard, then the ω-power (g(W )) ω ⊆ (X ∪ {d}) ω is Σ 1 1 -complete, and hence non Borel.

We use this result to prove our first proposition. In the sequel, for two sets A, B ⊆ 2 P r o o f. We shall use the substitution g defined above. Then let g ′ : X ∪ {d} -→ P(X ⋆ ) be the substitution simply defined by g ′ (0) = {0 • 1}, g ′ (1) = {0 • 1 2 }, and g ′ (d) = {0 • 1 3 }. And let G = g ′ • g be the substitution obtained by the composition of g followed by g ′ . Then, for every dictionary V ⊆ X ⋆ , the language G(V ) is also a dictionary over the alphabet X and G(V ω ) = (G(V )) ω . The substitution G will provide the reduction

X ⋆ we denote A ≤ B iff there is a continuous function H : 2 X ⋆ -→ 2 X ⋆ such that A = H -1 (B).
G : 2 X ⋆ -→ 2 X ⋆ .
Firstly, it is easy to see that the mapping G : 2 X ⋆ -→ 2 X ⋆ is continuous, [START_REF] Moschovakis | Descriptive set theory[END_REF].

Secondly, we claim that for every dictionary V ⊆ X ⋆ , it holds that:

V ∈ W(Σ 0 2 ) if and only if G(V ) ∈ W(∆ 1 1 ).
Assume first that V / ∈ W(Σ 0 2 ). By definition of W(Σ 0 2 ) this means that V ω is not a Σ 0 2 -subset of 2 ω . Then we can infer from Hurewicz's Theorem, see [15, page 160], that the ω-power V ω is Π 0 2 -hard because it is an analytic subset of 2 ω which is not a Σ 0 2 -set. Then it follows from [6, proof of Theorem 4.5 and Section 5] that the ω-power (g(V )) ω ⊆ (X ∪ {d}) ω is Σ 1 1 -complete, and hence non Borel. It is now very easy to check, applying the second substitution g ′ , that the ω-power (G(V )) ω ⊆ X ω is also non Borel. This means that G(V ) does not belong to the set W(∆ 1 1 ).

Conversely assume now that

V ∈ W(Σ 0 2 ). By definition of W(Σ 0 2 ) this means that V ω is a Σ 0 2 -subset of X ω , i.e. is a countable union of closed sets F n ⊆ X ω , n ≥ 1. Thus V ω = n≥1 F n and G(V ω ) = G( n≥1 F n ) = n≥1 G(F n ).
We are going to show that for every closed set F ⊆ X ω , it holds that G(F ) is a Borel subset of X ω .

Let then F ⊆ X ω be a closed set. Then there is a tree T ⊆ X ⋆ such that F = [T ], i.e. F is the set of the infinite branches of T . We first prove that g(F ) is Borel. For any ω-word y ∈ (X ∪ {d}) ω , it holds that y ∈ g(F ) if and only if there exist x ∈ F and sequences u i , v i ∈ X ⋆ , i ≥ 1, such that :

y = x(1) • (u 1 • d • v 1 ) • x(2) • (u 2 • d • v 2 ) • x(3) • • • where for each integer i ≥ 1, (|v i | = 2|u i |) or (|v i | = 2|u i | + 1).
Let then T 1 be the set of finite prefixes of such ω-words in the set g(F ). The set T 1 ⊆ (X ∪ {d}) ⋆ is a tree. We claim that g

(F ) = [T 1 ] ∩ ({0, 1} ⋆ • d) ω . The inclusion g(F ) ⊆ [T 1 ] ∩ ({0, 1} ⋆ • d) ω is straightforward.
To prove the inverse inclusion, let us consider an ω-word x ∈ [T 1 ] ∩ ({0, 1} ⋆ • d) ω . Then for each integer n ≥ 1 there exists (at least) one finite sequence (ε i ) 1≤i≤n ∈ {0, 1} n and one finite word a 1 • a 2 • • • a n ∈ X ⋆ and finite words u i and v i in X ⋆ , for 1 ≤ i ≤ n -1, and u ∈ X ⋆ , such that :

a 1 • (u 1 • d • v 1 ) • a 2 • (u 2 • d • v 2 ) • • • a n-1 (u n-1 • d • v n-1 ) • a n • u • d ⊑ x where for each integer i ∈ [1, n], (|v i | = 2|u i |) iff ε i = 0 and (|v i | = 2|u i | + 1) iff ε i = 1, and a 1 • a 2 • • • a n-1 ∈ T .
Consider now all the "suitable" sequences (ε i ) 1≤i≤n ∈ {0, 1} n defined as above. The set of these suitable sequences is closed under prefix. Therefore this set form a subtree of ({0, 1} ⋆ , ⊑), which is finitely branching. This tree is infinite so by König's Lemma it has an infinite branch. therefore there exists an infinite sequence

(ε i ) 1≤i<ω ∈ {0, 1} ω and one infinite word a 1 • a 2 • • • • a n • • • ∈ Σ ω
and finite words u i and v i in X ⋆ , for 1 ≤ i < ω, such that :

x = a 1 • (u 1 • d • v 1 ) • a 2 • (u 2 • d • v 2 ) • • • a n (u n • d • v n ) • • • where for each integer i ≥ 1, (|v i | = 2|u i |) iff ε i = 0 and (|v i | = 2|u i | + 1) iff ε i = 1, and a 1 • a 2 • • • a n • • • ∈ [T ] = F .
This shows that x ∈ g(F ).

Thus g(F ) = [T 1 ] ∩ ({0, 1} ⋆ • d) ω is the intersection of the closed set [T 1 ] and of the Π 0 2 -set ({0, 1} ⋆ • d) ω . Then g(F ) is a Borel Π 0 2 -set, and it is easy to see that G(F ) is also Borel. Assume now that V ∈ W(Σ 0 2 ), then V ω = n≥1 F n , where F n ⊆ X ω are closed sets. Then G(V ) ω = G(V ω ) = G( n≥1 F n ) = n≥1 G(F n ) is a Borel subset of X ω , so G(V ) belongs to the set W(∆ 1 1 ).
We can now improve the result :

W(∆ 1 1 ) ∈ Σ 1 2 (2 2 ⋆ )\D 2 (Σ 0 1 ) proved in [1]. Corollary 3.2 The following relation holds : W(∆ 1 1 ) ∈ Σ 1 2 (2 2 ⋆ )\Π 0 2 P r o o f. It follows directly from the relations W(Σ 0 2 ) ∈ Σ 1 2 (2 2 ⋆ )\ Π 0 2 and W(∆ 1 1 ) ∈ Σ 1 2 (2 2 ⋆
), proved by Lecomte in [1], and from Proposition 3.1 stating that W(Σ 0 2 ) ≤ W(∆ 1 1 ).

Remark 3.3

We have obtained only a slight improvement of Lecomte's result that

W(∆ 1 1 ) ∈ Σ 1 2 (2 2 ⋆ ) \ D 2 (Σ 0 1
). The question is still open of the exact complexity of the two sets W(∆ 1 1 ) and W(Σ 0 2 ) (and also of the other sets W(Σ 0 k ) and W(Π 0 k )). However, Proposition 3.1 could provide a better improvement of the lower bound on the complexity of W(∆ 1 1 ) as soon as a better improvement of the lower bound on the complexity of W(Σ 0 2 ) would be obtained. On the other hand, if one could obtain a better upper bound on the complexity of the set W(∆ 1 1 ), then this would provide, by Proposition 3.1, a better upper bound on the complexity of the set W(Σ 0 2 ). We consider now Borel ω-powers. It has been proved in [7] that for each integer n ≥ 1, there exist some ωpowers of (context-free) languages which are Π 0 n -complete Borel sets. (We refer the reader for instance to [START_REF] Autebert | Context free languages and pushdown automata[END_REF] for definitions and properties of context-free languages). These results were obtained by the use of an operation A -→ A ≈ over ω-languages which is a variant of Duparc's operation of exponentiation A -→ A ∼ , [START_REF] Duparc | [END_REF].

We first recall the definition of the operation A -→ A ∼ . Notice that this operation is defined over sets of finite or infinite words, called conciliating sets in [START_REF] Duparc | [END_REF].

Definition 3.4 (Duparc [19]) Let X be a finite alphabet, և / ∈ X, and x be a finite or infinite word over the alphabet Y = X ∪ {և}. Then x և is inductively defined by: λ և = λ, and for a finite word u ∈ (X ∪ {և}) ⋆ :

(u • a) և = u և • a, if a ∈ X, (u• և) և = u և with its last letter removed if |u և | > 0, i.e. (u• և) և = u և (1) • u և (2) • • • u և (|u և | -1) if |u և | > 0, (u• և) և = λ if |u և | = 0,
and for u infinite:

(u) և = lim n∈ω (u[n]) և , where, given β n and v in X ⋆ , v ⊑ lim n∈ω β n ↔ ∃n∀p ≥ n β p [|v|] = v.
(The finite or infinite word lim n∈ω β n is determined by the set of its (finite) prefixes). Remark 3.5 For x ∈ Y ≤ω , x և denotes the string x, once every և occuring in x has been "evaluated" to the back space operation, proceeding from left to right inside x. In other words x և = x from which every interval of the form "a և " (a ∈ X) is removed. The letter և may be called an "eraser".

For example if u = (a և) n , for n an integer ≥ 1, or u = (a և) ω , or u = (a ևև) ω , then (u) և = λ. If u = (ab և) ω then (u) և = a ω and if u = bb(և a) ω then (u) և = b.
Let us notice that in Definition 3.4 the limit is not defined in the usual way: for example if u = bb(և a) ω the finite word u[n] և is alternatively equal to b or to ba: more precisely u

[2n + 1] և = b and u[2n + 2] և = ba for every integer n ≥ 1 (it holds also that u[1] և = b and u[2] և = bb). Thus Definition 3.4 implies that lim n∈ω (u[n]) և = b so u և = b.
We can now define the operation A -→ A ∼ of exponentiation of conciliating sets: Definition 3.6 (Duparc [19]) For A ⊆ X ≤ω and և / ∈ X, let

A ∼ = df {x ∈ (X ∪ {և}) ≤ω | x և ∈ A}.
We now define the variant A -→ A ≈ of the operation A -→ A ∼ .

Definition 3.7 ( [7]

) Let X be a finite alphabet, և / ∈ X, and x be a finite or infinite word over the alphabet Y = X ∪ {և}. Then x ←֓ is inductively defined by: λ ←֓ = λ, and for a finite word u ∈ (X ∪ {և}) ⋆ :

(u • a) ←֓ = u ←֓ • a, if a ∈ X, (u• և) ←֓ = u ←֓ with its last letter removed if |u ←֓ | > 0, (u• և) ←֓ is undefined if |u ←֓ | = 0,
and for u infinite:

(u) ←֓ = lim n∈ω (u[n]) ←֓ , where, given β n and v in X ⋆ , v ⊑ lim n∈ω β n ↔ ∃n∀p ≥ n β p [|v|] = v.
The difference between the definitions of x և and x ←֓ is that here we have added the convention that (u. և) ←֓ is undefined if |u ←֓ | = 0, i.e. when the last letter և can not be used as an eraser (because every letter of X in u has already been erased by some erasers և placed in u). For example if u =և (a և) ω or u = a ևև a ω or u = (a ևև) ω , then (u) ←֓ is undefined.

Definition 3.8 For A ⊆ X ≤ω , A ≈ = {x ∈ (X ∪ {և}) ≤ω | x ←֓ ∈ A}.
The operation A -→ A ∼ was used by Duparc in his study of the Wadge hierarchy, [START_REF] Duparc | [END_REF]. The result stated in the following lemma will be important in the sequel. Lemma 3.9 Let X be a finite alphabet and L ⊆ X ω . Then the two ω-languages L ∼ and L ≈ are Wadge equivalent, i.e. L ∼ ≡ W L ≈ . P r o o f. Let X be a finite alphabet and L ⊆ X ω . We are going to prove that L ∼ ≡ W L ≈ , using Wadge games. a) In the Wadge game W (L ∼ , L ≈ ) the player in charge of L ≈ has clearly a winning strategy which consists in copying the play of the other player except if player 1 writes the eraser և but he has nothing to erase. In this case player 2 writes for example a letter a ∈ X and the eraser և at the next step of the play. Now if, in ω steps, player 1 has written the ω-word α and player 2 has written the ω-word β, then it is easy to see that [α և = β ←֓ ] and then α ∈ L ∼ iff β ∈ L ≈ . Thus player 2 has a winning strategy in the Wadge game W (L ∼ , L ≈ ).

b) Consider now the Wadge game W (L ≈ , L ∼ ). The only extra possibility for player 1 in charge of L ≈ is to get out of the set L ≈ by writing the eraser և when in fact there is no letter of his previous play to erase. But then his final play is surely outside L ≈ . If this happens at some point of the play, then player 2 may writes the eraser և forever. Then, after ω steps, player 2 has written an infinite word β such that β և = λ. In particular, β և / ∈ L because β և is not an infinite word, and β / ∈ L ∼ . On the other hand player 1 has written an infinite word α such that α ←֓ is undefined, hence α / ∈ L ≈ . Therefore player 2 wins the play in this case too, and player 2 has a winning strategy in the Wadge game W (L ≈ , L ∼ ).

The operation A -→ A ≈ is very useful in the study of ω-powers because it can be defined with the notion of substitution and preserves the ω-powers of finitary languages. Let L 1 = {w ∈ (X ∪ {և}) ⋆ | w ←֓ = λ}. L 1 is a context free (finitary) language generated by the context free grammar with the following productions: (S, aS և S) with a ∈ X; and (S, λ). Then, for each ω-language A ⊆ X ω , the ω-language A ≈ ⊆ (X ∪ {և}) ω is obtained by substituting in A the language L 1 • a for each letter a ∈ X. This implies that the operation A -→ A ≈ preserves the ω-powers of finitary languages. This is stated in the following lemma.

Lemma 3.10 ( [7]) Let X be a finite alphabet and let h be the substitution defined by h(a) = L 1 • a for every letter a ∈ X. If A = V ω for some language V ⊆ X ⋆ , then A ≈ = h(V ω ) = (h(V )) ω . Thus, if A is an ω-power, then A ≈ is also an ω-power.

We now recall the operation A -→ A b used by Duparc in his study of the Wadge hierarchy, [START_REF] Duparc | [END_REF]. For A ⊆ X ≤ω and b a letter not in X, A b is the ω-language over X ∪ {b} which is defined by :

A b = {x ∈ (X ∪ {b}) ω | x(/b) ∈ A}
where x(/b) is the sequence obtained from x when removing every occurrence of the letter b.

We can now state the following lemma. Lemma 3.11 Let X be a finite alphabet having at least two elements and A ⊆ X ω .

For each integer

k ≥ 2, A is a Π 0 k -subset of X ω iff A b is a Π 0 k -subset of (X ∪ {b}) ω . 2. For each integer k ≥ 3, A is a Σ 0 k -subset of X ω iff A b is a Σ 0 k -subset of (X ∪ {b}) ω .
P r o o f. We denote by Z ∞ the set of infinite words in (X ∪ {b}) ω having infinitely many letters in X. The set [START_REF] Kechris | Classical descriptive set theory[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. Notice that Z ∞ , equipped with the induced topology, is a topological subspace of the Cantor space (X ∪ {b}) ω . One can define the Borel hierarchy on the topological space Z ∞ as in the case of the Cantor space, see [15, page 68]. Then one can prove by induction that, for each non-null countable ordinal α, the Σ 0 α (respectively, Π 0 α )-subsets of Z ∞ are the intersections of Σ 0 α (respectively, Π 0 α )-subsets of (X ∪ {b}) ω with the set Z ∞ , see [15, page 167].

Z ∞ = {x ∈ (X ∪ {b}) ω | x(/b) ∈ X ω } is a well known example of Π 0 2 -subset of (X ∪ {b}) ω ,
Let now φ be the function from Z ∞ into X ω defined by φ(x) = x(/b). It is easy to see that, for each A ⊆ X ω , it holds that φ -1 (A) = A b . On the other hand, the function φ is continuous. Thus the inverse image of an open (respectively, closed) subset of X ω is an open (respectively, closed) subset of Z ∞ . And one can prove by induction that, for each non-null countable ordinal α, the inverse image of a Σ 0 α (respectively,

Π 0 α )-subset of X ω is a Σ 0 α (respectively, Π 0 α )-subset of Z ∞ , i.e. the intersection of a Σ 0 α (respectively, Π 0 α )-subset of (X ∪ {b}) ω with the set Z ∞ . Let now k ≥ 2 and A ⊆ X ω be a Π 0 k -subset of X ω . Then φ -1 (A) = A b is a Π 0 k -subset of of Z ∞ , i.e. the intersection of a Π 0 k -subset of (X ∪ {b}) ω with the set Z ∞ . But Z ∞ is a Π 0 2 -subset of (X ∪ {b}) ω thus φ -1 (A) = A b is the intersection of two Π 0 k -subsets of (X ∪ {b}) ω , hence also a Π 0 k -subset of (X ∪ {b}) ω .
In a similar way we prove that if k ≥

3 and A ⊆ X ω is a Σ 0 k -subset of X ω , then φ -1 (A) = A b is a Σ 0 k -subset of (X ∪ {b}) ω .
Conversely assume that for some integer k ≥ 2 and A ⊆ X ω the set A b is a Π 0 k -subset of (X ∪{b}) ω . Notice that X ω is a closed subset of (X ∪ {b}) ω . Thus A = A b ∩ X ω is the intersection of two Π 0 k -subsets of (X ∪ {b}) ω , hence also a Π 0 k -subset of (X ∪ {b}) ω . And A = A ∩ X ω so A is also a Π 0 k -subset of X ω .

In a similar way we prove that if for some integer k ≥ 3 and A ⊆ X ω the set A b is a Σ 0 k -subset of (X ∪ {b}) ω , then A is also a Σ 0 k -subset of X ω . Lemma 3.12 Let X be a finite alphabet having at least two elements and A ⊆ X ω .

For each integer

k ≥ 3, A is a Σ 0 k -subset of X ω iff A ≈ is a Σ 0 k+1 -subset of (X ∪ {և}) ω . 2. For each integer k ≥ 2, A is a Π 0 k -subset of X ω iff A ≈ is a Π 0 k+1
-subset of (X ∪ {և}) ω . P r o o f. Let X be a finite alphabet having at least two elements, A ⊆ X ω , and k ≥ 3 be an integer. Then the following equivalences hold: [START_REF] Duparc | [END_REF]Lemma 31]. ←→ A ∼ ∈ Σ 0 k+1 by Lemma 3.11. ←→ A ≈ ∈ Σ 0 k+1 by Lemma 3.9.

A ∈ Σ 0 k ←→ A b ∈ Σ 0 k by Lemma 3.11. ←→ A b ≤ W B b for some B ⊆ X ≤ω such that B b is Σ 0 k -complete. ←→ (A ∼ ) b ≤ W (B ∼ ) b by [19, Proposition 23]. ←→ (A ∼ ) b ∈ Σ 0 k+1 , because (B ∼ ) b is Σ 0 k+1 -complete by
In a very similar way we prove that if k ≥ 2 is an integer, then A ∈ Π 0 k iff A ≈ ∈ Π 0 k+1 .

We now state the following result about the classes W(Π 0 k ). Proposition 3. [START_REF] Moschovakis | Descriptive set theory[END_REF] For each integer k ≥ 2 it holds that: W(Π 0 k ) ≤ W(Π 0 k+1 ). P r o o f. We shall use the substitution h defined above. Let then h ′ : {0, 1, և} -→ P({0, 1} ⋆ ) be the substitution simply defined by h ′ (0) = {0 • 1}, h ′ (1) = {0 • 1 2 }, and h ′ (և) = {0 • 1 3 }. And let H = h ′ • h be the substitution obtained by the composition of h followed by h ′ . Then, for every dictionary V ⊆ X ⋆ = {0, 1} ⋆ , the language H(V ) is also a dictionary over the alphabet X and H(V ω ) = (H(V )) ω . The substitution H will provide the reduction H : 2 X ⋆ -→ 2 X ⋆ .

It is easy to see that the mapping H : 2 X ⋆ -→ 2 X ⋆ is continuous, [START_REF] Moschovakis | Descriptive set theory[END_REF].

We claim that for every dictionary V ⊆ X ⋆ , it holds that V ∈ W(Π 0 k ) if and only if H(V ) ∈ W(Π 0 k+1 ).

Firstly by definition of the class W(Π 0 k ) it holds that for every dictionary V ⊆ X ⋆ , V is in the class W(Π 0 k ) iff V ω is a Π 0 k -set. By Lemma 3.12, V ω is a

Π 0 k -set iff (V ω ) ≈ is a Π 0 k+1 -set. But (V ω ) ≈ = h(V ω ) = h(V ) ω . Thus V is in the class W(Π 0 k ) iff h(V ) ω is in the class Π 0 k+1 .
It is now easy to see, using the coding h ′ that this is equivalent to the assertion "(H(V )) ω is in the class Π 0 k+1 ", i.e. H(V ) is in the class W(Π 0 k+1 ).

In a very similar manner, we can prove the following result about the sets W(Σ 0 k ) for integers k ≥ 3. Proposition 3.14 For each integer k ≥ 3 it holds that: W(Σ 0 k ) ≤ W(Σ 0 k+1 ). Remark 3. [START_REF] Kechris | Classical descriptive set theory[END_REF] Notice that here k ≥ 3 because for L ⊆ X ω then L may be in the class Σ 0 2 while L b ⊆ (X ∪ {b}) ω is not in the class Σ 0 2 . For instance L = {0, 1} ω ⊆ {0, 1} ω is open and closed hence also in the class Σ 0 2 . But the ω-language L b is simply the set of ω-words over the alphabet {0, 1, b} which contain infinitely many letters 0 or 1 and it is a Π 0 2 -complete, hence non Σ 0 2 , subset of {0, 1, b} ω .

Concluding remarks

Lecomte proved that for every countable ordinal ξ ≥ 2 (respectively, ξ ≥ 3), W(Π 0 ξ ) ∈ Σ 1 2 (2 2 ⋆ ) \ D 2 (Σ 0 1 ) (respectively, W(Σ 0 ξ ) ∈ Σ 1 2 (2 2 ⋆ )\D 2 (Σ 0 1 )). Finkel and Lecomte proved that for every countable ordinal ξ ≥ 3, the sets W(Π 0 ξ ) and W(Σ 0 ξ ) are actually Π 1 1 -hard. The exact complexity of the sets W(Π 0 ξ ) and W(Σ 0 ξ ) is still unknown, but our new results could help to determine it.

Proposition 3 . 1

 31 So the relation ≤ is in fact the Wadge reducibility relation ≤ W . The following relation holds : W(Σ 0 2 ) ≤ W(∆ 1 1 ).

Copyright line will be provided by the publisher

Acknowledgements. Thanks to Dominique Lecomte and to the anonymous referee for useful comments on a preliminary version of this paper.