Falk M Hante
email: hante@iecn.u-nancy.fr

Mario Sigalotti
email: mario.sigalotti@inria.fr.

CONVERSE LYAPUNOV THEOREMS FOR SWITCHED SYSTEMS IN BANACH AND HILBERT SPACES

We consider switched systems on Banach and Hilbert spaces governed by strongly continuous one-parameter semigroups of linear evolution operators. We provide necessary and sufficient conditions for their global exponential stability, uniform with respect to the switching signal, in terms of the existence of a Lyapunov function common to all modes.

INTRODUCTION

It is well known that the existence of a common Lyapunov function is necessary and sufficient for the global uniform asymptotic stability of finite-dimensional continuous-time switched dynamical systems [START_REF] Lin | A smooth converse Lyapunov theorem for robust stability[END_REF]. In the linear finite-dimensional case, the existence of a common Lyapunov function is actually equivalent to global uniform exponential stability [START_REF] Molchanov | Lyapunov functions that specify necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems, I, II[END_REF][START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encountered in control theory[END_REF] and, provided that the system has finitely many modes, the Lyapunov function can be taken polyhedral or polynomial (see [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF][START_REF] Blanchini | A new class of universal Lyapunov functions for the control of uncertain linear systems[END_REF][START_REF] Wijesuriya | A converse Lyapunov theorem for a class of dynamical systems which undergo switching[END_REF] and also [START_REF] Brayton | Constructive stability and asymptotic stability of dynamical systems[END_REF] for a discrete-time version). A special role in the switched control literature has been played by common quadratic Lyapunov functions, since their existence can be tested rather efficiently (see the surveys [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF][START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF] and the references therein). It is known, however, that the existence of a common quadratic Lyapunov function is not necessary for the global uniform exponential stability of a linear switched system with finitely many modes. Moreover, there exists no uniform upper bound on the minimal degree of a common polynomial Lyapunov function [START_REF] Mason | Common polynomial Lyapunov functions for linear switched systems[END_REF].

The scope of this paper is to prove that the existence of a common Lyapunov function is equivalent to the global uniform exponential stability of infinite-dimensional switched systems of the type    d dt x(t) = A σ(t) x(t), t > 0

x(0) = x ∈ X (1)
where each A j is a (possibly unbounded) operator generating a strongly continuous semigroup T j (t) on a Banach space X and σ(•) belongs to the class of piecewise constant switching signals with values in an index set Q. Such systems provide a convenient design paradigm for modeling a wide variety of complex processes comprising distributed parameters, see [START_REF] Falk | Modeling and analysis of modal switching in networked transport systems[END_REF] and the references therein for examples in the context of networked transport systems.

Except for special cases, that is, when X has a Hilbert structure and the infinitesimal generators A j commute pairwise [START_REF] Sasane | Stability of switching infinite-dimensional systems[END_REF], when the switching signals satisfy a dwell-time constraint [START_REF] Michel | Stability analysis of discountinuous dynamical systems determined by semigroups[END_REF] or when A j is a linear convection-reaction operator with reflecting boundary conditions [START_REF] Amin | Stability analysis of linear hyperbolic systems with switching parameters and boundary conditions[END_REF], global uniform exponential stability of systems such as [START_REF] Amin | Stability analysis of linear hyperbolic systems with switching parameters and boundary conditions[END_REF] has not been investigated (up to our knowledge).

The characterization of exponential stability for a single linear dynamical system on Banach and Hilbert spaces dates back to Datko [START_REF] Datko | An extension of a theorem of A. M. Lyapunov to semigroups of operators[END_REF] and Pazy [START_REF] Pazy | On the applicability of Lyapunov's theorem in Hilbert space[END_REF] and has, since then, seen a broad range of applications in control theory for partial differential equations (see, for instance, [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF]). However, we recall that exponential stability of all subsystems (with σ(t) ≡ j fixed in [START_REF] Amin | Stability analysis of linear hyperbolic systems with switching parameters and boundary conditions[END_REF]) is of course necessary but not sufficient for the global uniform exponential stability with respect to all possible switching laws σ(•). This is a classical result for the finite dimensional case and we give an infinite dimensional variant with interesting destabilizing properties in Example 1 below.

Our starting point will be a switching system of the general form

x(t k+1 ) = T σ(t k ) (t k+1 -t k )x(t k ), k ∈ N, x(0) = x 0 ∈ X, (2)
where

σ : [0, ∞) → Q is a piecewise constant right-continuous switching signal with switching times 0 = t 0 < t 1 < • • • < t k < • • • . Each t → T j (t), j ∈ Q, is a strongly continuous semigroup on a Banach space X. If t ∈ (t k , t k+1 ), then x(t) = T σ(t k ) (t -t k )x(t k
). This framework includes, in particular, switched dynamical systems such as (1), even with the infinitesimal generators A j not sharing a common domain and also in the case of infinitely many available modes Q. (The semigroup formulation (2) corresponds to the choice of mild solutions for the Cauchy problem [START_REF] Amin | Stability analysis of linear hyperbolic systems with switching parameters and boundary conditions[END_REF]. The two formulations are clearly equivalent when X has finite dimension, with

T j (t) = e tAj .)
The main result of this paper is that the following three conditions are equivalent: (A) There exist two constants K ≥ 1 and µ > 0 such that, for every σ(•) and every x 0 , the solution x(•) to (2) satisfies

x(t) X ≤ Ke -µt x 0 X , t ≥ 0. (3)
(B) There exist two constants M ≥ 1 and ω > 0 such that, for every σ(•) and every x 0 , the solution x(•) to (2) satisfies

x(t) X ≤ M e ωt x 0 X , t ≥ 0, (4)
and there exists V :

X → [0, ∞) such that V (•) is a norm on X, V (x) ≤ C x 2 X , x ∈ X (5)
for a constant C > 0 and

lim inf t↓0 V (T j (t)x) -V (x) t ≤ -x 2 X , j ∈ Q, x ∈ X. ( 6
) (C) There exists V : X → [0, ∞) such that V (•) is a norm on X, c x 2 X ≤ V (x) ≤ C x 2 X , x ∈ X (7)
for some constants c, C > 0 and

lim inf t↓0 V (T j (t)x) -V (x) t ≤ -x 2 X , j ∈ Q, x ∈ X. (8)
The equivalence between (A) and (C) extends to infinite-dimensional systems the well-known result obtained in [START_REF] Molchanov | Lyapunov functions that specify necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems, I, II[END_REF] in the finite-dimensional setting.

Conditions ( 5) and [START_REF] Datko | An extension of a theorem of A. M. Lyapunov to semigroups of operators[END_REF] are redundant in the case of finite-dimensional systems, since V (•) and • X are comparable, by compactness of the unit sphere. Hence, condition (4) in (B) could be dropped for finite-dimensional systems. This is not the case for infinite-dimensional ones, as illustrated in Remark 4 by an example.

From the point of view of applications, condition (B), imposing less conditions on V than (C), is better suited for establishing that (A) holds (although the uniform exponential growth boundedness needs also be proved). On the other hand, the implication (A)⇒(C) can be used to select a Lyapunov function with tighter requirements.

The construction of a common Lyapunov function satisfying (B), under the assumption that (A) holds true, follows the same lines as in finite dimension. In particular, a possible choice of the Lyapunov function is 2 dt, as done in [START_REF] Falk | Converse Lyapunov theorems for switched systems in Banach spaces[END_REF].) The construction of a Lyapunov function satisfying (C) is similar, but one has to augment (2) with a further mode T j * (t) = e -µt I (where µ > 0 is the constant appearing in (A) and I denotes the identity on X) and to consider all the solutions to this augmented system in the definition of V .

V (x 0 ) = sup ∞ 0 x(t) 2 dt : x(•) solution to (2) for some σ . (Alternatively, one could take V (x 0 ) = ∞ 0 sup σ(•) x(t)
In the case of an exponentially stable single mode (Q = {0}), it was observed by Pazy [START_REF] Pazy | On the applicability of Lyapunov's theorem in Hilbert space[END_REF] that x → ∞ 0 T 0 (t)x 2 dt defines a Lyapunov function that is comparable with the squared norm if and only if T 0 extends to an exponentially stable strongly continuous group. Notice that, as a consequence of the implication (A)⇒(C), even if T 0 does not admit an extension to a group, a Lyapunov function comparable with the squared norm can still be found (see Remark 7).

Concerning the regularity of the Lyapunov functions obtained through the construction described above, they are always convex and continuous (since V (•) is a norm). In the special case in which X is a separable Hilbert space, we also prove the Fréchet directional differentiability of V and we establish a characterization of the directional Fréchet derivatives.

The paper is organized as follows. In Section 2 we introduce the main notations and discuss a motivation example. Section 3 provides a first necessary and sufficient condition for global uniform exponential stability in terms of the existence of a common Lyapunov function, namely, the equivalence of (A) and (B) (Theorem 3). We also discuss the possible redundancies of condition (B), showing that (4) cannot be removed (Remark 4). In Section 4 a second converse Lyapunov theorem is proved, establishing that (A) and (C) are equivalent (Theorem 6). In Section 5 we show the Fréchet differentiability of the common Lyapunov functions constructed in the previous sections when X is a separable Hilbert space (Corollary 9). In Section 6 we give some final remarks and point to open problems.

NOTATIONS AND PRELIMINARIES

By N, Q and R we denote the set of natural, rational and real numbers, respectively. Further, let X be a Banach space, L(X) be the space of bounded linear operators on X, Q be a countable set and, for all j ∈ Q, let t → T j (t) ∈ L(X), t ≥ 0 be a strongly continuous semigroup.

We wish to investigate the qualitative behavior of

x(t) = T σ(•) (t)x (9)
for x ∈ X, where σ : [0, ∞) → Q is a piecewise constant switching signal and

T σ(•) (t) = T jp (t -τ p )T jp-1 (τ p -τ p-1 ) • • • T j1 (τ 1 ) (10)
for σ(•) equal to j k on (τ k-1 , τ k ) for k = 1, . . . , p + 1 and

0 = τ 0 < τ 1 < • • • < τ p+1 = t.
In particular, we wish to study the asymptotic behavior of x(t) as t tends to +∞, uniformly with respect to the switching law σ(•) in the set Σ of all piecewise constant switching signals. We note that, for any given σ(•) ∈ Σ, the operator

T σ(•) (t) ∈ L(X) is strongly continuous with respect to t (lim t↓t0 T σ(•) (t) -T σ(•) (t 0 ) = 0) and satisfies T σ(•) (t + s) = T σs(•) (t)T σ(•) (s) (11)
for some switching signal σ s (•) ∈ Σ depending on s, but in general, T σ(•) (t) does not satisfy the semigroup property, i. e., equation [START_REF] Falk | Modeling and analysis of modal switching in networked transport systems[END_REF] with

σ s (•) replaced by σ(•) (independently of s). For a function V : X → [0, ∞) we define the generalized derivative Lj V (x) = lim inf t↓0 V (T j (t)x) -V (x) t , (12)
noting the possibility that | Lj V (x)| = ∞ for some x ∈ X and j ∈ Q. Further, we call a switched system (9) (completely determined by {T j } j∈Q ) globally uniformly exponentially stable when there exist constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly. ( 13
)
It is clear that (13) implies

x(t) X ≤ Ke -µt x X , t ≥ 0
globally for all x ∈ X and uniformly for all σ(•) ∈ Σ justifying the terminology. We point out that [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF] implies strong attractivity at the origin, i. e.,

lim t→∞ T σ(•) (t)x X = 0, x ∈ X, σ(•) ∈ Σ, (14)
and uniform stability, i. e.,

    

for all ε > 0 there exists a δ > 0, independent of σ(•), such that x X < δ implies

T σ(•) (t)x X < ε, t ≥ 0, σ(•)-uniformly (15)
but that the converse implication is false in general, even for a single mode: As a counterexample it suffices to take the left translation semigroup defined by

(T (t)f )(s) := f (s + t)
on the Lebesgue space X = L 1 (R + ). This is in contrast to the equivalence of ( 14) and ( 13) when X is a n-dimensional real coordinate space, Q is finite, and T j (t) is given by the matrix exponential e Aj t for some real n × n-matrix A j , as a consequence of Fenichel's Uniformity Lemma (see, for instance, [6, §5.2]). Before turning our attention to necessary and sufficient conditions for global uniform exponential stability, we give an example of a switched system exhibiting illustrative instability properties, though the subsystems are exponentially stable.

Example 1. Consider the bimodal system {T j (t)} j=1,2 with T j (t) defined on the Lebesgue space X = L 1 (-1, 1) by

(T 1 (t)f ) (s) =      2f (s + t), s ∈ [-1, 1 -t] ∩ [-t, 0] f (s + t), s ∈ [-1, 1 -t] \ [-t, 0] 0, s ∈ (1 -t, 1]
and Notice that both T 1 (•) and T 2 (•) are nilpotent semigroups, since T 1 (t) = T 2 (t) = 0 for t ≥ 2. In particular, each of them is exponentially stable.

(T 2 (t)f ) (s) =      2f (s -t), s ∈ [-1 + t, 1] ∩ [0, t] f (s -t), s ∈ [-1 + t, 1] \ [0, t] 0, s ∈ [-1, -1 + t). t s 2 -1 1 t s 2 -1 1
T σ(•) (t) L(X) t 1 1 δ Figure 1. Illustration of T j (t), j = 1,
It is easy to see that for suitable switching signals σ(•) ∈ Σ, e. g., switching at

τ k = kδ, k ∈ N, for a fixed δ < 1, T σ(•) (t) L(X) → +∞ as t → +∞.
In fact, the speed of blow-up is not uniformly exponentially bounded over the set of all possible σ(•), i. e., for any fixed t > 0, we have

T σ(•) (t) L(X) ≥ 2 ⌈ t δ ⌉ → +∞ as δ → 0,
with ⌈τ ⌉ = min{k ∈ N : τ ≤ k} for τ > 0 (see Figure 1). This can be seen by taking L 1 (-1, 1)-functions f of norm one, identically constant near x = 0 on progressively smaller intervals and zero elsewhere.

FIRST CONVERSE LYAPUNOV THEOREM

In this section we establish a first equivalence result for the global uniform exponential stability of a switched of the form [START_REF] Fabec | Fundamentals of infinite dimensional representation theory[END_REF]. The crucial step is given by the following lemma, related to the blow-up phenomenon illustrated in Example 1 in the previous section. It is a variant of a result obtained in [START_REF] Triggiani | A sharp result on the exponential operator-norm decay of a family of strongly continuous semigroups[END_REF] in the framework of strongly continuous semigroups. While extending the property to switched system of the form (9), the proof given in [START_REF] Triggiani | A sharp result on the exponential operator-norm decay of a family of strongly continuous semigroups[END_REF] should be modified in order to replace the semigroup property by [START_REF] Falk | Modeling and analysis of modal switching in networked transport systems[END_REF]. We include the modified proof for the sake of completeness. Lemma 2. Assume that i) there exist constants M ≥ 1 and ω > 0 such that

