Emmanuel De Langre
email: delangre@ladhyx.polytechnique.fr

Olivier Doaré
email: olivier.doare@ensta-paristech.fr

EDGE FLUTTER OF LONG BEAMS UNDER FOLLOWER LOADS

The linear instability of a beam tensioned by its own weight is considered. It is shown that for long beams, in the sense of an adequate dimensionless parameter, the characteristics of the instability caused by a follower force do not depend on the length. The asymptotic regime significantly differs from that of short beams: flutter prevails for all types of follower loads, and flutter is localized at the edge of the beam. An approximate solution using matched assymptotic expansion is proposed for the case of a semi-infinite beam. Using a local criterion based on the stability of waves, the characteristics of this regime as well as its range of application can be well predicted. These results are finally discussed in relation with cases of flow-induced instabilities of slender structures.

I. INTRODUCTION

The linear stability of a beam under the action of a follower force exerted at one of its extremities has been the subject of intensive research, as can be seen from the extensive review in [START_REF] Langthjem | Dynamic stability of columns subjected to follower loads: a survey[END_REF]. The interest in this problem lies in its potential applications and also in the large variety of fundamental topics of mechanics involved in the solution method. Practical examples of direct application in the field of fluid-structure interactions are numerous: fluidconveying pipes, plates subjected to axial flow or towed cylindrical bodies are modelled by equations that are similar, though not identical, to those of a beam under a compressive follower force [START_REF] Païdoussis | Fluid-Structure Interactions, slender structures and axial flows[END_REF][START_REF] Païdoussis | Fluid-Structure Interactions, slender structures and axial flows[END_REF]. More generally, follower forces have been extensivelly discussed in the literature, including in terms of their physical reality, see [START_REF] Elishakoff | Controversy associated with the so-called" follower forces": critical overview[END_REF] for a full review. The case of a cantilevered beam of finite length under a partial follower force is well documented, see [START_REF] Bolotin | Nonconservative problems of the theory of elastic stability[END_REF], with many results on the effect of characteristics of the beam or of the load on the critical load that causes instability, and on the nature of the instability, be it divergence (buckling) or flutter.

We seek here to establish the characteristics of instability of a beam in the case where its length is much larger than the region where an unstable motion will develop. This arises when a constant load, such as gravity acting on a vertically hanging beam, produces a tension that increases along the beam, from zero at the lower free end to a maximum at the upper fixed end. The increasing tension induces a corresponding increasing stiffness. Motion is then confined to the lower end, corresponding to edge flutter. This has been studied both experimentally and numerically in three of the problems of flow-induced vibrations mentioned above: hanging fluid-conveying pipes [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF][START_REF] De Langre | Force suiveuse critique sur une colonne pesante semi-infinie: modèle et expériences[END_REF], hanging ribbons under axial flow [START_REF] Lemaitre | Instability of a long ribbon hanging in axial air flow[END_REF] and towed cylinders under axial flow [START_REF] De Langre | Flutter of long flexible cylinders in axial flow[END_REF][START_REF] Obligado | An experimental investigation of the equilibrium and stability of long towed cable systems[END_REF]. In all these systems it was observed that there exists a limit state in which the length does not affect the stability. This limit state is found for length larger than a limit value given by simple considerations on the local stability of bending waves [START_REF] De Langre | Flutter of long flexible cylinders in axial flow[END_REF][START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF].

The objective of this paper is to establish similar results on the generic case of a beam under a partially follower force (or subtangential force), tensioned by a load such as gravity.

In Section II we shall recall the equations of motion and the possible choices of dimensionless variables. The effect of the beam length on stability is analysed in Section III, using numerical computations of the eigenmodes. In Section we address the particular case of a semi-infinite beam, using various types of modelling. The application of the results given in the paper to problems of flow-induced instabilities is discussed in Section V. A partial follower force is applied at its lower end [START_REF] Langthjem | Dynamic stability of columns subjected to follower loads: a survey[END_REF]. The linear equation governing the in-plane lateral deflection Y (Z, T ) reads

EI ∂ 4 Y ∂Z 4 + ∂ ∂Z (P -mgZ) ∂Y ∂Z + m ∂ 2 Y ∂T 2 = 0, (1)
where EI is the flexural rigidity, P is the load, g is gravity and m is the mass per unit length. No damping is considered here, though it is known to significantly influence some aspects of the problem, see for instance in [START_REF] Detinko | Lumped damping and stability of beck column with a tip mass[END_REF]. The boundary conditions at the lower end, Z = 0 are

EI ∂ 2 Y ∂Z 2 (0) = 0 , EI ∂ 3 Y ∂Z 3 (0) + (1 -η)P ∂Y ∂Z (0) = 0, ( 2
)
where η is a coefficient that expresses the part of the loading that follows the beam slope; hence η = 0 corresponds to a non-follower force and η = 1 to a pure follower force. At the upper end, we assume a clamped condition,

Y (L) = 0, ∂Y ∂Z (L) = 0. (3)
Using the length of the beam, L, as a reference we define the following dimensionless variables:

z = Z L , y = Y L , t = EI m 1/2 1 L 2 T, p = P L 2 EI , γ = mgL 3 EI . (4)
Then Eq.( 1) may be re-written in dimensionless form as

∂ 4 y ∂z 4 + ∂ ∂z (p -γz) ∂y ∂z + ∂ 2 y ∂t 2 = 0, (5)
with the boundary conditions

∂ 2 y ∂z 2 (0) = 0; ∂ 3 y ∂z 3 (0) + (1 -η)p ∂y ∂z (0) = 0; y(1) = 0; ∂y ∂z (1) = 0. ( 6
)
This dimensionless set of equations is adequate to analyse the effect of γ on the critical loading, but only if the length L is kept constant. As we need to vary the length L, it is necessary to define a new set of dimensionless parameters. We now use a length scale defined by the ratio of the two stiffnesses of the beam, namely the flexural rigidity and the stiffness related to tension induced by gravity [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF],

L g = EI mg 1/3 (7)
which will be referred to as the gravity length. Note that this length scales like the critical length that causes buckling of the beam under its own weight. Using L g as the reference length to define dimensionless variables we have

x = Z L g , y = Y L g , τ = EI m 1/2 1 L 2 g T, q = P L 2 g EI , ℓ = L L g , (8)
where L g has been substituted for L. These are related to the previous set of variables by

x = zℓ, τ = tℓ 2 , q = p ℓ 2 , ℓ = γ 1/3 . (9)
Eq. ( 1) now becomes

∂ 4 y ∂x 4 + ∂ ∂x (q -x) ∂y ∂x + ∂ 2 y ∂τ 2 = 0, (10)
and the corresponding boundary conditions are

∂ 2 y ∂x 2 (0) = 0; ∂ 3 y ∂x 3 (0) + (1 -η)q ∂y ∂x (0) = 0; y(ℓ) = 0; ∂y ∂x (ℓ) = 0. ( 11
)

III. STABILITY OF FINITE BEAMS

A. Solution for short beams

For short beams, in the sense where ℓ ≪ 1, the critical load q c may be derived by considering that γ ≪ 1 so that Eq. ( 5) becomes

