Antoine Montiel

Thuy Nguyen

Cindy L Rountree

Valérie Geertsen

Patrick Guenoun

Daniel Bonamy

Effect of architecture disorder on the elastic response of two-dimensional lattice materials

Keywords: numbers: 46.50.+a, 62.20.M-, 78.55.Qr Keywords: elasticity, random lattice, elastic constants, numerical simulation, beam model

à la diffusion de documents scientifiques 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.

I. INTRODUCTION

Cellular, reticulated, truss and lattice materials can exhibit remarkable stiffness-to-weight ratio [START_REF] Gibson | Cellular Solids: Structure and properties[END_REF][START_REF] Fleck | [END_REF][3][4]. Nature exemplifies this phenomenon, e.g. in the cellular structure of wood [5], trabecular bones [6], plant parenchyma [7] and sponges [8]. Aerogels, metallic foams and bioinspired lightweight cellular materials also find a broad range of applications in industry, with transportation and aerospace driving the field. Still, the large porosity of these materials inevitably causes substantial reduction in the mechanical properties. The stiffness of a stochastic foam with a relative density of 1% is about a millionth of that of its constituent material [9,10].

Recent and formidable progress in additive manufacturing and 3D printing boosted research in the field [3,4], giving way to the fabrication of high precision micro-/nanoarchitectured cellular materials of complex geometries [4]. In this context, micro-/nanolattice materials consisting of periodically arranged beams or tubes of micrometer/nanometer dimensions exhibit unprecedented stiffness-to-weight ratio [11][12][13][14][15][16]. In general, the Young's modulus, E, typically scales as the density cubed ρ 3 in foams, aerogels and other cellular materials with randomly distributed porosity [17][18][19]. On the other hand, E scales as ρ 2 in periodic hollow-tube microlattices with octahedral basic cells [11], as ρ 1.6 in octet-truss geometry [12], or even linearly with ρ for well-chosen hierarchical architectures [13,15].

The E vs. ρ scaling finds its origin in the deformation mode of the lattice [20][21][22]. When deformation is dominated by the bending of the constituent beams, E ∼ (s/ ) 4 (E ∼ (s/ ) 3 in 2D) where s and are the typical cross-sectional size and length of solid beams. When the lattice deformation arises from beam stretching or compression, E ∼ (s/ ) 2 (E ∼ s/ in 2D). Relative density goes as ρ ∼ (s/ ) 2 (ρ ∼ s/ in 2D). Hence, E ∼ ρ 2 (E ∼ ρ 3 in 2D) in bending-dominated lattices, and E ∼ ρ (likewise in 2D) in stretching-dominated lattices. To assess whether a lattice material is stretching-or bendingdominated one has to consider the collapse mechanisms in a pin-jointed structure of the same geometry [20,23]. Periodic pin-jointed structures of node connectivity Z < 6 (Z < 4 in 2D) do not satisfy Maxwell's conditions and are non-rigid [20,24]. Consequently, the deformations in the parent welded-joint lattice material are governed by the beam rotation at the nodes, and bending dominates elastic behavior. Pin-jointed frames with Z ≥ 12 (Z ≥ 6 in 2D) possess no collapse mechanism, in the sense that any deformation generates an increase of the strain energy [20,25]. They are fully-rigid, the associated lattice materials are predicted to be stretching-dominated, and the Gurtner-Durand bound provides a maximum achievable Young's modulus in isotropic structures [26]. Note that this predicts E ∼ ρ in Octet-truss lattices (Z = 12). This is in apparent contradiction with the experimental observation of E ∼ ρ 1.6 reported in Ref. [12]. This discrepancy is discussed in Ref. [12] and attributed to the hollowness of the tubes, affecting the structural integrity of the nodes and yielding an effective connectivity smaller than 12.

Finally, periodic structures of intermediate connectiv-ity 6 ≤ Z < 12 (4 ≤ Z < 6 in 2D) are referred to as periodically rigid. The pin-jointed version of these lattices obeys Maxwell conditions, but there exists at least one periodic mechanism causing them to collapse. In the Kagome structure [27], this collapse mechanism does not produce macroscopic strain [23] and the parent welded-joint lattice exhibits a stretching-dominated behavior when loaded in any direction. Conversely, the square lattice is bending-dominated when loaded in the diagonal direction. This is because its pin-jointed version collapses upon such loading.

Literature exemplifies a number of works concerning the mechanics of lattice materials with periodic (crystalline) geometries. However, only a limited number of studies examined disordered or non-periodic architectures [28][29][30][31][32][33][34]. Hence, the present study focuses on lattices with constant node connectivity, with a large range of beam aspect ratios and levels of geometrical disorder. Starting from 2D crystalline lattices, increasing levels of disorder are introduced. Subsequently, studies herein examine how this modifies their elasticity response via numerical simulations on beam networks. Sec. II presents the method. In this regard, different initial geometries are selected as representative of mechanically isotropic/anisotropic structures, and low, intermediate and large connectivity. Section IIIA analyzes the impact of disorder on the spatial distribution of stress and strain fields at the local scale, and subsequently Sec. IIIB analyzes its impact on the local compliance tensor. Special emphasize is paid to determine the correlation length associated with the spatial fluctuations, and subsequently the continuum-level scale elasticity tensor. Section IIIC concentrates on how anisotropy evolves with increasing disorder. Lastly, Sec. IIID looks at how disorder affects the elastic response over a broad range of beam aspect ratios. Additionally, it investigates how disorder affects the Young's modulus prefactor and Poisson's ratio in isotropic lattices. Section IV discusses the results, and Sec. V provides a brief conclusion.

II. SIMULATION FRAMEWORK

A. Lattice geometry

All lattice specimens studied hereafter are enclosed within disks of radius R. Starting meshes are summarized in Tab. I. Nodes are connected by elements of length and cross-section size s. Clamping conditions are prescribed at the nodes, and there is an energy cost associated with node rotation.

To gradually move from an ordered (crystalline) to a disordered (amorphous) structure, we proceeded as follow: Nodes are first placed in a 2D periodic configuration. This sets the initial crystalline lattice. Then, a tunable disorder is introduced by displacing every node by a prescribed distance u along a randomly chosen direction. Figure 1 shows a typical snapshot of a specimen obtained following this procedure. The disorder intensity is set by u, which lies in the range 0 ≤ u < 0.5 0 , so that struts cannot overlap. Three initial periodic lattices were selected: triangular lattice that is mechanically isotropic and fully rigid (connectivity Z = 6), honeycomb lattice that is isotropic and non-rigid (Z = 3), and square lattice that is anisotropic and periodically rigid (Z = 4). Henceforth, the lattice architecture is given by four control parameters: geometry (triangular, honeycomb or square), element length 0 and element aspect ratio s/ 0 in the parent crystalline lattice, and level of disorder u. The specimen size is set by the specimen radius R. In the following, 0 is chosen equal to unity and R > 30 0 .

B. Mechanical test simulation

In the following, {x, ŷ} refers to the global frame. {x l , ŷl } refers to the local frame at the considered element, so that xl and ŷl are respectively parallel and perpendicular to this element. A beam model was used to determine the lattice deformation in response to a prescribed loading. Each beam has a length , a square-section of side length s and are made of an isotropic bulk material of Young's modulus E s and Poisson's ratio ν s . The state of each node is given by three parameters: the two components of the displacement vector U and the rotation φ.

Timoshenko-Ehrenfest beam theory [35] is used to relate the axial force N , shear force V , and torque M applied on beam elements to the nodal displacements U and rotations φ. The local stiffness matrix is:

K l =          EsS 0 0 -EsS 0 0 0 12EsI (1+λ) 3 6EsI (1+λ) 2 0 -12EsI (1+λ) 3 6EsI (1+λ) 2 0 6EsI (1+λ) 2 (4+λ)EsI (1+λ) 0 -6EsI (1+λ) 2 (2-λ)EsI (1+λ) -EsS 0 0 EsS 0 0 0 -12EsI (1+λ) 3 -6EsI (1+λ) 2 0 12EsI (1+λ) 3 -6EsI (1+λ) 2 0 6EsI (1+λ) 2 (2-λ)EsI (1+λ) 0 -6EsI (1+λ) 2 (4+λ)EsI (1+λ)          (1)
where S and I are the cross-section area and moment of inertia of the beam element; λ is the shear correction factor. For square beams, S = s 2 , I = s 4 /12 and λ = (12/5)(1 + ν s )(s/ )

] = [F x l (A), F y l (A), M (A), F x l (B), F y l (B), M (B)] T is: [K l ][d l ] = [b l ]. (2)
In this setting, the subscript l refers to local quantities, the superscript T represents the transpose of a vector or matrix, and A and B refer to the edge nodes of the considered element. To construct the system of equations for the complete lattice, one needs (1) write each element stiffness matrix in the global coordinate frame (by multiplying it by the appropriate rotation matrix), and

(2) subsequently, add the element matrix in the global stiffness matrix as classically done in finite element (FE) or beam models [36]. The set of equations describing equilibrium at each node is:

[K][d] = [b], (3)
Here,

[b] = [F x (A 1 ), F y (A 1 ), M (A 1 ), F x (A 2 ), F y (A 2 ), M (A 2 ), ...] T is the load vector, [d] = [U x (A 1 ), U y (A 1 ), φ(A 1 ), U x (A 2 ), U y (A 2 ), φ(A 2 ), .
..] T is the global displacement vector, and [K] is the global stiffness matrix.

Loading is applied by imposing a displacement on the boundary nodes [Fig. 1]. A loading direction θ load with respect to x is prescribed. Imposed displacement is then set to unity along this direction, and decreases as a cosine law as the considered direction departs from θ load :

U(M b ) = Ûtens/shear cos(θ b -θ load ), (4)
where (r b , θ b ) are the polar coordinates of the considered node M b along the specimen boundary. Ûtens and Ûshear are unit vectors parallel and perpendicular to θ load , and are associated with tension and shear loading, respectively. This cosine variation allows a minimization of the impact of boundary discreetness on the stress and strain fields in the bulk lattice. The loading conditions above are implemented in Eq. 3, by setting F(M b ) = U(M b ) in {b} at the appropriate places and replacing the corresponding blocks in the stiffness matrix [K] by identity matrix blocks. The final set of equations is solved by inverting the stiffness matrix, using sparse Cholesky decomposition to speed up the process. This provides the displacements U(M) and rotation φ(M) of each node M in the loaded lattice.