T σ(•) (t) L(X) ≤ M e ωt , t ≥ 0, σ(•)-uniformly; ii) there exists a constant C > 0 and some p ∈ [1, ∞) such that ∞ 0 T σ(•) (t)x p X dt ≤ C x p X , x ∈ X, σ(•)-uniformly.
Then, there exist constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly.
Proof. First, we show that under the assumptions i) and ii), for every x ∈ X, there exists a constant C x > 0 such that

T σ(•) (t)x X ≤ C x , t ≥ 0, σ(•)-uniformly (16)
and that, for all σ(•) and for all x ∈ X,

lim t→+∞ T σ(•) (t)x X = 0. ( 17
)
To this end, let t > 1 ω and set

∆(t) = [t -1 ω , t].
Observe that, for every σ(•) and every τ ∈ ∆(t), there exists a σ τ (•) such that

T σ(•) (t)x X = T στ (•) (t -τ )T σ(•) (τ )x X ≤ T στ (•) (t -τ ) L(X) T σ(•) (τ )x X . (18)
Moreover, by assumption i) and by definition of ∆(t), we have

T στ (•) (t -τ ) L(X) ≤ M e ω(t-τ ) ≤ M e ω 1 ω = M e, (19)
yielding

T σ(•) (τ )x X ≥ T σ(•) (t)x X M e , τ ∈ ∆(t). ( 20
)
Now suppose [START_REF] Michel | Stability analysis of discountinuous dynamical systems determined by semigroups[END_REF] does not hold. Then, there exist x ∈ X, a sequence of switching signals (σ i (•)) i∈N in Σ and a sequence of times (t i ) i∈N such that

δ i = T σi(•) (t i )x X → +∞ as i → +∞. ( 21
)
Assumption i) guarantees that t i is diverging. Without loss of generality,

t i > 1 ω for every i ∈ N. For τ ∈ ∆(t i ), (20) yields
T σi(•) (τ )x X ≥ δ i M e , τ ∈ ∆(t i ). (22)
Hence, using [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF] and again the size of ∆(t i ), we obtain from ( 21)

∞ 0 T σi(•) (τ )x p X dτ ≥ ∆(ti) T σi(•) (τ )x p X dτ ≥ δ i M e p 1 ω → ∞
as i → ∞. This contradicts assumption ii). Hence, (16) holds true. Next, suppose [START_REF] Molchanov | Lyapunov functions that specify necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems, I, II[END_REF] does not hold. Then, there exist x ∈ X, σ(•) ∈ Σ, δ > 0 and a diverging sequence of times (t i ) i∈N such that

T σ(•) (t i )x X ≥ δ for all i. ( 23
)
Without loss of generality t i > t i-1 + 1 ω for every i ∈ N with t 0 = 0. For τ ∈ ∆(t i ), (20) yields

T σ(•) (τ )x X ≥ δ M e , τ ∈ ∆(t i ). (24)
Hence, using [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF] and again the size of ∆(t i ), we obtain

∞ 0 T σ(•) (τ )x p X dτ ≥ ∞ i=1 ∆(ti) T σ(•) (τ )x p X dτ ≥ δ M e p ∞ i=1 1 ω = ∞.
This again contradicts assumption ii) and hence (17

) holds true. Let t x,σ(•) (ρ) = max{t : T σ(•) (t)x X ≥ ρ x X , 0 ≤ s ≤ t}.
By [START_REF] Molchanov | Lyapunov functions that specify necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems, I, II[END_REF], t x,σ(•) (ρ) is finite (and positive) for every σ(•) and x ∈ X \ {0}. By strong continuity,

T σ(•) (t x,σ(•) (ρ))x X = ρ x X .
Using assumption ii),

t x,σ(•) (ρ)ρ p x p X ≤ t x,σ(•) (ρ) 0 T σ(•) (t)x p X dt ≤ ∞ 0 T σ(•) (t)x p X dt ≤ C x p X whereby, t x,σ(•) (ρ) ≤ C ρ p =: t 0 , independent of σ(•)
. By the principle of uniform boundedness, [START_REF] Michel | Stability analysis of discountinuous dynamical systems determined by semigroups[END_REF] implies that there exists a constant k > 0 such that

T σ(•) (t) L(X) ≤ k, t ≥ 0, σ(•)-uniformly. (25)
Hence, for t > t 0 , we have

T σ(•) (t)x X ≤ sup σ(•) T σ(•) (t -t x,σ(•) (ρ)) L(X) ρ x X ≤ kρ x X , σ(•)-uniformly.
Choose ρ > 0 such that β := kρ < 1, so that

T σ(•) (t)x X ≤ β x X , t ≥ t 0 , σ(•)-uniformly.
Finally, let t 1 > t 0 be fixed and let t = nt 1 + s, 0 ≤ s < t 1 . Then,

T σ(•) (t) L(X) ≤ sup σ(•), σ(•) T σ(•) (s) L(X) T σ(•) (nt 1 ) L(X) ≤ k sup σ(•) T σ(•) (t 1 ) L(X) n ≤ kβ n ≤ Ke -µt , t ≥ 0, σ(•)-uniformly with K = C β and µ = -1 t1 ln β > 0.
Lemma 2 allows us to prove the first of the converse Lyapunov theorems that are the object of this paper.

Theorem 3. The following conditions:

i) there exist constants M ≥ 1 and ω > 0 such that

T σ(•) (t) L(X) ≤ M e ωt , t ≥ 0, σ(•)-uniformly, (26)
ii) there exists V :

X → [0, ∞) such that V (•) is a norm on X, V (x) ≤ C x 2 X , x ∈ X, (27)
for a constant C > 0 and

Lj V (x) ≤ -x 2 X , j ∈ Q, x ∈ X, (28)
with Lj V (x) defined as in (12) are necessary and sufficient for the existence of constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly. ( 29
)
Proof. Assume that the conditions i) and ii) hold. For all σ(•) ∈ Σ, x ∈ X and for t ≥ 0 small enough so that the restriction of σ(•) to the interval [0, t] is constant, we have

0 ≤ V (T σ(•) (t)x) ≤ V (x) - t 0 T σ(•) (τ )x 2 X dτ
as it follows from (28) and [20, §VI.7] (see also [START_REF] Hagood | Recovering a function from a Dini derivative[END_REF]). Thus, for all σ(•) and x ∈ X,

∞ 0 T σ(•) (τ )x 2 X dτ ≤ V (x) ≤ C x 2 X . (30)
The uniform exponential decay (29) now follows from ( 26) and (30), thanks to Lemma 2 with p = 2. Conversely, assume that (29) holds for some constants K ≥ 1 and µ > 0. Then, (26) holds for M = K and arbitrary ω > 0. Define V : X → [0, ∞) by

V (x) = sup σ(•)∈Σ ∞ 0 T σ(•) (t)x 2 X dt. (31)
Then, by assumption, V (x) satisfies

V (x) ≤ sup σ(•) ∞ 0 K 2 e -2µt x 2 X dt = K 2 2µ x 2 X , establishing (27) with C = K 2 2µ .
In particular, V is well-posed. Notice that, by definition, V is positive definite and homogenous of degree 2. In order to show that it is the square of a norm, we are left to prove that it is convex and continuous.

The convexity of V follows from the fact that each

x → ∞ 0 T σ(•) (t)x 2 X dt is convex.
In order to verify the continuity of V , let (x n ) n∈N be a sequence in X converging to x in X. By definition of V ,

∞ 0 T σ(•) (t)x n 2 X dt ≤ V (x n ), (32)
for all σ(•) ∈ Σ. So taking the lim inf over n ∈ N in (32) on both sides and using the continuity of T σ(•) (t) for all t ≥ 0, we have

∞ 0 T σ(•) (t)x 2 X dt ≤ lim inf n→∞ ∞ 0 T σ(•) (t)x n 2 X dt ≤ lim inf n→∞ V (x n ). ( 33
)
Taking the sup over σ(•) in (33) then yields