∂ 4 y ∂z + p ∂ 2 y ∂z 2 + ∂ 2 y ∂t 2 = 0. (12)
The corresponding stability diagram of p c versus η is that of the generalized Beck's column [START_REF] Langthjem | Dynamic stability of columns subjected to follower loads: a survey[END_REF] and is shown in Fig. 2(a). For η < 0.5 instability arises in the form of a divergence, whereas flutter prevails for η > 0.5. The corresponding frequency at the flutter limit is shown in Fig. 2(b). The critical load and frequency at flutter expressed in the dimensionless variables of Eq. ( 8) are

q c (η, ℓ) = p c (η) ℓ 2 ; ω c (η, ℓ) = Ω c (η) ℓ 2 . (13)

B. Effect of length

We now investigate the effect of the length ℓ on the stability threshold and the nature of the instability. The numerical method utilized to this end is the finite difference method, as in [START_REF] Sugiyama | Vibration and stability of elastic columns under the combined action of uniformly distributed vertical and tangential forces[END_REF]. It allows us to compute the eigenvalues ω and the eigenvectors ϕ, such that

ϕ (4) + [(q -x)ϕ ′ ] ′ -ω 2 ϕ = 0 ( 14
)
with

ϕ ′′ (0) = ϕ (3) (0) + (1 -η)qϕ ′ (0) = ϕ(ℓ) = ϕ ′ (ℓ) = 0. ( 15
)
The critical load and the nature of the corresponding instability can be determined from the evolution of the real and imaginary parts of the frequency. The beam is unstable if the frequency ω has a negative imaginary part. If the real part is zero, the instability results in an exponential growth in time of the deformation , without oscillation and the instability is of the divergence type. If the real part is non zero, the instability results in an exponential growth of oscillations, and the instability is of the flutter type. Fig. 3 show the evolution of the critical load with length, for several values of η of particular interest. For η = 0, Fig. 3(a), which is the case of a non-follower force, the critical load decreases steeply with length, up to about ℓ = 5 where it reaches a limit value and does not change when the length is increased further. Instability is for all lengths of the divergence type. On the same figure are shown computations from [START_REF] Naguleswaran | Transverse vibration of an uniform euler-bernoulli beam under linearly varying axial force[END_REF] and [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF], for intermediate values of the length. In [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF], the static instability of a towed beam has been considered, which yields equations similar to that used here. Details of the equivalence are discussed in the last section of this paper, but suffice to say here that we may use the results of Fig. 4 of [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF] with the change of variables ℓ = ελ 2/3 and q = λ 2/3 . It is seen that their results and those of this paper are in very good agreement. For η = 0.2, Fig. 3(b), the critical load for divergence also decreases and reaches a limit value, but the flutter threshold becomes lower than that for divergence, for beams longer than ℓ = 5. For η = 0.3, Fig. 3(c), no divergence is found for ℓ > 3. Instability is that range of ℓ is of the flutter type. For η = 1, Fig. 3(d), the system loses stability by flutter, similarly to Beck's column; the critical load for flutter decreases with ℓ until it reaches a limit value.

From these four cases it can be stated that there exists a limit configuration for all long beams, say ℓ > 10. For these lengths, the type of instability, flutter or divergence, may differ from that observed for short beams at the same value of η.

This is further confirmed in the evolutions of the stability diagram q c (η) shown in Fig. 4. At ℓ = 1 the diagram is similar, though not identical, to that for short beams; since ℓ = 1 we have here q c = p c and Figs. 2 and4(a) can be directly compared. At ℓ = 100, Fig. 4(b) a limit state is almost reached, where stability is always lost by flutter, for all values of η.

Fig. 5 shows the mode shape at the critical load, which may be a divergence or a flutter instability depending on the values of η and ℓ, as shown above. Note that at the instability threshold ϕ is real, even for flutter instability. In fact, in Eq. ( 14), when ω is real so is ϕ. For η = 0, Fig. 5(a), the mode shape, here for divergence, becomes independent of the length when ℓ > 3. This is consistent with Fig. 3(a) where the critical load was found to be stationnary in this range. For η = 0.3 and η = 1, Figs. 5(b) and(c), the mode shapes also converge to a constant shape as the length is increased. There, the displacement is confined to the lower part of the beam. Note that the instability is of the flutter type, except for η = 0.3 at ℓ = 1. Yet, the limit mode shape closely resembles that of the divergence instability at η = 0.

IV. STABILITY OF A SEMI-INFINITE BEAM A. Boundary conditions

We now seek to determine the characteristics of the instability when the beam is assumed to be of infinite length in the X axis. This is expected to be the solution to which the results of the preceding section converge as ℓ is increased. Whereas the boundary condition at the lower end is unchanged, the condition that the beam is clamped at X = L needs to be replaced by the conditions that the displacement remains finite as X goes to infinity and that in this limit

B. Divergence instability

The case of divergence instability may be analysed by neglecting all time derivatives in the equations, so that (10) becomes

∂ 4 y ∂x 4 + ∂ ∂x (q -x) ∂y ∂x = 0 ( 17
)
and the boundary conditions are only By defining λ = q 3/2 and Z = x -q, this set of equations is identical to that solved by [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF] for the case of a towed cylinder. Using their solution with our variables, the critical load for divergence q c (η) is found to satisfy