C. Local stress and strain computation

The next step determines the continuum stress and strain fields in the sample. For this, we draw inspiration from methods developed to study granular flows [37,38]. Voronoi tessellation associates a continuum elementary volume to each node M of the lattice. At each location (x, y) within the Voronoï polyhedron P vor (M) centered on M, the local stress tensor σ is:

σ = 1 2S vor s p F Mp→M ⊗ (x(M) -x(M p )) , (5)
where S vor is the area of the Voronoï polyhedron, M p are the nodes connected to M, x(M p ) and x(M) are the position of M and M p , F Mp→M is the force applied by the beam connecting M and M p to M, and ⊗ is the vector dyadic product. A best-fit algorithm then determines the local strain tensor on the same Voronoi polyhedron. The components e ij = ∂U i /∂x j of the displacement gradient tensor are prescribed so that they minimize:

χ i = p (e ij (M) (x j (M p ) -x j (M)) -(U i (M p ) -U i (M))) 2 , (6)
where indices {i, j} ∈ {x, y}. Einstein summation convention is used here on repeated indices. The components of the strain tensor are:

ij (M) =

III. RESULTS

A. Spatial distribution of local stress and strain tensors: influence of disorder

Figure 2 shows local stress and strain maps for a periodic square lattice loaded in tension along x axis. Note that σ xy (x, y) = σ yx (x, y) everywhere, as expected for a Cauchy stress tensor. This is always observed, regardless of the lattice geometry and amount of disorder introduced. Note also that σ xx is two orders of magnitude larger than σ xy and σ yy . This is due to the fact that Poisson's ratio ν xy in a square lattice is equal to zero [START_REF] Gibson | Cellular Solids: Structure and properties[END_REF].

Here we use the notation ν xy rather than ν to emphasize that square lattices do not exhibit isotropic elasticity response, but orthotropic one (see next section). Note finally that σ xx (x, y) is proportional to xx (x, y) everywhere. The prefactor gives the Young modulus of the lattice measured along x. It is equal to E x = E s s/ 0 = 1/8, as expected for a square lattice [START_REF] Gibson | Cellular Solids: Structure and properties[END_REF].

Figure 3 presents typical snapshots of the components of local stress and strain tensors in a disordered square lattice. Large spatial inhomogeneities are clearly visible. Note in particular the chain-like structure of the most stressed zones in the top, left panel of Fig. 3. These resemble force chains observed in granular media [39]. Chain-like structures are less visible in the strain maps where heterogeneities take the form of relatively isotropic spots [Fig. 3, top, right panel]. Sec. IIIB takes a closer look at fluctuations to infer relevant length scales which aid in defining a representative elementary volume (REV). Averaging such maps over many configurations of same loading, initial crystal geometry and amount of disorder u (but different realizations) allows smoothening the high frequency fluctuations and reveals the large scale spatial variations of stress and strain fields [Fig. 4]. The configuration-averaged maps obtained in presence of disorder are significantly different from the maps observed in the pristine crystalline lattice, which show that the introduced disorder changes the elasticity constants.

B. Spatial distribution of local elasticity constants: on the RVE scale

The next step is to determine the relevant constants to characterize the elastic response of the lattice at local scale. Using Voigt notation, stress and strain components under plane stress assumption are related via:

where the symmetric compliance tensor, S, fully characterizes the material elasticity. For isotropic materials such as triangular and honeycomb lattices, S iso is given by:

S iso =   1 E -ν E 0 -ν E 1 E 0 0 0 2(1+ν) E .   (9)
The elasticity response is fully characterized by two constants: the Young's modulus E and Poisson's ratio ν.

For orthotropic materials such as square lattices, S ort is given by:

S ort =    1 Ex -νyx Ey 0 -νxy Ex 1 Ey 0 0 0 1 G    , with -ν yx E y = -ν xy E x (10)
The elasticity response is fully characterized by four constants: Young's moduli E x and E y along the x and y axis, Poisson's ratio ν xy , and the shear modulus G. Note that in square lattices, E x = E y and only three of the sought constants S kl are required.

In the most general situation of disordered architectures, the six constants, S kl of the compliance tensor should be determined. As Eq. 8 only provides three independent equations, a single test is not sufficient to determine them [40]. Hence, for each specimen studied, six different tests were performed: three tensile tests and three shearing tests. For these tests, the imposed external displacements are given by Eq.

Such homogenization methods are classically used, in FEA, to determine the homogenized elastic constants of complex materials such as composites [41]. Figure 5 displays typical maps S kl (x, y) obtained in a disordered square lattice (same lattice material as in Fig. 3). Note the large spatial variations observed on the S kl maps. Ensemble averaging over 100 samples allows decreasing spatial variability [Fig. 6]. Still, the maps continue to present the same visual aspects: Except for the edges, these maps are statistically spatially homogeneous, with localized spots uniformly distributed. Note the absence of spatial variations at large wavelength (continuum-level scale), as expected for material constants and contrary to what is observed on the ensemble averaged stress and strain maps [Fig. 4] To characterize the typical size of the random spots observed in the maps of Fig. 5, we compute the radial correlation function g kl (r):

kl (r) = Skl (r 0 + rê θ ) Skl (r 0 ) S2 kl (r 0 + rê θ ) S2 kl (r 0 ) , ( 12
)
where Skl (r 0 ) = S kl (r 0 ) -S kl and denotes averaging over all positions r 0 and subsequently over all direction êθ . S is the global compliance tensor calculated with averaged stress σ and strain

. By analogy with S, g kl (r) forms a symmetric radial correlation matrix g(r). Figure 7 presents the variation of its Euclidean norm, g(r) = ||g(r)||, as a function of r at increasing disorder u. Very rapidly, g(r) drops to zero. Fitting these curves by an exponential function g(r) = exp(-r/l c ) allows defining a correlation length, l c . Its evolution with u is shown in Fig. 8 in the different geometries studied. It is measured to be ∼ 0 in all cases except the disorder-free square lattice, where l c 3 0 .

A priori, the knowledge of l c allows setting a REV size l REV : Calling N = l REV /l c , one can split the REV into n = N d elementary cells (d = 2 in 2D, d = 3 in 3D) where the quantity of interest is independent and identically distributed (i..i.d.). Calling σ the standard deviation of this quantity over one elementary cell, the central limit theorem tell us that the standard deviation of the same quantity over the REV goes as σ/ √ n = σ/(l REV /l c ) d/2 . As a result, a given quantity coarse-grained over the REV will typically exhibit typical fluctuations that decrease as l c /l REV in 2D (or (l c /l REV ) 3/2 in 3D). Additional work (see appendix A for details) also shows that when REV size is equal to 4 0 then global compliance tensor can be calculated directly from macroscopic stresses and strains or alternatively from the averaging of local compliance tensor on REV cells. As will be discussed in Sec. IV A, this condition does not imply that the elastic constants are independent of specimen size. In fact, a much larger REV should be prescribed to ensure that these elastic constants are bulk material constants (Sec. IV A and Fig. 14)

The next section analyzes the global compliance tensor S for different levels of disorder and a large range of aspect ratios.

C. Anisotropy of elasticity response: influence of disorder

This section takes a look at how disorder affects the anisotropy of the elasticity response. Initially the global compliance tensor S is calculated. Next the effective compliance tensor S ef f is defined as: Honeycomb-based (red ), square-based (green ), and triangular (blue ). Here, beam aspect ratio is s/ 0 = 1/8 and specimen size is R = 40 0. u is expressed in 0 units. In all the curves, UAI has been obtained from the analysis of a single specimen. Black in inset shows the result obtained after having averaged over 100 configurations in a square-based lattice with u = 0.3. u is expressed in 0 units. This tensor meets the requirement that S = S ef f in mechanically isotropic materials. Lastly, the Universal Anisotropy Index (U AI) is defined by analogy to the Zener index which is limited to the cubic crystals case [42]:

S ef f =    S11+S22 2 S 12 0 S 12 S11+S22 2 0 0 0 S11+S22+S44-2S12 2    (13
U AI = ||S ef f -S|| ||S ef f || (14)
It quantitatively defines how close S is to S ef f . Indeed, with this definition, if the elastic material is isotropic then U AI = 0, otherwise U AI > 0. Moreover, as U AI increases, the anisotropy increases. Figure 9 presents the evolution of U AI with disorder intensity for the three studied geometries. In absence of disorder, U AI = 0 in honeycomb and triangular lattice and these lattice materials obey isotropic elasticity, as expected. Increasing disorder has nearly a null effect on the anisotropy index of the already isotropic materials. The largest value in this context is U AI = 5.7%, which is observed in the honeycomb lattice at maximum disorder (u = 0.45 0 ). Conversely, in absence of architecture disorder, the square lattice is highly anisotropic, with U AI = 97%. In this case, increasing architecture disorder significantly improves the elasticity isotropy, and Here, specimen size is R = 32 0. G is expressed in Es units and u is expressed in 0 units.

U AI is nearly half the initial value, ∼ 58%, for the maximum disorder intensity.

D. Elasticity versus aspect ratio scaling: effect of disorder on material stiffness

Now let us shift to understanding how the material lattice compliance depends on the beam aspect ratio and disorder. Figure 10 presents the shear modulus G = E s /S 44 as a function of the aspect ratio s/ 0 for increasing disorder levels in the three investigated geometries (honeycomb, square, and triangular). In absence of disorder, the elasticity constants can be determined theoretically (Table II and Ref. [START_REF] Gibson | Cellular Solids: Structure and properties[END_REF]), and the values from the simulations match theoretical predictions.

In honeycomb-based lattices, G ∼ (s/ 0 ) 3 (that is G ∼ ρ 3 ) independent of the disorder level. This is expected, as the node connectivity (Z = 3) does not satisfies Maxwell's condition for rigidity. Hence, bendingdominated deformations dominate and elastic modulus scale as (s/ 0 ) 3 [20].

Similar to honeycomb-based lattices, increasing disorder does not modify the scaling G ∼ s/ 0 in triangularbased lattices. In these cases, Z = 6, which ensures that the pin-jointed version of the lattice is fully rigid; hence G ∼ s/ 0 [20].

The behavior of square-based disordered lattices is surprising. As disorder is introduced, the coexistence of two distinct scaling regimes is observed: G ∼ s/ 0 at small aspect ratios and G ∼ (s/ 0 ) 3 at large ones. On the contrary, a similar transition is not observed for E x = E s /S 11 whose scaling exponent increases from 1 to 1.38 as disorder is introduced. But this change happens with a unique regime (Fig. 11).

All but the square-based lattices are mechanically isotropic. Hence, the elasticity behavior is fully characterized by two constants: Young's modulus and Poisson's ratio. Figure 12(a) (resp. Figs. 12(b)) presents E/(s/ 0 ) 3 (resp. E/(s/ 0 )) versus s/ 0 for increasing architecture disorder in honeycomb-based lattices (resp. in triangular-based lattices). In absence of disorder, the

Lattice geometry

Honeycomb Square Triangular Density (ρs

) ρ = (2/ √ 3)(s/ ) ρ = 2s/ ρ = 2 √ 3(s/ ) Young's modulus (Es) E = (4/ √ 3)(s/ ) 3 Ex = Ey = s/ E = (2/ √ 3)(s/ ) Poisson's ratio ν = 1 ν = 0 ν = 1/3 Shear modulus (Es) G = (1/ √ 3)(s/ ) 3 G = (1/2)(s/ ) 3 G = ( √ 3/4)(s/ )
TABLE II. Elasticity constants in 2D crystalline lattices in absence of introduced disorder (from [START_REF] Gibson | Cellular Solids: Structure and properties[END_REF]).

curves coincide with the theoretically predicted value (Tab. II) in the limit of slender beams (i.e. s 0 ). The plateau departure observed at larger s/ 0 is also fully consistent with the theoretical corrections provided in [29,43] for thicker beams. In bending-dominated lattice (honeycomb-based lattice), increasing disorder stiffens the material and increases E/(s/ 0 ) 3 by ∼ 40% for the maximum disorder (u = 0.45 0 ), see Fig. 12(a). This variation is qualitatively consistent but quantitatively more pronounced than what is reported in the literature [29,32,44,45]. The root cause of these differences lies with how disordering occurs, by displacing randomly the points, the Voronoi tessellation of which provides the initial periodic honeycomb lattice. In stretchingdominated lattices (triangular-based lattices), increasing disorder yields softening effect and decreases E/(s/ 0 ) by respectively ∼ 8% and ∼ 12% for maximum disorder (Fig. 12(b)). This is consistent with the finite element observations reported in [31] on imperfect triangular lattices.

Figure 13 shows the variations of Poisson's ratio, ν, as a function of s/ 0 for the honeycomb-(panel (a)) and triangular-based (panel (b)) lattices. Like E versus s/ 0 curves (and probably for the same reason), plateaus occur for s/ 0 0.1, and a departure exists for higher values. In honeycomb-based lattices, ν starts from the theoretically predicted value ν = 1 in absence of disorder, and decreases to ν 0.78 as disorder increases to u = 0.45. This decrease is significantly larger than that reported in Refs. [29,44,45]. In triangular-based lattices, ν starts at the theoretically predicted value ν = 1/3 and increases up to ν 0.42 as disorder level increases to u = 0.45.

IV. DISCUSSION AND ANALYTICAL ANALYSIS

This numerical study was designed to shed light on how the introduction of disorder in the architecture of lattice materials modifies their elasticity response. In this context, we derived and validated a novel procedure to determine the spatial distribution of Hooke's softness tensor at the local (joint) scale in 2D beam networks of prescribed architecture. Introducing disorder yields large spatial variations for local elasticity constants. Nevertheless, the correlation length associated with these spatial variations is small, approximately the beam length. Averaging them over the specimen provides an accurate estimation of the continuum-level scale values.

A first effect of disordering is to promote elasticity

/ 0) = (2 √ 3) × (1 + s 2 / 2 0 )/(3 + s 2 / 2 0 ) [43].
Here, specimen size is R = 40 0. E is expressed in Es units and u is expressed in 0 units. isotropy when the parent crystalline architecture exhibits anisotropic elasticity (Fig. 9). This is expected since increasing disorder attenuates the rotation axis inherent to the pristine crystalline lattice and makes it more and more statistically invariant upon rotation.

Beyond isotropy, introducing disorder modifies the continuum-level (global) scale elastic constants in a way that depends deeply on the parent periodic geometry and connectivity. In summary: I In lattices of high and low connectivity like triangular-based and honeycomb-based ones respectively, increasing disorder does not modify the scaling between elastic modulus and s/ 0 (or equivalently ρ): E ∼ s/ 0 in highly connected lattices (Z = 6) and E ∼ (s/ 0 ) 3 in weakly connected ones

ν = (1/3) × (1 -s 2 / 2 0 )/(1 + s 2 /3 2 0 ) [43].
Here, specimen size is R = 40 0. u is expressed in 0 units.

(Z = 3), no matter how much disorder is introduced.

II Increasing disorder softens highly connected (triangular) lattices; the prefactor, E/(s/ 0 ) decreases with the amount of disorder, u.

III Increasing disorder stiffens weakly connected (honeycomb) lattices, with a prefactor, E/(s/ 0 ) 3 decreasing with u.

IV Introducing disorder in lattices of intermediate connectivity like square-based ones (Z = 4) dramatically modifies the scaling between shear modulus and s/ 0 . Indeed, in the absence of any disorder, G ∼ (s/ 0 ) 3 over the whole range, but a novel scaling regime G ∼ s/ 0 ocurs at small s/ 0 values as soon as disorder is introduced.

On the effect of disorder on E vs. s/ scaling at low and high connectivity

As already mentioned in Sec. III.D, observation I is explained by the fact that introducing disorder, here, does not change lattice connectivity. In disordered triangular-based lattices, the connectivity is always sufficient (Z ≥ 6) to prevent collapsing mechanisms in the pin-jointed version; hence deformations, are always stretching-dominated [20]. Similarly, in honeycombbased lattices, Z = 3 no matter how much disorder is introduced; Maxwell's criterion for stability is not fulfilled and, as such the structure remains bending-dominated at any value u.

A. Local vs global elasticity constants in disordered lattices

Observations II and III are more counter-intuitive. In particular, observation II is opposite to what would have been analytically predicted for local elastic modulus, at the cell scale, after averaging over disorder configurations (Appendix B). This highlights that, as soon as disordered lattices are considered and irrespectively of the amount of disorder (even for arbitrary small ones), spatial correlation in stress redistribution should be taken into account and a large enough specimen should be defined. Figure 14 shows how the prefactor E/(s/ 0 ) (resp. E/(s/ 0 ) 3 ) evolves with the specimen radius R in disordered triangular-based (resp. honeycomb-based) lattices. Specimens of radius R > 30 0 should be prescribed to ensure that the determined elasticity moduli are truly material constants, independent of R.

B. On the origin of disorder-induced softening in stretching-dominated lattices

Because of the nonlocality mentioned in the previous section, observation II is extremely difficult to rationalize quantitatively. It has been shown in Ref. [26], that the stiffness of stretching-dominated lattices decreases when geometrical disorder yields non-affine strain fields. Here, we propose an alternative explanation and argue that the observed softening is due to the increase of mean beam length as disorder increases. The stretching force applying onto the considered beam is F = σ sF(θ) where θ is the typical angle between two joint beams and F(θ) is the typical distance separated two successive vertically stretched beams. In response to this stretching force, each edge of the beam moves over a distance δ. Thick black vertical plain line and dotted black inclined lines present the considered beam and two jointed ones before the lattice deformation while gray vertical thick plain line and gray dotted inclined lines show the same beams after deformation.

To some extent, this can be rationalized by considering a given beam, OM, and a constant compressive stress σ applying parallel to it OM (Fig. 15). The force F applying at each edge of the beam is F = σ sF(θ) where is the beam length, θ is the typical angle between two joint beams (considered to be the same everywhere, e.g. θ = π/6 in disorder-free triangular lattice), and F(θ) is the typical distance separating two successive beams compressed by σ (Fig. 15). Each node, O and M, moves by δ = F /E s s 2 = σ 2 F(θ), due to beam contraction. This yields a strain = δ/ = σ F(θ)/E s s. Finally, Young's modulus E (str) = σ/ is given by:

E (str) = E s s F(θ) (15)
Now, disorder is introduced on edge position: x(M) = x 0 (M) + uη(M), where η(M) is given by: (16) where θ M and θ O are two angles selected randomly between -π and π. This yields fluctuations of the beam 0.0 0.1 0.2 0.3 0.4 0.5 u 1.04 1.06 1.08 1.10 1.12 1.14 16. (color online) Young's modulus prefactors for triangular lattices computed numerically (black triangles) and estimated through analytical second order's expansion (Eq. 18), with

η(M) = x(cos θ M -cos θ O ) + ŷ(sin θ M -θ O ),
E(l/s) Numerical Analytical FIG.
E (str) 0 = 2 √ 3s/ 0 (Tab. II).
length, which, to second order terms in u, now writes

= 0 + uη y (M) + u 2 η 2 x (M)/(2 0 ) + o(u 2 / 2 0
). As a result, the strain also fluctuates in space. By averaging over different configurations {θ O , θ M }, one gets = σ F(θ)/E s s, and the effective Young's modulus becomes:

E (str) = E s s F(θ) (17)
To the second order in u, the mean beam length is (u) = 0 + 1/2u 2 / 0 + o(u 2 / 2 0 ), and finally:

E (str) (u) = E (str) 0 1 - 1 2 u 2 2 0 + o u 2 2 0 (18)
As shown in Fig. 16, this analytical estimate is consistent with numerical observations in triangular-based disordered lattices, as least as long as u is not too large.

