domain: spi phys

text:
1Abstract-Measuring uranium ore samples with high resolution gamma spectrometers requires long acquisition times and expensive high-purity germanium (HPGe) detectors that are difficult to operate in the field (crystal cooling at very low temperature). In this work, we present a spectrometer based on a 1.5"×1.5" LaBr3(Ce) scintillator able to measure, in a few minutes, the uranium concentration and the possible disequilibrium of the uranium chain. The method is based on the total counts in two energy bands of the gamma spectrum, of which one at low energy that is sensitive to the top of the 238 U chain (including 234 [START_REF] Marchais | Characterization of Uranium Ore Samples by HPGe Gamma-Ray Spectroscopy[END_REF] are widely used in the laboratory but low-resolution NaI(Tl) scintillators are preferred in the field to estimate the uranium grade and the potential radioactive disequilibrium between uranium, radium and radon (see Fig. 1) in ore samples [START_REF] Marchais | Low-resolution gamma spectroscopy of uranium ores to determine U concentration and U/Rn imbalance[END_REF]. The disequilibrium is caused by the difference in mobility of uranium and radium in roll-fronts deposits [START_REF] Boulesteix | Ilmenites and their alteration products, sinkholes for uranium and radium in roll-front deposits after the example of South Tortkuduk (Kazakhstan)[END_REF]. We consider here that radium and radon are in equilibrium as the beakers containing uranium ores have been hermetically closed to prevent radon leakage, more than one This work has been performed in the frame of an R&D collaboration between CEA and Orano Mining. Bertrand Pérot (bertrand.perot@cea.fr), Thomas Marchais and Pierre-Guy Allinei are with CEA, DES, IRESNE Institute, DTN, SMTA, Nuclear Measurement Laboratory, F-13108 Saint-Paul-Lez-Durance, France. month before measurements to allow the equilibrium recovery between 222 Rn (radioactive half-life of 3.8 days) and its daughters. Radon effects are also observed in boreholes just after drilling, with equilibrium recovery after about one month. In this work, we will refer equivalently to U/Ra or U/Rn disequilibrium. This paper reports MCNP6.1 [START_REF]MCNP6, User's manual -Version 1[END_REF] calculations to design and study the uncertainties of these LaBr tools for uranium exploration and exploitation, and their first tests to validate the expected performances.

Hervé Toubon, Youcef Bensedik and Romain Goupillou are with Orano Mining, F-92320 Châtillon, France.

II. LABR SPECTROMETER FOR URANIUM ORE SAMPLES

Monte Carlo simulations with the MCNP6.1 computer code [START_REF]MCNP6, User's manual -Version 1[END_REF] have been performed to optimize the design of the LaBr spectrometer and perform parametric studies on different effects, such as ore density, mineralogy, filling level in the beaker, and gamma self-absorption in uranium. The MCNP model and industrial design of the spectrometer is shown in Fig. 1. It includes a 1.5"×1.5" LaBr3(Ce) scintillator from Saint-Gobain Crystals, coupled to CAEN "i-Spector" (Intelligent Silicon Photomultiplier Tube with Digital MCA), a 2.5 cm thick lead shield against external background, and the crushed ore beaker.

Figure 3 shows the relative contributions of the two main groups of uranium and radon (cf. Fig. 1), with the two energy bands from 87 to 110 keV (gamma rays of 234 Th at 92.4 and 92.8 keV, and Kα1 fluorescence X-ray of uranium at keV), and from 560 to 660 keV (609 keV peak of 214 Bi) used to estimate the radioactive disequilibrium and the uranium grade.

Following the method detailed in [START_REF] Marchais | Low-resolution gamma spectroscopy of uranium ores to determine U concentration and U/Rn imbalance[END_REF] and [START_REF]MCNP6, User's manual -Version 1[END_REF], the count ratio of the two energy bands linearly depends on U/Ra disequilibrium (activity ratio):

C U band C Rn band = α A 𝑈𝑈 A 𝑅𝑅𝑅𝑅 + β (1)
in which α and β parameters can be estimated using MCNP simulations (α = 0.64 and β = 1.38 for the reference sample) or measured experimentally with ore samples having different disequilibria. MCNP parametric studies have shown that the mineralogy (SiO2 vs. Na2CO3 or CaCO3) has a negligible impact on the spectrum, hence on α and β, as well as the uranium grade up to 5000 ppm (beyond this value, gamma selfabsorption by uranium becomes significant). However, when the density varies between 0.7 and 1.7 g.cm -3 , α and β vary respectively of ± 1 % and ± 12 % around their reference values (for 1.2 g.cm -3 ), and when the filling height changes between 1 and 7 cm, α and β vary of ± 2 % and ± 19 % with respect to the reference filling height (4 cm). Therefore, the beaker will be systematically filled to a level of 4 cm (± 10 %) and the density will be determined by weighing the crushed ore sample (with a precision of ± 10 %), which will limit the relative uncertainties on α and β to about 1 % and 7 %, respectively. The disequilibrium D between U and Rn activities is deduced from (1):

D = A 𝑈𝑈 A 𝑅𝑅𝑅𝑅 = C U band C Rn band -β α (2)
And its relative standard deviation is:

σ D D = � � α × D + β α × D � 2 × 1 τ U + 1 τ Rn Tc + � β α × D � 2 × � σ β β � 2 + � σ α α � 2 (3)
in which τU and τRn are the count rates in the respective U and Rn bands (in s -1 ), and TC is the counting time.

Figure 4 and Table I show that for a 300 s measurement, counting statistics may significantly affect the uncertainty on D, especially at low uranium grade or low U/Rn activity ratio.

Fig. 2. LaBr spectrometer for uranium ore samples (from left to right the MCNP model, the "i-Spector" module, and the industrial design).

Fig. 3. Simulated contributions of the uranium and radium-radon groups for a reference ore sample with a SiO2 mineralogy, a 1000 ppm grade of uranium (here with the chain in equilibrium), a filling height of 4 cm, a density of 1.2 g.cm -3 and a mass of 157 g. The overall agreement is satisfactory and the largest discrepancy is observed on the uranium concentration of sample 4. It could be due to local heterogeneities in the crushed ore and hence to the representativeness of the small sample extracted for ICP-MS analysis. Nevertheless, the 100 % numerical calibration performed with MCNP6.1 provides suitable results and more samples will be analyzed to confirm this preliminary conclusion.

III. LABR PROBE FOR BOREHOLE LOGGING

MCNP6.1 Monte Carlo simulations have been performed with the new LaBr probe to study the feasibility of the 1001 keV gamma-ray detection [START_REF]MCNP6, User's manual -Version 1[END_REF] in the calibration blocks of ORANO CIME (Innovation Center for Extractive Metallurgy) calibration station in Bessines, see Fig. 6, and of the two approaches based on low-energy energy bands [START_REF] Th | Method of evaluating the uranium content by gamma spectrometry in a borehole and associated device[END_REF]. This last is illustrated in Fig. 7, with a narrow band (in blue) focused on the 98.4 keV self-fluorescence X-ray of uranium, induced by the gamma rays of the ore sample [START_REF] Marchais | Characterization of Uranium Ore Samples by HPGe Gamma-Ray Spectroscopy[END_REF][START_REF] Marchais | Low-resolution gamma spectroscopy of uranium ores to determine U concentration and U/Rn imbalance[END_REF]. This band is insensitive to the uranium grade because of the competitive effects of selfabsorption and self-fluorescence. However, the ratio of the counts in this band to that in the [560-660] keV band is linear with U/Rn disequilibrium, and same equations as (1) and ( 2) are used, here with αSXRF and βSXRF coefficients (SXRF for selfinduced X-ray fluorescence). Conversely, the low-energy band between 120 and 170 keV is inversely proportional to U grade up to 5000 ppm, see Fig. 8, while being insensitive to U/Rn disequilibrium D. The relationship between the count ratio and uranium mass concentration CmU (i.e. uranium grade in ppm) is written as:

C [120-170]keV C [960-1046]𝑘𝑘𝑘𝑘𝑘𝑘 = β 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑅𝑅 -α 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝑅𝑅 × 𝐶𝐶𝐶𝐶 𝑈𝑈 (3)
from which CmU is given by:

𝐶𝐶𝐶𝐶 𝑈𝑈 = β 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 - C [120-170]keV C [960-1046]𝑘𝑘𝑘𝑘𝑘𝑘 α 𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 (4)
The LaBr probe was tested at ORANO CIME calibration station, in seven reference concrete blocks in radioactive equilibrium and with increasing uranium grades. The measured spectra are given in Fig. 9. These spectra are normalized with the counts of the band from 960 to 1046 keV. As shown in Fig. 10, the normalized number of counts in the low-energy band between 120 and 170 keV is inversely proportional to uranium grade (as in Fig. 8). Figure 10 also shows the relationship between the net area of the 1001 keV peak and the uranium concentration in each reference concrete block. The results of the approach using self-induced uranium fluorescence (disequilibrium) are not reported as the blocks are all in radioactive equilibrium (D = 1.03).

IV. CONCLUSION AND PROSPECTS

After the preliminary experimental validation of the energy bands method with the new LaBr spectrometer, we will acquire more LaBr gamma spectra of uranium ore samples characterized at ORANO CIME laboratories by HPGe and ICP-MS reference techniques, in order to complete the validation on a wider range of uranium grades and radioactive disequilibria. On the other hand, the LaBr probe will be sent in the coming weeks to the ISR (In Situ Recovery) mine of Katco, in Kazakhstan, to test the in situ calibration method [START_REF] Marchais | Method for assessing the uranium content using gamma spectrometry in a wellbore and associated device[END_REF] in reference boreholes. In addition, an optimization of its MCNP model will be carried out in order to study different effects such as density, borehole diameters or mineralogy. This optimization will be realized thanks to a comparison of experimental results and MCNP simulations for the measurements in the concrete blocks at ORANO CIME, in Bessines, France.

  Th gamma rays near 92 keV and the 98.4 keV X-ray due to uranium selfinduced fluorescence). The second band, around the 609 keV peak of 214 Bi (bottom of the chain), is insensitive to uranium and is used for normalization. We will also present the development of a borehole logging probe based on a LaBr3(Ce) detector and two energy-band approaches, first with a narrower low-energy band focused on the 98.4 keV X-ray and the same normalization with the 609 keV peak. Their ratio is almost insensitive to uranium grade, owing to competitive effects of self-fluorescence and selfabsorption, but it gives the radioactive disequilibrium through a linear correlation. In the second approach, the low-energy band is sensitive to the attenuation of the Compton continuum due to uranium, divided by the counts in an energy band encompassing the 1001 keV gamma ray of 234m Pa. The ratio is not sensitive to the disequilibrium, but is linear with uranium concentration. Finally, it is also possible to measure the net area of the 1001 keV gamma ray with the LaBr3(Ce) probe, at high uranium grade. Among these three approaches, the most efficient one is chosen depending on uranium grade and radioactive disequilibrium. The 1001 keV net area is also used at low grade with a longer acquisition time to self-calibrate the probe in real boreholes. Index Terms-LaBr3(Ce) spectrometer for uranium ore samples, LaBr3(Ce) probe for uranium borehole logging I. INTRODUCTION RANO Mining and the Nuclear Measurement Laboratory of CEA IRESNE Institute are developing a new gamma spectrometer for uranium ore samples and a logging probe for borehole exploration based on LaBr3(ce) scintillators. High resolution HPGe spectrometers