V (x) = sup σ(•) ∞ 0 T σ(•) (t)x 2 X dt ≤ lim inf n→∞ V (x n ),
proving that V is lower semi-continuous. On the other hand, for a fixed ε > 0, there exist σ ε (•) ∈ Σ such that

V (x n ) - ε 2 < ∞ 0 T σε(•) (t)x n 2 dt ≤ (1 + m) ∞ 0 T σε(•) (t)(x n -x) 2 dt + 1 + 1 m ∞ 0 T σε(•) (t)x 2 dt,
for any m > 0. Notice that, by definition of V ,

∞ 0 T σε(•) (t)(x n -x) 2 dt ≤ V (x n -x) ≤ C x n -x 2 X , ∞ 0 T σε(•) (t)x 2 dt ≤ V (x).
Thus, for any m > 0, we have

V (x n ) - ε 2 < C(1 + m) x n -x 2 X + 1 + 1 m V (x). ( 34
)
In particular, choosing m such that (1+ 1 m )V (x) < V (x)+ ε 4 and taking n sufficiently large, so that

(1 + m)C x n -x 2 X ≤ ε 4 , we have from (34) V (x n ) < V (x) + ε, n sufficienty large.
This implies the upper semi-continuity of V . Resuming, we proved the continuity of V .

To complete the proof of the theorem, we are left to show that V satisfies (28). Fixing t > 0, j ∈ Q and letting Σ t,j = {σ(•) ∈ Σ : σ| [0,t] ≡ j} be the set of switching signals whose restriction to the interval [0, t] is constantly equal to j, we have, since Σ t,j ⊆ Σ,

V (x) ≥ sup σ(•)∈Σt,j ∞ 0 T σ(•) (τ )x 2 X dτ = t 0 T j (τ )x 2 X dτ + sup σ(•)∈Σt,j ∞ t T σ(•) (τ )x 2 X dτ. (35)
Moreover, thanks to [START_REF] Falk | Modeling and analysis of modal switching in networked transport systems[END_REF] and the invariance of Σ by time-shift,

V (T j (t)x) = sup σ(•)∈Σ ∞ 0 T σ(•) (τ )T j (t)x 2 X dτ = sup σ(•)∈Σ ∞ t T σ(•) (τ -t)T j (t)x 2 X dτ = sup σ(•)∈Σt,j ∞ t T σ(•) (τ )x 2 X dτ.
This and (35) yield

V (T j (t)x) -V (x) ≤ - t 0 T j (τ ) 2 X dτ, for all j ∈ Q and t > 0. Therefore Lj V (x) = lim inf t↓0 V (T j (t)x) -V (x) t ≤ -lim sup t↓0 1 t t 0 T j (τ )x 2 X dτ = -x 2 X t s 1 0 4 -j 1 Figure 2. Illustration of T j (t), j ∈ Q, of the example in Remark 4.
for all j ∈ Q, establishing (28).

Remark 4. We show here, through an example, that condition i) appearing in the statement of Theorem 3 cannot be removed. Consider the family of semigroups {T j (t)} j∈Q with Q = N and T j (t) defined on the Lebesgue space

X = L p (0, 1), p ∈ [1, ∞), by (T j (t)f ) (s) =      2 1 p f (s + t), s ∈ [0, 1 -t] ∩ [0, 4 -j ) f (s + t), s ∈ [0, 1 -t] \ [0, 4 -j ) 0, s ∈ (1 -t, 1], (36)
cf. also Figure 2. Notice that, for all j ∈ Q, T j (•) is a nilpotent semigroup, since T j (t)f X = 0 for t > 1. In particular, each of them is exponentially stable. Moreover, for all σ(•) ∈ Σ, we have

T σ(•) (t)f (s) ≤ 2 k p |f (s + t)|, with k = #{l ∈ N : s < 4 -l ≤ s + t}.
In particular,

T σ(•) (t)f (s) ≤ 2 k p |f (s + t)|, if 4 -k-1 ≤ s < 4 -k , yielding ∞ 0 T σ(•) (t)f p X = 1 0 1-t 0 T σ(•) (t)f (s) p ds dt = 1 0 1-s 0 T σ(•) (t)f (s) p dt ds ≤ ∞ k=0 4 -k 4 -k-1 2 k 1-s 0 |f (s + t)| p dt ds ≤ ∞ k=0 1 4 k - 1 4 k+1 2 k 1 0 |f (t)| p dt = 3 2 f p X .
Hence, defining V (x) as in (31), we have

V (x) = sup σ(•) ∞ 0 T σ(•) (t)x 2 X dt ≤ 3 2 x 2 X
and, by the same arguments as in the proof of Theorem 3,

Lj V (x) ≤ -x 2 X , for all j ∈ Q, so condition ii) in Theorem 3 holds with C = 3 2 .
Nevertheless, for a sequence of switching signals (σ n (•)) n∈N ⊂ Σ with switching times τ k = 1 4 k and modes j k = k + 1, 0 ≤ k ≤ n, we have for functions ½ [s,1] of L p norm one concentrated on the interval [s, 1],

T σn(•) (1 -ǫ)½ [s,1] = 2 n p ½ [s-1+ǫ,ǫ] , if 1 ≥ s ≥ 1 -ǫ > 1 -4 -n . Therefore, for ǫ < 4 -n , T σn(•) (1 -ǫ) L(X) = sup f X =1 T σn(•) (1 -ǫ)f X ≥ lim s↑1 T σn(•) (1 -ǫ)½ [s,1] X = 2 n p . Hence, sup{ T σn(•) (1 -ǫ) L(X) : ǫ ∈ [0, 1], n ∈ N} = +∞ (37)
violating any uniform bound of the form (29). This example also shows that assumption i) appearing in Lemma 2 is necessary for the validity of the lemma.

SECOND CONVERSE LYAPUNOV THEOREM

If one wishes to conclude that a switched system is globally uniformly exponentially stable, Theorem 3 requires the knowledge of a squared norm V (•) satisfying ( 27), ( 28) for all modes j ∈ Q and the knowledge of a global uniform exponential bound (26). As an alternative, we will, in Theorem 6, show that the existence of a Lyapunov norm V (•) that is comparable with the norm • X allows to conclude that the system is globally uniformly exponentially stable, without knowledge of a global uniform exponential bound of the type (26). Notice that the norm V (•) constructed in the proof of Theorem 3 (see definition (31)) is in general not comparable with • X , i. e., in general it does not satisfy a lower bound of the form