C. On the origin of disorder-induced stiffening in bending-dominated lattices A priori, the same argument can be applied to bending-dominated lattices. As E bnd ∼ (s/ ) 3 , this would yield E bnd (u) = E bnd 0 (1 -3/2u 2 / 2 0 + o(u 2 / 2 0 ); hence, the lattice would have been expected to soften as disorder increases. Observation III is the opposite.

We argue that the disorder-induced stiffening observed in bending-dominated lattices translates the fact that, in any bending-dominated lattice, part of applied stress is accommodated by beam stretching. Indeed, as force applied on a given node, its projection parallel to the considered beam yields beam dilation or stretching while the part perpendicular to this beam yields bending. As disorder increases, the relative importance of the stretching part increases. Assuming that the lattice deformation due to strecthing are negligible with respect to those due to bending, the total lattice deformation is fully governed by the part of applied stress accomodated by beam bending, only. Then, as the Young's modulus E (bnd) is set by the total force over the total deformation ratio, E (bnd) is set by the total force over effective bending force ratio, which increases as disorder increases.

D. On the two elasticity scaling regimes in disordered square lattices

As in honeycomb-based bending-dominated lattices, the appearance of two scaling regimes in the G vs. s/ curves (Fig. 10b) in disordered square lattice is also attributed to the fact that an increasing proportion of applied shear stress is accommodated via latttice stretching as introduced disorder increases. In this specific case, this can be rationalized as follow.

Let us first consider the case of disorder-free square lattice loaded by a constant shear stress, τ , applied perpendicularly to a given beam OM (Fig. 17). Force F exerted on node M is F = τ s , and it applies perpendicular to the beam. Due do beam bending, M moves over a distance δ = F 3 /(E s s 4 ) = τ 4 /(E s s 3 ). O moves along the opposite direction over the same distance, and the resulting elementary shear deformation γ = 2δ/ = τ 2 3 /E s s 3 is:

γ = 2 3 E s s 3 τ (19)
Let us now introduce disorder on edge positions. This yields fluctuations on the angle θ between OM and the vertical to applied shear (Fig. 17b). As a result F , is not perpendicular to OM anymore. The perpendicular component T = F cos θ makes the beam bend and M moves over a distance δ T = F cos θ 3 /(E s s 4 ) along a direction perpendicular to OM; the parallel component N = F sin θ makes the beam stretch and M moves over a distance δ N = F sin θ /(E s s) in a direction parallel to OM. The former implies a bending-induced elementary shear deformation γ (bnd) = δ T cos θ/ = 1/2τ cos 2 θ 3 /(E s s 3 ); the latter implies a shear-induced elementary shear deformation γ (str) = δ N sin θ/ = 1/2τ sin 2 θ /(E s s).

Let us now assume that disorder is introduced by moving lattice edge over a random displacement as stipulated in Eq. 16. To the second order in u/ 0 , cos 2 θ = 1 -1/2η FIG. 17. (color online) (a) Sketch of beam deformation in a square lattice loaded under a shear stress τ . Due to the shear, the force applying onto the considered beam is F = τ . In response to F , the beam bends and its two edges moves over a distance δ. Thick black vertical plain line and dotted black inclined lines present the considered beam and two jointed one before the lattice deformation while gray vertical thick plain line and gray dotted inclined lines show the same beams after deformation. (b) Due to disorder, the considered beam makes now an angle θ with respect to the perpendicular of shear. Applied force F then splits into a component T perpendicular to the beam and a parallel one, N . The former makes the beam bend and its two edges move over a distance δT and the former makes the beam stretch and its two edges move over a distance δN .

γ (bnd) (u) = τ 2 E s 3 0 s 3 1 - 1 2 u 2 2 0 + o u 2 2 0 γ (str) (u) = τ 2 E s 0 s 1 2 u 2 2 0 + o u 2 2 0 (20
Finally, the averaged shear-induced and bending-induced elementary shear moduli G (str) = τ /γ (str) and G (bnd) = τ /γ (bnd) become:

(bnd) (u) = E s 2 s 3 3 0 1 + 1 2 u 2 2 0 + o u 2 2 0 G (str) (u) = E s s 0 u 2 2 0 + o u 2 2 0 ( 21
)
The difficulty is to go from these local, configurationaveraged, shear moduli to the global specimen-scale shear moduli, G (sq) . As discussed in Sec. IV A, this upscaling is not trivial and cannot be obtained quantitatively via the simple addition of the two contributions. Still, making G (sq) = G (bnd) + G (str) allows reproducing at least qualitatively the observed features: When s/ u/ , G (str) (u) G (bnd) (u) and G (sq) (u) ≈ G (str) (u) ∼ s/ ; conversely, when s/ u/ , G (str) (u) G (bnd) (u) and

G (sq) (u) ≈ G (bnd) (u) ∼ s 3 / 3
. This qualitatively explain observation IV and Fig. 10b, with a linear scaling regime G ∼ s/ at small aspect ratios, a cube scaling regime G ∼ s 3 / 3 at large aspect ratios, and a crossover aspect ratio increasing as disorder increases. Actually, as shown on Fig. 18, all the numerical curves obtained in disordered square lattices are reproduced quantitatively using a weighted sum:

G (sq) (u) = (1 -αu 2 )G (bnd) (u) + αu 2 G (str) (u) (22)
with α 0.1.

V. CONCLUSION

The series of simulations reported here investigated how the introduction of disorder modifies the elasticity behavior of 2D lattice materials of various architectures. A procedure inspired from the modeling of granular systems has been developed to determine the map of the full elasticity tensor at the local scale. This procedure has been validated via comparisons with theoretical results known for pure crystalline lattices. Introducing disorder has the disadvantage of generating important spatial fluctuations on these elastic constants. Nevertheless, the associated correlation length remains small, on the order of the beam length . Averaging over the specimen provides an accurate determination of the continuum-level scale elasticity constants (compliance tensor).

First, as demonstrated here on 2D square-based lattice materials, introducing disorder in a crystalline architecture of initial anisotropic elasticity promotes elasticity isotropy. Note that, while there are elastically isotropic crystalline architectures in 2D (e.g. the triangular or honeycomb lattice studied here), this is no longer the case in 3D [42]. Lattice structures with isotropic elasticity are important for many applications and, as such, are the subject of several works [26,[46][47][48][49]. Introducing disorder in a tunable way as proposed here may offer a promising route to this aspect.

Second, introducing disorder softens highly-connected stretching-dominated lattice materials. This observation is somehow counter-intuitive since a simple argument, based on the analysis of the elastic energy stored in an elementary cell of the parent crystalline lattice and the evolution of this configuration-averaged energy in presence of disorder would have predicted the opposite (appendix B). This highlights the importance of nonlocality (and the induced difficulty to anticipate the effect of disorder) on the elasticity properties of lattice materials. This also relates to previous studies [26] that evidence correlations between network stiffness and disorder-induced non-affine strain fields in stretching-dominated lattices.

Third, introducing disorder helps stiffening low connectivity bending-dominated lattice materials. The effect is quite small in honeycomb lattices: elastic modulus varies as the cube of density (driven by changing the beam aspect ratio) regardless of the disorder level, and disorder only plays on the prefactor, which increases by ∼ 40%. On the other hand, the effect is drastic in squarebased lattices. In this scenario, stiff regime (linear scaling between shear modulus and density) is observed at low density, whilst the soft regime observed in absence of disorder (cubic scaling between shear modulus and density) is only recovered at large density. Additionally, the crossover density between these two regimes is selected by the disorder level. We conjecture that similar features will be observed in any lattices where connectivity is too low to ensure full structure rigidity (Z < 6 in 2D, Z < 12 in 3D), but large enough to get rigid local cells (Z > 3 in 2D, Z > 4 in 3D).

On-going work aims at assessing this conjecture. If this were the case, modulating spatially the disorder introduced in an initially crystalline architecture would provide a promising way to obtain meta-composites made of soft and stiff zones, the spatial entanglement of which could be arranged. This may allow the design of novel architectures for materials with both large stiffness and energy-absorbers, which are a priory antagonist. Here, beam aspect ratio is s/ 0 = 1/8 and specimen size is R = 32 0. u is expressed in 0 units.

(and not 1/2) in Eq. B2 that comes from the fact that the energy of each beam equally splits in the two Voronoi cell associated to each edge. as strain ij are uniform: This compliance matrix is that of a linear elastic isotropic material of Young's modulus and Poisson's ratio given by:

U i (p) = ij x j (p), (
E 0 (tr) = 2 √ 3 E s s 0 , ν 0 (tr) = 1 3 (B7)
Now, disorder is introduced on the positions: x(p) = x0 (p) + uη(p) where η(p) is given by Eq. 16. These changes are introduced in Eq. B5 and the compliance matrix is deduced: where Voight notation has been used and S vor has been assumed to remain unchanged by the disordering procedure. After expanding to second order in u/ 0 and subsequently averaging over disorder configurations so that η x = η y = η x η y = 0 and η 2

x = η 2 y = 1, we get: This increase is opposite to the decrease observed for global (specimen-scale) Young's modulus (Fig. 16). Note that Eq. B3 assume uniform strain at the local scale, which is not true in the presence of geometrical disorder [26].

C(tr|u) = 3 4 √ 3 E s s 0   3

FIG. 1 .

 1 FIG. 1. (color online) Square lattice disordered by displacing randomly every node by a prescribe distance u = 0.3 0 along a randomly chosen direction. Tensile loading (Thick horizontal blue arrows) is applied by imposing a prescribed displacement U(M b ) at every node M b on the lattice boundary (cosine dependency, see Eq. 4).

1 2 (FIG. 2 .

 122 FIG. 2. (color online) Maps of local stress and strain in a square lattice in absence of architecture disorder. The eight panels correspond to the σxx, σxy, σyx and σyy (left column), and xx, xy , yx and yy (right column). ij are expressed in 0/R units and σij are expressed in Es 0/R units. Horizontal tensile loading is imposed by prescribing the displacement at the boundary nodes according to Eq. 4 with θ load = 0. In this simulation, s/ 0 = 1/8 and the specimen size is R = 50 0.

FIG. 3 .

 3 FIG. 3. (color online) Maps of local stress and strain in a disordered square lattice (disorder intensity: u = 0.3 0, beam aspect ratio s/ 0 = 1/8, specimen size R = 50 0). The eight panels correspond to the σxx, σxy, σyx and σyy (left column), and xx, xy , yx and yy (right column). ij are expressed in 0/R units and σij are expressed in Es 0/R units. Horizontal tensile loading is imposed by prescribing the displacement at the boundary nodes according to Eq. 4 with θ load = 0.

FIG. 4 .S 11 S

 411 FIG. 4. (color online) Ensemble averaged maps of local stress (left column) and strain (right column) in a disordered square lattice (disorder amount: u = 0.3 0, beam aspect ratio s/ 0 = 1/8, specimen size R = 50 0). The average was taken over 100 samples with same loading and u, but different disorder realizations. The eight panels correspond to the σxx, σxy, σyx and σyy (left column), and xx, xy , yx and yy (right column). ij are expressed in 0/R units and σij are expressed in Es 0/R units. Horizontal tensile loading is imposed by prescribing the displacement at the boundary nodes according to Eq. 4 with θ load = 0.

  4 and θ load = {0, π/4, π/2} (square-based lattices) or θ load = {0, π/3, π/2} (triangular-and honeycomb-based lattices). Each test p provides maps of local stress σ (p) ij (x, y) and strain

2 + p 2

 22 (p) ij (x, y). Hence, Eq. 8 provides at each location (x, y) 18 relations between(p) ij and σ (p) ij . These relations involve the six S kl constants needed. The best-fit procedure provides them such that the following equation is minimized for each constant: χ = p (p) xx -S 11 σ (p) xx -S 12 σ (p) xx -S 14 σ (p) yy -S 12 σ (p) xx -S 22 σ p xx -S 24 σ (p) xy (p) xy -S 14 σ (p) xx -S 24 σ (p) xx -S 44 σ (p) xy 2

  FIG. 5. (color online) Maps of local compliance tensor S in a disordered square lattice (disorder amount: u = 0.3 0, beam aspect ratio s/ 0 = 1/8, specimen size R = 50 0). The six panels correspond to the six components S11, S12, S22, S22, S24, S44 [Eq. 8]. They are all expressed in Es units.

24 FIG. 6 .

 246 FIG.6. (color online) Ensemble averaged maps of local compliance tensor S in a disordered square lattice (disorder amount: u = 0.3 0, beam aspect ratio s/ 0 = 1/8, specimen size R = 50 0). The average was taken over 100 samples of different disorder realisations. The six panels correspond to the six components S11, S12, S22, S22, S24, S44 (Eq. 8). They are all expressed in Es units.

  g

45 FIG. 7 .FIG. 8 .FIG. 9 .

 45789 FIG. 7. (color online) Radial correlation function g(r) at 6 increasing disorder u in honeycomb-based (panel a), squarebased (panel b), and triangular-based (panel c). r and u are expressed in 0 units. Here, beam aspect ratio is s/ 0 = 1/8 and specimen size is R = 40 0.

45 FIG. 10 .

 4510 FIG. 10. (color online) Shear modulus G as a function of beam aspect ratio s/ 0 with increasing disorder u in honeycombbased lattices (panel a), square-based lattices (panel b), and triangular-based lattices (panelc). In all panels, axes are logarithmic. In panels (a) and (c), blue (dark gray) curve correspond to u = 0 (no disorder) and red (light gray) curve corresponds to u = 0.45 (maximal disorder). In these two panels, the introduction of disorder does not affect the scaling exponent, which remains equal to 3 in honeycomb-based (panel (a)), and to 1 in triangular-based lattice (panel (c)). Conversely, the introduction of disorder affect the scaling in square-based lattice (panel (b)), and the two scaling exponents are observed: 1 at small aspect ratios and 3 at large ones. The different colors correspond to different levels of disorder u (see caption in panel (b)). Here, specimen size is R = 32 0. G is expressed in Es units and u is expressed in 0 units.

45 FIG. 11 .

 4511 FIG. 11. (color online) Young's modulus along the x-axis Ex as a function of beam aspect ratio s/ 0 for increasing disorder u in the square-based lattices. The different curves correspond to different values u: u = 0 for the blue (upper) curve and u = 0.45 for red (lower) curve. Here, the specimen size is R = 32 0. Ex is expressed in Es units and u is expressed in 0 units.

FIG. 12 .

 12 FIG. 12. (color online) Prefactor of scaling E ∼ (s/ 0) n as a function of beam aspect ratio s/ 0 for increasing disorder u in honeycomb-based lattices (panel a, n = 3) and triangular-based lattices (panel b, n = 1). The different colored curves correspond to different values u according to the legend provided in panel c. Thick dash gray curve in panel a is the theoretical prediction E/(s/ 0) 3 = (4 √ 3/3)/(1 + (5.4 + 1.5νs)s 2 / 2 0 ) [29]. Thick dash gray curve in panel b is the theoretical prediction E/(s/ 0) = (2 √ 3) × (1 + s 2 / 2 0 )/(3 + s 2 / 2 0 ) [43].Here, specimen size is R = 40 0. E is expressed in Es units and u is expressed in 0 units.

FIG. 13

 13 FIG. 13. (color online) Poisson's ratio ν as a function of beam aspect ratio s/ 0 at increasing disorder u in honeycombbased lattices (panel a) and triangular-based lattices (panel b). The different colored curves correspond to different values u according to the legend provided in panel b. Thick dash gray curve in panel a is the theoretical prediction ν = (1 + (1.4 + 1.5νs)s 2 / 2 0 )/(1 + (5.4 + 1.5νs)s 2 / 2 0 ) [29]. Thick dash gray curve in panel b is the theoretical predictionν = (1/3) × (1 -s 2 / 2 0 )/(1 + s 2 /3 2 0 ) [43].Here, specimen size is R = 40 0. u is expressed in 0 units.

FIG. 14 .

 14 FIG. 14. (color online) Prefactor of Young's modulus for hexagonal and triangular lattices as function of the size of the sample. Lattices are disordered at u = 0.45 and have an aspect ratio of s/ 0 = 1/1024.

FIG. 15

 15 FIG.15. (color online) (a) Sketch of beam deformation in a streching-dominated lattice loaded under a compressive stress σ. The stretching force applying onto the considered beam is F = σ sF(θ) where θ is the typical angle between two joint beams and F(θ) is the typical distance separated two successive vertically stretched beams. In response to this stretching force, each edge of the beam moves over a distance δ. Thick black vertical plain line and dotted black inclined lines present the considered beam and two jointed ones before the lattice deformation while gray vertical thick plain line and gray dotted inclined lines show the same beams after deformation.

45 FIG. 18 .

 4518 FIG.18. (color online) Shear modulus G as a function of beam aspect ratio s/ at increasing disorder u in square-based disordered lattices. Colored symbols connected by plain lines are the curves obtained via simulation. Colored dash lines are the analytical expression given by Eq. 22 with α = 0.1. G is expressed in Es units and u is expressed in units.

G

45 FIG. 19 .

 4519 FIG. 19. (color online) Ratio α (Eq. A1) as a function of coarse-graining scale N , at increasing levels of disorder u, in honeycomb-based lattices (panel a), square-based lattices (panel b) and triangular-based lattices (panelc). In each panel, the three curves correspond to u = 0 for the blue (lower) curve, u = 0.25 for the green (intermediate) curve and u = 0.45 for the red (upper) curve. Here, beam aspect ratio is s/ 0 = 1/8 and specimen size is R = 32 0. u is expressed in 0 units.

√ 3 / 2 ,

 32 B3) where x(p) = x(M p ) -x(O) is the relative position of node M p with respect to node O. Due to their high connectivity, deformation in triangular-based lattices are dominated by beam stretching. Hence, F(p) is:F i (p) = E s s 2 x i (p)x j (p) (p) 3 U j (p),(B4)where (p) is the length of beam p. Finally, one gets:C ijkl = E s s 2S vor Z p x i (p)x j (b)x k (p)x l (p) (p) 3 (B5)Let us first consider a disorder-free triangular lattice. Then, all beams have same length 0 , S vor = 2 0 and the relative positions x 0 (p) of the six nodes M p are: { 0 , 0}, { 0 /2, 0 √ 3/2}, {-0 /2, 0 √ 3/2}, {-0 , 0}, , {-0 /2, -0 √ 3/2)} and { 0 /2, -

  (p) + uη x (p))4 ((x 0 (p) + uη x (p)) 2 + (y 0 (p) + uη y (p)) 2 ) 3/2 C 22 = E s s 2S vor Z p (y 0 (p) + uη y (p)) 4 ((x 0 (p) + uη x (p)) 2 + (y 0 (p) + uη y (p)) 2 ) 3/2 C 12 = E s s 2S vor Z p (x 0 (p) + uη x (p)) 2 (y 0 (p) + uη y (p)) 2 ((x 0 (p) + uη x (p)) 2 + (y 0 (p)) + uη y (p)) 2 ) (p) + uη x (p)) 3 (y 0 (p) + uη y (p)) ((x 0 (p) + uη x (b)) 2 + (y 0 (p) + uη y (p)) 2 ) (p) + uη x (p))(y 0 (p) + uη y (p)) 3 ((x 0 (p) + uη x (p)) 2 + (y 0 (p) + uη y (p)) 2 ) 3/2 (B8)

  In the disordered triangular-based lattice, elasticity remains isotropic and local configuration-averaged Poisson's ratio at the elementary cell scale remains constant, ν(tr|u) = 1/3. Conversely, local Young's modulus increases with disorder strength: E(tr|u) = E 0 (tr) 1