γ

  Fig. 1. 238 U decay chain (WikipediA) in which the circles show the groups of interest in terms of radioactive disequilibrium (see text for details).

Fig. 4 .

 4 Fig. 4. Calculated standard deviation of D disequilibrium between U and Rn as a function of D and uranium grade, for a 300 s measurement time.

Figure 5

 5 Figure 5 reports four spectra measured by ORANO Mining with real ore samples and TableIIcompares the results of the LaBr energy bands method with reference measurements of the uranium grade (ICP-MS) and U/Rn disequilibrium (HPGe). The overall agreement is satisfactory and the largest discrepancy is observed on the uranium concentration of sample 4. It could be due to local heterogeneities in the crushed ore and hence to the representativeness of the small sample extracted for ICP-MS analysis. Nevertheless, the 100 % numerical calibration performed with MCNP6.1 provides suitable results and more samples will be analyzed to confirm this preliminary conclusion.

Fig. 5 .

 5 Fig. 5. Measured LaBr spectra of uranium ore samples.

Fig. 6 .

 6 Fig. 6. MCNP model of the new LaBr probe in a reference concrete block of ORANO CIME calibration station (Bessines, France).

Fig. 7 .

 7 Fig. 7. MCNP6.1 simulated spectra of the LaBr borehole logging probe in the seven reference concrete blocks of ORANO CIME.

Fig. 9 .

 9 Fig. 9. Gamma spectra measured with the LaBr probe in the seven reference concrete blocks in radioactive equilibrium (D = 1.03)

TABLE I EXAMPLES

 I OF STANDARD DEVIATIONS AND RELATIVE STANDARD DEVIATIONS ON THE DISEQUILIBRIUM D BETWEEN U AND RN ACTIVITIES U grade (ppm)

		Disequilibrium D	σD	σD/D
	100	0.2	0.23	120%
	100	0.4	0.24	60%
	100	1	0.27	27%
	1000	0.2	0.16	80%
	1000	0.4	0.17	35%
	1000	1	0.17	17%

TABLE II URANIUM

 II GRADE AND U/RA DISEQUILIBRIUM MEASURED WITH LABR ENERGY BANDS, COMPARED TO REFERENCE HPGE OR ICP-MS MEASUREMENTS

		LaBr energy bands	Reference data
	Sample #	U/Ra	U grade (ppm)	U/Ra a (activity ratio)	U grade b (ppm)
	1	2.53 ± 0.16	699 ± 44	1.82	704
	2	0.73 ± 0.16	226 ± 48	0.86	268
	3	0.71 ± 0.16	66 ± 15	0.6	78
	4	1.06 ± 0.16	106 ±16	1.1	156
	a Measured by high resolution gamma spectroscopy (HPGe)
	b Measured by ICP-MS


domain: info math

text:
Florian Ingels
email: florian.ingels@univ-lille.fr

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac

Keywords: tree isomorphism, AHU algorithm, prime numbers multiplication, DAG compression

The Aho, Hopcroft and Ullman (AHU) algorithm has been the state of the art since the 1970s for determining in linear time whether two unordered rooted trees are isomorphic or not. However, it has been criticized (by Campbell and Radford) for the way it is written, which requires several (re)readings to be understood, and does not facilitate its analysis. In this article, we propose a different, more intuitive formulation of the algorithm, as well as three propositions of implementation, two using sorting algorithms and one using prime multiplication. Although none of these three variants admits linear complexity, we show that in practice two of them are competitive with the original algorithm, while being straightforward to implement. Surprisingly, the algorithm that uses multiplications of prime numbers (which are also be generated during the execution) is competitive with the fastest variants using sorts, despite having a worst theoretical complexity. We also adapt our formulation of AHU to tackle to compression of trees in directed acyclic graphs (DAGs). This algorithm is also available in three versions, two with sorting and one with prime number multiplication. Our experiments are carried out on trees of size at most 10 6 , consistent with the actual datasets we are aware of, and done in Python with the library treex, dedicated to tree algorithms.

Introduction

Context

The Aho, Hopcroft and Ullman (AHU) algorithm, introduced in the 1970s [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF]Example 3.2], establishes that the tree isomorphism problem can be solved in linear time, whereas the more general graph isomorphism problem is still an open problem today, where no proof of NP-completeness nor polynomial algorithm is known [START_REF] Sch | Graph isomorphism is in the low hierarchy[END_REF]. However, the problem is considered to be solved in practice; powerful heuristics exist, such as the quasi-polynomial algorithm from [START_REF] Lászl Ó Babai | Graph isomorphism in quasipolynomial time[END_REF]; see also [START_REF] Mckay | Practical graph isomorphism, II[END_REF].

As far as we know, AHU remains the only state-of-the-art algorithm for determining, in practice, whether two trees are isomorphic. Recently, Liu [START_REF] Liu | A tree distinguishing polynomial[END_REF] proposed to represent a tree by a polynomial of two variables, computable in linear time, and where two trees have the same polynomial if and only if they are isomorphic. Unfortunately, the existence of an algorithm to determine the equality of two polynomials in polynomial time is still an open question [START_REF] Saxena | Progress on Polynomial Identity Testing[END_REF]. We should also mention [START_REF] Samuel | Alogtime algorithms for tree isomorphism, comparison, and canonization[END_REF], which proposes an alternating logarithmic time algorithm for tree isomorphism -under NC complexity class framework, that is, problems efficiently solvable on a parallel computer [START_REF] David A Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in NC[END_REF].

However, one criticism -emerging from Campbell and Radford in [START_REF] Douglas | Tree isomorphism algorithms: Speed vs. clarity[END_REF] -directed at the AHU algorithm is that it is presented in such a way that it is difficult to understand. We leave it to the reader to form their own opinion by reproducing the original text of the algorithm in Section 1.3, after a brief introduction of key background in Section 1.2. To the best of our knowledge, the remark from Campbell and Radford seems to have remained a dead letter in the community, and no alternative, clearer version of the algorithm seems ever to have been published -with the exception of Campbell and Radford themselves, which have nevertheless remained fairly close to the original text.

In this article, we propose to revisit the AHU algorithm by giving several alternative versions, all of them easier to understand and straightforward to implement. However, these variants have supra-linear complexity (which is also the case for the Campbell and Radford version). In practice, on trees of reasonable size (≤ 10 6 ), with a Python implementation using the treex library [START_REF] Azaïs | Treex: a Python package for manipulating rooted trees[END_REF], we find that two of the three proposed variants are faster than the original algorithm -one of them sorts lists of integers (like the original algorithm), while the other replaces this step by calculating the product of a list of primes. We also propose a direct adaptation of our variants to compute tree compression into directed acyclic graphs (DAGs) [START_REF] Godin | Quantifying the degree of self-nestedness of trees: application to the structural analysis of plants[END_REF] this time achieving state of the art complexity. Section 1.2 introduces the notations and definitions useful for the rest of the paper; the original AHU algorithm is presented in Section 1.3, as well as the aim of the paper.

Tree isomorphisms

A rooted tree T is a connected directed graph without any undirected cycle such that (i) there exists a special node called the root and (ii) any node but the root has exactly one parent. The parent of a node u is denoted by P(u), whereas its children are denoted by C(u). The leaves L(T ) of T are the nodes without any children. Rooted trees are said to be unordered if the order among siblings is not significant; otherwise they are said to be ordered. This paper focuses only on unordered rooted trees, referred to simply as trees in the remainder of this article.

The degree of a node u is defined as deg(u) = # C(u) and the degree of a tree T as deg(T ) = max u∈T deg(u). The depth D(u) of a node u is the length of the path between u and the root. The depth D(T ) of T is the maximal depth among all nodes. The level of a node u is defined as D(T ) -D(u). The sets of nodes of level d in a tree T is denoted by T d , and the mapping d → T d can be constructed in linear time by a simple traversal of T . Definition 1. Two trees T 1 and T 2 are said to be isomorphic if there exists a bijective mapping φ : T 1 → T 2 so that (i) the roots are mapped together and (ii) for any u Such a mapping φ is called a tree isomorphism. An example of isomorphic trees is provided in Figure 1. Whenever two trees T 1 and T 2 are isomorphic, we note T 1 ≃ T 2 . It is well known that ≃ is an equivalence relation on the set of trees [START_REF] Valiente | Algorithms on trees and graphs[END_REF]. The tree isomorphism problem consists in deciding whether two trees are isomorphic or not.