c x X ≤ V (x), x ∈ X ( 38
)
for a constant c > 0. Such a lower bound always holds, on the contrary, when X has finite dimension, as it is exploited in [START_REF] Molchanov | Lyapunov functions that specify necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems, I, II[END_REF][START_REF] Wijesuriya | A converse Lyapunov theorem for a class of dynamical systems which undergo switching[END_REF]. The bound (38) may fail to hold even in the case of a single strongly continuous semigroup, as it is the case, for instance, of the semigroups T 1 (•) and T 2 (•) introduced in Example 1. (For a characterization of exponentially stable strongly continuous semigroups whose Lyapunov function defined as in (31) is comparable with the squared norm, see [START_REF] Pazy | On the applicability of Lyapunov's theorem in Hilbert space[END_REF].)

In order to obtain a Lyapunov norm comparable with • X for infinite dimensional switched systems, we make use of the following lemma imposing a stronger assumption on the family of semigroups T j (•).

Lemma 5. Assume that there exists j * ∈ Q such that T j * (•) can be extended to a group of bounded linear operators on X. Moreover, assume that there exist constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly. ( 39
)
Then there exists a function V :

X → [0, ∞) such that V (•) is a norm on X, c x 2 X ≤ V (x) ≤ C x 2 X , x ∈ X, (40)
for constants c, C > 0 and

Lj V (x) ≤ -x 2 X , j ∈ Q, x ∈ X, (41)
with Lj V (x) defined as in [START_REF] Falk | Converse Lyapunov theorems for switched systems in Banach spaces[END_REF].

Proof. Assume that (39) holds for some constants K ≥ 1 and µ > 0 independent of σ(•). Define V (•) by (31). As seen in the proof of Theorem 3, (39) guarantees that V is the square of a norm, satisfies (41) and that there exist C > 0 such that V (x) ≤ C x 2 X . The remaining bound c x 2 ≤ V (x) for some constant c > 0 is a consequence of the assumption that T j * (•) can be extended to a group. Indeed, T j * (t) is then invertible for every t ≥ 0 and satisfies T j * (t)x X ≥ ( T j * (-t) L(X) ) -1 x X (cf. [START_REF] Pazy | On the applicability of Lyapunov's theorem in Hilbert space[END_REF]). Hence

V (x) = sup σ(•) ∞ 0 T σ(•) (t)x 2 X dt ≥ ∞ 0 T j * (t)x 2 X ≥ ∞ 0 ( T j * (-t) L(X) ) -2 dt x 2 X = c x 2 X with c = ∞ 0 ( T j * (-t) L(X) ) -2 dt < ∞.
We can now state and prove our second converse Lyapunov theorem.

Theorem 6. The existence of a function V :

X → [0, ∞) such that V (•) is a norm on X, c x 2 X ≤ V (x) ≤ C x 2 X , x ∈ X, (42)
for constants c, C > 0 and

Lj V (x) ≤ -x 2 X , j ∈ Q, x ∈ X, (43)
with Lj V (x) defined as in [START_REF] Falk | Converse Lyapunov theorems for switched systems in Banach spaces[END_REF] is necessary and sufficient for the existence of constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly. (44)
Proof. Assume that there exists a function V : X → [0, ∞) such that (42) and (43) hold for c, C > 0. Then, for all x ∈ X, σ(•) ∈ Σ, and t ≥ 0,

c T σ(•) (t)x 2 X ≤ V (T σ(•) (t)x) ≤ V (x) - t 0 T σ(•) (τ )x 2 X dτ,
so, using again (42) and dividing by c,

T σ(•) (t)x 2 X ≤ C c x 2 X - 1 c t 0 T σ(•) (τ )x 2 X dτ.
From Gronwall's Lemma, we obtain

T σ(•) (t)x 2 X ≤ C c e -1 c t x 2 X , t ≥ 0, σ(•)-uniformly. Hence, T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly,
for the constants K = C c ≥ 1 and µ = 1 2c > 0, establishing (44). Conversely, assume that (44) holds for K ≥ 1 and µ > 0 and consider the switched system with σ * (•) taking values in Q * = Q ∪ {j * }, where

T j * (t) = e -µt I (45)
and I : X → X denotes the identity. Then,

T j * (t)T j (s) = T j (s)T j * (t), t, s ≥ 0, j ∈ Q.
Moreover, for t * = |{τ ∈ [0, t] : σ * (τ ) = j * }| and some σ(•) just taking values in Q,

T σ * (•) L(X) = T σ(•) (t -t * )e -µt * L(X) ≤ Ke -µ(t-t * ) e -µt * = Ke -µt , t ≥ 0, σ(•)-uniformly (46)
where we have used (44). The existence of a squared norm V : X → [0, ∞) and constants c, C > 0 such that (42) and ( 43) hold now follows from (46) and Lemma 5, noting that (45) actually defines a group.

Remark 7. In the case of a single strongly continuous semigroup T (•), Theorem 6 shows that its global exponential stability is equivalent to the existence of a Lyapunov norm comparable with the norm • X . When T (•) is globally exponentially stable, such a Lyapunov norm can be obtained by the construction suggested in the proof of Theorem 6.

An alternative construction of a common Lyapunov function has been proposed in [START_REF] Falk | Converse Lyapunov theorems for switched systems in Banach spaces[END_REF], where (31) is replaced by

Ṽ (x) = ∞ 0 sup σ(•)∈Σ T σ(•) (t)x 2 X dt. (47)
In the case of a single mode and following the strategy of augmenting Q by adding a group corresponding to a diagonal operator, this construction leads to the explicit expression

Ṽ (x) = ∞ 0 max s∈[0,τ ] e 2µ(s-τ ) T (s)x 2 X dτ,
for any fixed µ > 0.

It should be noticed that, although not stated in [START_REF] Falk | Converse Lyapunov theorems for switched systems in Banach spaces[END_REF], the definition of Ṽ given in (47) identifies a function which is positive definite, homogenous of degree 2, continuous and convex, i.e., a squared norm. The proof of this fact can be rather easily obtained by adapting the proof of Theorem 3.

COMMON LYAPUNOV FUNCTIONS ON HILBERT SPACES

The goal of this section is to prove further regulatity properties of the common Lyapunov functions constructed in the previous sections in the case in which X is a separable Hilbert space. The proof of the following lemma adapts arguments presented in [4, §4.3.1].

Recall that a function V : X → R is said to be directionally differentiable in the sense of Fréchet at x ∈ X if for every ψ ∈ X there exists

V ′ (x, ψ) = lim t↓0 V (x + tψ) -V (x) t
and, moreover,

lim ψ→0 V (x + ψ) -V (x) -V ′ (x, ψ) ψ X = 0.
Notice that, in general, V ′ (x, •) needs not be linear.

Lemma 8. Let X be a separable Hilbert space with scalar product •, • and assume that there exist constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly. ( 48
)
Then, there exists a subset B of L(X), compact for the weak operator topology and made of self-adjoint operators, such that

sup σ(•)∈Σ ∞ 0 T σ(•) (t)x 2 X dt = max B∈B x, Bx =: V (x). ( 49
)
In particular, V is directionally differentiable in the sense of Fréchet and its derivative in the direction ψ ∈ X is given by

V ′ (x, ψ) = max B∈S(x) 2 ψ, Bx , (50)
where S(x) = arg max B∈B x, Bx .

Proof. For a fixed σ(•) ∈ Σ and all t ≥ 0, let T * σ(•) (t) ∈ L(X) be the adjoint operator of T σ(•) (t) ∈ L(X), uniquely defined by

T σ(•) (t)x, x ′ = x, T * σ(•) (t)x ′ , x, x ′ ∈ X. If T σ(•) (t) has the expression given in (10), then T * σ(•) (t) = T * j1 (τ 1 ) • • • T * jp-1 (τ p -τ p-1 )T * jp (t -τ p )
, where T * j (t) denotes the adjoint semigroup of T j (t), t ≥ 0, j ∈ Q. Assuming that there exist constants K ≥ 1 and µ > 0, independent of σ(•), such that (48) holds, the operator B σ(•) : X → X, given by

B σ(•) x = ∞ 0 T * σ(•) (t)T σ(•) (t)x dt,
is linear, self-adjoint, and satisfies

B σ(•) x X ≤ ∞ 0 T * σ(•) (t) L(X) T σ(•) (t) L(X) x X dt ≤ ∞ 0 K 2 e -2µt x X dt = K 2 2µ x X ,
where we have used (48). In particular, B σ(•) ∈ L(X) for all σ(•) ∈ Σ and

B σ(•) L(X) ≤ K 2 2µ , σ(•)-uniformly. (52)
Therefore, the set

B = {B ∈ L(X) : there exists a sequence (σ n (•)) n∈N ⊂ Σ such that B σn(•) WOT -→ B}
is compact for the weak operator topology. We recall that B σn(•) WOT -→ B (i. e., B σn(•) converges to B for the weak operator topology) if, for every sequence (x n , y n ) converging to (x, y) in X × X, we have

lim n→∞ x n , B σn(•) y n = x, By , (53)
and that every bounded closed subset of L(X) is sequentially compact for the weak operator topology (see, for instance, [9, Theorem III.4]). Notice that (53) guarantees that B consists of self-adjoint operators. Define V as in (49). The maximization makes sense because of (53) (with x n = y n = x) and of the compactness of B. Moreover,

V (x) = max B∈B x, Bx = sup σ(•)∈Σ x, B σ(•) x = sup σ(•)∈Σ x, ∞ 0 T * σ(•) (t)T σ(•) (t)x dt = sup σ(•)∈Σ ∞ 0 x, T * σ(•) (t)T σ(•) (t)x dt = sup σ(•) ∞ 0 T σ(•) (t)x 2 dt,
for all x ∈ X. Hence V coincides with the Lyapunov function defined in (31) and we recover that V satisfies the condition ii) of Theorem 3. In particular, V is continuous.

Again by the Mean Value Theorem,

| x 0 + ψ n , Bn (x 0 + ψ n ) -x 0 , Bn x 0 -2 ψ n , Bn x 0 | ≤ ψ n X 1 0 Φ( Bn , x 0 + ψ n ) dt ≤ ε 2 ψ n X
for all n large enough. Thus,

V (x 0 + ψ n ) -V (x 0 ) ≤ 2 ψ n , Bn x 0 + ε 2 ψ n X .
Using one more time the compactness of B, there exist a subsequence n(k) such that Bn(k)

WOT -→ B for some B ∈ B. Moreover, by continuity of V and because of (53), B ∈ S(x 0 ). Hence,

V (x 0 + ψ n(k) ) -V (x 0 ) ≤ 2 ψ n(k) , Bx 0 + 2 ψ n(k) , ( Bn(k) -B)x 0 + ε 2 ψ n(k) X ≤ max B∈S(x0) 2 ψ n(k) , Bx 0 + 3 4 ε ψ n(k)
where we used that 2 ψ n(k) , ( Bn(k) -B)x 0 ≤ ε 4 ψ n(k) X for k sufficiently large. This contradicts (59) and completes the proof.

The following Corollary is now a direct consequence of Lemma 8 and the choice of the Lyapunov function V (•) in the proof of Theorem 3.

Corollary 9. Let X be a separable Hilbert space and assume that there exist constants K ≥ 1 and µ > 0 such that

T σ(•) (t) L(X) ≤ Ke -µt , t ≥ 0, σ(•)-uniformly. (60)
Then, there exists a function V : X → [0, ∞) such that V (•) is a norm on X, V (•) is directionally Fréchet differentiable,

c x 2 X ≤ V (x) ≤ C x 2 X , x ∈ X, (61)
for constants c, C > 0 and

Lj V (x) ≤ -x 2 X , j ∈ Q, x ∈ X, (62)
with Lj V (x) defined as in [START_REF] Falk | Converse Lyapunov theorems for switched systems in Banach spaces[END_REF].

FINAL REMARKS AND OPEN PROBLEMS

We presented necessary and sufficient conditions for a (possibly infinite) family of semigroups to be globally uniformly exponentially stable for arbitrary switching signals σ(•), in terms of the existence of a common Lyapunov function. In particular, our results apply to switched dynamical systems such as (1), involving (possibly unbounded) operators on a Banach space X.

We have shown that the existence of a norm, decaying uniformly along trajectories and either bounded from above by a multiple of the Banach norm in presence of a uniform exponential growth bound for the switched system or comparable with the Banach norm is equivalent to the switched system being globally uniformly exponentially stable. The latter generalizes a well-known result for switched linear dynamical systems in R n , n ∈ N [START_REF] Molchanov | Lyapunov functions that specify necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems, I, II[END_REF]. In the case in which X is a separable Hilbert space the common Lyapunov function is shown to be Fréchet directionally differentiable.

As an application, our results answer for example the question of existence of a common Lyapunov function for the switched linear hyperbolic system with reflecting boundaries considered in [START_REF] Amin | Stability analysis of linear hyperbolic systems with switching parameters and boundary conditions[END_REF].

Concerning the differences between Theorems 3 and 6, we already noticed that a Lyapunov function V (•) satisfying condition ii) of the statement of Theorem 3 does not necessarily satisfy the stronger conditions appearing in the statement of Theorem 6. Hence, Theorem 3 is better suited for proving the global uniform exponential stability of a switched system (although the uniform exponential growth boundedness should also be proved), while Theorem 6 provides more information on a switched system that is known to be globally uniformly exponentially stable, by tightening the properties satisfied by V (•).

In the same spirit one could characterize the global uniform exponential stability of a switched system by (a priori) loosening the hypotheses on V (•), replacing inequalities (28) and (43) by Lj V (x) ≤ -κ x 2

X , for all j ∈ Q, for some κ > 0. One could also remove the hypothesis that V is the square of a norm. Conversely, one could (a priori) tighten the same hypotheses replacing Lj V (x) by

Lj V (x) = lim sup t↓0 V (T j (t)x) -V (x) t .
As an open problem it remains to understand if smoothing can improve the regularity properties of the Lyapunov function V (•). For the finite-dimensional case, it is for instance known that V (•) can be taken polyhedral or polynomial [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF][START_REF] Blanchini | A new class of universal Lyapunov functions for the control of uncertain linear systems[END_REF][START_REF] Wijesuriya | A converse Lyapunov theorem for a class of dynamical systems which undergo switching[END_REF]. It would be interesting to recover results in the same direction for infinite dimensional switched systems.

  Figure 1. Illustration of T j (t), j = 1, 2, (left) and the blow up of the operator norm of T σ(•) (t) (right) in Example 1.

This work was supported by the ANR project ArHyCo, Programme ARPEGE, contract number ANR-2008 SEGI 004 01-30011459.

In order to verify the directional differentiability in the sense of Fréchet and to prove (50), we show below that lim ψ→0 V (x + ψ) -V (x)max B∈S(x) 2 ψ, Bx

First observe that the map x → x, Bx is differentiable on X in the sense of Fréchet for all B ∈ L(X). For B self-adjoint, the derivative is given by 2 •, Bx . Fix now some x 0 ∈ X and define