TABLE I .

 I Deformation mode and isotropy in the 2D crystalline lattices studied here, in absence of introduced disorder (from[START_REF] Gibson | Cellular Solids: Structure and properties[END_REF]).

	Mesh type Node connectivity Isotropic Deformation mode
	3	Yes	Bending
	4	No	Mixed
	6	Yes	Stretching

ACKNOWLEDGMENTS

Support through the CEA PTC Materiaux & Procédés (project LightToughMetaMat) is gratefully acknowledged.

Appendix A: On the effect of averaging procedure onto macroscale compliance tensor

Compliance tensor can be calculated following two schemes. First, S is classically obtained using macroscopic stress and strain. Second, a local S N (x, y) is computed by first coarse-graining local stress and strain fields over square meta-cell of edge size N 0 which gives σ N (x, y) and N (x, y) and then using the classical best-fit procedure.

A coefficient α is defined as:

where denotes the specimen average and || || the Euclidean norm. Figure 19 shows the variation of α with N in the different geometries studied here. Like g(r), α(r) decreases rapidly to zero. Hence, it is equivalent to average over space or over configurations for compliance tensor components.

Appendix B: Analytical expression of local configuration-averaged elastic moduli in disordered triangular-based lattices

The idea is based on the equivalence between the continuum-level scale elastic strain energy stored in a unit cell, U continuum and the total energy stored in the beams of this cell, U cell [50,51]. U continuum is given by:

Where C ijkl are the components of stiffness tensor and ij are the components of strain tensor. Here and in the following, Einstein summation convention is employed on repeated indices. Moreover, ij are considered to be uniform throughout the lattice. U cell is given by:


Antonio Al Serhali

Joachim Niehren

A Benchmark Collection of Deterministic Automata for XPath Queries

Keywords: XML, regular path queries, automata, nested words, trees, hedges. docbook/Latex

We provide a benchmark collection of deterministic automata for regular XPath queries. For this, we select the subcollection of forward navigational XPath queries from a corpus that Lick and Schmitz extracted from real-world XSLT and XQuery programs, compile them to stepwise hedge automata (Shas), and determinize them. Large blowups by automata determinization are avoided by using schema-based determinization. The schema captures the XML data model and the fact that any answer of a path query must return a single node. Our collection also provides deterministic nested word automata that we obtain by compilation from deterministic Shas.

Introduction

XML is one of the most used standardized formats for representing exchanging structured data between various tools and applications. XML documents form unranked data trees. Processing XML documents in both in-memory and streaming modes are widely studied for many years [START_REF] Kay | The saxon xslt and xquery processor[END_REF] [START_REF] Labath | A uniform programming language for implementing XML standards[END_REF] [14] [START_REF] Genevès | A system for the static analysis of xpath[END_REF] [START_REF] Gauwin | Streaming Tree Automata and XPath[END_REF]. The most frequent tasks are validating, querying and transforming XML documents. In the XML technology, this is done with standardized languages based on XPath queries, such as Xslt and XQuery.

Automata-based algorithms are not only relevant for validating XML documents with respect to a schema (as with RelaxNG) but also for querying XML streams [START_REF] Muñoz | Streaming enumeration on nested documents[END_REF] [START_REF] Debarbieux | Early nested word automata for xpath query answering on XML streams[END_REF] [START_REF] Mozafari | High-performance complex event processing over XML streams[END_REF] [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF]. The problem with syntax-oriented approaches for answering XPath queries on XML streams yield only low coverage. Automata approaches, in contrast, can deal with all of XPath 3.0 as shown by Sebastian, Niehren, and Debarbieux [START_REF] Debarbieux | Early nested word automata for xpath query answering on XML streams[END_REF]. When applying automata, however, it is natural to abstract XML documents to nested words [START_REF] Alur | Adding nesting structure to words[END_REF], which generalize on unranked data trees and sequences thereof that are also called forests or hedges. Automata for nested words are also relevant for enumerating query answers of document spanners in in-memory mode [START_REF] Fagin | Document spanners: A formal approach to information extraction[END_REF] [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF], and for enumerating query answers on data trees [START_REF] Martens | Expressiveness and complexity of XML Schema[END_REF] [3] [START_REF] Courcelle | Linear delay enumeration and monadic second-order logic[END_REF].

Deterministic automata are relevant to keep the computational complexity of various problems tractable. In particular it enables automata minimization in polynomial time and universality testing in linear time. In contrast, universality becoming EXP-complete for nondeterministic automata on trees or nested words [START_REF] Comon | Tree automata techniques and applications[END_REF] [START_REF] Seidl | Deciding equivalence of finite tree automata[END_REF]. Note that universality testing can be used as a stopping condition for automata algorithms. More concretely, determinism is required for the streaming algorithms of [START_REF] Muñoz | Streaming enumeration on nested documents[END_REF] and [START_REF] Gauwin | Earliest query answering for deterministic nested word automata[END_REF] but also for the inmemory algorithm of [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF]. Therefore, deterministic automata on nested words need to be produced for regular path queries [START_REF] Libkin | Querying graph databases with xpath[END_REF] [21] [START_REF] Fischer | Propositional dynamic logic of regular programs[END_REF] for benchmarking these algorithms.

Compiling regular path queries to automata is less problematic, but their determinization may blowup the automata sizes exponentially. This also happens in practice. For the XPath query //a[following-sibling::b[.//c][./d]]/e for instance, [START_REF] Debarbieux | Early nested word automata for xpath query answering on XML streams[END_REF] construct a nested word automaton (Nwa) with 38 states of overall size 7338. The determinization of this automaton has more than 5000 states and 20 million transition rules. It is so big that it cannot be computed an a standard laptop. This shows that the usual determinization algorithm for Nwas [START_REF] Von Braunmühl | Input driven languages are recognized in log n space[END_REF] [1] [START_REF] Okhotin | Complexity of input-driven pushdown automata[END_REF] quickly leads to a size explosion.

Niehren and Sakho [START_REF] Niehren | Determinization and Minimization of Automata for Nested Words Revisited[END_REF] improved this situation by using the determinization algorithm for stepwise hedge automata (Shas), which in turn can be compiled to deterministic Nwas. In this way deterministic Shas and Nwas of decent size could be obtained for the 10 forward navigational XPath queries for the XPathMark benchmark [START_REF] Franceschet | Xpathmark performance test[END_REF]. But even the determinization of Shas may lead to unreasonably large automata for pratically relevant XPath queries. For the XPath query /a/b//(* | @* | comment() | text()), for instance, a deterministic Sha with 145 states and size 348 got reported, whose determinization has 10 005 states and overall size 1 634 123 [START_REF] Niehren | Schema-Based Automata Determinization[END_REF].

Niehren, Sakho, and Al Serhali showed recently [START_REF] Niehren | Schema-Based Automata Determinization[END_REF] that this determinization problem for Shas can be solved by using schemas, i.e., deterministic automata that model which nested words are valid inputs of the automaton. In the case of XPath queries, the schema captures the XML data model, and that each query answer must return a unique node of the XML document.

The first schema-based approach is to determinize the product of the query automaton with the schema automaton. For the above XPath query, this yields a deterministic Sha with 92 states and size 417, which after minimization goes down to 27 states and size 98. Nevertheless, this approach may seem surprising at first sight, since the schema-product is usually bigger than the query automaton itself. But indeed it works quite nicely in practice. The intuition is that the deterministic schema reduces the number of subsets of states that are to be considered during determinization since all states in such subsets must be aligned to the same schema state.

The second schema-based approach is to clean the determinized automaton with respect to the schema. This means removing all states and transitions that cannot be aligned to the schema. Schema-based cleaning has the advantage of always yielding smaller automata. Unfortunately, however, it is not always computationally feasible in practice, since the automaton produced by determinization is often too large for being schema-cleaned.

The third schema-based approach is schema-based determinization, an algorithm proposed in [START_REF] Niehren | Schema-Based Automata Determinization[END_REF]. The idea is integrate schema-based cleaning directly into the determinization algorithm, in order to avoid large blowups from the beginning, while producing the same result as with the second approach. The automata obtained by schema-based determinization are usually smaller than by determinizing the schema-product, also after minimization, since they do not recognize the same language.