, v ∈ T 1 , v ∈ C(u) ⇐⇒ φ(v) ∈ C(φ(u)).
For the broader graph isomorphism problem, it is not usual to explicitly construct the isomorphism φ -let us mention nonetheless [START_REF] Fortin | The graph isomorphism problem[END_REF]Section 3.3] and [START_REF] Ingels | Isomorphic unordered labeled trees up to substitution ciphering[END_REF][START_REF] Azaïs | Detection of common subtrees with identical label distribution[END_REF] -but rather to compute a certificate of non-isomorphism. For instance, Weisfeiler-Lehman algorithms, also known as colour refinement algorithms [START_REF] Ningyuan | A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants[END_REF][START_REF] Kiefer | Power and limits of the Weisfeiler-Leman algorithm[END_REF], colour the nodes of each graph according to certain rules, and the histograms of the colour distributions are then compared: if they diverge, the graphs are not isomorphic. This test is not complete in the sense that there are non-isomorphic graphs with the same colour histogram -even though the distinguishing power of these algorithms is constantly being improved [START_REF] Grohe | Deep weisfeiler leman[END_REF]. While the graph isomorphism problem is not solved in the general case, it is solved for trees by virtue of the AHU algorithm, which is built on a colouring principle similar to that of Weisfeiler-Lehman.

The Aho, Hopcroft and Ullman algorithm

We reproduce below the original text of the algorithm, as introduced in 1974 by Ahu, Hopcroft and Ullman in [1, Example 3.2] -only minor changes have been made to fit the notations used in this paper.

1. First, assign to all leaves in T 1 and T 2 the integer 0.

2. Assume by induction that all nodes at level d -1 of T 1 and T 2 have been assigned an integer. Let L 1

(respectively L 2 ) be the list of nodes in T 1 (respectively T 2 ) at level d -1 sorted by non-decreasing value of the assigned integers.

3. Assign to the nonleaves of T 1 at level d a tuple of integers by scanning the list L 1 from left to right and performing the following actions:

• For each vertex on list L 1 take the integer assigned to u to be the next component of the tuple associated with P(u). • On completion of this step, each nonleaf w of T 1 at level d will have a tuple (i 1 , i 2 , . . . , i k ) associated with it, where i 1 , . . . , i k are the integers, in non-decreasing order, associated with the children of w.

• Let S 1 be the sequence of tuples created for the vertices of T 1 on level d.

Repeat

Step 3 for T 2 and let S 2 be the sequence of tuples created for the vertices of T 2 on level d.

5.

Sort S 1 and S 2 lexicographically. Let S ′ 1 and S ′ 2 , respectively, be the sorted sequence of tuples. 6. If S ′ 1 and S ′ 2 are not identical, then halt: the trees are not isomorphic. Otherwise, assign the integer 1 to those vertices of T 1 on level d represented by the first distinct tuple on S ′ 1 , assign the integer 2 to the vertices represented by the second distinct tuple, and so on. As these integers are assigned to the vertices of T 1 on level d, replace L 1 by the list of the vertices so assigned. Append the leaves of T 1 on level d to the front of L 1 . Do the same for L 2 . L 1 and L 2 can now be used for the assignment of tuples to nodes at level d + 1 by returning to Step 3.

7.

If the roots of T 1 and T 2 are assigned the same integer, T 1 and T 2 are isomorphic.

Note that, in Step 5, the authors resort to a variant of radix sort [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF]Algorithm 3.2]. Actually, the tree isomorphism problem and AHU algorithm are only introduced in the book as an application example of this sorting algorithm. This algorithm can sort n lists of varying lengths l 1 , . . . , l n , containing integers between 0 and m -1, in complexity O n i=1 l i + m . Expressed within our framework, the length of each list is exactly the degree of the associated node, and m = #{c(u) : u ∈ T d } -where c(u) designates the integer associated to node u.

+ #{c(u) : u ∈ T d } . Noticing that u∈T d deg(u) = #T d-1 and that #{c(u) : u ∈ T d } ≤ #T d ,
and summing over all levels indeed yields a linear complexity for all those sorts. Remark 1. A point (very) briefly addressed by the authors of AHU algorithm specifies that the maximum integer m used in Step 5 must be not "too large" [1, Section 3.2, p.77]. Indeed, the sorting algorithm works if the integers can actually be considered as integers, and not as sequences of 0's and 1's, as pointed out by Radford and Campbell [START_REF] Douglas | Tree isomorphism algorithms: Speed vs. clarity[END_REF] in which they show that there are large trees for which the algorithms runs in O(n log n).

How large are we talking? For the integers to not fit on one word of memory, we must assume that m > 2 k with a k-bit machine. The smallest tree T with m = 2 k has roughly k2 k nodes (see Appendix A). With k = 64, this would imply trees of size ≈ 10 21 . For most practical applications, this is unlikely to be a problem.

Without any additional context for interpreting what the algorithm does, perhaps the reader will agree with this comment, arguing that the formulation of the algorithm is utterly opaque. Even on second or third reading. When an algorithm is written it should be clear, it should persuade, and it should lend itself to analysis.

-Douglas M. Campbell and David Radford [START_REF] Douglas | Tree isomorphism algorithms: Speed vs. clarity[END_REF] In Campbell and Radford view, the formulation of the algorithm is detrimental to understanding it, analyse it, and implement it. It is true that the theoretical contribution of the AHU algorithm is indisputable, since it establishes that the tree isomorphism problem is linear. On the other hand, and to support Campbell and Radford's point of view, AHU would benefit from a formulation that is simpler to understand and implement. From a pedagogical point of view, it is likely that AHU is one of the first algorithms that people might want to study or implement when they learn about tree graph theory. AHU algorithm is also used by more advanced algorithms, such as the compression of trees into directed acyclic graphs (DAG) -see Section 2.3; or routinely for the construction of marked tree isomorphisms in [START_REF] Ingels | Isomorphic unordered labeled trees up to substitution ciphering[END_REF][START_REF] Azaïs | Detection of common subtrees with identical label distribution[END_REF]. [START_REF] Douglas | Tree isomorphism algorithms: Speed vs. clarity[END_REF], Campbell and Radford provide a very clear, step-by-step exposition of the intuitions that lead to the AHU algorithm, and they even provide an algorithm similar to AHU that associates bitstrings to nodes instead of integers -with O(n log n) time complexity. In this paper, we introduce yet another formulation for the AHU algorithm. This formulation assigns integers to the nodes, as does AHU and unlike Campbell and Radford's version. Several possible implementations of our approach are studied, both from a theoretical and a practical point of view. In addition to clarifying the intuition behind the original algorithm, our variants are straightforward to implement -at the cost, however, of worse complexity. With respect to Remark 1, when used with trees of reasonable size in line with common use cases, they nonetheless perform better in practice. The outline of the paper is as follows:

Aim of the paper In

• Section 2 introduces our intuition for the AHU algorithm, in three variants: two using list sorts, and one using multiplication of lists of primes instead. We also present an adaptation of AHU for the compression of trees into directed acyclic graphs (DAG), also in three variants.

• Section 3 tests these algorithms on simulated data of reasonable size, in competition with the original algorithm whenever possible (i.e. excluding DAG compression).

Although the theoretical complexities of the algorithms presented here exceed the linear complexity of the original algorithm, we show that in practice, with the exception of one of the sorting variants, the others are competitive with the original. In particular, the variant using prime number multiplication is competitive with the best variant using sorts, even though it also has to generate the primes on the fly in addition to multiplying them.

Finally, in Appendix A, we study a very specific class of trees, which allows us to prove results -namely Lemmas 1 and 2 -relating the size of trees to the number of distinct integers needed to assign classes level by level in the AHU algorithm (whatever its variant). To the best of our knowledge, this matter has never been addressed before.

Revisiting AHU algorithm

In this section, we present variants of the original AHU algorithm. First, Section 2.1 provides a new intuition of the algorithm, in the form of a colouring process. We propose two variant implementations, each using a different sorting algorithm. In Section 2.2, we replace the sorting step by the multiplication of a list of primes, leading to a new variant of AHU. Finally, in Section 2.3, we focus on the compression of trees into directed acyclic graphs (DAGs), which can be achieved via a simple modification of our version of AHUdeclined in three implementations: two with sorting, one with prime multiplication, as before.

An intuition for AHU and two variants

As already stated, the interested reader can found in [START_REF] Douglas | Tree isomorphism algorithms: Speed vs. clarity[END_REF] a step-by-step explaination of the concepts at works behind AHU algorithm. Here, we introduce another intuition for the AHU algorithm, presented as a colouring process, thus making the connection with Weisfeiler-Lehman algorithms for graph isomorphism already mentioned.

The core idea behind AHU algorithm is to provide each node in trees T 1 and T 2 a canonical representative of its equivalence class for ≃, thus containing all the information about its descendants.

The nodes of both trees are simultaneously browsed in ascending levels. Suppose that each node u of level d -1 has been assigned a colour c(u), representing its equivalence class for the relation ≃.

Each node u of level d is associated with a multiset C c (u) = {{c(v) : v ∈ C(u)}} -if u is a leaf, this multiset is denoted ∅.
Each distinct multiset is given a colour, which is assigned to the corresponding nodes. An illustration is provided in Figure 2. In the end, the trees are isomorphic if and only if their roots receive the same colour.

Moreover, after processing level d, if the multiset of colours assigned to the nodes of level d differs from one tree to the other, we can immediately conclude that the trees are not isomorphic. ⋆: We could have used colour because colours are assigned level by level and not globally. We have chosen to use another colour for the sake of clarity. In this example, the colours correspond exactly to the equivalence classes of the nodes.

Consider the number of colours required by any version of AHU algorithm; this number is given by max

d∈[[0,D(T )]] #{c(u) : u ∈ T d }. (1)
We call it the width of T and denote it by W(T ).

In practice, colours are represented by integers. To associate different integers with distinct multisets, we need to keep track of which ones we have already encountered. In order to check in constant time whether a multiset has already been seen (which is the case in the original algorithm: as the tuples are sorted in

Step 5, it is enough to compare a tuple with its predecessor in the list S ′ i to find out whether they are different or not), we need a perfect hash function that works on multisets. Obviously, this is a very strong assumption. Hash functions for multisets do exist -see for instance [START_REF] Clarke | Incremental multiset hash functions and their application to memory integrity checking[END_REF][START_REF] Maitin-Shepard | Elliptic curve multiset hash[END_REF] -but they involve advanced concepts, which would make implementation difficult for non-specialists. For the sake of this article, let us assume that we do not have access to such methods. Since we will be focusing on Python applications later on, we assume that the Python dictionary structure can be seen as a perfect hash table; it can hash integers, strings or tuples.