∂ 2 y ∂x 2 (0) = 0; ∂ 3 y ∂x 3 (0) + (1 -η)q ∂y ∂x (
Ai ′ (-q c ) -q c η 1 3 - -qc 0 Ai(s)ds = 0, ( 19
)
where Ai is the Airy function [START_REF] Abramowitz | Handbook of Mathematical Functions: With Formulars, Graphs, and Mathematical Tables[END_REF].

C. Flutter instability

We give here an approximate solution for the critical load for flutter of a semi-infinite beam, which is an extension from the work of [START_REF] De Langre | Force suiveuse critique sur une colonne pesante semi-infinie: modèle et expériences[END_REF] for a purely follower force, η = 1. The approach used in the matched assymptotic expansions follows that proposed by [START_REF] Triantafyllou | The paradox of the hanging string: An explanation using singular perturbations[END_REF] for the dynamics of vibrating strings tensionned by gravity.

We consider Eq. ( 10), with the boundary conditions [START_REF] Langthjem | Dynamic stability of columns subjected to follower loads: a survey[END_REF] at the bottom end, and ( 16) for a semi-infinite beam. We seek harmonic solutions of this set of equations, of the form

y(x, t) = Real[ϕ(x)e iωt ] ( 20
)
as a function of the follower force magnitude q. Instability will be associated with Im(ω) < 0. The variation in space of the solution satisfies

ϕ (4) + [(q -x)ϕ ′ ] ′ -ω 2 ϕ = 0, (21)
with the boundary conditions

ϕ (2) (0) = 0; ϕ (3) (0) + (1 -η)qϕ ′ (0) = 0 (22)
where () ′ denotes derivation with respect to x. The condition for radiating waves reads

lim x→∞ Real[ϕ ′ (x)e iωt ]Real[iωϕ(x)e iωt ] < 0. ( 23
)
Let us consider first the lower part of the beam where x is of the order of q. In this "inner" domain of length q, we may derive an approximate solution ϕ i (x) by simply lumping all its inertia at the lower end of the beam, so that the boundary conditions at x = 0 read now

ϕ (2) i (0) = 0; ϕ (3) i (0) + (1 -η)qϕ ′ i (0) = qω 2 ϕ i (0), (24)
and Eq. ( 21) reduces to

ϕ (4) i + [(q -x)ϕ ′ i ] ′ = 0. (25)
The corresponding solution reads

ϕ i (x) = a + x 0 [bAi(s -q) + cBi(s -q) + dGi(s -q)] ds (26)
where Ai, Bi and Gi are the Airy functions, a, b, c, d being four coefficients. For the sake of clarity we now use the notation F (x) =

x 0 F (s)ds and F for F (-q) unless otherwise specified, where F could be any of the Airy functions above.

In terms of the coefficients a, b, c, d the boundary conditions at the lower end are

bAi ′ + cBi ′ + dGi ′ = 0; (27) bAi ′′ + cBi ′′ + dGi ′′ + (1 -η)q(bAi + cBi + dGi) = aqω 2 . ( 28
)
Conversely, in the upper part of the beam, that is where x ≫ q, we rescale the equations by using new variables in space and time, namely

χ = xε; r = ω √ ε , (29)
where ε = L g /Λ, the length Λ being an arbitrary large scale. Using this set of variables, Eq. (21) reads

ε 3 ϕ (4) + [(ε 2 q -εχ)ϕ ′ ] ′ -εr 2 ϕ = 0, (30)
where () ′ denotes now differentiation with respect to χ. This allows us to derive the equation at the leading order in the "outer"domain,

(-χϕ ′ e ) ′ -r 2 ϕ e = 0, (31)
the solution of which, in terms of Bessel functions, is (see also in [START_REF] Elishakoff | Exact and effective approximate solutions of some divergence-type non-conservative problems[END_REF])

ϕ e (χ) = αJ 0 (2r √ χ) + βY 0 (2r √ χ). (32)
The radiation condition, Eq. ( 23), implies that

α -iβ = 0. ( 33
)
We may now match the inner and outer solutions by considering their respective limits [START_REF] Abramowitz | Handbook of Mathematical Functions: With Formulars, Graphs, and Mathematical Tables[END_REF][START_REF] Triantafyllou | The paradox of the hanging string: An explanation using singular perturbations[END_REF]. Equating these two limits yields three conditions for the coefficients defining the inner and outer solutions, namely

c = 0; d = β; a + b 1 3 -Ai + d 2γ + ln 3 3π -Gi = α + β 2 π (ln ω + γ) ( 34
)
where γ is Euler's constant. The set of boundary conditions ( 27), ( 28), (33), with the three matching conditions (34) are six linear equations between the six coefficients α, β, a, b, c, d. This defines an implicit relationship between the two parameters ω and q, so that there exists a non-trivial solution. It reads

-ηq[Gi ′ Ai -GiAi ′ ] - 1 π Ai ′ + qω 2 1 3 -Ai Gi ′ - ln 3 -4γ -3iπ -6 ln ω 3π -Gi Ai ′ = 0. ( 35
)
The particular value of the flutter instability threshold q c may be directly derived by assuming that ω is real in Eq.( 35). As all functions of q in (35) are real this implies that Ai ′ (-q c ) = 0; q c ≃ 1.02.

(36)

The real part of the frequency at the instability threshold is then derived using ( 35) and (36 ) as

ω 2 c = η Ai(-q c ) (1/3) -Ai(-q c ) . ( 37
)
At η = 0, the solution of [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF] for divergence is recovered, both in terms of critical load and frequency. Using this approximate solution, flutter is found to exist for all values of η, and the corresponding critical load does not vary with η. In Fig. 6(a) this is compared with the numerical solution for very long beams, ℓ = 100. The approximate solution, equation ( 36), predicts a lower bound, q c = 10.2, equal to that for η = 0. The flutter frequency is very well predicted, as may be seen in Fig. 6(b). At the instability threshold the modal shape ϕ is real and reduces to

ϕ(x) = x 0 Ai(s -p) ds - 1 3 . ( 38
)
This is compared, Fig. 7, with the computed mode shapes at ℓ = 10. For η = 0, Fig. 7(a), Eq. ( 38) is actually the exact solution for a semi-infinite beam, which derives from the results of [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF]. For η = 0.3 and even η = 1, it is remarkable that Eq. ( 38) stills gives a very good approximation of the mode shape at the flutter threshold, Figs. 7(b) and (c).

D. A model based on local wave stability

Following [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF], we consider now a criterion based on the local characteristics of waves, at a given position x. From Eq. ( 10), the dispersion relation is

k 4 -(q -x)k 2 -ω 2 = 0 ( 39
)
where k is the wavenumber and ω is the frequency of the wave. All points such that x < q bear unstable waves. Beams of length ℓ larger than q are expected to have a behaviour not affected by length as waves are damped above x = q In dimensional variables this allows us to define a the length L N for neutral stability,

L N = P mg , (40)
above which the medium only bears stable waves. In Eq. ( 1) this is the point where the local tension goes through zero. Considering that the part of the beam above this, Z > L N , plays a negligible role in the instability, we may approximate the critical load for the semi-infinite beam by that for a finite beam of length L N : a beam of length L N , without gravity, has a dimensional critical load where p c is the dimensionless critical load for short beams. As the length L N varies with the load P , this results in

P c = EI L 2 N p c . (41)
P 3 c = EI(mg) 2 p c . (42)
Using now dimensionless variables pertaining to the case of long beams, this reads

q c = p 1/3 c ; (43)
similarly, we have In Fig. 8(a) this is plotted for comparison with numerical results for the very long beam. The order of magnitude of the critical load is well recovered. Yet, divergence is predicted for η < 0.5, instead of flutter. Note also that the critical load at η = 1 is very well predicted. Figure 8(b) summarizes this approach: the limit line ℓ = q is found to be a good approximation of the transition between the behaviour of short beams, that depend on length, and that of long beams, that does not. For short beams the approximation of Eq. ( 13) applies. For long beams Eq. ( 43) is a good approximation.

ω c = Ω c p 2/3 c . ( 44
)

V. DISCUSSION

A. Domains of instability

In the results presented in this paper two regions can be indentified in a beam tensionned by a load such as gravity. In the part near the free end, x ≪ 1 in our dimensionless variables, that is Z ≪ L g = (EI/M g) 1/3 , the stiffness that opposes lateral displacement is dominantly that of the flexural rigidity. Conversely for x ≫ 1 the stiffness is due to the tension that results from gravity.

For a given beam, if its length L much smaller than L g , or ℓ ≪ 1, gravity effects can be neglected everywhere. In terms of stability the behaviour is that of short beams in our denomination. The upper boundary condition, here clamping, plays a crucial role, and the instabilty may be divergence or flutter. If the length is much larger than L g , so that ℓ ≫ 1, gravity effects dominate in all the upper part. This results in a confinement of the instabilty in the lower part of the beam, as it appeared in all the mode shapes. The upper boundary condition plays a lesser role. It is remarkable that the characteristics of the instability of these long beams seem to be much simpler than that of short beams: flutter prevails in all cases, and the critical load, the frequency and the mode shape have very simple evolutions.

For long beams flutter is reached when the load q is of order 1. In that range of loading the neutral point where tension vanishes, at x = q, is located near the limit between the two regions, x = 1. The critical load is then such that, in dimensionless variables

P ≃ (EI) 1/3 (mg) 2/3 , (45)
which shows the balance between the loading P and the two stiffnesses of the systems, EI for the flexural rigidity and mg for the tension induced by gravity.

It should be recalled here that damping was not considered in our calculations. Damping may significantly modify the critical value for flutter instability even when small [START_REF] Langthjem | Dynamic stability of columns subjected to follower loads: a survey[END_REF], and has been found to have both a stabilizing and destabilising effects. In some cases, such as that of Beck's column, it has been found that addition of damping destabilizes the system and changes the instability type from flutter to buckling. In gyroscopic systems such as fluid conveying-pipes or plates in axial flows, damping was found to destabilise neutral waves at zero frequency [START_REF] Doaré | Dissipation effect on local and global stability of fluid-conveying pipes[END_REF][START_REF] Doaré | Nonlinear Physical Systems: Spectral Analysis, Stability and Bifurcations, chapter Dissipation Effect on Local and Global Fluid-Elastic Instabilities[END_REF], which may also cause the instability to change from flutter to buckling in finite length systems. The generalisation to the present case of a semi-infinite system tensionned by gravity needs to be addressed to see how damping could alter the buckcling/flutter stability maps, and if it prevents flutter to prevail for all values of the follower force coefficient η.

B. Relation to flow-induced instabilities

The equivalence between the loading produced by the flow along a structure and a follower force exerted at its free end is discussed in [START_REF] Païdoussis | Fluid-Structure Interactions, slender structures and axial flows[END_REF][START_REF] Païdoussis | Fluid-Structure Interactions, slender structures and axial flows[END_REF]. Depending on the geometry of the problem, the load maybe either a fully follower load (fluid-conveying pipe) or partially a follower load (cylinder with axial flow). In the latter case, the shape of the downstream free end strongly influences the value of η.

For systems mainly tensionned by gravity, such as hanging fluid-conveying pipes or hanging ribbons under axial flow [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF][START_REF] Lemaitre | Instability of a long ribbon hanging in axial air flow[END_REF] the equations of motion can be put in the common dimensionless form

∂ 4 y ∂x 4 + ∂ ∂x (v 2 -x) ∂y ∂x + 2v β ∂ 2 y ∂x∂τ + ∂ 2 y ∂τ 2 = 0, (46)
where the dimensionless variables have been defined using the length L g , as we did in the present paper. Here v is a dimensionless flow velocity and β expresses the proportion of the fluid mass in the total mass. The boundary conditions at the lower end read

∂ 2 y ∂x 2 (0) = 0; ∂ 3 y ∂x 3 (0) = 0, (47)
which expresses the case of a purely follower load. Eq. ( 46) is identical to [START_REF] De Langre | Force suiveuse critique sur une colonne pesante semi-infinie: modèle et expériences[END_REF], except for the gyroscopic term which is dependent on β. The stability diagram for the case of a long hanging pipe has been analysed by [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF] and for long hanging ribbons by [START_REF] Lemaitre | Instability of a long ribbon hanging in axial air flow[END_REF]. The critical velocity v c was found to depend on the length in a manner very similar to that found in this For very long pipes flutter arises at a critical velocity v c that depends only on β. Defining q c = v 2 , and in the particular limit of β = 0, the results of [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF] should converge to that found in this paper for η = 1. This is not exactly the case when the results of [START_REF] Doaré | Local and global instability of fluid-conveying pipes on elastic foundations[END_REF] are used, as there calculations have been done for small but non vanishing values of β. It is a well known feature that the case β = 0 is only found as the limit of very small values (10 -3 ) of β [START_REF] Païdoussis | Fluid-Structure Interactions, slender structures and axial flows[END_REF]. If the tensioning load is not gravity but a flow-induced friction on the slender structure, the form of the problem is changed in several ways [START_REF] Païdoussis | Fluid-Structure Interactions, slender structures and axial flows[END_REF]. First, the tensioning load increases with the flow velocity, which does not allow one to define an equivalent to the length L g , as for gravity. The reference length that can then be defined scales the flow-induced forces that are proportionnal to volume (added stiffness forces) and those that are proportionnal to surface (friction). Second, the friction load is not constant in direction, as is gravity, but acts tangentially to the instantaneous position of the beam. Third, in the case of axial flow outside of a structure, the flow may also induce forces perpendicular to the instantaneous position of the beam, in the form of a transverse drag. Moreover, the boundary condition at the free end include other terms that depend on the local geometry of the flow. If all time dependent terms are neglected, to determine the static stability of the beam under flow, the equation defining the deflection reads [START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF] ∂ 4 y ∂s 4

+ v 2 ∂ ∂s (1 -s) ∂y ∂s = 0. ( 48
)
Upon defining x = v 2/3 s and q = v 2/3 , the equation for the static behaviour of the beam, Eq. ( 17), is recovered. If the end-condition sustains a force only in the beam axis, like in reference [START_REF] Naguleswaran | Transverse vibration of an uniform euler-bernoulli beam under linearly varying axial force[END_REF], the results at η = 0 are recovered. For the analysis of the dynamic instability not only inertial terms need to be considered, as in the case of this paper. A gyroscopic term, as in Eq. ( 46), and a damping term appear, further complicating the behaviour of the system. In the analysis of long towed cylinder [START_REF] De Langre | Flutter of long flexible cylinders in axial flow[END_REF] edge flutter was also found, confirming the generality of the results presented here in a generic case.

FIG. 1 :

 1 FIG.1: Semi-infinite hanging beam with a partially follower force.

FIG. 2 :

 2 FIG.2: Critical load, (a), and frequency at instability, (b), for short beams. Dashed vertical lines are guides for the eyes that do not correspond to calculations.

FIG. 3 :

 3 FIG. 3: Effect of length on the critical load for divergence and for flutter instabilities, (a) η = 0,(b) η = 0.2, (c) η = 0.3, (d) η = 1.. (-), present results for divergence; (--), present results for flutter; (o), computations by[START_REF] Naguleswaran | Transverse vibration of an uniform euler-bernoulli beam under linearly varying axial force[END_REF] for η = 0; (∆), computations by[START_REF] Triantafyllou | Analytic determination of the buckling speed of towed slender cylindrical beams[END_REF]..

FIG. 4 :FIG. 5 :

 45 FIG. 4: Effect of the ratio η on the critical load for divergence, (-), and for flutter, (--). (a) Short beam, ℓ = 1, (b) Long beam, ℓ = 100.

FIG. 6 :

 6 FIG. 6: Critical load qc, (a), and frequency ωc of flutter,(b), of a long beam. (-), numerical results for ℓ = 100; (-.-) solution for the semi-infinite beam using matched assymptotic expansions, Eqs. (36) and (37).

FIG. 7 :

 7 FIG. 7: Mode shape at the critical load for a long beam. (a) η = 0, (b) η = 0.3, (c) η = 1. (-), numerical results for ℓ = 10; (o), solution for the semi-infinite beam using matched assymptotic expansions, Eq.(38).

FIG. 8 :

 8 FIG. 8: Models for the critical load based on local wave stability, (a) critical load (-) numerical results for ℓ = 100; (--), model based on local wave stability, Eq. (43) and (44). (b) Effect of length η = 1. (-), computations of Section III B; (--), short beam model; (...), transition line; (-.-), long beam model.


Tom Sebastian

Joachim Niehren

Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams

We present an evaluator for navigational XPath on Xml streams with projection. The idea is to project away those parts of an Xml stream that are irrelevant for evaluating a given XPath query. This task is relevant for processing Xml streams in general since all Xml standard languages are based on XPath. The best existing streaming algorithm for navigational XPath queries runs nested word automata. Therefore, we develop a projection algorithm for nested word automata, for the first time to the best of our knowledge. It turns out that projection can speed up the evaluation of navigational XPath queries on Xml streams by a factor of 4 in average on the usual XPath benchmarks.

Introduction

Projection is most relevant for efficient Xml processing algorithms, as shown for in-memory evaluators for XQuery in [START_REF] Marian | Projecting XML documents[END_REF] and for a fragment of in XPath [START_REF] Maneth | XPath whole query optimization[END_REF]. The projection algorithm for XQuery runs in Saxon [START_REF] Kay | The saxon XSLT and XQuery processor[END_REF], today's most used Xml processing tool. Projection algorithms for the in-memory evaluation of Xslt are missing though.

The objective of the present paper is to initiate the development of projection algorithms for processing Xml streams. Given that a single program written in one of the Xml standards XQuery, Xslt, or XProc contains a collection of XPath queries, we are interested in the evaluation of a collection of XPath queries on a single input stream. The parsing time can be shared between many XPath queries, and thus be should counted seperately. Therefore, we are mainly interested in the parsing-free time for query evaluation. Note however, that the parsing-free time for a single query is often dominated by the parsing time.

We will restrict ourselves to projection for navigational XPath queries, since these are fundamental to all others. For instance, in order to check whether the root of a tree has at least 5 a-children, all other children of the root can be projected. The computation of the projection still requires to read the entire input tree, but the time for this can be shared similarly to the parsing time.

The most efficient evaluation algorithm for navigational XPath queries on Xml streams so far was presented in [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF]. Similarly to many recent evaluation algorithms for XPath on Xml streams [START_REF] Madhusudan | Query automata for nested words[END_REF][START_REF] Mozafari | High-performance complex event processing over XML streams[END_REF][START_REF] Gauwin | Streamable fragments of forward XPath[END_REF], it is based on the compilation of navigational XPath queries to nested word automata (Nwas) [START_REF] Alur | Adding nesting structure to words[END_REF]. Given that Xml streams are nested words, Nwas provide a canonical formalism for defining algorithms on Xml streams. This leads to highly efficient algorithms based on first principles as argued in [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF]: In particular, one can rely on the nondeterminism of Nwas to express XPath queries with recursive axes, such as "descendant" or "following", and then use on-the-fly determinization for their evaluation. The evaluation of an XPath query can then be reduced to running an Nwa on all possible answer candidates. Furthermore, the runs of multiple answer candidates in the same state can be shared.

Projection for finite automata is well known [START_REF] Frisch | Regular tree language recognition with static information[END_REF][START_REF] Maneth | XPath whole query optimization[END_REF]. It amounts to project away all letters of the input word that do not change the state. Projection for Nwas is more tedious, since such automata have a stack by which they can pass information from opening tags to corresponding closing tags. Therefore, one cannot simply project an opening tag away without taking care of the corresponding closing tag. Our idea is that a projected nested word should contain jump symbols i . . . for projected factors, where the integer i stands for the excess of the factor, i.e., the difference between the number of opening and closing tags. We present projection nested word automata ( PNwas), a kind of mixed pushdown and counting automata, that input projected nested words which beside others contain integers as letters. These integers allow the automaton to compute the depth of the current node of the tree at any time, and also the excess of the last jump. Conversely, a projection of a nested word with respect to a given Nwa can be computed by any corresponding PNwa. It may be surprising, but it turns out there may exist different PNwas with maximal projection for the same Nwa. Therefore, our projection algorithm has to make its choices.

We then lift Nwa projection to the evaluation of navigational XPath queries on Xml streams. It turns out that the parsing-free time for query answering is reduced by a factor of 4 on average on the usual XPathMark benchmark compared to the previously existing algorithm [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF]. Outline. In Section 2, we recall Nwas and their usage for XPath evaluation on Xml streams. In Section 3, we introduce PNwas. In Section 4, we introduce notions of irrelevant labels and prefixes of nested words for states of Nwas. In Section 5, we use them to project Nwas to PNwas. In Section 6, we present our experimental results for XPath evaluation on Xml streams. The appendix of the present paper at hal.inria.fr/hal-01182529 contains additional examples of PNwas, an extension of Nwa projection for node selection, and the collection of queries used in our experiments.

Nested Word Automata

We recall the definition of Nwas, while pointing out the close relationship between nested words and Xml streams.

Let Σ be a finite alphabet. Let P Σ be the set of parenthesis with labels in Σ, that is the set of opening tags a and closing tags /a where a ∈ Σ. A nested word over Σ is a word over P Σ which is well-balanced, so that any opening tag a can be assigned to a unique corresponding closing tag /a , and vice versa, and such that the initial opening tag of the word corresponds to the closing tag at its end. Our nested words are more restricted than in the general case [START_REF] Alur | Adding nesting structure to words[END_REF], in that internal symbols are omitted, corresponding opening and closing tags must have the same label, and initial opening tags cannot be closed before the end.

An Xml stream is a nested word that is obtained by linearizing an unranked tree in document order. This is a strong simplification of the Xml data model, in that we ignore data values (internal symbols) and the different types of nodes (text, element, attribute, etc). An example of an unranked tree is given in Fig. 1. The Xml stream obtained by linearizing this unranked tree into a nested word is given in Fig. 2. It should be mentioned that we cannot assume any a priori knowledge on the set of tags of an Xml document in practice (where no Xml schemas are available). Instead, the finite alphabet Σ is determined by the tags appearing in the XPath query of interest [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF].

An Nwa is a pushdown automaton on nested words [START_REF] Alur | Adding nesting structure to words[END_REF], whose stack is "visible" in the sense that only a single symbol is pushed at opening events and popped at closing events. Here we assume that Nwas are early [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF], so that whenever a final state is reached, any continuation completing the nested word will be accepted. More formally, an (early) Nwa is a tuple A = (Σ, Q, I, F, Γ, R) where Σ is a finite alphabet, Q a finite set of states with subsets I, F ⊆ Q of initial and final states, Γ a finite set of stack symbols, and R is a set of transition rules of the following two types, where q, q ′ ∈ Q, a ∈ Σ, and γ ∈ Γ :

Open: q a ↓γ ---→ q ′ . When processing an opening tag a , γ is pushed onto the stack, and the state is changed from q to q ′ . Close: q /a ↑γ ----→ q ′ . When processing a closing tag /a , γ is popped from the stack and the state is changed from q to q ′ . A configuration of an Nwa is a word in QΓ * consisting of a state q ∈ Q and a stack S ∈ Γ * . A run of an Nwa on a nested word w ∈ P * Σ is a function r that maps prefixes w ′ of w to configurations. The initial configuration must contain an initial state and the empty stack, i.e. r(ǫ) ∈ I. The Nwa then rewrites this configuration: for any prefix w ′ p of w, r(w ′ p) is produced from r(w ′ ) by applying some rules consuming tag p ∈ P Σ . A run on w is successful if r(w) ∈ F , i.e. if it reaches at the end a final state and the empty stack. Since we assume early Nwas, any run reaching a configuration with a final state on some prefix of a nested word can always be continued into a successful run. The language L(A) of an Nwa A is the set of all nested words that permit a successful run by A.

q1 i -label ∅ q2 i -label {b,c} q3 i -label {a} i -tree {c}\{a} q4 i -label Σ qrej i -label ∅ Σ ↓ α /c ↑ γ a ↓ α /a ↑ α c ↓ γ b ↓ α {b, c} ↓ β ′ /{b, c} ↑ β ′ a ↓ β /a ↑ β Σ ↓ δ /Σ ↑ δ /Σ ↑ α /Σ ↑ β /Σ ↑ β ′ /Σ ↑ α
An Nwa is called deterministic if it is deterministic as a pushdown automaton. Note that Nwas can always be determinized [START_REF] Alur | Adding nesting structure to words[END_REF] in contrast to more general pushdown automata. Our streaming algorithms will determinize Nwas constructed from XPath expressions on the fly (as explained in [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF]), so that we will only have to project deterministic Nwas but this while creating them on the fly.

An example for a deterministic Nwas is given in Fig. 3. It defines the XPath filter [//a/b] which accepts all Xml trees that contain some a-descendant with a b-child. Rules containing label sets represent sets of rules, one for each label. Node selection XPath queries can be compiled to deterministic Nwas in a similar manner [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF] by adding variables to the alphabet. This requires some minor extensions for Nwa projection which are out of the scope of the present paper.

Projection NWAs

We next introduce projected nested words. Let N be the set of natural numbers, N 0 = N ⊎ {0}, and Z the set of integers. For any unranked tree, we are interested in the binary node relations child ch, descendant ch + , n-th grand parents ch -n where n ∈ N, descendants of n-th grand parents ch -n /ch + , children of n-th grand parents ch -n /ch, and stay at self. So let:

Rels = {ch, ch + , ch -n , ch -n /ch + , ch -n /ch, self | n ∈ N}.
A projected nested word is a word whose letters are jump symbols i . . . where i ∈ Z and jump targets p@r where p ∈ P Σ and r ∈ Rels. We write P ... Σ for the set of all these letters. We assume that any jump target is proceeded by a jump symbol that indicates the excess of the jump, that is the depth difference in the tree or equivalently, the difference of the numbers of opening and closing tags in the nested word. We also assume that projected nested words are well-nested up to jumping.

Two examples for projected nested words are given in Fig. 4. Both are valid descriptions of the nested word in Fig. 2: pw 1 projects to the letters drawn in blue, while pw 2 projects to the letters drawn in green. As we will see, both projections can be obtained from the Nwa in Fig. 3. Note that the initial opening tag is always kept for technical reasons. Except of this, both projections are pw 1 : for all a-nodes without an a-parent and all non-a-children of a-nodes keep the opening and closing tags, until the opening tag of the first match of //a/b:

c 0 . . . a @ch + 2 . . . c @ch + 0 . . . /c @self -2 . . . c @ch -3 /ch + 0 . . . a @ch + 0 . . . /a @self 0 . . . /c @ch -1 0 . . . b @ch -1 /ch +
c 0 . . . a @ch + 0 . . . a @ch + 0 . . . a @ch + 0 . . . /a @self 0 . . . /a @ch -1 1 . . . a @ch -1 /ch + 0 . . . /a @self -1 . . . b @ch -2 /ch
Fig. 4: Two projected nested words describing the nested word in Fig. 2.

maximal, in that no further tags can be projected away: they just preserve enough information for deciding whether the original nested word satisfies the filter [//a/b]. Nevertheless, none of these two projections is more general than the other. The green projection pw 2 has the advantage to keep only tags with letters occurring in the XPath filter [//a/b]. The blue projection pw 1 , has the advantage to keep fewer of these tags, but therefore, it also keeps some others. The blue projection pw 1 starts with c , meaning that any matching nested word must start with c . The next factor 0 . . . a @ch + describes a nested word with excess 0 that is followed by a in descendant position, i.e., by the opening tag of an a-child of the root. The next factor 2 . . . c @ch + describes a nested word with excess 2 followed by c opening a descendant. Then 0 . . . /c @self requires to jump with excess 0 to the closing tag /c of the same node. Next, -2 . . . c @ch -3 /ch + asks to jump with excess -2 to an opening tag c of a descendant of a grand-grand-grand-parent, etc.

We next introduce PNwas as a mixture of a pushdown and a counting automaton, that receive projected nested words as input. The counting serves for updating the depths of nodes when jumping, so that the depth of the current node can always be deduced from the current stack. Whenever jumping over a projected factor, the excess of this factor is pushed. This is an integer that is popped when trying to close the jump. Q,I,F,Γ,R) like an Nwa but with different kinds of transition rules: given a ∈ Σ, γ ∈ Γ , and q, q ′ ∈ Q, there are rules of the following types in R, for changing the state from q to q ′ . Open: q a ↓γ ----→ q ′ Like for Nwas.

Definition 1 A PNwa is a tuple A = (Σ,

Close: q

/a ↑γ ----→ q ′ . Like for Nwas.

Jump to a child or a descendant: q z ... a @r ↓z↓γ --------→ ∀z≥0 q ′ , where r ∈ {ch, ch + }.

When r = ch then z must be 0, and we jump to the opening tag of an a-child and push first 0 and then γ onto the stack. When r = ch + then we jump over z descendants to the opening tag of an a-descendant, and push first z and then γ onto the stack. For short we denote this transition as q ju( a ,r,γ) -------→ q ′ . Rejump to another child or descendant:

q z ... a @ch -(z ′ +1) /r ↑z ′ ↓z+z ′ ↓γ -------------------→ ∀z,z ′ . z ′ ≥0,z+z ′ ≥0 q ′ ,
where r ∈ {ch, ch + }.

While trying to close a jump from some grand parent to some node one can rejump to another opening a-tag of a child or a descendant of the same grand parent. The excess of the jump to the first node z ′ on the stack is updated to the excess of the second node z + z ′ . Furthermore, γ is pushed. For short, we write this transition as q reju( a ,r,γ)

--------→ q ′ .
Jump to the closing tag of the self node: q 0 ... /a @self ↑γ ---------→ q ′ . Jump to the closing tag of the self a-node. In this case, γ is popped from the stack.

Jump back to the jump's origin: q -z ... /a @ch -(z+1) ↑z↑γ --------------→ ∀z≥0 q ′ . When trying to close a jump, one may jump back to the closing tag of the a-node where the current jump started. The excess of -z is popped from the stack together with the symbol γ which was pushed for the non-jumped a-node. For short we write q ju-back( /a ,γ)

----------→ q ′ .
Close last jump step: q /a ↑z↓z-1 --------→ ∀z>0 q ′ . When trying to close a jump, one may read a closing a-tag for which the corresponding opening a-tag was jumped, so that no stack symbol was pushed. In this case the excess of the jump on the stack must be updated from z to z -1.

A configuration of a PNwa is a word in Q(Γ ⊎ N 0 ) * consisting of a state in Q and a stack in (Γ ⊎ N 0 ) * . A run r of a PNwa A on a projected nested word over Σ is a function that maps any prefix of the projected nested word to a configuration. The run must start in some configuration with some initial state and the empty stack, i.e., r(ǫ) ∈ I. Furthermore, for any prefix wl where l ∈ P ... Σ , the configuration r(w) must be transformed into r(wl) by applying some rule consuming letter l. A run on a projected nested word w is called successful if it eventually reaches a configuration with a final state, i.e., if r(w ′ ) ∈ F (Γ ⊎N 0 ) * for some prefix w ′ of w. The language L(A) of a PNwa A is the set of all projected nested words that permit a successful run on A.

In Fig. 5 we present PNwa A 1 that is a projection of the Nwa in Fig. 3 for the XPath filter [//a/b]. This automaton accepts the blue projection pw 1 in Fig. 4 of the nested word in Fig. 2. Automaton A 1 visits the opening and closing tags of all a-nodes with no a-parent, and of all non-a-children of these a-nodes, and jumps over all other nodes. Automaton A 1 accepts when the first match of [//a/b] arrives. In Fig. 6, we illustrate a successful run of A 1 on pw 1 . The states of configurations are placed below the tags, while the stack consists of the labels on the subedges above the state. Edges between tags indicate their correspondence. Furthermore there are edges for jumps to children and descendants, where the excess is pushed, while jumps to the jump origin close the jump, and rejumps update the excess on the stack. The only exceptions are jumps to the closing tag of self nodes, where no excess is pushed. In general PNwa A 1 works as follows. It starts in the initial state q 1 , it opens the root and goes into q 2 , where either the root can be closed to q rej or where it can jump over b and c nodes to the opening tag of an a-descendant and go to q 3 . There are 3 possibilities depending on what happens first: (1) close the a-node, and go to q 2 [q 2 ], (2) jump down over a sequence of a-nodes to the opening tag of a c-descendant and go to q 2 , or (3) jump down over a sequence of a-nodes to the opening tag of a b-descendant and accept in q 4 . In state q 2 a c-node with a sequence of a-grand parents can be closed to q 3 [q 3 ]. The sequence of a-grand parents consists of a sequence of jumped a-nodes and one not jumped a-node π at the top. Continuing depending on what comes first, the following can happen in q 3 [q 3 ]: (1) jump back to the closing tag of the a-grand parent π and go to q 2 [q 2 ], (2) rejump over a sequence of a-nodes, while staying below π, to the opening tag of a c-descendant and go to q 2 , or (3) rejump over a sequence of a-nodes, while staying below π, to the opening tag of a b-descendant, and accept in state q 4 . In state q 2 [q 2 ] there are 3 possibilities depending on what happens first: (1) rejump over a sequence q L ↓ γ /L ↑ γ Fig. 7:

q1 q2 q3 q4 qrej q3[q3] q2[q2] Σ ↓ α I ju( a , ch + , α[q2]) II ju( c , ch + , γ[q3]) II ju( b , ch + , α[q3]) II 0 . . . /c @self ↑ γ[q3] V ju-back ( /a , α[q2]) V reju( c , ch + , γ[q3]) II 0 . . . /a @self ↑ α[q2] V ju-back ( /c , γ[q3]) V reju( a , ch + , α[q2]) II reju( b , ch + , α[q3]) II ju -b a c k ( / Σ , α ) V 0 . . . / Σ @ s e lf ↑ α V
@ch + q3 2 . . . c @ch + q2 0 . . . /c @self q3[q3] -2 . . . c @ch -3 /ch + q2 0 . . . a @ch + q3 0 . . . /a @self q2[q2] 0 . . . /c @ch -1 q3[q3] 0 . . . b @ch -1 /ch + q4 γ[q3] 2 0 α[q2] 0 γ[q3] α[q3] 0 α[q2]
q ∈ i-label L . q q ′ L ↓ γ /L ↑ γ L ′ ↓ γ ′′ Σ \ {L ′ } ↓ γ ′ /Σ \ {L ′ } ↑ γ ′ Fig. 8: q ∈ i-tree L\L ′ .
of b and c nodes to the opening tag of an a-descendant and goto q 3 , while staying below a not-jumped c-grand parent with a sequence of a-grand parents if exists, (2) jump back to the closing tag of a not-jumped c-grand parent with the a-grand parents sequence if exists, or else (3) close the root to q rej . Next we are interested to evaluate a collection of PNwas obtained from deterministic Nwas on a single nested word. For this, we need to project the nested word with respect to the PNwas, and run the PNwas on the respective projected nested word. Therefore, we have to define how to project a nested word w with respect to a deterministic PNwa. More generally, we define a projection π q (w) for any suffix w of some nested word in P * Σ and state q of a PNwa A:

π q (w) = i . . . p@r π q ′ (w ′′ )
such that w = w ′ pw ′′ for some p ∈ P Σ and w ′ , w ′′ ∈ P * Σ , where w ′ is the shortest prefix, so that there exists a rule of A from q to q ′ consuming letter p@r for some r ∈ Rels, and i is the excess of w ′ .

Irrelevant Labels and Prefixes of Nested Words

In this section, we define properties of Nwa states which allow to skip parenthesis with irrelevant labels and irrelevant prefixes of nested words, that is prefixes of linearizations of subtrees.

Definition 2 An Nwa E can jump over parenthesis with labels in L and incoming state q -in formulas q ∈ i-label L -if there exists a stack symbol γ, such that E has all transitions shown in Fig. 7, no other opening transition pushing γ, no other a-opening transition in q, and no other a-closing transition with γ.

If q ∈ i-label L then any sequence of letters in P L is irrelevant in state q, so that it can be removed from the nested word and replaced by a jump symbol. Consider a run of E on a nested word w and assume q ∈ i-label L . We next argue, that we can replace all letters in P L of w with ingoing state q by jump symbols, while "repairing" the run. The first point is that the state is not changed when reading such letters, so that their removal keeps the states correct. But we must also take care of the stack. If an opening tag a is removed but not the corresponding closing tag, then we have to repair the run, in order to be able to reproduce the missing stack symbol when needed. The idea is to memoize the state before jumping. Since this state does not change while jumping, one can then recompute the stack symbol that was pushed for any letter that was jumped over. Conversely, it is not possible that a closing tag /a was removed but not the corresponding opening tag, since the symbol pushed at a must be γ, and by definition of q ∈ i-label L there is no other opening transition pushing γ than that started in q.

Definition 3 An Nwa E in state q can jump over prefixes of nested words (subtrees) that start in L , do not contain letters in P L ′ , and either end with the closing tag of the subtree's root or with a letter in L ′ , if there exist three different stack symbols γ, γ ′ , γ ′′ and a state q ′ such that the transitions shown in Fig. 8 exist, but no further opening transitions with γ, no further transitions with γ ′ , and no further opening transitions in q ′ for L ′ , and no further closing transition in q for L popping γ. In this case, we write q ∈ i-tree L\L ′ and call q a state of irrelevant subtrees.

In the easiest case where q ∈ i-tree L\∅ one can jump over nested words linearizing subtrees, with incoming state q and labels in L only. When opening the root of the subtree, the state changes to q ′ and stays there until closing the root and going back to q. So the removal of the subtree does not change the state globally. In this case, the full nested word of the subtree is read, so the stack difference is zero. In the case where L ′ = ∅ it is more tricky to repair the run, in order to deal with missing stack symbols. But it remains possible, since the state used within the subtree does not change, so that it can be memoized and so that missing stack symbols can be recomputed at closing time.

For illustration, we have annotated the state of the Nwa in Fig. 3 with the properties that they satisfy. It turns out that state q 3 satisfies both properties i-label {a} and i-tree {c}\{a} , but that we cannot perform the two corresponding projections at the same time. When choosing projection with i-label {a} then we obtain the PNwa A 1 from Fig. 5.

Projection from Nwas to PNwas

We show how to project deterministic Nwas E to a PNwa A. For any state q of E, we chose a projection property choice(p), which is either i-label L or i-tree L\L ′ for some sets L, L ′ ⊆ Σ. Note that i-label ∅ can always be assigned, so that this assumption can always be satisfied, but not always in a unique manner.

Any state of A is either a state of q of E or a pair of states of E that we write as q[q ′ ]. Such a pair means that one is in state q and that on the top of the stack is a jump symbol i that was pushed from a jump over i descendants that started in state q ′ . Any stack symbol of A is either a stack symbol γ of E or a pair written as γ[q] of a stack symbol and a state of E. γ serves as the stack symbol that was pushed before at opening tags, while q is the state where a previous jump started. Whenever such a pair γ[q] is on the stack then the symbol below is always a jump symbol i that was pushed by a jump over i descendants that started in state q. The sets of initial and final states remain unchanged.

Every transition rule of E gives rise to a possible empty set of transition rules of A, according to rules I-VII in Fig. 9. In PNwa A 1 from Fig. 5 we annotated transitions accordingly. Transitions from an initial state are translated to nonjumping transitions that open the root. If choice(q) = i-label L , then all looping transitions required by i-label L are removed. The other opening transitions starting from q are translated to jumping and rejumping transitions to descendants and descendants of grand parents. If choice(q) = i-tree L\∅ then the opening and closing L transitions, and looping transitions required by i-tree L\∅ are removed. The other opening transitions starting from q are translated to jumping and rejumping rules to children and children of grand parents. If choice(q) = i-tree L→L ′ then the opening and closing L transitions, and looping transitions required by i-tree L→L ′ are removed. All other transitions with opening tag a ∈ L ′ departing q are translated to jumping and rejumping rules for descendants. Closing transitions are translated to six rules: Two rules to close self nodes, two rules to jump back to jump's origins, and two last rules that close parents in a state q[q ′′ ] for q = q ′′ . Those states do not allow to rejump, since the previous jump started in a different state q ′′ than the current state q, and therefore they also do not allow to jump back to the jump's origin. For these states opening and closing transitions are translated as indicated, while recomputing stack symbols, that have not been pushed for jumped grand parents.

Proposition 1 (Soundness) Let E be a deterministic Nwa E with initial state q 0 and A be a PNwa obtained from E by our projection algorithm. It then holds for any nested word w that w ∈ L(E) if and only if π q0 (w) ∈ L(A).

Experiments

We implemented Nwa projection within the QuiXPath system [START_REF] Debarbieux | Quix-tool suite[END_REF] and tested it on the (revised) XPathMark query set [START_REF] Franceschet | XPathMark: An XPath benchmark for the XMark generated data[END_REF] for navigational queries. As argued in the introduction, it is most natural to measure the efficiency in parsing-free time which can be measured as described in [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF].

In a first experiment, we start from the best existing XPath evaluator on Xml streams so far which is based on Nwas [START_REF] Debarbieux | Early nested word automata for XPath query answering on XML streams[END_REF] (see there for comparisons to alternative tools by [START_REF] Kay | The saxon XSLT and XQuery processor[END_REF][START_REF] Mozafari | High-performance complex event processing over XML streams[END_REF] and others), and enhance it with projection. The results are presented in Fig. 10 for a 559 MB XPathMark document. It turns out that projection reduces the parsing-free running time for this query set by a factor of 4.3, which is a major improvement, in particular when evaluating many XPath queries in parallel as needed for streaming Xslt or XQuery In our second experiment, we compare the overall running time of our PNwa evaluator of XPath queries on Xml streams with Saxon's in-memory evaluator [START_REF] Kay | The saxon XSLT and XQuery processor[END_REF]. For each of our queries, we compare the full running times including parsing, when evaluating the query n-times. The results are given in Fig. 11. It turns out that QuiXPath with projection for Nwas can answer on average a query up to 12 times in parallel, in no more time than needed by Saxon for the same task.

One observes that running less than 12 queries in parallel with PNwas is a lot quicker than running them with Saxon, mostly due to the expensive in-memory I: q q ′ a ↓ α q ∈ I =⇒ q q ′ a ↓ α II: q q ′ a ↓ α a / ∈ L = ∅, q / ∈ I =⇒ choice(q) = i -labelL q q ′ q[q] ju( a , ch + , α[q] ) reju ( a , ch + , α[q] ) III: q q ′ a ↓ α a / ∈ L = ∅, q / ∈ I =⇒ choice(q) = i -tree L\∅ or choice(q) = i -label ∅ q q ′ q[q] ju( a , ch, α[q] ) reju ( a , ch, α[q] ) IV: q a ↓ α a / ∈ L = ∅, a ∈ L ′ , q / ∈ I =⇒ choice(q) = i -tree L\L ′ q q[q] ju( a , ch + , α[q ′ ]) a , ch + , α[q]) V: q q ′ /a ↑ α q = q ′′ =⇒ q q ′ [q ′′′ ] q ′ q[q] q[q ′′ ] 0 . . . /a @ se lf ↑ α[ q ′′′ ] j ub a c k ( / a , α ) ju-back ( /a , α[q ′′′ ]) 0 . . . /a @ se lf ↑ α 0 . . . /a @ch -1 ↑ 0 ↑ α 0 . . . / a @ c h -1 ↑ 0 ↑ α [q ′′ ′ ] VI: q q ′ a ↓ α q = q ′′ =⇒ q ′ q[q ′′ ] a ↓ α[q ′′ ] VII: tree creation. But when running more than 12 queries on small documents, the advantage of in-memory evaluation takes over. Indeed, without the time for parsing and in-memory tree construction, Saxon in-memory evaluation is still faster by a factor 20 in average than streaming with PNwas. With the improvements of the present paper, it now seems possible that stream processing can become more efficient than in-memory evaluation in practice in the future.

q q ′ /a ↑ α q ′′ q ′′′ a ↓ α q = q ′′ =⇒ q[q ′′ ] q ′ [q ′′ ] /a ↑ z ↓ z -1 ∀z > 0

Conclusion and Future Work

We have developed a projection algorithm for evaluation navigational XPath queries on Xml streams. The next step will be to lift this algorithm to all of XPath 3.0. We believe that this can be done by decomposing general XPath queries into a network of navigational XPath queries. Such a decomposition underlies the implementation of XPath 3.0 in our QuiXPath tool [START_REF] Debarbieux | Quix-tool suite[END_REF], which is unpublished so far. Once this is done, one can hope to lift our XPath projection to Xslt and XQuery, by using X-Fun as an intermediate language [START_REF] Labath | A uniform programming language for implementing XML standards[END_REF].

Fig. 1 :Fig. 2 :

 12 Fig. 1: An unranked tree.

Fig. 3 :

 3 Fig. 3: A deterministic Nwa over Σ = {a, b, c} for XPath filter [//a/b].

pw 2 :

 2 for all a-nodes and all b-children of a-nodes keep the opening and closing tags, until the opening tag of the first match of //a/b:

Fig. 5 :

 5 Fig. 5: PNwa A 1 for the XPath filter [//a/b].

0 αFig. 6 :

 06 Fig. 6: A successful run of the PNwa A 1 of Fig. 5 on pw 1 .

Fig. 9 :

 9 Fig. 9: Rewriting system for rules of a deterministic Nwa to rules of the PNwa.

Fig. 10 :Fig. 11 :

 1011 Fig. 10: Improvement by Nwa projection of XPath query evaluation.