We applied the implementations of all three approaches to show that small deterministic Shas and Nwas can be obtained for all the regular XPath queries in the benchmark corpus that Lick and Schmitz [START_REF] Lick | XPath Benchmark (Last visited[END_REF] [START_REF] Lick | Logique de requêtes à la XPath : systèmes de preuve et pertinence pratique[END_REF] harvested from Xslt and XQuery programs available online (docbook, teixml, htmlbook, ...). The third solution based on schema-based determinization followed by minimization yields the best results. The largest Sha obtained in this way for the whole benchmark collection has 58 states. In average there are 22 states and 71 transition rules per automaton. All automata are published in the software heritage archive at https://archive.softwareheritage.org/browse/origin/?origin_url=https: //gitlab.inria.fr/aalserha/xpath-benchmark.

The fact that we can indeed determinize the automata of most if not all practical XPath queries with a mild size increase, gives new hope to improve the situation on XML streaming in the near future, building on approaches requiring deterministic automata [START_REF] Muñoz | Streaming enumeration on nested documents[END_REF] [12] [START_REF] Sakho | Certain Query Answering on Hyperstreams[END_REF].

Outline

We present our selection of regular XPath benchmark queries from the corpus of Lick and Schmitz [START_REF] Lick | XPath Benchmark (Last visited[END_REF] in in Section 2. Nested words and their relationship to XML documents are recalled in in Section 3. A deterministic stepwise hedge automata defining the schema of valid XML documents is given in in Section 3.2. A formal definition of stepwise hedge automata follows for the sake of self-containedness in in Section 4. In in Section 5 we discuss our compiler from XPath expressions to deterministic automata, and illustrate it by example automata from our benchmark collection. In in Section 6 we discuss how we tested our automata for correctness on a sample of annotated XML documents produced from the XPath query based on Saxon Xslt. The sizes of automata in our benchmark collection of Shas are discussed in in Section 7. We conclude in in Section 8. Some complementary information can be found in in Appendix A.

XPath Benchmark Queries

We start with the collection of 21000 XPath queries that Lick and Schmitz [START_REF] Lick | XPath Benchmark (Last visited[END_REF] extracted from real-world XQuery and Xslt programs available on the Web. The purpose of this corpus is to reflect the form and distribution of XPath queries in practical applications. The much smaller XPathMark benchmark [START_REF] Franceschet | Xpathmark performance test[END_REF], in contrast, focuses on functionality testing.

We then filter the subclass of around 4500 forward navigational XPath queries of Lick's and Schmitz's corpus. The other queries contain comparisons of data values, arithmetics, and functions, including higher-order functions to iterate over sequences, which may be nonregular. We also removed boolean queries and kept only node selection queries. We then selected the 180 largest queries of this subcorpus.

Finally, we removed duplicates of queries up to renaming of XML namespace prefixes and local names, and syntactical details, such as .//author or descendant-or-self::author or descendant-or-self::corpauthor. This leads us to the collection of 79 queries. The first 10 queries are shown in in Table 1.

Id

XPath Query 18330 /descendant-or-self::node()/child::parts-of-speech 17914 /descendant-or-self::node()/child::tei:back/descendant-or-self::node() /child::tei:interpGrp The first 10 of the 79 queries of the benchmark collection (see Table 3).

We note that the XPath query 18339 is considered as large since it contains the recursive axis descendant-or-self. Other queries are considered as large since having a parse tree with more than 15 nodes, for instance 05684 and 05684.

Nested Words for XML Documents

We use nested words to abstract from XML documents since automata can be defined more easily for nested words.

Nested Words

Nested words generalize on words by adding parenthesis that must be wellnested. Nested words also generalize on unranked trees and over sequences thereof that are often called hedges. We restrict ourselves to nested words with a single pair of opening and closing parenthesis 〈 and 〉 since named parenthesis can be encoded easily. Let Σ be a set that we call the alphabet. Nested words in N Σ have the following abstract syntax.

w, w ∈ N Σ ::= ε | a | w | w • w
where a ∈ Σ.

We assume that concatentation • is associative, and that the empty word ε is a neutral element, that is w

• (w • w ) = (w • w ) • w and ε • w = w = w • ε.
Nested words can be identified with hedges, i.e., sequences of unranked trees and letters, that is

N Σ = (Σ ∪ N Σ ) * .

XML Documents

XML documents are labeled unranked trees that can be serialized into a text, such as for instance:

<s:a name="uff"> <s:b> gaga <s:d/> <s:b/> <s:c/> <s:a> We represent XML documents as nested words over the signature Σ XM L that contains 4 disjoint types of letters: the XML node-types {elem, attr, text, comment}, the XML namespaces of the document {s}, the XML names of the document {a, . . . , d, name}, and the characters of the data values, say UTF8. For the above example, we get the nested word:

elem•s•a• attr•name•u•f •f elem•s•b• text•g•a•g•a elem•s•d elem•s•c

Automata for Nested Words

Stepwise hedge automata (Shas) [START_REF] Niehren | Determinization and Minimization of Automata for Nested Words Revisited[END_REF] extend on classical finite state automata (Nfas) from words to nested words. They provide a graphical way to define regular languages of nested words, and thus regular languages of XML documents. Shas are often easier to read that the better-known nested word automata (Nwas) and help us to avoid large size blowups coming with Nwa determinization. In this section we recall the definition of Shas based on the definition of Nfas and discuss their relationship Nwas.

Finite State Automata (NFAs)

We consider finite state automata with else rules and possibly infinite alphabets. Definition 1. An Nfa (with else rules) is a tuple A=(Σ, Q, ∆, I, F ) such that alphabet Σ is a possibly infinite set, ∆ = ∆ ∆ contains a subset of transition rules for letters ∆ ⊆ (Q×Σ)×Q and a subset of else rules ∆ ⊆ Q×Q. We call Nfa A deterministic or equivalently a Dfa if ∆ and ∆ are partial function.

As usual when using automata, we draw Nfas as graphs whose nodes are the states. A state q ∈ Q is drawn with a circle q , an initial state q ∈ I with an incoming arrow → q , and a final state with a double circle q . A letter transition rule (q 1 , a, q 2 ) ∈ ∆ is drawn as a black edge q 1 a -→ q 2 that is labeled by a letter a ∈ Σ. An else rule (q, q ) ∈ ∆ is drawn as q -→ q . It permits that the automaton in state q can go to state q when reading any letter a ∈ Σ such that there exists no q with q a -→ q ∈ ∆. Any else rule can be expanded to a set of letter transitions rules as follows:

q - → q ∈ ∆ a ∈ Σ ¬∃q ∈ Q. q a -→ q ∈ ∆ q a -→ q ∈ ∆ exp q a -→ q ∈ ∆ q a -→ q ∈ ∆ exp

Stepwise Hedge Automata (SHAs)

We extend Nfas to Shas by adding adding apply rules that read states of subtrees rather than letters from the alphabet. Definition 2. An Sha (with else rules) is a tuple A = (Σ, Q, P, ∆, I, F ) where ∆ = ∆ ∆ so that A = (Σ, Q, ∆ , I, F ) is a Nfa. Furthermore, P is a finite set of tree states and ∆ = ( ∆ , @ ∆ , -→ ∆ ) such that ∆ ⊆ Q is a subset of tree initial states, @ ∆ ⊆ (Q × P) × Q a set of apply rules, and -→ ∆ ⊆ Q × P a set of tree final rules.

We draw Shas as graphs extending on the graphs of Nfas. A tree state p ∈ P is drawn in gray p . A tree initial state q ∈ ∆ is a hedge state is drawn as -→ q with an incoming tree arrow. An apply rule (q 1 , p, q 2 ) ∈ @ ∆ is drawn by a blue edge q 1 p -→ q 2 carrying a state p ∈ P rather than a letter a ∈ Σ. It states that a nested word in state q 1 ∈ Q can be extended by a tree in state p ∈ P and go into state q 2 ∈ Q. A tree final rule (q, p) ∈-→ ∆ is drawn as q -→ p . It states that if w is a nested word in state q ∈ Q then w is a tree in state p ∈ P.

Transitions of Shas have the form q w -→ q wrt ∆ where w ∈ N Σ and q, q ∈ Q. They are defined by the inference rules:

q ∈ Q q ε -→ q wrt ∆ q a -→ q ∈ ∆ exp q a -→ q wrt ∆ q 0 w1 --→ q 1 wrt ∆ q 1 w2 --→ q 2 wrt ∆ q 0 w1•w2 ----→ q 2 wrt ∆ q ∈ ∆ q w -→ q wrt ∆ q -→ p ∈ ∆ q 1 p -→ q 2 ∈ ∆ q 1 w --→ q 2 wrt ∆
The last inference rule says that when reading a tree w the automaton can transit from a state q 1 to a state q 2 if with w it can transit from some tree initial state q to q, so that there is some tree final rule q -→ p ∈ ∆ and some apply rule q 1 p -→ q 2 ∈ ∆. The language L(A) of a Sha is defined as usual for Nfas except that nested words may be recognized too:

L(A) = {w ∈ N Σ | q w -→ q wrt ∆, q ∈ I, q ∈ F }
The notion of determinism for Shas extends on the notion of left-to-right determinism of Nfas and on the notion of bottom-up determinism of tree automata. Definition 3. We call an Sha A deterministic or equivalently a dSha, if the contained finite automaton A is a Dfa, there is at most one tree initial state in ∆ , and @ ∆ and -→ ∆ are partial functions.

Adding Typed Else Rules

Suppose that the alphabet Σ is typed, in that any letter a ∈ Σ can be given some types in some type set T . We can then add typed else rules (q, τ, q ) ∈ ∆ × T × ∆ that we draw as q -τ --→ q . In contrast to untyped else rules, a typed else rule cannot be expanded with all letters from Σ, but only with those that can be given the type τ .

A Schema for XML Documents

The most frequent type of XPath queries select nodes of XML documents. For referring to selected nodes, we fix a single selection variable x. We call an XML document or subdocument, in which a single node is annotated by x, an x-annotated example. An x-annotated example is called positive for a query if the query selects the x-annotated node in the XML document, and negative otherwise.

The dSha xml&one x : a schema for x-annotated XML documents in Fig. 1 recognizes the set of all x-annotated examples. These must satisfy the XML data model and contain exactly one occurence of x. The automaton starts in hedge state 0 where it expects to read a nested word w , that can be evaluated to tree state 28, in order to go to the final state 29, where it accepts. The sequence of children w of the tree must be evaluated form the tree initial state, which is equally the hedge state 0. If w starts with letter doc indicating an XML document node at the root, the automaton moves from state 0 to state 5. There it may either read the variable x and go to state 5, where it expects a subtree in state 21, i.e. an XML element of which no node is annotated by x. Or it may read the symbol ¬x and move to state 6, where it expects a subtree in state 19, i.e. an XML element of which exactely one node is annotated by x. In both cases it can go to the hedge state 26 and from there to the tree state 28. The automaton also states the relationships of elements, attributes, text and comment nodes according to the XML data model.

The alphabets of names and namespaces of XML documents are infinite. In order to represent infinite sets of transition rule symbolically in a finite manner, the automaton use type else rules. The typed else rule in state 3, for instance, is labeled by -namespace, permitting to read any namespace and to go to state 9. State 9 in turn has an else rule labeled by -name which permits to read any (local) name and move to state 13.

Nested Word Automata (NWAs)

Nested word automata (Nwas) [START_REF] Okhotin | Complexity of input-driven pushdown automata[END_REF][1] are well known pushdown machines for defining regular languages of nested words. They can process nested words in a streaming manner: top-down, left-to-right, and bottom-up manner. Shas in contrast operate bottom-up and left-to right only. They avoid any top-down processing, since it quickly leads to huge size increases during Nwa determinization.

Any Sha can be compiled in linear time to an Nwa such that determinism is preserved. There also exists an inverse translation in quadratic time (but not preserving determinisim), so both automata classes have the same expressiveness, also when restricted by determinism. We omit the details, but provide deterministic Nwas in our collection. See for instance: The dNwa nwa(det(A 2 )) obtained from the dSha det(A 2 ) in Fig. 4.

Compiler to Automata

We extended on the compilation chain for regular XPath queries to automata from [START_REF] Niehren | Determinization and Minimization of Automata for Nested Words Revisited[END_REF]. As a running example, we consider the following query:

Q 2 : h:body[@lang != '']
Query Q 2 selects a node if it has a child named body in namespace h, that has the attribute node named lang containing a nonempty text.

Parser

Our parser for XPath expressions computes a parse tree following the grammar of XPath 3.1 from the W3C. In addition, it returns for any forward regular XPath expression a logical formula in the language FXP [START_REF] Debarbieux | Early nested word automata for xpath query answering on XML streams[END_REF]. For the XPath example Q 2 , we obtain the following FXP formula: child(lab elem:type ∧ lab h:namespace ∧ lab body:name ∧ lab x:var ∧ child(lab att:type ∧ cand def ault:namespace ∧ lab lang:name ∧ string = ))

Our previous parser needed considerable improvement in order to be able to cover the large variety of queries from the corpus of Lick and Schmitz [START_REF] Lick | XPath Benchmark (Last visited[END_REF].

Nested Regular Expressions

We next compile Fxp formulas to nested regular expressions, which extend on standard regular expressions from words to nested words. Again, considerable work was needed to enable a sufficiently large coverage. For the query Q 2 our compiler yields the nested regular expression:

Compiler to SHAs

The compiler then converts nested regular expressions into Shas. This is done by extending a usual compiler from regular expressions to Nfas. The interaction of recursion and nesting leads to some nasty issues, that are discussed and resolved in [START_REF] Niehren | Determinization and Minimization of Automata for Nested Words Revisited[END_REF]. For developping the present benchmark, we needed to add a treatment of typed wildcards such as -char. This is done by introducing typed else rules. For the query Q 2 we obtain: Sha in The nondeterministic Sha A 2 = sha(Q 2 ). in Fig. 2. Similarly to the nested regular expression, this Sha may recognize some annotated nested words, that are not x-annotated examples, i.e., that do not belong to the language of the schema L(xml&one x ).

Determinization

The usual determinization algorithms for Nfas and tree automata can be lifted to a determinization algorithm for Shas. When applied to query Q 2 however, we obtain a Sha with 25 states and 183 transition rules, which is much larger than one might expect. It is given in The determinization det(A 2 ) of the Sha A 2 in Fig. 5 of the appendix. Even worse, in some cases, the determinization algorithm does not finish after some hours.

Determinizing the Schema Product

Determinization applied to the product of the queries' automaton and the schema xml&one x permits to compute deterministic automata for all queries of our benchmark within a timeout of 100 seconds. The result for Q 2 is a dSha with 53 states and 110 transition rules, see automaton The determinization of the schema product det(A 2 × xml&one x ) in Fig. 6 of the appendix. The overall size is smaller, and the automaton is much easier to understand, but the number of states increased.

Schema-Based Determinization

Schema-based determinization as proposed in [START_REF] Niehren | Schema-Based Automata Determinization[END_REF] improves the situation further. For query Q 2 it yields: Sha in The schema-based determinization det S (A 2 ) where S = xml&one x in Fig. 3 which has only 22 states and 45 transitions. The size is roughly devided by 2 compared to: The determinization of the schema product det(A 2 × xml&one x ) in Fig. 6.

Minimization

We then minimize the dSha from The schema-based determinization det S (A 2 ) where S = xml&one x in Fig. 3. This often reduces the size and the number of states in an important manner and often makes it easy to see how the automaton is functioning. Exceptionally in the case of Q 2 , no states are fusioned when minimizing the dSha obtained by schema-based determinization.

It should be noticed that minimizing the determinization of the schema product usually yields a different result then minimizing the schema-based determinization. This is since both automata may recognize different languages. Some nested words outside the schema may be accepted after schema-based determinization, but not by the schema product.

Compiler to NWAs

The compiler finally maps Shas to Nwas in linear time, while preserving determinism. For instance the minimal dSha in The schema-based determinization det S (A 2 ) where S = xml&one x in Fig. 3 is converted to: The dNwa nwa(det(A 2 )) obtained from the dSha det(A 2 ) in Fig. 4.

Testing Automata on Samples

For testing the stepwise hedge automata, we created a sample with positive and negative x-annotated examples for each of the queries. Please contact the authors if you are interested in the test samples. They can be provided without problem.

For this we produced an XML document for each of the Xslt programs from which the XPath queries of Lick and Schmitz were extracted. We did this in such a way that each of the queries has at least one answer on one of the subdocuments of the document of its collection. Subdocuments are important here, since the XPath queries of an Xslt program will be applied to subdocumens naturally.

By using Saxon Xslt, we computed the answer set of all the queries on all the subdocument of the produced XML documents. For this, we exported query answers in Dewey notation, similarly to the way that nodes are returned by Schematron: The Dewey noation of a node is its relative address from the root, i.e., by the list of child steps leading to the node. Such lists can be easily encoded in XML format.

Each query query answer yields a positive x-annotated examples for the query, that is obtained by annotating the XML document by x at the selected position. Negative x-annotated examples are obtained from the answers of the other queries on the same document. The annotation of the XML document is done by yet another Xslt stylesheet that we wrote for this purpose. Here we use the fact that query answers are also represented in XML format.

By testing the automaton on these samples, we could fix various problems that arised on the way to our final collection. Currently, no test failures are remaining, except for the query 13896 below that we removed from the corpus for the current version. The problem here is raised by the blank symbol in the attribute value 'evans citation': //HEADER//IDNO[@TYPE='evans citation']

Statistics of the Benchmark Automata

We compiled all of our 79 XPath queries to deterministic automata using the compilation chain described in in Section 5. Here we present the statistics of the benchmark automata that we obtained. The summary is given in in Table 2. We show for each automaton two numbers size(#states) where size is the overall size of the automaton and #states the number of its states. The nondetermnistic Shas compiled from the nested regular expressions was cleaned using the schema xml&one x : The dSha xml&one x : a schema for xannotated XML documents in Fig. 1. The result is called A = sha(Q) leading to the statistics in the second column of in Table 2.

We note that 37% of the Shas original stepwise hedge automata for the queries A = sha(Q) have more than 100 states, so they are sometimes bigger than one might expect. The biggest is for query 06176 with 630 states and an overall size of 1391. The reason is that this query is selecting a union of 20 subqueries, all with descendant-or-self axis. Foe each subquery, we have 4 construsts of respective state sizes: 2, 6, 10 and 13, making a subtotal of 31 * 20 = 620. With an additional 8 states for one subquery that select all descendants with an attribute named id and another 2 for reading any tree, we end up with our total 630 states.

Table 2: Experiment results on the XPath subcorpus from Lick and Schmitz in Table 3. For each automaton we present: size(number-of-states).

query B = C = B = C = Q of id A det(A) det(A × S) det S (A) mini(B) mini(C) nwa(C ) 18330
99 (41) 465 ( 43) 145 (44) 74 ( 22) 128 (39) 61 ( 18) 73 ( 18)

The column for det(A) contains the statistics for the determinization of A. No schema is used there. We use a timeout of 100 seconds. Whenever this is not enough, the cell in the table is left blank. Indeed, the determinization fails with this timeout for 37% of the queries of our corpus. Roughly, the determinization fails for all Shas with more than 100 states. For instance, for query 11780 the Sha A has has size 205 (88), while the dSha det(A) has size 3832 (190).

The column for B = det(A × S) contains the determinization of the product of A and the schema S = xml&one x . Even though A × S is always larger than A, we were able to always determinize A × S within the timeout, in contrast to A. The largest dSha B obtained is for for query 04358: it has size 3580 (559). This show that B may still be quite big, but often a big improvement in size over det(A).

The next column reports on C = det S (A) obtained by schema-based determinization with schema S = xml&one x . Again, the computation succeeds in all cases within the timeout of 100 seconds. The size of C for query 04358 is 2021 (433), which improves in size over B.

In the next two columns, we respectively minimize the determinized Shas B and C, using a naïve minimization algorithm. All automata can be minimized within the timeout of 100 seconds. We note that C = mini(C) is always smaller than B = mini(B), showing that schema-based determinization yields smaller minimal automata than determinizing the schema-product. The maximal number of states of the minimal dShas C = mini(C) is 58 for query 04358. In average the number of states decreases by 55%.

In the last column, we compiled the minimized dShas of C to the dNwa nwa(C ). It has the same number of states than C for all queries and a minor increase is the number of transitions. All these results, including the automata of the intermediate steps, generated during the whole compilation chain are available at in the software heritage archive at the following url: https://archive. softwareheritage.org/browse/origin/?origin_url=https://gitlab.inria. fr/aalserha/xpath-benchmark.

Conclusion

We provide a benchmark of deterministic automata for regular XPath queries obtained with an algorithm for schema-based determinization of symbolic Shas that we presented. Our benchmark is compiled from forward navigational XPath queries: the 79 largest queries modulo renaming of the 4500 forward navigational XPath queries of the corpus of Lick and Schmitz [START_REF] Lick | XPath Benchmark (Last visited[END_REF]. From the Shas of these 79 queries, 37% cannot be determinized in less then 100 seconds by schema-less determinization. Schema-based determinization, in contrast, succeeds for 100% of them. Furthermore, all dShas obtained by schema-based determinization are sufficiently small so that they can be minimized with the naïve quadratic algorithm. This leads us to a collection of minimal dShas with an average number of states of 22, and 71 as the average number of transition rules.

We hope that the automata of our collection will be used for experimenting with algorithms for XPath queries in the near future and for developing and comparing the performance of algorithms for answering XPath queries on XML streams in particular.

Fig. 1 :

 1 Fig. 1: The dSha xml&one x : a schema for x-annotated XML documents.

  (elem:type. ) + doc:type). . . elem:type.h:namespace.body:name.x:var. att.type.def ault:namespace.lang:name. .( char.( char) * . . .Note that the test for a nonempty string got translated by the regular expression char.( char) * . It should also be noticed that this expression matches some x-annotated nested words, that are not x-annotated examples, i.e. not belonging to the language L(xml&one x ) of the schema. This is since the nested subwords matching universal expression are completely unconstrained.

Fig. 2 :

 2 Fig. 2: The nondeterministic Sha A 2 = sha(Q 2 ). .

Fig. 3 :

 3 Fig. 3: The schema-based determinization det S (A 2 ) where S = xml&one x .

Fig. 4 :

 4 Fig. 4: The dNwa nwa(det(A 2 )) obtained from the dSha det(A 2 ) .

Fig. 6 :

 6 Fig. 6: The determinization of the schema product det(A 2 × xml&one x ).

Table 1 :

 1

10745 *//tei:imprint/tei:date[@type='access'] 02091 * | .//refentry 00744 .//@id | .//@xml:id 12060 .//attDef 02762 .//authorgroup/author | .//author 06027 .//authorinitials | .//author 02909 .//bibliomisc[@role='serie'] 06415 .//email | address/otheraddr/ulink