To get around multisets, a simple solution is to see them as lists, which we sort before hashing them as tuples. This approach, in particular, is used in Weisfeiler-Lehman algorithms, where the same problem arises -see, for example, [START_REF] Kiefer | Power and limits of the Weisfeiler-Leman algorithm[END_REF]Algorithm 3.1]. The pseudocode for AHU as presented in this section, using prior sorting of multisets, is presented in Algorithm 1.

Note that to compare the multisets of integers associated at current level d, on line 14, it is not necessary to hash but simply to sort the two lists and compare them term by term. This can be accomplished via pigeonhole sort [START_REF] Paul | Dictionary of algorithms and data structures[END_REF]. Remember that pigeonhole sorting a list of k integers within the range 0 to m -1 is done in O(k+m). Here, since colours are attributed at each level, m ≤ #T d i ; hence a complexity of O(#T d i ) for this step. The overall complexity of Algorithm 1 depends on the sorting algorithm used in line 9 to sort C c (u). It may be tempting to reuse the pigeonhole sort, already used in the algorithm, or to use a comparison sorting algorithm, such as timsort, Python's native algorithm [START_REF] Auger | On the worst-case complexity of TimSort[END_REF]. We assume that T 1 = T 2 = T -this is the worst case, since, if T 1 ̸ ≃ T 2 , we do not visit all the levels. The results holds in case (i) by virtue of the following lemma, whose proof can be found in Appendix A. Neither version of Algorithm 1 is linear; we will see later in Section 3 how they behave in practice. In the next section, we will consider another approach, which does not resort to sorting, but instead replaces multiset hashing with prime number multiplication.

Algorithm 1: TREEISOMORPHISM

Input: T 1 , T 2 Output: ⊤ if and only if T 1 ≃ T 2 1 if D(T 1 ) ̸ = D(T 2 ) then 2 return ⊥ 3 else 4 for d from 0 to D(T 1 ) do 5 k ← 0 6 Let f : ∅ → 0 7 for i ∈ {1, 2} and u ∈ T d i do 8 C c (u) ← (c(v) : v ∈ C(u)) 9 Sort C c (u) 10 if f(C c (u)) is not defined then 11 k ← k + 1 12 Define f(C c (u)) = k 13 c(u) ← f(C c (u)) 14 if {{c(u) : u ∈ T d 1 }} ̸ = {{c(u) : u ∈ T d 2 }}
Remark 2. It should be noted that Algorithm 1 can be straightforwardly adapted to handle ordered and/or labelled trees (where each node carries a label). For ordered trees, it suffices to not sort C c (u). For labelled trees, we have to assume that labels can be hashed. We replace C c (u) by the tuple (label(u), C c (u)) and consider two tuples to be equal if both the label and the multiset are identical. Note that another way of handling labels exists, requiring not the equality of labels but rather the respect of label equivalence classes. This variant is known as marked tree isomorphism [START_REF] Kellog | Problems polynomially equivalent to graph isomorphism[END_REF] and proved to be as hard as graph isomorphism -for which no polynomial algorithm is known, even though in practice very efficient algorithms exist; see [START_REF] Mckay | Practical graph isomorphism, II[END_REF][START_REF] Lászl Ó Babai | Graph isomorphism in quasipolynomial time[END_REF] for instance. Marked tree isomorphism is far beyond the scope of this article; but we refer the interested reader to [START_REF] Azaïs | Detection of common subtrees with identical label distribution[END_REF][START_REF] Ingels | Isomorphic unordered labeled trees up to substitution ciphering[END_REF].

The authors of the AHU algorithm have provided in [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] a way of adapting their method to labeled trees -but only with labels that can be totally ordered. It suffices to add of label of node u as the first element of the tuple associated to it, before the lexicographical sort of Step 5. While not provided in [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF], their algorithm can also be modified to account for ordered trees. In Step 3, the tuple associated to node u at level d is instead calculated as the tuple of integers associated with its children, in order. The list L i is not longer necessary.

AHU with primes

In Algorithm 1, we need to associate a unique integer f(C c (u)) to each distinct multiset C c (u) of integers encountered. There is a particularly simple and fundamental example where integers are associated with multisets: prime factorization. Indeed, via the fundamental theorem of arithmetic, there is a bijection between integers and multisets of primes. For example, 360 = 2 3 • 3 2 • 5 is associated to the multiset {{2, 2, 2, 3, 3, 5}}.

Note that this bijection is well known [START_REF] Blizard | Multiset theory[END_REF], and has already been successfully exploited in the literature for prime decomposition, but also usual operations such as product, division, gcd and lcd of numbers [START_REF] Tarau | Towards a generic view of primality through multiset decompositions of natural numbers[END_REF]. To the best of our knowledge, this link has never been exploited to replace multiset hashing, a fortiori in the context of graph isomorphism algorithms -such as Weisfeiler-Lehman, or AHU for trees. Note, however, that this approach has been used in the context of evaluating poker hands [START_REF] Suffecool | Cactus kev's poker hand evaluator[END_REF], where prime multiplication has been preferred to sorting cards by value in order to get a unique identifier for each distinct possible hand.

Since the previous versions of AHU we presented (both the original and our variants) sort lists of integers, the main challenge of this substitution concerns the potential additional complexity of multiplying lists of primes compared to sorting lists of integers. The subroutine NEXTPRIME, introduced in Algorithm 3, returns the next prime not already used at the current level; if there is no unassigned prime in the current prime list P, then new primes are generated using a segmented version of the sieve of Eratosthenes.

Algorithm 2: TREEISOMORPHISMWITHPRIMES

Input: T 1 , T 2 Output: ⊤ if and only if T 1 ≃ T 2 1 if D(T 1 ) ̸ = D(T 2 ) then
Algorithm 3: NEXTPRIME Input: N sieve , the largest number for which the sieve of Eratosthenes has already been performed, the list P of primes ≤ N sieve in ascending order, with length(P) ≥ 6, and a prime p ∈ P 1 if p is the last of element of P then 2 N sieve , P ← SIEVEOFERATOSTHENES(N sieve , P) / * At least one new prime has been added to P * / 3 Let p ′ be the next prime after p in P 4 return N sieve , P, p ′ Let us denote p n the n-th prime number. There are well known bounds on the value of p n [START_REF] Dusart | The k-th prime is greater than k(ln k + ln ln k -1) for k ≥ 2[END_REF][START_REF] Rosser | Explicit bounds for some functions of prime numbers[END_REF] -with ln denoting the natural logarithm and n ≥ 6: n(ln n + ln ln n -1) < p n < n(ln n + ln ln n).

(

) 2
Suppose we have the list of all primes P ≤ N sieve , where N sieve is the largest integer sieved so far. With #P = n -1, to generate p n , we simply resume the sieve up to the integer ⌈n(ln n + ln ln n)⌉, starting from ⌊n(ln n + ln ln n -1)⌋ or N sieve + 1, whichever is greater -to make sure there is no overlap between two consecutive segments of the sieve. With this precaution in mind, the total complexity of the segmented sieve is the same as if we had directly performed the sieve in one go [START_REF] Bays | The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10 12[END_REF]; i.e., O(N log log N) for a sieve performed up to integer N. Therefore, to generate the first n prime numbers, according to (2), we have N = n(ln n + ln ln n) = O(n log n) and the final complexity of the sieve can be evaluated as O(n log n log log n). See [START_REF] Neill | The genuine sieve of Eratosthenes[END_REF] for practical considerations on the implementation of the segmented sieve of Eratosthenes.

Remark 3. Note that other sieve algorithms exist, with better complexities -such as Atkin sieve [START_REF] Atkin | Prime sieves using binary quadratic forms[END_REF] or the wheel sieve [START_REF] Pritchard | Linear prime-number sieves: A family tree[END_REF]; the sieve of Eratosthenes has the merit of being the simplest to implement and sufficient for our needs. Also, a better asymptotic complexity but with a worse constant can be counterproductive for producing small primes -which is rather our case since we generate the primes in order.

We now analyse the complexity of Algorithm 2, assuming that T 1 = T 2 = T . Following the previous discussion, we can consider separately the complexity for generating the primes numbers.