Indeed, suppose by contradiction that there exists some ε > 0, a sequence (x n ) n∈N converging to x 0 in X and a sequence (

Thanks to the compactness of B, there exist B ∈ B and a subsequence n(k

Then, it follows from (53) that

The Mean Value Theorem then gives

for ε > 0, ψ sufficiently close to zero, and uniformly with respect to B ∈ B, as it follows from (55). Let S(•) be defined as in (51). Notice that, for every x ∈ X, S(x) is close and therefore compact for the weak operator topology. For any B ∈ S(x 0 ), V (x 0 ) = x 0 , Bx 0 and V (x 0 + ψ) ≥ x 0 + ψ, B(x 0 + ψ) . Thus, using (57),

In order to prove (54), it therefore remains to show that for all ε > 0 and ψ close to zero,

So, suppose (58) not to hold. Then there exist ε > 0 and a sequence (ψ n ) n∈N in X converging to zero such that

By definition of V , there exist B 0 , Bn ∈ B such that V (x 0 + ψ n ) -V (x 0 ) = x 0 + ψ n , Bn (x 0 + ψ n )x 0 , B 0 x 0 ≤ x 0 + ψ n , Bn (x 0 + ψ n )x 0 , Bn x 0 .


Grégoire Laurence

Aurélien Lemay

Joachim Niehren

Slawomir Staworko

Marc Tommasi

S Lawek Staworko

Normalization of Sequential Top-Down Tree-to-Word Transducers

come   L'archive ouverte pluridisciplinaire

Introduction

The classical problems on transducers are equivalence, minimization, learning, type checking, and functionality [START_REF] Berstel | Transductions and context-free languages[END_REF][START_REF] Maneth | Models of Tree Translation[END_REF][START_REF] Martens | Typechecking top-down XML transformations: Fixed input or output schemas[END_REF][START_REF] Filiot | Properties of visibly pushdown transducers[END_REF]. Except for the latter two questions, one usually studies deterministic transducers because non-determinism quickly leads to fundamental limitations. For instance, equivalence of non-deterministic string transducers is known to be undecidable [START_REF] Griffiths | The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines[END_REF]. We thus follow the tradition to study classes of deterministic transducers. The problems of equivalence, minimization, and learning are often solved using unique normal representation of transformations definable with a transducer from a given class [START_REF] Gurari | The equivalence problem for deterministic two-way sequential transducers is decidable[END_REF][START_REF] Friese | Minimization of deterministic bottom-up tree transducers[END_REF][START_REF] Engelfriet | Deciding equivalence of top-down XML transformations in polynomial time[END_REF][START_REF] Lemay | A learning algorithm for top-down XML transformations[END_REF]. Normalization i.e., constructing the normal form of a given transducer, has been studied independently for various classes, including string transducers [START_REF] Choffrut | Minimizing subsequential transducers: a survey[END_REF][START_REF] Choffrut | Contribution à l'étude de quelques familles remarquables de fonctions rationnelles[END_REF], top-down tree transducers [START_REF] Engelfriet | Deciding equivalence of top-down XML transformations in polynomial time[END_REF], and bottom-up tree transducers [START_REF] Friese | Minimization of deterministic bottom-up tree transducers[END_REF].

In this paper, we study the normalization problem for the class of deterministic sequential top-down tree-to-word transducers (stws). stws are finite state machines that traverse the input tree in top-down fashion and at every node produce words obtained by the concatenation of constant words and the results from processing the child nodes. The main motivation to study this model is because tree-to-word transformations are better suited to model general xml transformations as opposed to tree-to-tree transducers [START_REF] Engelfriet | Deciding equivalence of top-down XML transformations in polynomial time[END_REF][START_REF] Lemay | A learning algorithm for top-down XML transformations[END_REF][START_REF] Martens | Typechecking top-down XML transformations: Fixed input or output schemas[END_REF]. This follows from the observation that general purpose xml transformation languages, like xslt, allow to define transformations from xml documents to arbitrary, not necessarily structured, formats. Also, stw capture a large subclass of deterministic nested-word to word transducers (dn2w), which have recently been the object of an enlivened interest [START_REF] Filiot | Properties of visibly pushdown transducers[END_REF][START_REF] Raskin | Visibly pushdown transducers[END_REF][START_REF] Staworko | Equivalence of nested word to word transducers[END_REF].

Expressiveness of stws suffers from two limitations: 1) every node is visited exactly once, and 2) the nodes are visited in the fix left-to-right preorder traversal of the input tree. Consequently, stws cannot express transformations that reorder the nodes of the input tree or make multiple copies of a part of the input document. Stws remain, however, very powerful and are capable of: concatenation in the output, producing arbitrary context-free languages, deleting inner nodes, and verifying that the input tree belongs to the domain even when deleting parts of it. These features are often missing in tree-to-tree transducers, and for instance, make stws incomparable with the class of top-down tree-to-tree transducers [START_REF] Engelfriet | Deciding equivalence of top-down XML transformations in polynomial time[END_REF][START_REF] Lemay | A learning algorithm for top-down XML transformations[END_REF].

Normal forms of transducers are typically obtained in two steps: output normalization followed by machine minimization. A natural way of output normalization is (re)arranging output words among the transitions rules so that the output is produced as soon as possible when reading the input, and thus transducers producing output in this fashion are called earliest. Our method subscribes to this approach but we note that it is a challenging direction that is not always feasible in the context of tree transformations. For instance, it fails for bottom-up tree-to-tree transducers, where ad-hoc solutions need to be employed [START_REF] Friese | Minimization of deterministic bottom-up tree transducers[END_REF].

We propose a natural normal form for stws because on being earliest for stws and define the corresponding class of earliest stws (estws) using easy to verify structural requirements. We present an effective procedure to convert an stw to an equivalent estw. This process is very challenging and requires novel tools on word languages. We point out that while this procedure works in time polynomial in the size of the output estw, we only know a doubly-exponential upper-bound and a single-exponential lower bound of the size of the output estw. This high complexity springs from the fact that the output language of an stw may be an arbitrary context-free language. We also show that minimization of earliest stws is in ptime thanks to a fundamental property: two equivalent estws have rules of the same form and allow bisimulation. General stws are unlikely to enjoy a similar property because their minimization is np-complete.

Overall, we obtain an effective normalization procedure for stws. Our results also offer an important step towards a better understanding of the same problem for dn2ws because stws capture a large class of top-down dn2ws modulo the standard first-child next-sibling encoding and the conversion from one model to another can be done efficiently [START_REF] Staworko | Equivalence of nested word to word transducers[END_REF]. It is a significant result because there exist arguments suggesting that arbitrary dn2ws are unlikely to have natural normal forms [START_REF] Alur | Congruences for visibly pushdown languages[END_REF].

Organization. In Section 2 we present basic notions and introduce stws and estws. Section 3 introduces important tools on word languages and presents an stw to estw conversion algorithm. In Section 4 we deal with minimization of stws and estws. Section 5 summarizes our work and outlines future directions. Because of space restrictions we omit the proofs, which can be found in the full version at http://hal.inria.fr/inria-00566291/en/.

Sequential top-down tree-to-word transducers

A ranked alphabet is a finite set of ranked symbols Σ = k≥0 Σ (k) where Σ (k) is the set of k-ary symbols. We assume that every symbol has a unique arity i.e., Σ (i) ∩ Σ (j) = ∅ for i = j. We use f, g, . . . to range over symbols of non negative arity and a, b, . . . to range over constants i.e., symbols of arity 0. We write f (k) to indicate that f ∈ Σ (k) if the arity of f is not known from the context. A tree is a ranked ordered term over Σ. We use t, t 0 , t 1 , . . . to range over trees. For instance, t 0 = f (a, g(b)) is a tree over Σ = {f (2) , g (1) , a (0) , b (0) }.

For a finite set ∆ of symbols by ∆ * we denote the free monoid on ∆. We write u • v for the concatenation of two words u and v and ε for the empty word. We use a, b, . . . to range over ∆ and u, v, w, . . . to range over ∆ * . For a word w by |w| we denote its length. Given a word u = u p • u f • u s , u p is a prefix of u, u f a factor of u, and u s a suffix of u. The longest common prefix of a nonempty set of words W , denoted lcp(W ), is the longest word u that is a prefix of every word in W . Analogously, we define the longest common suffix lcs(W ). Definition 1. A deterministic sequential top-down tree-to-word transducer (stw)

is a tuple M = (Σ, ∆, Q, init, δ) where Σ is a ranked alphabet of input trees, ∆ is a finite alphabet of output words, Q is a finite set of states, init ∈ ∆ * • Q • ∆ * is the initial rule, δ is a partial transition function from Q × Σ to (∆ ∪ Q) * such that if δ(q, f (k)
) is defined, then it has exactly k occurrences of elements from Q. By stws we denote the class of deterministic sequential top-down tree-to-word transducers.

In the sequel, if u 0 • q 0 • u 1 is the initial rule, then we call q 0 the initial state. Also, we often view δ as a set of transition rules i.e., a subset of Q × Σ × (∆ ∪ Q) * , which allows us to quantify over δ. The size of the stw M is the number of its states and the lengths of its rules, including the lengths of words used in the rules. The semantics of the stw M is defined with the help of auxiliary partial functions T q (for q ∈ Q), recursively defined on the structure of trees as follows:

T q (f (t 1 , . . . , t k )) =      u 0 • T q1 (t 1 ) • u 1 • . . . • •T q k (t k ) • u k , if δ(q, f ) = u 0 • q 1 • u 1 . . . • q k • u k , undefined, if δ(q, f ) is undefined.
The transformation T M defined by M is a partial function mapping trees over Σ to words over ∆ defined by

T M (t) = u 0 • T q0 (t) • u 1 , where init = u 0 • q 0 • u 1 .
Two transducers are equivalent iff they define the same transformation.

Example 1. We fix the input alphabet Σ = {f (2) , g (1) , a (0) } and the output alphabet ∆ = {a, b, c}. The stw M 1 has the initial rule q 0 and the following transition rules:

δ(q 0 , f) = q 1 • ac • q 1 , δ(q 1 , g) = q 1 • abc, δ(q 1 , a) = ε.
It defines the transformation T M1 (f (g m (a), g n (a))) = (abc) m ac(abc) n , where m, n ≥ 0, and T M1 is undefined on all other input trees. The stw M 2 has the initial rule p 0 and these transition rules:

δ(p 0 , f) = p 1 • p 3 • ab, δ(p 1 , g) = a • p 2 , δ(p 2 , g) = ab • p 3 , δ(p 3 , g) = p 3 , δ(p 0 , a) = ba, δ(p 1 , a) = ε, δ(p 2 , a) = ε, δ(p 3 , a) = ε.
Now, T M2 (a) = ba and for n ≥ 0, the result of T M2 (f (g m (a), g n (a)) is ab for m = 0, aab for m = 1, and aabab for m ≥ 2; T M2 is undefined for all other input trees. Note that p 3 is a deleting state: it does not produce any output but allows to check that the input tree belongs to the domain of the transducer.

In the sequel, to simplify notation we assume every state belongs to exactly one transducer, and so T q above is defined in unambiguous manner. We consider only trimmed stws i.e., transducers where all states define a nonempty transformation and are accessible from the initial rule. Also, by dom q we denote the set dom(T q ), the domain of T q i.e., the set of trees on which T q is defined, and by L q the range of T q i.e., the set of words returned by T q . For instance, dom q0 = {f (g m (a), g n (a) | m, n ≥ 0} and L q0 = (abc) * ac(abc) * . We observe that dom q is a regular tree language and L q is a context-free word language (cfl).

Next, we introduce the notion of being earliest that allows us to identify normal forms of transformations definable with stws. It is a challenging task because the notion of being earliest needs to be carefully crafted so that every transducer can be made earliest. Take, for instance, the transformation turn that takes a tree over Σ = {a (1) , b (1) , ⊥ (0) } and returns the sequence of its labels in the reverse order e.g., turn(a(b(b(⊥)))) = bba. It is definable with a simple stw.

δ(q turn , a) = q turn • a, δ(q turn , b) = q turn • b, δ(q turn , ⊥) = ε.
One way to view the transformation is a preorder traversal of the input tree that produces one output word upon entering the node and another word prior to leaving the node. When analyzing turn from this perspective, the earliest moment to produce any output is when the control reaches ⊥, and in fact, the whole output can be produced at that point because all labels have been seen. This requires storing the label sequence in memory, which is beyond the capabilities of a finite state machine, and thus, turn cannot be captured with a transducer satisfying this notion of being earliest.

We propose a notion of being earliest that is also based on preorder traversal but with the difference that both output words are specified on entering the node and the output of a node is constructed right before leaving the node. Intuitively, we wish to push up all possible factors in the rules. Clearly, the stw above satisfies the condition. We remark that in some cases the output words in the rule can be placed in several positions, e.g. the rule δ(q 1 , g) = q 1 • abc in M 1 (Examples 1) can be replaced by δ(q 1 , g) = abc • q 1 without changing the semantics of M 1 . Consequently, we need an additional requirement that resolves this ambiguity: intuitively, we wish to push left the words in a rule as much as possible.

Definition 2. An stw M = (Σ, ∆, Q, init, δ) is earliest (estw) iff the following two conditions are satisfied:

(E 1 ) lcp(L q ) = ε and lcs(L q ) = ε for every state q, (E 2 ) lcp(L q0 • u 1 ) = ε for the initial rule u 0 • q 0 • u 1 and for every transition

δ(q, f ) = u 0 •q 1 •. . .•q k •u k and 1 ≤ i ≤ k we have lcp(L qi •u i •. . .•L q k •u k ) = ε.
Intuitively, the condition (E 1 ) ensures that no factor can be pushed up in the traversal and (E 2 ) ensures that no factor can be pushed left. We note that (E 1 )

and (E 2 ) can be efficiently checked in an stw because we need only to check that the results of lcp and lcs are ε. The main contribution of this paper follows.

Theorem 1. For every stw there exists a unique minimal equivalent estw.

The proof consists of an effective procedure that works in two stages: In the first stage we normalize the outputs, i.e. from the input stw we construct an equivalent estw, and in the second stage we minimize the obtained estw. The first stage is, however, quite complex as illustrated in the following example.

Example 2 (contd. Example 1). M 1 is not earliest because (E 1 ) is not satisfied at q 0 : every word of L q0 = (abc) * ac(abc) * begins with a i.e., lcp(L q0 ) = a, and ends with c i.e., lcs(L q0 ) = c. Consequently, we need to push up these two symbols to the new initial rule a • q 0 • c, but we also need to retract them from the rule δ(q 0 , f) = q 1 • ac • q 1 producing a new state q 0 and new rules for this state. Essentially, we need to push the symbol a to the left through the first occurrence of q 1 and push the symbol c to the right through the second occurrence of q 1 . Pushing symbols through states produces again new states with rules obtained by reorganizing the output words. Finally, we obtain

δ (q 0 , f) = q 1 •q 1 , δ (q 1 , g) = bca•q 1 , δ (q 1 , g) = cab•q 1 , δ (q 1 , a) = δ (q 1 , a) = ε. M 2 is not earliest because (E 2 ) is not satisfied by δ(p 0 , f) = p 1 • p 3
• ab: every word produced by this rule starts with a. First, we push the word ab through the state p 3 , and then we push the symbol a through the state p 1 . Pushing through p 3 is easy because it is a deleting state and the rules do not change. Pushing through p 1 requires a recursive push through the states of the rules of p 1 and this process affects the rules of p 2 . Finally, we obtain an estw with the initial rule p 0 and the transition rules

δ (p 0 , f) = a • p 1 • b • p 3 , δ (p 1 , g) = a • p 2 , δ (p 2 , g) = ba • p 3 , δ (p 3 , g) = p 3 , δ (p 0 , a) = ba, δ (p 1 , a) = ε, δ (p 2 , a) = ε, δ (p 3 , a) = ε.

Output normalization

The first phase of normalization of an stw consists of constructing an equivalent estw, which involves changing the placement of the factors in the rules of the transducer and deals mainly with the output. Consequently, we begin with several notions and constructions inspired by the conditions (E 1 ) and (E 2 ) but set in a simpler setting of word languages. We consider only nonempty languages because in trimmed stws the ranges of the states are always nonempty.

Reducing languages

Enforcement of (E 1 ) corresponds to what we call constructing the reduced decomposition of a language. A nonempty language L is reduced iff lcp(L) = ε and lcs(L) = ε. Note that the assumption that we work with a nonempty language is essential here. Now, take a nonempty language L, that is not necessarily reduced. We decompose it into its reduced core Core(L) and two words Left(L) and Right(L) such that Core(L) is reduced and

L = Left(L) • Core(L) • Right(L). ( 1
)
We observe that different decompositions are possible.

Pushing words through languages

In this subsection, we work with nonempty and reduced languages only. Condition (E 2 ) introduces the problem that we call pushing words through languages.

To illustrate it, suppose we have a language L = {ε, a, aa, aaab} and a word w = aab, which together give L • w = {aab, aaab, aaaab, aaabaab}. The goal is to find the longest prefix v of w such that

L • w = v • L • u, where w = v • u and L is some derivative of L.
Intuitively speaking, we wish to push (a part of) the word w forward i.e., from right to left, through the language L. In the example above, the solution is v = aa, L = {ε, a, aa, abaa}, and u = b (note that L is different from L). In this section, we show that this process is always feasible and for cfls it is constructive. The result of pushing a word w through a language L will consist of three words: push(L, w) the longest part of w that can be pushed through L, rest(L, w) the part that cannot be pushed through, and offset(L, w) a special word that allows to identify the corresponding derivative of L. There are three classes of languages that need to be considered, which we present next together with an outline of how the pushing is done.

The first class contains only the trivial language L = {ε} e.g., the range of the state p 3 of M 2 in Example 1. This language allows every word to be pushed through and it never changes in the process. For instance, if w 0 = ab, then push(L p3 , w 0 ) = ab, rest(L p3 , w 0 ) = ε, and offset(L p3 , w 0 ) = ε.

The second class consists of non-trivial periodic languages, essentially languages contained in the Kleene closure of some period word. An example is L q1 = (abc) * = {ε, abc, abcabc, . . .} whose period is abc. Periodic languages allow to push multiplicities of the period and then some prefix of the period e.g., if we take w 1 = abcabcaba, then push(L q1 , w 1 ) = abcabcab and rest(L q1 , w 1 ) = a. The offset here is the corresponding prefix of the period: offset(L q1 , w 1 ) = ab.

The third class contains all remaining languages i.e., non-trivial non-periodic languages. Interestingly, we show that for a language in this class there exists a word that is the longest word that can be pushed fully through the language, and furthermore, every other word that can be pushed through is a prefix of this word. For instance, for L p1 = {ε, a, aab} from Example 1, aa is the longest word that can be pushed through. If we take w 2 = ab, then we get push(L p1 , w 2 ) = a and rest(L p1 , w 2 ) = b. Here, the offset is the prefix of aa that has been already pushed through: offset(L p1 , w 2 ) = a. Note that this class also contains the languages that do not permit any pushing through e.g., L p0 = {ba, ab, aab} does not allow pushing through because it contains two words that start with a different symbol.

We now define formally the pushing process. First, for L ⊆ ∆ * we define the set of words that can be pushed fully through L:

Shovel (L) = {w ∈ ∆ * | w is a common prefix of L • w}.
For instance, Shovel (L p1 ) = {ε, a, aa} and Shovel (L q0 ) = (abc) * • {ε, a, ab}. We note that Shovel ({ε}) = ∆ * and Shovel (L) always contains at least one element ε because L is assumed to be nonempty. Also, as we prove in appendix, Shovel (L) is prefix-closed and totally ordered by the prefix relation.

Next, we define periodic languages (cf. [START_REF] Lothaire | Combinatorics on Words[END_REF]). A language L ⊆ ∆ * is periodic iff there exists a nonempty word v ∈ ∆ * , called a period of L, such that L ⊆ v * . A word w is primitive if there is no v and n ≥ 0 such that w = v n . Recall from [START_REF] Lothaire | Combinatorics on Words[END_REF] that every non-trivial periodic language L has a unique primitive period, which we denote Period (L). For instance, the language {ε, abab, abababab} is periodic and its primitive period is ab; abab is also its period but not primitive. In the sequel, by Prefix (w) we denote the set of prefixes of the word w.

Proposition 1. Given a reduced and non-trivial language

L, Shovel (L) is infi- nite iff L is periodic. Furthermore, if L is periodic then Shovel (L) = Period (L) * • Prefix (Period (L)).
This result and the observations beforehand lead to three relevant cases in the characterisation of Shovel (L) for a language L. 0 o L = {ε} (trivial language), and then Shovel (L) = ∆ * , 1 o L is periodic and L = {ε}, and then Shovel (L) = Period (L) * •Prefix (Period (L)). 2 o L is non-periodic, and Shovel (L) = Prefix (v) for some v ∈ Shovel (L). Now, suppose we wish to push a word w ∈ ∆ * through a language L ⊆ ∆ * and let s = max ≤ prefix (Prefix (w) ∩ Shovel (L)) and w = s • r. We define push(L, w), rest(L, w), and offset(L, w) depending on the class L belongs to: Offsets play a central role in the output normalization procedure, which is feasible thanks to the following result. Proposition 2. The set {offset(L, w) | w ∈ ∆ * } is finite for any reduced L.

0 o L = {ε}: push(L, w) = w, rest(L, w) = ε,

Pushing words backwards

Until now, we have considered the problem of pushing a word through a language from right to left. However, in Example 1 if we consider the second occurrence of q 1 in the rule δ(q 0 , f) = q 1 • ac • q 1 , we realize that pushing words in the opposite direction needs to be investigated as well. These two processes are dual but before showing in what way, we present a natural extension of the free monoid ∆ * to a pregroup (or groupoid) G ∆ . It allows to handle pushing in two directions in a unified manner and simplifies the output normalization algorithm.

A pregroup of words over ∆ is the set

G ∆ = ∆ * ∪ {w -1 | w ∈ ∆ + },
where w -1 is a term representing the inverse of an nonempty word w. This set comes with two operators, a unary inverse operator: (w) -1 = w -1 , ε -1 = ε, and (w -1 ) -1 = w for w ∈ ∆ * , and a partial extension of the standard concatenation that satisfies the following equations (complete definition in appendix):

w -1 •w = ε and w • w -1 = ε for w ∈ ∆ * , and v -1 • u -1 = (uv) -1 for u, v ∈ ∆ * .
We note that some expressions need to be evaluated diligently e.g., ab

• (cb) -1 • cd = ab • b -1 • c -1 • cd = ad,
while some are undefined e.g., ab • a -1 . In the sequel, we use w, u, v, . . . to range over ∆ * only and z, z 1 , . . . to range over elements of G ∆ . Now, we come back to pushing a word w backwards through L, which consists of finding u

• v = w and L such that w • L = u • L • v.
We view this process as pushing the inverse w -1 through L i.e., we wish to find u

• v = w such that L • w -1 = v -1 • L • u -1 because then L • v -1 = v -1 • L , and consequently, w • L = (u • v) • (v -1 • L • v) = u • L • v.
But to define pushing backwards more properly we use another perspective based on the standard reverse operation of a word e.g., (abc) rev = cba. Namely, pushing w backwards through L is essentially pushing w rev through L rev because (w

• L) rev = L rev • w rev and if L rev • w rev = v 0 • L 0 • u 0 , then w • L = u rev 0 • L rev 0 • v rev 0 .
Thus push(L, w -1 ) = (push(L rev , w rev ) rev ) -1 , rest(L, w -1 ) = (rest(L rev , w rev ) rev ) -1 , and offset(L, w -1 ) = (offset(L rev , w rev ) rev ) -1 . Now, the main condition of pushing words through languages is: for every L and z ∈ G ∆ we have

L•z = push(L, z)•(offset(L, z) -1 •L•offset(L, z))•rest(L, z).
Because the output normalization procedure works on stws and not languages, to prove its correctness we need a stronger statement treating independently every word of the language. Proposition 3. Given a reduced and nonempty language L ⊆ ∆ * and z ∈ G ∆ , for any word

u ∈ L u • z = push(L, z) • (offset(L, z) -1 • u • offset(L, z)) • rest(L, z).

Output normalization algorithm

We fix an stw M = (Σ, ∆, Q, init, δ) and introduce the following macros:

Lq = Core(L q ), Left(q) = Left(L q ), Right(q) = Right(L q ), push(q, z) = push( Lq , z), offset(q, z) = offset( Lq , z), rest(q, z) = rest( Lq , z).
Also, let Offsets(q) = {offset(q, z) | z ∈ G ∆ } and note that by Proposition 2 it is finite. The constructed stw M = (Σ, ∆, Q , init , δ ) has the following states

Q = { q, w | q ∈ Q, w ∈ Offsets(q)}.
Our construction ensures that T M = T M and for every q ∈ Q, every z ∈ Offsets(q), and every t ∈ dom q

T q,z (t) = z -1 • Left(q) -1 • T q (t) • Right(q) -1 • z If init = u 0 • q 0 • u 1 , then init = u 0 • q 0 • u 1 ,
where u 0 , u 1 , and q 0 are calculated as follows:

1: v := Right(q 0 ) • u 1 2: q 0 := q 0 , offset(q 0 , v) 3: u 0 := u 0 • Left(q 0 ) • push(q 0 , v) 4: u 1 := rest(q 0 , v) For a transition rule δ(p, f ) = u 0 • p 1 • u 1 • . . . • u k-1 • p k • u k and any z ∈ Offsets(p) we introduce a rule δ ( p, z , f) = u 0 • p 1 • u 1 • . . . • u k-1 • p k • u k ,
where u 0 , . . . , u k and p 1 , . . . p k are calculated as follows:

1: z k := Right(p k ) • u k • Right(p) -1 • z 2: for i := k, . . . , 1 do 3: u i := rest(p i , z i ) 4: p i := p i , offset(p i , z i ) 5: z i-1 := Right(p i-1 ) • u i-1 • Left(p i ) • push(p i , z i ) 6: u 0 := z -1 • Left(p) -1 • z 0
where (for convenience of the presentation) we let Right(p 0 ) = ε. We remark that not all states in Q are reachable from the initial rule and in fact the conversion procedure can identify the reachable states on the fly. This observation is the basis of a conversion algorithm that is polynomial in the size of the output.

Example 3. We normalize the stw M 1 from Example 1. The initial rule q 0 becomes a • q 0 , ε • c with Left(q 0 ) = a and Right(q 0 ) = c being pushed up from q 0 but with nothing pushed through q 0 . The construction of the state q 0 , ε triggers the normalization algorithm for the rule δ(q 0 , f) = q 1 • ac • q 1 with Left(q 0 ) = a and Right(q 0 ) = c to be retracted from left and right side resp. (and nothing pushed through since z = ε). This process can be viewed as a taking the left hand side of the original rule with the inverses of retracted words a -1 •q 1 •ac•q 1 •c -1 and pushing words forward as much as possible, which gives a

-1 • q 1 • ac • c -1 • q 1 , c -1 and then a -1 •a• q 1 , a • q 1 , c -1 . This gives δ ( q 0 , ε , f) = q 1 , a • q 1 ,
c -1 . Note that while Offsets(q 1 ) = {(bc) -1 , c -1 , ε, a, ab}, only two states are constructed.

Next, we need to construct rules for the new state q 1 , a with z = a and Left(q 1 ) = Right(q 1 ) = ε. We start with the rule δ(q 1 , a) = ε and to its left hand side we add a -1 at the beginning and a at its end: a -1 • ε • a = ε, which yields the rule δ ( q 1 , a , a) = ε. Now, for the rule δ(q 1 , g) = q 1 • abc we obtain the expression a -1 • q 1 • abca. Recall that L q1 = (abc) * is a periodic language, and so push(q 1 , abca) = abca, rest(q 1 , abca) = ε, and offset(q 1 , abca) = a. Consequently, we obtain the rule δ ( q 1 , a , g) = bca• q 1 , a . Here, it is essential to use the offsets to avoid introducing a redundant state q 1 , abca and entering an infinite loop. Similarly, we obtain: δ ( q 1 , c -1 , g) = cab • q 1 , c -1 and δ ( q 1 , c -1 , a) = ε. Theorem 2. For an stw M let M be the stw obtained with the method described above. Then, M is equivalent to M and satisfies (E 1 ) and (E 2 ). Furthermore, M can be constructed in time polynomial in the size M , which is at most doubly-exponential in the size of M .

Because of space limitations, the details on complexity have been omitted and can be found in the full version available online.

Exponential lower bound

First, we show that the size of a rule may increase exponentially.

Example 4. For n ≥ 0 define an stw M n over the input alphabet Σ = {f (2) , a (0) } with the initial rule q 0 , and these transition rules (with 0 ≤ i < n):

δ(q i , f) = q i+1 • q i+1 , δ(q n , a) = a.
The transformation defined by M n maps a perfect binary tree of height n to a string a 2 n . M n is not earliest. To make it earliest we need to replace the initial rule by a 2 n • q 0 (x 0 ) and the last transition rule by δ(q n , a) = ε.

The next example shows that also the number of states may become exponential.

Example 5. For n ≥ 0 and take the stw N n with Σ = {g

0 , a

1 , a (0) 0 }, the initial rule q 0 , and these transition rules (with 0 ≤ i < n):

δ(q i , g 0 ) = q i+1 , δ(q n , a 0 ) = ε, δ(q i , g 1 ) = q i+1 • a 2 i , δ(q n , a 1 ) = a 2 n • #.
While the size of this transducer is exponential in n, one can easily compress the exponential factors 2 2 i and obtain an stw of size linear in n (cf. Example 4). M n satisfies (E 1 ) but it violates (E 2 ), and defines the following transformation.

T Nn = {(g b0 (g b1 (. . . g bn-1 (a 0 ) . . .)), a b ) | b = (b n-1 , . . . , b 0 ) 2 } ∪ {(g b0 (g b1 (. . . g bn-1 (a 1 ) . . .)), a 2 n • # • a b ) | b = (b n-1 , . . . , b 0 ) 2 }, where (b n-1 , . . . , b 0 ) 2 = i b i * 2 i .
The normalized version N n has the initial rule q 0 , ε and these transition rules:

δ ( q i , a j , g 0 ) = q i+1 , a j , δ ( q n , a k , a 0 ) = ε, δ ( q i , a j , g 1 ) = a 2 i • q i+1 , a j+2 i , δ ( q n , a k , a 1 ) = a 2 n -k #a k ,
where 0 ≤ i < n, 0 ≤ j < 2 i , and 0 ≤ k < 2 n . We also remark that N n is the minimal estw that recognises T Nn .

Minimization

In this section we investigate the problem of minimizing the size of a transducer. Minimization of estws is simple and relies on testing the equivalence of estws known to be in ptime [START_REF] Staworko | Equivalence of nested word to word transducers[END_REF]. For an estw M the minimization procedure constructs a binary equivalence relation ≡ M on states such that q ≡ M q iff T q = T q . The result of minimization is the quotient transducer M/ ≡ M obtained by choosing in every equivalence class C of ≡ M exactly one representative state q ∈ C, and then replacing in rules of M every state of C by q.

To show that the obtained estw is minimal among all estws defining the same transformation, we use an auxiliary result stating that all estws defining the same transformation use rules with the same distribution of the output words and allow bisimulation.

A labeled path is a word over k>0 Σ (k) × {1, . . . , k}, which identifies a node in a tree together with the labels of its ancestors: ε is the root node and if a node π is labeled with f , then π • (f, i) is its i-th child. By paths(t) we denote the set of labeled paths of a tree t. For instance, for t 0 = f (a, g(b)) we get paths(t 0 ) = {ε, (f, 1), (f, 2), (f, 2) • (g, 1)}. We extend the transition function δ to identify the state reached at a path π: δ(q, ε) = q and δ(q, π • (f, i)) = q i , where δ(q, π) = q and δ(q , f) = u 0 • q 1 • u 1 • . . . • q k • u k . Now, the lemma of interest.

Lemma 1. Take two estws M = (Σ, ∆, Q, init, δ) and M = (Σ, ∆, Q , init , δ ) defining the same transformation T = T M = T M and let init = u 0 • q 0 • u 1 and init = u 0 •q 0 •u 1 . Then, u 0 = u 0 and u 1 = u 1 , and for every π ∈ paths(dom(T )), we let q = δ(q 0 , π) and q = δ (q 0 , π), and we have 1. T q = T q , 2. δ(q, f ) is defined if and only if δ (q , f) is, for every f ∈ Σ, and 3. if δ(q, f ) = u 0 • q 1 • u 1 • . . . • q k • u k and δ (q , f) = u 0 • q 1 • u 1 • . . . • q k • u k , then u i = u i for 0 ≤ i ≤ k.

The proof is inductive and relies on properties (E 1 ) and (E 2 ), and the determinism of the transducers. We show the correctness of our minimization algorithm by observing that it produces an estw whose size is smaller than the input one, and Lemma 1 essentially states that the result of minimization of two equivalent transducers is the same transducer (modulo state renaming). This argument also proves Theorem 1. We also point out that Lemma 1 (with M = M ) allows to devise a simpler and more efficient minimization algorithm along the lines of the standard dfa minimization algorithm [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF].

Theorem 3. Minimization of estws is in ptime.

In stws the output words may be arbitrarily distributed among the rules, which is the main pitfall of minimizing general stws. This difficulty is unlikely to be overcome as suggested by the following result. Theorem 4. Minimization of stws i.e., deciding whether for an stw M and k ≥ 0 there exists an equivalent stw M of size at most k, is np-complete.

Conclusions and future work

We have presented an effective normalization procedure for stws, a subclass of top-down tree-to-word transducers closely related to a large subclass of nestedword to word transducers. One natural continuation of this work is find whether it can be extended to a Myhill-Nerode theorem for stws, and then, to a polynomial learning algorithm. Also, the question of exact complexity of the normalization remains open. Finally, the model of stws can be generalized to allow arbitrary non-sequential rules and multiple passes over the input tree.

  For instance, L = {a, aba} has two decompositions L = a • {ε, ba} • ε and L = ε • {ε, ab} • a. We resolve the ambiguity by choosing the former decomposition because it is consistent with (E 1 ) and (E 2 ) which indicate to push to the left. Formally, Left(L) = lcp(L) and Right(L) = lcs(L ), where L = Left(L)•L . The reduced core Core(L) is obtained from (1). As an example, the reduced decomposition of L q0 = (abc) * ac(abc) * from Example 1 is Left(L q0 ) = a, Right(L q0 ) = c, and Core(L q0 ) = (bca) * (cba) * .

  and offset(L, w) = ε. 1 o L is non-trivial and periodic: s = Period (L) k • o for some (maximal) proper prefix o of Period (L), and we assign push(L, w) = s, rest(L, w) = r, and offset(L, w) = o. 2 o L is non-periodic: push(L, w) = s, rest(L, w) = r, and offset(L, w) = s.


Markus ; Bier
email: bier@mf.mpg.de

Siegfried Dietrich

Dietrich Dietrich

Vapour pressure of ionic liquids

Keywords: vapour pressure, ionic liquids, triple point vapour pressure, ionic liquids, triple point

published or not. The documents may come

An extremely low vapour pressure (e.g. ca. 100 pPa at 298 K for [C 4 mim][PF 6 ] [1] compared with 3 kPa at 298 K for H 2 O [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]) is one of the extraordinary properties of room temperature ionic liquids (RTILs), i.e. molten salts with melting points below 100 • C. As a consequence, RTILs such as [C 4 mim][PF 6 ] at 298 K are liquids which do not evaporate significantly even under ultrahigh vacuum (UHV) conditions (i.e. for a pressure range 100 nPa . . . 100 pPa [START_REF] Redhead | [END_REF]), which offers the possibility to use RTILs, e.g. as substitutes for volatile organic solvents [4,5]. Only a decade ago RTILs were still described as "non-volatile" [4], but meanwhile direct measurements of their vapour pressures and enthalpies of vapourisation at elevated temperatures have been carried out [6,7]; even the distillation of RTILs [8] has been achieved. Since non-ionic liquids (NILs, such as benzene and water) exhibit triple point pressures p 3 above 1 Pa (see Table 1(a)), one might be tempted to attribute the extremely low triple point pressures of RTILs exclusively to their ionic character. However, a comparison of RTILs, which are composed of organic ions, with inorganic fused salts (IFSs), which are also of ionic character, reveals that the triple point pressures of the latter are above 1 Pa (see Table 1(c)), such as for NILs. This rules out the ionic character as the only reason for the low triple point pressures of RTILs.

We shall show below that it is not the Coulomb interaction alone but the combination of the melting point to occur below room temperature and of the ionic character which leads to the observed low triple point pressures of RTILs. In other words, it will be argued that any substance with a strong ionic character which is fluid at room temperature inevitably exhibits extremely low vapour pressures near its triple point. As it is apparent from the discussion above on NILs, RTILs and IFSs, low melting temperatures and ionic interactions are independent and non-contradicting properties and it is precisely the class of RTILs for which both properties are present simultaneously. Moreover, a comparison of NILs and RTILs shows that low melting temperatures alone do not imply low triple point pressures.

The arguments presented are of general nature and do not resort to a specific model. Moreover, we shall not address the mechanism leading to the low standard melting temperatures of RTILs, which has been explained in terms of a frustrated crystallisation due to asymmetric ion shapes, charge delocalisation, packing inefficiency and conformational degeneracy [9][10][11][12]. All what is needed for our line of arguments is a low melting temperature -irrespective of its origin for an actual substance or a specific model under consideration. Figure 1 displays the experimental vapour pressures p sat (T ) for liquid-vapour coexistence at temperature T for the non-polar liquid benzene (C 6 H 6 , see Reference [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]), the hydrogen bond forming liquid water (H 2 O, see Reference [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]), the paradigmatic RTILs [7,13]), as well as fused cadmium chloride (CdCl 2 ) and sodium chloride (NaCl) as representatives of IFSs (see Reference [14]). At low temperatures the boiling curves terminate at the triple point temperature T 3 (see Table 1 and References [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF][15][START_REF]CRC Handbook of Chemistry and Physics[END_REF][START_REF] Paulechka | [END_REF]), which is close the standard melting temperature of the corresponding substance because the melting curve is very steep. At high temperatures the boiling curves of the NILs and the IFSs terminate at their critical temperatures T c (see Tables 1(a) and (c) and References [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]18]), whereas RTILs decompose at a substance specific decomposition temperature T d (see Table 1(b) and References [4,15,19]). As it is apparent from Figure 1 In order to understand the position of the boiling curves of RTILs in Figure 1, we note that with respect to the strength of the particle-particle interaction, RTILs lie in between NILs, which interact via relatively weak dispersion forces and possibly hydrogen bonds, and IFSs, which interact predominantly via strong Coulomb forces. Due to the larger size of the RTIL ions and a possible delocalisation of the charge their interaction is, however, weaker than that of IFS ions. Hence, ignoring for the time being the decomposition of RTILs at T d , the molar enthalpies of vapourisation ∆ vap H(p) > 0 at pressure p are expected to be ordered as ∆ vap H NIL (p) < ∆ vap H RTIL (p) < ∆ vap H IFS (p). On the other hand, in the spirit of Trouton's rule [START_REF] Atkins | Physical chemistry[END_REF], the molar entropies of vapourisation ∆ vap S(p) at pressure p are expected to depend only weakly on the kind of substance, because their values are dominated by the translational and rotational degrees of freedom whereas vibrational and electronic modes and the structural arrangements contribute only as small corrections [START_REF] Vincett | [END_REF]. Data for organic and inorganic liquids tabulated in References [START_REF]CRC Handbook of Chemistry and Physics[END_REF][START_REF] Janz | Molten Salts Handbook[END_REF] suggest a Trouton-like rule ∆ vap S(p 0 ) ≈ (95±15) J/mol at ambient pressure p 0 = 10 5 Pa. According to ∆ vap H(p) = T b (p)∆ vap S(p) [START_REF] Atkins | Physical chemistry[END_REF] with T b (p) denoting the boiling temperature at pressure p one expects the relation

[C 4 mim][dca], [C 2 mim][NTf 2 ] and [C 8 mim][NTf 2 ] (see Refer- ences
T NIL b (p) < T RTIL b (p) < T IFS b (p)
, which is indeed consistent with the experimental findings for NILs and IFSs [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF][START_REF]CRC Handbook of Chemistry and Physics[END_REF][START_REF] Janz | Molten Salts Handbook[END_REF] and the extrapolations for RTILs to ambient pressure [START_REF] Rebelo | [END_REF] (see also Figure 1 and Table 1). Away from the critical point ∆ vap H(p) and ∆ vap S(p) depend only weakly on p [START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF][START_REF]CRC Handbook of Chemistry and Physics[END_REF], such that we can approximate ∆ vap H(p) ≈ ∆ vap H(p 0 ) and ∆ vap S(p) ≈ ∆ vap S(p 0 ) for a certain reference pressure p 0 such as the ambient pressure. Within this approximation the Clausius-Clapeyron equation [START_REF] Atkins | Physical chemistry[END_REF] allows one to estimate the vapour pressure p sat (T ) for liquid-vapour coexistence at temperature T : According to the above reasoning concerning ∆ vap H and ∆ vap S one infers the relation

p sat (T ) ≈ p 0 exp - ∆ vap H(p 0 ) RT + ∆ vap S(p 0 ) R . (1
p NIL sat (T ) ≫ p RTIL sat (T ) ≫ p IFS sat (T ). (2)
Actually, liquid-vapour coexistence at p sat (T ) occurs only in the temperature ranges T 3 ≤ T ≤ T c for NILs and IFSs and T 3 ≤ T ≤ T d for RTILs (see Figure 1). Equation ( 2) follows from general considerations concerning the strength of the particle-particle interaction and the entropy of vapourisation. According to these simple arguments it is indeed the strong ionic character which leads to a downshift of the boiling curves p sat (T ) of RTILs relative to those of NILs. However, the reason for IFSs having not an even lower triple point pressure than RTILs is the large difference in the triple point temperatures (T RTIL 3 < T IFS 3 , see Table 1) induced by a large difference in standard melting temperatures. Hence the extremely low vapour pressures of RTILs near their triple points can be understood on very general grounds based on both a strong ionic character and low melting temperatures; the conclusions are independent of substance specific properties which explains why this phenomenon is a common feature of RTILs.

In summary, we have shown that near its triple point the vapour pressure of a room temperature ionic liquid of strong ionic character is very small, because it depends exponentially on the ratio of a large enthalpy of vapourisationwhich is almost as large as that of inorganic salts -and a small thermal energy near the triple point, which is as small as that of non-ionic liquids. According to p sat (T ) ∼ exp(-∆ vap H/(RT )), where the prefactor is approximately independent of the kind of substance, an increase of ∆ vap H, reflecting the ionic character of room temperature ionic liquids relative to non-ionic liquids, leads to a downshift of p sat (T ). For room temperature ionic liquids these low vapour pressures are physically accessible due to their low triple points, induced by their low melting temperature -which is part of the definition of room temperature ionic liquids (see Figure 1). The even stronger ionic character of inorganic fused salts would in principle lead to even lower vapour pressures; however, these cannot be reached for their liquid state because they are preempted by a significantly higher freezing and thus triple point temperature (see Figure 1).

F

Molecular Physics Text˙2

Table 1. Experimental data for characteristic temperatures of (a) non-ionic liquids (NILs), (b) room temperature ionic liquids (RTILs) and (c) inorganic fused salts (IFSs) corresponding to the substances discussed in Figure 1.

T3 and p3 denote the temperature and the pressure, respectively, at the triple point, Tc is the critical temperature and T d denotes the temperature for the onset of decomposition of an RTIL [15,19]. T b denotes the standard boiling temperature at ambient pressure p0 = 10 [7,13]), as well as fused cadmium chloride (CdCl 2 ) and sodium chloride (NaCl) as examples of IFSs (see Reference [14]). At low temperatures all curves terminate at the corresponding triple point temperature T 3 (see Table 1), which is close to the standard melting temperature of that substance. At high temperatures the boiling curves for the RTILs terminate at the decomposition temperature T d , whereas the boiling curves of the other liquids end at their critical points (see Table 1). Room temperature T 0 = 298 K and ambient pressure p 0 = 10 5 Pa are indicated.

Figure

  Figure1. Experimental vapour pressures psat(T ) at liquid-vapour coexistence of non-ionic liquids (NILs), room temperature ionic liquids (RTILs) and inorganic fused salts (IFSs) as a function of temperature T for the non-polar liquid benzene (C 6 H 6 , see Reference[START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]), the hydrogen bond forming liquid water (H 2 O, see Reference[START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]), the paradigmatic RTILs[C 4 mim][dca], [C 2 mim][NTf 2 ] and [C 8 mim][NTf 2 ] (see References[7,13]), as well as fused cadmium chloride (CdCl 2 ) and sodium chloride (NaCl) as examples of IFSs (see Reference[14]). At low temperatures all curves terminate at the corresponding triple point temperature T 3 (see Table1), which is close to the standard melting temperature of that substance. At high temperatures the boiling curves for the RTILs terminate at the decomposition temperature T d , whereas the boiling curves of the other liquids end at their critical points (see Table1). Room temperature T 0 = 298 K and ambient pressure p 0 = 10 5 Pa are indicated.

Page 7 of 8 URL

 8

  , RTILs do not boil at ambient pressure p 0 = 10 5 Pa because boiling is preempted by decomposition; consequently Table 1(b) displays only extrapolated standard boiling temperatures T extr

b

for RTILs.

5

  Pa for NILs and IFSs, whereas the standard boiling temperatures T extr bfor RTILs are estimated by extrapolation[START_REF] Rebelo | [END_REF] because boiling of RTILs is preempted by decomposition.

	December 31, 2009 17:38 Molecular
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

  1. Experimental vapour pressures psat(T ) at liquid-vapour coexistence of non-ionic liquids (NILs), room temperature ionic liquids (RTILs) and inorganic fused salts (IFSs) as a function of temperature T for the non-polar liquid benzene (C 6 H 6 , see Reference[START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]), the hydrogen bond forming liquid water (H 2 O, see Reference[START_REF] Lemmon | Thermophysical Properties of Fluid Systems[END_REF]), the paradigmatic RTILs [C 4 mim][dca], [C 2 mim][NTf 2 ] and [C 8 mim][NTf 2 ] (see References

 [14,[START_REF]CRC Handbook of Chemistry and Physics[END_REF]18]