Proposition 2. Generating the primes required for Algorithm 2 can be done in O(#T log log T ).

Proof. To generate the first n primes, the sieve must be carried out up to the integer n • (ln n + ln ln n), for total complexity O(n log n log log n). As defined in (1), the number of primes needed by Algorithm 2 is equal to W(T ). We result immediately follows by virtue of the upcoming lemma, whose proof can be found in Appendix A.

Lemma 2. For any tree T , W(T ) ln W(T ) = O(#T ).

Finally, we have the following result. Proof. The proof can be found in Appendix B.

This new variant is no more linear than the two versions introduced in Section 2.1. We shall see in Section 3 that, in practice, this version is competitive with its rivals.

Computing classes globally for DAG compression

In AHU algorithm as it has been presented so far, the colours assigned to the nodes are assigned level by level, and therefore make it possible to determine the equivalence class of the node relative to the level at which it is located. It is legitimate to ask whether the colours can be associated globally, so that the colour of a node is an exact reflection of its equivalence class in the tree -see Figure 2. In this way, two nodes located at different levels but having the same colour induce isomorphic subtrees.

The need to assign equivalence classes globally notably arises when considering the (lossless) compression of trees into directed acyclic graphs (DAG). Trees can have many redundancies in their structure, and the aim of DAG compression is precisely to eliminate these redundancies. There are many applications of DAG compression, some of which are: the representation of trees in computer graphics [START_REF] Sutherland | Sketchpad: A man-machine graphical communication system[END_REF][START_REF] John | Efficient antialiased rendering of 3-D linear fractals[END_REF], the simplification of queries on XML documents [START_REF] Buneman | Path queries on compressed XML[END_REF][START_REF] Frick | Query evaluation on compressed trees[END_REF] or again the computation of convolution kernels [START_REF] Aiolli | Fast on-line kernel learning for trees[END_REF][START_REF] Azaïs | The weight function in the subtree kernel is decisive[END_REF].

The set of vertices of the DAG compression R(T ) of a tree T corresponds to the set of equivalence classes of the subtrees of T . For any vertices a, b ∈ R(T ), the multiplicity of the arc a → b corresponds to the number of children of class b of a subtree of class a. An example can be found in Figure 3. A more precise definition and an algorithm can be found in [START_REF] Godin | Quantifying the degree of self-nestedness of trees: application to the structural analysis of plants[END_REF]. However, it should be noted that a simple adaptation of Algorithm 1 can also be used to construct the DAG compression of a tree, namely Algorithm 4.

Figure 3: A tree T (left) and its DAG compression R(T ) (right). Nodes are colored according to their equivalence class under ≃.

Remark 4.

In light of Remark 2, the same adjustments can be applied to Algorithm 4 to take into account ordered and/or labelled trees.

In addition, for labelled trees, the vertex in Q associated to the tuple (label(u), C c (u)) is labelled with label(u); f must be initialized as an empty mapping, and Q as an empty graph. For ordered trees, the order of children of C c (u) must be respected in Q.

As with Algorithm 1, the complexity of Algorithm 4 depends on the sorting algorithm used. With timsort, the sorting complexity remains O(deg(u) log deg(u)) and the global complexity is the same as for Algorithm 1. However, for pigeonhole sort, things are diffrent. By computing the classes globally, the number of colours needed is not W(T ) but exactly # R(T ), that can be roughly bounded by #T ; therefore sorting C c (u) via pigeonhole has complexity O(deg(u) + #T ) and leads to a global complexity of O(#T 2 ).

C c (u) ← (c(v) : v ∈ C(u)) 7 Sort C c (u) 8 if f(C c (u)) is not defined then 9 k ← k + 1 10 Define f(C c (u)) = k 11 Create a vertex k in Q with children C c (u) 12 c(u) ← f(C c (u))
The state-of-the-art complexity for computing R(T ) is O(#T log deg(T ))1 [25, Section 2.2.1], so our approach is consistent if we use timsort.

Algorithm 2 can also be adapted so that the DAG is constructed using multiplication of primes. As stated above, the largest colour (thus prime) used in the algorithm is no longer W(T ), but # R(T ). Using the same rough bound of # R(T ) ≤ #T , the complexity of Algorithm 2 would be modified to

O #T log #T • M deg(T ) log #T + log log #T ,
the final complexity depending on the chosen multiplication algorithm and whether M(deg(T ) log #T ) outweighs or not log log #T -recalling that M(n) varies from log n to n. Remark 5. Concerning the bound # R(T ) ≤ #T , note that # R(T ) = #T is achieved if and only if T is a chain; in which case all nodes have at most one child, and only one prime is actually needed. We could refine the bound with # R(T ) ≤ #T -# L(T ) + 1, since all leaves of T have the same equivalence class. In general, if we choose a tree T uniformly at random among trees with n nodes, the expected value of R(T ) is

ln 4 π n √ ln n 1 + O 1 ln n [17, Theorem 29].
The most compressible trees are called self-nested trees and achieve # R(T ) = D(T ) -on that matter, see [START_REF] Godin | Quantifying the degree of self-nestedness of trees: application to the structural analysis of plants[END_REF][START_REF] Azaïs | Nearest embedded and embedding self-nested trees[END_REF][START_REF] Azaïs | Approximation of trees by self-nested trees[END_REF].

Finally, note that AHU as stated in the original paper [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF] cannot be extended to take into account this global assignment of colours.

Numerical experiments

Table 1 summarizes the different algorithms seen so far and whether or not they can be adapted to compute DAG compressions of trees. We implemented in Python those 7 different algorithms. All of them are written to be fully compatible with the library treex [START_REF] Azaïs | Treex: a Python package for manipulating rooted trees[END_REF], dedicated to tree algorithms.

Original AHU with AHU with AHU with primes AHU pigeonhole sort timsort Tree

O(#T ) O #T 2 log #T O(#T log deg(T )) O(#T log #T • M (deg(T ) log #T ))) Isomorphism DAG ✗ O(#T 2 ) O(#T log deg(T )) O #T log #T • M deg(T ) log #T + log log #T Compression
Table 1: Complexities of the various algorithms studied in this paper.

Most of auxiliary functions used in those algorithms have been implemented as well, such as the variant of radix sort used by AHU [1, Algorihm 3.2], pigeonhole sort or the prime variant of pigeonhole sort discussed in Appendix B. For the algorithm using primes, we have also implemented a variant that uses a pregenerated list of primes, large enough so that no additional sieving step is needed during execution -in this way we intend to study the impact of multiplication compared with sorting. The divide and conquer recursive multiplication strategy discussed in Appendix B as well as the sieve of Eratosthenes have been also implemented. Note that our implementation of the segmented sieve of Eratosthenes ignores multiples of 2 and 3, thus making the sieve 6 times faster. The noteworthy native Python functionalities we used are (i) the dictionary structures for hash tables, (ii) the sort method for lists -that use timsort algorithm [START_REF] Auger | On the worst-case complexity of TimSort[END_REF] and (iii) the multiplication operator * -which use schoolbook multiplication for small integers, and Karatsuba for large ones.

All experiments have been conducted on a HP Elite Notebook with 32 Go of RAM and Intel Core i7-1365U processor.

Results for tree isomorphism

We generated 100 pairs of trees (T 1 , T 2 ) of size n = 10 i for each i ∈ [ [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF][START_REF] Azaïs | Approximation of trees by self-nested trees[END_REF]], and for each case T 1 ≃ T 2 or T 1 ̸ ≃ T 2 , following the procedure below:

• for T 1 ≃ T 2 , we generate a random recursive tree [START_REF] Zhang | On the number of leaves in a random recursive tree[END_REF] T 1 of size n, and generate T 2 as a copy of T 1 ;

• for T 1 ̸ ≃ T 2 , T 1 and T 2 are both random recursive trees of size n.

When processing a couple, we executed all five algorithms (original AHU, AHU with pigeonhole sort, AHU with timsort, AHU with primes and AHU with pregenerated primes) on that same couple, so that the results are comparable. The computation times we got are depicted in Figure 4.

As one might expect, in the case T 1 ≃ T 2 , the behaviour of AHU with pigeonhole is supralinear. However, this is not the case for the other variants, which are in fact faster than the original algorithm. This can be explained by the fact that AHU has a large constant, scanning each list several times during its execution. Furthermore, there doesn't seem to be any significant difference between AHU with timsort, with primes or with pregenerated primes (for the same tree, we found that timsort is actually slightly faster in most of the cases). It's not surprising that the two versions with prime numbers are similar: it has already been established that the complexity of generating the prime numbers is negligible compared with the other steps in the algorithm. However, the proximity between timsort on the one hand, and prime numbers on the other, suggests that at this scale it is just as fast to sort lists as it is to multiply them.

Whenever T 1 ̸ ≃ T 2 , all algorithms are roughly equally fast. This is likely due to the early stopping conditions: the distribution of random recursive trees generates trees that are too dissimilar for several levels to be visited during the execution. Remark 6. One could argue that 10 6 is not very large, as an upper limit to our simulations. However, most of the real tree databases we are aware of already do not have trees of this size. Among the 8 datasets studied in [START_REF] Azaïs | The weight function in the subtree kernel is decisive[END_REF], the largest trees have a few thousand nodes; among the 5 studied in [START_REF] Shin | A comprehensive study of tree kernels[END_REF], a few hundred. If gigantic tree databases were to be built (for example, spanning trees from graphs with billions of nodes), it seems reasonable to imagine that they would be processed, in any case, with algorithms implemented in C, C++ or Rust rather than in Python (at the very least to be able to compute them efficiently, with the spanning trees example).

Results for DAG compression

Here, we generated 100 random recursive trees T of size n = 10 i for each i ∈ [ [START_REF] Aho | The Design and Analysis of Computer Algorithms[END_REF][START_REF] Azaïs | Approximation of trees by self-nested trees[END_REF]]. The results are provided in Figure 5. One can see that the pigeonhole variant seems to confirm a quadratic behaviour, while the timsort variant confirms its slight advantage over the versions with prime numbers. This time, a difference can be seen between the version that uses pregenerated primes and the one that does not (as might be expected given the theoretical complexity).

Concluding remarks

In this article, we have provided a new intuition for understanding the AHU algorithm, as well as several algorithmic variants that are straightforward to implement, albeit at the cost of increased complexity. However, we have shown that on trees of reasonable size, with a Python implementation, some of these variants were faster than the original algorithm. We have shown that a simple adaptation of our algorithms can also be used to calculate the DAG compression of trees.

Perhaps counter-intuitively, we have shown that in this context we can multiply lists of primes almost as quickly as we can sort lists of integers. However, if one had to pick just one variant, the one with timsort would probably be the simplest to implement and the most effective in practice -bot for tree isomorphism and DAG compression. The version using prime numbers could possibly become competitive with timsort if the list multiplication and prime number generation operations were implemented in CPython (as is the case for timsort), but this is beyond the scope of this article.

One may also wonder whether our variant using prime numbers could be applied to other algorithms similar to AHU, such as (1-dimensional) Weisfeiler-Lehman algorithm for graph isomorphism. While this issue is outside the scope of this paper, and remains to be investigated, let us nonetheless mention two points that may prove challenging. First, the way Weisfeiler-Lehman operates can lead to processing as many colours as there are nodes in the graph, and therefore having to generate as many prime numberswhich relates to the DAG compression case studied in this paper, for which our variant performed slightly worse than the others. Next, we would multiply lists whose size depends on the degree of the current node; in a dense or complete graph, this means lists whose size is comparable to the number of nodes in the graph. The complexity of performing these multiplications could prove far more expensive than for trees. Since Weisfeiler-Lehman can be implemented in O((#V + #E) log #V) for a graph G = (V, E), it remains to be investigated to which extent the additional complexities mentioned above exceeds that of the original algorithm. See [32, Section 3.1] and references therein for a more precise description of the Weisfeiler-Lehman algorithms.

A.1 A special tree

Let k ≥ 1 be a fixed integer. A tree T such that W(T ) = k can be obtained by placing k trees T i , i ∈ [ [1, k]], under a common root, so that T i ̸ ≃ T j for i ̸ = j. Note that this construction by no means encompasses all types of trees T with W(T ) = k. On the other hand, by cleverly choosing the T i 's, we can build a tree with the minimum number of nodes among all trees verifying W(T ) = k.

First, T 1 would be the tree with a unique node. Then, T 2 the only tree with two nodes. Then, T 3 and T 4 would be the two non-isomorphic trees with three nodes; T 5 to T 8 the four non-isomorphic trees with four nodes, and so on until we reach T k . See Figure 6 for an example with k = 5. It should be clear that this construction ensures that W(T ) = k and #T is minimal. Following this construction, the total number of nodes in T , that we denote by t k , is therefore closely related to the number of non-isomorphic trees and their cumulative sum. Let us denote a n the number Taking the logarithm of the asymptotic equivalents provided earlier on both equations yields the result.

a 1 a 2 a 3 k -b 3 b 2 b 3
Combining the two previous lemmas, we derive the following two corollaries. From Lemma 3, we get that for any tree T , W(T ) ln W(T ) = O(#T ), which ends the proof of Lemma 2.

B Proof of Theorem 2

Following Proposition 2, the generation of primes is done in O(#T log log #T ). This term vanishes in the final complexity due to the upcoming term in #T log #T . Let us denote by p W(T ) the largest prime needed by the algorithm. Fix d ∈ [[0, D(T )]] and u ∈ T d .

Complexity of multiplication

The complexity for multiplying two n-bits numbers varies from O(n 2 ) for usual schoolbook algorithm, to O(n log n) [START_REF] Harvey | Integer multiplication in time O (n log n)[END_REF] -even if this result is primarily theoretical, by the authors' own admission. Karatsuba algorithm, which is widely used, runs in O(n log 3 ) [START_REF] Alekseevich | Multiplication of many-digital numbers by automatic computers[END_REF]. This algorithm is actually used in Python when the numbers get large, and schoolbook otherwise. Let us denote the complexity of multiplication as n • M(n), with M(n) varying from log n to n depending on the algorithm used.

Multiplying two n-bits numbers together yields a 2n-bits number. To compute the product of m numbers of n bits, we adopt a divide and conquer approach and multiply two numbers which themselves are the recursive product of m/2 numbers. This strategy leads to a complexity of O(mn • M(mn)) by virtue of the Master Theorem [START_REF] Louis | A general method for solving divide-andconquer recurrences[END_REF] Other points Testing whether or not f(N(u)) is defined in line 12 can be done in O(1) since N(u) is an integer, as per our assumption of perfect hash tables working with integers, strings and tuples.

For comparing the multisets in line 16, we resort to pigeonhole sort as for Algorithm 1. Classic pigeonhole would have complexity O(#T d + p n ), where p n is the biggest prime in the list; but many holes will be unnecessary (as c(u) is necessarily prime). Using a perfect hash table that associate to the i-th prime number the integer i, one can use only n holes, one for each prime number, which reduces the complexity to O(#T d + n). Since the primes are reallocated at each level, at level d we need as many primes as there are different equivalence classes at that level -i.e. #{c(u) : u ∈ T d }. This number is ≤ #T d , therefore the complexity of the sort collapses to O(#T d ).

Conclusion

Figure 1 :

 1 Figure 1: Two isomorphic trees.

Theorem 1 (

 1 Aho, Hopcroft & Ullman). AHU algorithm runs in O(n) where n = #T 1 = #T 2 . Proof. See the proofs in [1, Example 3.2] for the whole algorithm and especially [1, Algorithm 3.2] for sorting lists S 1 and S 2 in Step 5. As stated above, Step 5 has complexity O u∈T d deg(u)

Figure 2 :

 2 Figure 2: Assigning colours to nodes in AHU algorithm. ⋆: We could have used colourbecause colours are assigned level by level and not globally. We have chosen to use another colour for the sake of clarity. In this example, the colours correspond exactly to the equivalence classes of the nodes.

Proposition 1 . 1 i.

 11 Algorithm 1 runs (i) in O #T 2 log #T using pigeonhole sort; (ii) in O(#T log deg(T )) using timsort. Proof. Fix a level d and a node u ∈ T d i . Building C c (u) requires O(deg(u)). Then, sorting C c (u) depends on the algorithm used. (i) Pigeonhole sort is done in O(deg(u)+max(C c (u))). Since the colours are attributed from 0 to W(T )-1 -recall W(T ) from (1), we have max(C c (u)) ≤ W(T ) and therefore a complexity of O(deg(u) + W(T )). (ii) The worst-case complexity of timsort is O(deg(u) log deg(u)) [4]. Notice that u∈T d i deg(u) = #T d-Recalling that line 14 is processed in O(#T d i ) via pigeonhole sort, the complexity of treating level d is O(#T d i W(T )) for case (i), and O(#T d i log deg(T )) for case (ii) -using log deg(u) ≤ log deg(T ). Summing over d leads to the result for (ii), and to O(#T W(T )) for (i).

Lemma 1 .

 1 For any tree T , W(T ) = O #T log #T .

4 P 6 Let f : 1 → 2 7 p ← 2 8do 9 Nis not defined then 11 N

 46122911 ←[START_REF] Aiolli | Fast on-line kernel learning for trees[END_REF][START_REF] Atkin | Prime sieves using binary quadratic forms[END_REF][START_REF] Azaïs | Nearest embedded and embedding self-nested trees[END_REF][START_REF] Azaïs | Detection of common subtrees with identical label distribution[END_REF][START_REF] David A Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in NC[END_REF][START_REF] Louis | A general method for solving divide-andconquer recurrences[END_REF] and N sieve ← 16 5 for d from 0 to D(T 1 ) do for i ∈ {1, 2} and u ∈ T d i sieve , P, p ← NEXTPRIME(N sieve , P, p) 12 Define f(N(u)) = p 13 c(u) ← f(N(u))14 if {{c(u) : u ∈ T d 1 }} ̸ = {{c(u) : u ∈ T d 2Suppose that each node u at level d has received a prime number c(u), assuming that all nodes at that level and of the same class of equivalence have received the same number. Then, to a node u at level d, instead of associating the multiset C c (u) = {{c(v) : v ∈ C(u)}}, we associate the numberN(u) = v∈C(u) c(v).The nodes of level d are then renumbered with prime numbers -where each distinct number N(u) gets a distinct prime. The fundamental theorem of arithmetic ensures that two identical multisets C c (•) receive the same number N(•). The pseudocode for this new version of AHU is presented in Algorithm 2.

Theorem 2 .

 2 Algorithm 2 runs in O #T log #T • M deg(T ) log #T where M(n) varies from log n to n depending on the multiplication algorithm used.

Proposition 3 . 2

 32 Algorithm 4 computes R(T ) (i) in O #T 2 using pigeonhole sort; (ii) in O(#T log deg(T )) using timsort. Let f : ∅ → 0 3 Let Q be a graph with a unique vertex 0 4 for d from 0 to D(T ) do 5 for u ∈ T d do 6

  We assume that creating a new vertex can be done in O(# C c (u)) = O(deg(u). Then, note that since we can determine whether f(C c (u) is defined in O(1) at line 8, the complexity of constructing the DAG is bounded by O u∈T deg(u) = O(#T ) (the worst case would be when all nodes of T are of different equivalence class), and can be counted independently from other steps in the algorithm.

Figure 4 :

 4 Figure4: Computation times (in log scale) for tree isomorphism using different algorithms, according to the size of the trees, with 100 replicates for each size.

Figure 5 :

 5 Figure 5: Computation times (in log scale) for DAG compression using different algorithms, according to the size of the trees, with 100 replicates for each size.

Figure 6 : 1 + 1 • a 1 + 2 • a 2 + 3 • a 3 + 4 •

 611122334 Figure 6: The smallest tree so that W(T ) = 5. We have b 3 < 5 ≤ b 4 and #T = 1 + 1 • a 1 + 2 • a 2 + 3 • a 3 + 4 • (5 -b 3 ) = 14.

Lemma 6 .

 6 ln k ∼ +∞ ln t k ∼ +∞ n ln d with d ≈ 2.955765. Proof. By definition, b n < k ≤ b n+1 and n i=1 i • a i < t k ≤ 1 + n+1 i=1 i • a i . Hence, k ∼ b n and t k ∼ n i=1 i • a i .

Corollary 1 .

 1 k = O t k ln(t k )From Lemma 3, and since x → x log x is increasing (for x ≥ 3), we get that for any tree T , W(T) = O #T log #T -hence Lemma 1 holds. Corollary 2. k ln k = O(t k ).

  . Since computing N(u) implies multiplying deg(u) primes with at most log p W(T ) bits, this lead to a complexity of O deg(u) log p W(T ) • M deg(u) log p W(T ) . Using (2) we have p W(T ) < W(T ) (ln W(T ) + ln ln W(T )). With Lemma 2, we have p W(T ) = O(#T ); thus a final complexity of O(deg(u) log #T • M (deg(u) log #T )) for computing N(u).

  Processing level d thus requiresO   u∈T d deg(u) • log #T • M (deg(u) • log #T ) + #T d   .First, notice that u∈T d deg(u) = #T d-1 . Bounding other occurrences of deg(u) by deg(T ) and summing over d leads to the claim.

Actually, in[START_REF] Godin | Quantifying the degree of self-nestedness of trees: application to the structural analysis of plants[END_REF], the authors announce a complexity of O(#T deg(T ) log deg(T )); but their proof does not exploit the fact that u∈T deg(u) = #T -1. Taking this into account, we can simplify their result and obtain exactly O(#T log deg(T )).

Acknowledgements

The author would like to thank Dr. Romain Azaïs and Dr. Jean Dupuy for their helpful suggestions on the first drafts of the article; as well as the anonymous reviewers who provided feedback on a previous version of this article.

of non-isomorphic trees of size n, and b n the number of non-isomorphic trees of size at most n -so that b n = n i=1 a i . Let n be the integer so that b n < k ≤ b n+1 . All trees with size up to n -1 are used in the construction, as well as k -b n trees of size n + 1 (no matter which ones). Therefore,

A.2 Relationships between k and t k

We require some preliminary results. We begin with the following lemma.

Proof. Obviously the sequence d n • n -α diverges, and therefore we have

, it is easy to see that the right-hand term goes to 1 as n → ∞.

. We now derive our main results. Proof. We have

First, the left-hand term tends to 1 as k → ∞. We now prove that the right-hand term tends to 0 as k → ∞. Since b n < k, we have

Notice that n i=1 i • a i ∼ nb n . By definition of ∼ and o(•) notations, for any (positive) sequences u n and v n ,

→ 0, hence the result.


Christine Faye-Dumanget

Julie Carré

Margaux Le Borgne

French Validation of Maslach Burnout Inventory-Student Survey (MBI-SS)

Keywords: Burnout, French, MBI-SS, Psychometric characteristics, Student, Validity

Introduction: Several international studies have been carried out on student burnout. To contribute to the clinical examination as well as research on the mental health of students, the MBI-SS (Maslach Burnout Inventory-Student Survey) has been validated and used in different countries but not in French. Objective: The aim of this study is to examine the validity of the three-dimensional model of the French version of the Maslach Burnout Inventory-Student Survey (MBI-SS) which is characterized by emotional "Academic Exhaustion" (EA); "Cynicism" (CY) and low scores in "Academic Efficacy" (EA). Method: 667 university students were questioned to study the three-dimensional structure of the French translation of the MBI-SS. Results and Conclusion: The results validate the three-dimensional structure of the Maslach Burnout Inventory-Student Survey (MBI-SS) and indicate satisfactory psychometric values. It is concluded that the MBI-SS can be used to assess burnout in French students.

INTRODUCTION

The transition from high school to university involves educational (course schedules, exams), social (change of living place, loss/discovery of friends) and emotional (dating, parental alienation) changes. In 2006, the World Health Organization (WHO) warned about the risks of mental distress and suicide in students and reaffirmed the need to promote their welfare when dealing with various life situations (WHO | Prévenir le suicide: ressource pour conseillers, 2006). A recent international meta-analysis showed an increase in anxiety and depression [START_REF] Ibrahim | A systematic review of studies of depression prevalence in university students[END_REF] and burnout [START_REF] Schaufeli | Burnout and engagement in university students a cross-national study[END_REF] among students. In France, many studies have shown links between stress in university students and their distress or psychological suffering [START_REF] Boudoukha | Anxiété et stress: impact de la préparation du concours de pharmacie[END_REF][START_REF] Boujut | La santé mentale chez les étudiants: suivi d'une cohorte en première année d'université[END_REF][START_REF] Lassarre | Stress des étudiants et réussite universitaire: Les conditions économiques, pédagogiques et psychologiques du succès (French)[END_REF][START_REF] Strenna | Santé psychique chez les étudiants de première année d'école supérieure de commerce: liens avec le stress de l'orientation professionnelle, l'estime de soi et le coping[END_REF]. These studies converge with those of the Student Life Observatory (OVE, 2014) and the University Preventive Medicine and Health Promotion Service [START_REF] Sumpps | Suivi des consultations du SUMPPS 2003/2013[END_REF], which report that the majority of students say they are exhausted, with data gathered from clinical interviews. However, it is not possible to specify whether this is burnout; the major dimension "emotional exhaustion" is insufficient for the assessment of burnout [START_REF] Maslach | Job burnout[END_REF].

In international research, the Maslach Burnout Inventory-Student Survey (MBI-SS) is the tool most used. Clearly, measuring burnout among students requires investigating the generalizability of burnout as operationalized by the MBI-Student Survey in French.

Definition of burnout

The concept of "burnout" was first introduced in the 1970s by Freudenberger to describe the fatigue syndrome observed among service professionals. In fact, "burnout" designates "chronic emotional and interpersonal stressors at work" (Maslach et al., 2001, p. 399). It is characterized by a multidimensional syndrome whose components are: emotional exhaustion, referring to feelings of being depleted of one's emotional resources; depersonalization, which refers to cynical or excessively detached responses to other people at work; and reduced personal accomplishment, which represents self-evaluation and refers to a lowered sense of efficacy [START_REF] Maslach | Job burnout[END_REF]. In this perspective, emotional exhaustion is the central feature and the most predictive dimension of burnout.

Burnout can be described as the smothering of a fire. People at work perceive themselves as being literally "dumped" by their work. Emotional exhaustion, which refers to feelings of being depleted of one's emotional resources, represents the basic individual stress component of the syndrome. Cynicism, as a relational dimension, is an attempt at interpersonal distancing, ignoring social conventions and common morality. The individual in difficulty or suffering from prolonged relationships with others disengages from the relationship by showing an attitude of indifference or discouragement and contempt. Finally, in connection with the other two dimensions, the individual develops a tendency to devalue his/her work and loses the sense of accomplishment and professional goals. The three dimensions interact with each other simultaneously and interdependently.

Burnout can be seen as a disengagement process because of the continued tension felt and as a state of existential loss of meaning in one's work [START_REF] Pines | Stress and burnout: The significant difference[END_REF]. On a continuum of responses, the individual who has not found or has run out of resources has the feeling of being overcome in his/her relationships due to the chronic situations he/she faces. When suffering reaches its climax, the terms "pathological burnout or burnout dysfunctional disorder" are used [START_REF] Boudoukha | Burn-out et traumatismes psychologiques[END_REF]. This can then lead to serious consequences such as difficulties in one's relationship to work (absenteeism, turnover), health problems (anxiety, depression, chronic somatic disorders, conduct disorders) or a decrease in overall life satisfaction [START_REF] Hayes | Optimism, stress, life satisfaction, and job burnout in restaurant managers[END_REF].

Measure of burnout: the Maslach Burnout Inventory (MBI)

Since the 1980s, research on burnout has been conducted empirically. Burnout has been quantitatively studied through investigation by questioning a broad range of employees in professional care (doctors, nurses), public safety (police, fire) and education (teachers and educators) because of their close relationship with and commitment to the public even when suffering. It is measured by a questionnaire of twenty-two items that uses the three-dimensional structure of the Maslach Burnout Inventory (MBI) [START_REF] Maslach | Job burnout[END_REF]. This questionnaire was first adapted specifically for service or education professions with the MBI-Human Services Survey (MBI-HSS) or the MBI-Educators Survey (MBI-ES) before being modified as the MBI-General Survey Version (MBI-GS) to be usable in all professional fields.

Replication of the research and adaptation of the inventory in many countries, including translation and psychometric studies in French [START_REF] Dion | Validation de la traduction de l'Inventaire d'épuisement professionnel de Maslach et Jackson[END_REF] and Dutch [START_REF] Schaufeli | The construct validity of two burnout measures[END_REF], showed internal consistency and construct validity similar to the original version. It was therefore used later during the training of future professionals, mainly in the care sector [START_REF] Dziegielewski | Addressing stress with social work students: A controlled evaluation[END_REF][START_REF] Le Tourneur | Burn out des internes en médecine générale: état des lieux et perspectives en France métropolitaine[END_REF].

Burnout in the student population

In recent years, the number of studies on burnout has expanded to non-occupational samples such as students and has shown that they are also subject to this phenomenon [START_REF] Campos | Adaptação transcultural Portugal-Brasil do Inventário de Burnout de Maslach para estudantes[END_REF]Capri, Ozkendir, Ozkurt, and Karakus, 2012;Galán, Sanmartín, Polo & Giner, 2011;[START_REF] Hu | The Factorial validity of the Maslach Burnout Inventory-Student Survey in China[END_REF][START_REF] Schaufeli | Burnout and engagement in university students a cross-national study[END_REF][START_REF] Walburg | Burnout among high school students: A literature review[END_REF]Watson, Deary, Thompson & Li, 2008). In fact, although being a student cannot be considered a professional status, from a psychological perspective its core activities, such as lessons and exams, are repeated stressful situations because of the expectations of academic performance. These may also be considered "work activities" [START_REF] Schaufeli | Burnout and engagement in university students a cross-national study[END_REF]. Therefore, the stress associated with burnout may also occur among students. This exhaustion has been examined in different countries using the MBI-Student Survey (MBI-SS), which is tailored to students in fifteen items assessing academic burnout in higher education. Like the MBI-General Survey used for professionals, the MBI-Student Survey retains a three-dimensional structure: Emotional Exhaustion (EE) due to the study requirements (five items such as "I feel emotionally drained by my studies"); Cynicism (CY), which refers to a detached attitude towards one's studies (four items such as "I have become more cynical about the use of my studies"); and Academic Effectiveness (AE) linked to a sense of achievement as a student (six items such as "In my opinion, I am a good student"). The assessment is carried out by the students on a six-point Likert scale ranging from 1 (never) to 6 (always).

The MBI-SS has shown satisfactory psychometric properties for the three dimensions with different student populations in different countries [START_REF] Campos | Adaptação transcultural Portugal-Brasil do Inventário de Burnout de Maslach para estudantes[END_REF][START_REF] Hu | The Factorial validity of the Maslach Burnout Inventory-Student Survey in China[END_REF][START_REF] Rostami | The psychometric characteristics of Maslach Burnout Inventory Student Survey: Among students of Isfahan university[END_REF][START_REF] Schaufeli | Burnout and engagement in university students a cross-national study[END_REF].

However, its validity has not been established among french-speaking student populations.

The aim of the current study is to validate a french version of the Maslach Burnout

Inventory-Student Survey (MBI-SS) . Indeed, having a French-speaking version of the MBI-SS is required to better evaluate the exhaustion reported by students. We hypothesize that the three-factor structure of the MBI-Student Survey, Emotional Exhaustion (EE), Cynicism (CY) and Academic Efficacy (AE), will be replicated in the French version.

METHOD

Forward and backward translation

Two translators, master students in psychology, conducted the translation and reverse translation of the English version of the MBI-SS. A French translator (native speaking French) first translated the English version into French and then a British translator (native speaking English) carried out the backward translation from French into English.

Sample

Procedure

During a pre-test phase, thirty students enrolled in or summoned to the University Preventive Medicine and Health Promotion Service (SUMPPS) completed a questionnaire including socio-demographic characteristics (age, gender and level of studies) and the French version of the MBI-SS. They were interviewed about the completion of the questionnaire and the nature of the inventory to ensure its clarity of form and content; it was clear for all of them.

For the actual research phase, education officials and teachers of each component were contacted in order to obtain authorization to intervene during lesson time. In agreement with the university schedule, we decide to administrate the questionnaires after the examination period, to avoid examination impact . The voluntary principle was explained orally to students and none refused to participate. Data were collected by self-administered questionnaire completed in the group during fifteen minutes in our presence. Questionnaires with missing values were not included in the analysis.

RESULTS

The data were first studied descriptively (Table 1) before the three-dimensional structure of the factors Emotional Exhaustion (EE), Cynicism (CY) and Academic Effectiveness (EA) was evaluated. A Confirmatory Factor Analysis (CFA), presupposing the appropriateness of the items associated with the three factors, was performed from the overall sample using the AMOS 22 computer program [START_REF] Arbuckle | IBM SPSS Amos 22 user's guide[END_REF].

Reliability analysis

Regarding internal consistency, each latent factor has a Cronbach's alpha coefficient greater than .70. Like the results of [START_REF] Schaufeli | Burnout and engagement in university students a cross-national study[END_REF], with values of 0.77 and 0.72 for the dimensions Emotional Exhaustion and Academic Efficacy, respectively, and 0.81 for Cynicism, the coefficients are above the desirable level (Nunnally, Bernstein, & Berge, 1967).

Validity analysis

First, according to the criteria of [START_REF] Weston | A brief guide to structural equation modeling[END_REF] of within ± 3 for skewness and ± 7 for kurtosis, the MBI-Student Survey French version presents a normal distribution; the coefficients of each item in the MBI-SS give values between -0.96 and 1.45 for asymmetry and between -0.97 and 1.88 for flattening.

Secondly, the results for correlational analyses (Figure 1) show a moderate positive link between the dimensions Emotional Exhaustion and Cynicism (r <0.49) and a negative one between Cynicism and Academic Efficacy factors (r > -0.58). The dimensions Emotional Exhaustion and Academic Efficacy (r <-0.2) maintain their low negative links.

Finally, as regards the loadings of the items, except for item Q13 that has a saturation <0.4 in the Emotional Exhaustion factor, the items saturate the latent factor model with values above 0.60 for the Emotional Exhaustion and Cynicism dimensions. In other words, the items heavily saturate these two dimensions [START_REF] Costello | Best practices in exploratory factor analysis: four recommendations for getting the most from your analysis[END_REF]. A Confirmatory Factor Analysis (CFA) (Figure 1) was used to test the suitability of the model on the entire sample. It was studied by several fit indices such as Chi2, the Root Mean Square

Error of Approximation or error of approximation (RMSEA) and incremental indexes: the Confirmatory Fit Index (CFI) and the Tucker-Lewis Index (TLI). With a value of 0.08 for the RMSEA and 0.8 for the CFI and TLI respectively (Table 2), the French version of the MBI-SS model has an acceptable fit [START_REF] Hu | Cutoff criteria for fit indexes in covariance structure analysis: Conventional criteria versus new alternatives[END_REF][START_REF] Schumacker | A beginner's guide to structural equation modeling[END_REF].

DISCUSSION

Burnout is a phenomenon that has been studied for decades and is well-known in the professional world. For ten years, it has also been studied with academic populations [START_REF] Walburg | Burnout among high school students: A literature review[END_REF]. This aim of this work was to examine the psychometric properties of the French version of the Maslach Burnout Inventory-Student Survey (MBI-SS).

A limitation of this study is that the students were recruited only from a university in France.

However, the French language is used in several countries and therefore it would be interesting to compare the findings of this research with those from other French-speaking areas.

Regarding reliability, our results show coefficients whose values are adequate for each of the studied dimensions. Furthermore, the factor structure of the inventory is just acceptable while its construct validity, although satisfactory, appears low. In particular, the inconclusive results

for the Academic Efficacy dimension challenge the "third dimension" of academic burnout i.e.

to experience the feeling of (in)efficacy [START_REF] Brandon Morgan | Operationalizing burnout in the Maslach Burnout Inventory-Student Survey: personal efficacy versus personal inefficacy[END_REF][START_REF] Bresó | In search of the "third dimension" of burnout: Efficacy or inefficacy?[END_REF]. Our results are quiet similar to those observed in Spanish, Portuguese or Dutch MBI-SS versions (Schaufeli, Martinez, Pinto, Salanova & Bakker, 2002) or in Chinese [START_REF] Hu | The Factorial validity of the Maslach Burnout Inventory-Student Survey in China[END_REF].

Regarding its applications, the French version of the

  667 participants aged 18-25 (mean [SD] 20.7 [1.5]) were recruited from three different components of the "Grand Ouest University" in France: Psychology (n = 233), Science and Techniques of Physical and Sports Activities (STAPS) (n = 299), and Polytechnic University (Polytech'Nantes) (n = 135). 797 questionnaires have been distributed, 130 questionnaires could not be analyzed because of missing values. The confidentiality and anonymity of participants were guaranteed by the ethical code of psychologists. The sample consisted of 343 women (51.4%) and 324 men (48.6%).

Figure 1 :

 1 Figure 1: Hierarchical structure of the MBI-Student Survey French version

Table 1 :

 1 Descriptive analysis of the Maslach Burnout Inventory-Student Survey (MBI-SS)

Table 1 :

 1 Descriptive analysis of the Maslach Burnout Inventory-Student Survey (MBI-SS)

			N							Percentiles
		Valid	Missing	Mean	SD	Asymmetry	Kurtosis Min Max	25	50	75
	EE	667	0	13.82	3.70	.57	.14	5	27 11.00 13.00 16.00
	CY	667	0	13.88	2.69	.03	.30	4	23 12.00 14.00 16.00
	EA	667	0	18.58	3.57	.26	.25	7	31 16.00 18.00 21.00

Table 2 :

 2 Confirmatory factor analysis of the tested model (N = 667).

	Model	df	2	2 /df	RMSEA	CFI	TLI
	MBI-SS	87	522.6***	6.00	0.08	0.85	0.83

une liste de sentiments et sensations que vous pouvez ressentir. Indiquez la fréquence avec laquelle vous éprouvez ce qui est proposé pour chaque phrase. Entourez la fréquence correspondante.

  Maslach Burnout Inventory-Student Survey (MBI-SS) was used to evaluate a multimodal prevention program of burnout from models based on Behavioral, Cognitive and Positive Therapies during research to develop knowledge about the mental health of students. Items de la Maslach Burnout Inventory-Student Survey (MBI-SS) • Epuisement émotionnel (EE) : 1. Je me sens émotionnellement vidé(e) par mes études 4. Je me sens à bout à la fin d'une journée à l'université 7. Je me sens épuisé(e) par mes études 10. Je me sens fatigué(e) quand je me lève le matin et j'ai à affronter une autre journée à l'université 13. Etudier ou assister à un cours m'est vraiment éprouvant • Cynisme (CY)2. Je suis moins intéressée par mes études depuis mon inscription à l'université 5. Je me sens moins enthousiaste par rapport à mes études 11. Je suis devenue plus cynique par rapport à l'utilité potentielle de mes études 14. Je doute du sens de mes études• Efficacité académique (EA)3. Je sais régler efficacement les problèmes qui arrivent dans mes études 6. Je crois que je contribue efficacement aux cours auxquels j'assiste 8. A mon avis, je suis un(e) bon(ne) étudiant(e) 9. J'ai appris beaucoup de choses intéressantes au cours de mes études 12. Je me sens dynamisé(e) quand j'atteins mes objectifs académiques 15. En cours, je me sens efficace dans mon travail

	Voici 1	2	3	4	5	6
	Jamais					Toujours
	1. Je me sens émotionnellement vidé(e) par mes études		1 2 3 4 5 6
	2. Je suis moins intéressé(e) par mes études depuis mon inscription à l'université		1 2 3 4 5 6
	3. Je sais régler efficacement les problèmes qui arrivent dans mes études		1 2 3 4 5 6
	4. Je me sens à bout à la fin d'une journée à l'université		1 2 3 4 5 6
	5. Je me sens moins enthousiaste par rapport à mes études		1 2 3 4 5 6
	6. Je crois que je contribue efficacement aux cours auxquels j'assiste		1 2 3 4 5 6
	7. Je me sens épuisé(e) par mes études			1 2 3 4 5 6
	8. A mon avis, je suis un(e) bon(ne) étudiant(e)			1 2 3 4 5 6
	9. J'ai appris beaucoup de choses intéressantes au cours de mes études Niveaux de sévérité de burnout académique		1 2 3 4 5 6
	10. Je me sens fatigué(e) quand je me lève le matin et que j'ai à • Epuisement émotionnel : affronter une autre journée à l'université Faible : [5 ; 13] 11. Je suis devenue plus cynique par rapport à l'utilité potentielle Modéré : [14 ; 22] de mes études Sévère : [23 ; 30] 12. Je me sens dynamisé(e) quand j'atteins mes objectifs académiques • Cynisme		1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
	13. Etudier ou assister à un cours m'est vraiment éprouvant 14. Je doute du sens de mes études Faible : [4 ; 10] 15. En cours, je me sens efficace dans mon travail Modéré : [11 ; 17] Sévère : [18 ; 24]		1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
	• Efficacité Académique
	Faible : [6 ; 16]
	Modéré : [17 ; 26]
	Sévère : [27 ; 36]


domain: sdv sdu shs spi

text:
Hugo De

Hugo De Vries

The European Partnership on Sustainable Food Systems in International Context

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