Mathieu Caralp

Pierre-Alain Reynier

Jean-Marc Talbot

A polynomial procedure for trimming visibly pushdown automata

We describe a polynomial procedure which, given a visibly pushdown automaton that accepts only well-nested words, returns an equivalent visibly pushdown automaton that is trimmed. We also show that this procedure can be applied to weighted visibly pushdown automata such as visibly pushdown transducers.

Introduction

Visibly pushdown automata (VPA) are a particular class of pushdown automata working over an alphabet splitted into call, internal and return symbols [START_REF] Alur | Visibly pushdown languages[END_REF][START_REF] Alur | Adding nesting structure to words[END_REF]. In VPA's, the stack behaviour is imposed by the input word: on a call symbol, the VPA pushes a symbol onto the stack, on a return symbol, it must pop the top symbol of the stack, and on an internal symbol, the stack remains unchanged.

Trimming a finite state automaton amounts to remove useless states, that is states that do not occur in some accepting computation of the automaton. This can be done easily in linear time simply by solving two reachability problems in the graph representing the automaton. However, the problem is more difficult for VPA's as the current state of a computation (called a configuration) is given by both a "control" state and a stack content.

As VPA are a restriction of pushdown automata, one can try to apply trimming procedures for pushdown automata to VPA. We are aware of two such procedures. A first one, described in [START_REF] Girault-Beauquier | Some results about finite and infinite behaviours of a pushdown automaton[END_REF], has an exponential time complexity. A second one relies on the translation of pushdown automata into context-free grammars 1 . More precisely, one can first translate the automaton into an equivalent context-free grammar, then eliminate from this grammar variables generating the empty language or not reachable from the start symbol, and third convert the resulting grammar into the pushdown automaton realizing its top-down analysis. This construction has a polynomial time complexity. However, in this form, it does not apply to VPA because the resulting pushdown automaton may not satisfy the condition of visibility. It is not clear whether it can be adapted to the setting of VPA.

In this work, we present a polynomial time procedure for trimming VPA that accept only well-nested words. Note that this construction could be extended to the complete class of VPA. In addition, we show how this procedure can be applied to weighted VPA, that is VPA in which transitions are also labelled by weights (such as visibly pushdown transducers for instance).

Definitions

Words and nested words Let Σ be a finite alphabet partitioned into three disjoint sets Σ c , Σ r and Σ ι , denoting respectively the call, return and internal alphabets. We denote by Σ * the set of (finite) words over Σ and by ǫ the empty word. The length of a word u is denoted by |u|. The set of well-nested words Σ * wn is the smallest subset of Σ * such that Σ * ι ⊆ Σ * wn and for all c ∈ Σ c , all r ∈ Σ r , all u, v ∈ Σ * wn , cur ∈ Σ * wn and uv ∈ Σ * wn . We define the height h(u) of some well-nested word u by induction as follows:

h(u) = 0 if u ∈ Σ * ι , h(uv) = max(h(u), h(v)) for u, v ∈ Σ *
wn , and h(cur) = 1 + h(u). Given a family of words w 1 , w 2 , . . . , w n , we denote by Π n i=1 w i the concatenation w 1 w 2 . . . w n .

Visibly pushdown automata (VPA) Visibly pushdown automata are a restriction of pushdown automata in which the stack behaviour is imposed by the input word. On a call symbol, the VPA pushes a symbol onto the stack, on a return symbol, it must pop the top symbol of the stack, and on an internal symbol, the stack remains unchanged. Formally:

Definition 1 (Visibly pushdown automata). A visibly pushdown automaton (VPA) on finite words over Σ is a tuple

A = (Q, I, F, Γ, δ) where Q is a finite set of states, I ⊆ Q is the set of initial states, F ⊆ Q the set of final states, Γ is a finite stack alphabet, δ = δ c ⊎ δ r ⊎ δ ι the (finite) transition relation, with δ c ⊆ Q × Σ c × Γ × Q, δ r ⊆ Q × Σ r × Γ × Q, and δ ι ⊆ Q × Σ ι × Q. A configuration of a VPA is a pair (q, σ) ∈ Q × Γ * . A run of A on a word u = a 1 . . . a l ∈ Σ * from a configuration (q, σ) to a configuration (q ′ , σ ′
) is a finite sequence of configurations ρ = {(q k , σ k )} 0≤k≤l such that q 0 = q, σ 0 = σ, q l = q ′ , σ l = σ ′ and for each 1 ≤ k ≤ l, there exists γ k ∈ Γ such that either (q k-1 , a k , γ k , q k ) ∈ δ c and σ k = σ k-1 γ k or (q k-1 , a k , γ k , q k ) ∈ δ r and σ k-1 = σ k γ k , or (q k-1 , a k , q k ) ∈ δ ι and σ k = σ k-1 . Depending on the case, let t k ∈ δ be the corresponding transition. Then we say that the run ρ is over the sequence of transitions (t k ) 1≤k≤l . We write (q, σ) u -→ (q ′ , σ ′ ) when there exists a run on u from (q, σ) to (q ′ , σ ′ ). We may omit the superscript u when irrelevant. We denote by ⊥ the empty word on Γ . Initial (resp. final) configurations are configurations of the form (q, ⊥), with q ∈ I (resp. q ∈ F ). A configuration (q, σ) is reachable (resp. is co-reachable) if there exist u ∈ Σ * and a configuration c such that c is initial and c u -→ (q, σ) (resp. such that c is final and (q, σ) u -→ c).

Definition 2. An automaton A is trimmed if it fulfills the two following conditions:

-every configuration of A is reachable iff it is co-reachable, -every state of A belongs to a reachable configuration.

We say that a run is accepting if it starts in an initial configuration and ends in a final configuration. A word is accepted by A iff there exists an accepting run of A on this word. The language of A, denoted by L(A), it the set of words accepted by A.

Note that the model we consider differs from the one introduced in [START_REF] Alur | Visibly pushdown languages[END_REF], for two reasons. First, there are return transitions that can be performed on the empty stack and second, the definition of final configurations does not require an empty stack. In particular, unlike in our definition, accepted words are not necessarily well-nested. However, the results we present in this work could be extended to the general class of VPA.

Trimming VPA

Let A = (Q, I, F, Γ, δ) be a VPA on the structured alphabet Σ. In this section, we define a new VPA A ′ = (Q ′ , I ′ , F ′ , Γ ′ , δ ′ ) on Σ, denoted trim(A), which recognizes the same language, and in addition is trimmed.

First, we define the following set:

WN = {(p, p ′ , p ′′ ) ∈ Q 3 | ∃(p, ⊥) → * (p ′ , ⊥) → * (p ′′ , ⊥)}
This set can be computed in polynomial time. More precisely, the following set can be computed first:

WN 2 = {(p, p ′ ) ∈ Q 2 | ∃(p, ⊥) → * (p ′ , ⊥)}.
WN 2 can be defined as the least set such that

-{(p, p) | p ∈ Q} ⊆ WN 2 , -if (p, p ′ ) ∈ WN 2 and (p ′ , p ′′ ) ∈ WN 2 , then (p, p ′′ ) ∈ WN 2 -if (p, q) ∈ WN 2 , and ∃(q, i, q ′ ) ∈ δ ι , then (p, q ′ ) ∈ WN 2 -if (p, q) ∈ WN 2 and ∃(p ′ , c, γ, p) ∈ δ c , (q, r, γ, q ′ ) ∈ δ r , then (p ′ , q ′ ) ∈ WN 2
Then, WN is obtained from WN 2 by the following property:

(p, p ′ , p ′′ ) ∈ WN ⇐⇒ (p, p ′ ) ∈ WN 2 ∧ (p ′ , p ′′ ) ∈ WN 2
We now define the four first components of the trimmed VPA A ′ as follows:

-

Q ′ = WN -I ′ = WN ∩ {(i, i, f ) | i ∈ I ∧ f ∈ F } -F ′ = WN ∩ {(i, f, f ) | i ∈ I ∧ f ∈ F } -Γ ′ = Γ × Q × Q
Intuitively, the VPA A ′ simulates the VPA A as follows: if a run of A ′ goes through a state (p, q, r) with a stack σ ′ of height n, then the run of A ′ at this position mimics a run of A whose current configuration is (q, σ), with σ of height n, and such that the top symbol of σ has been pushed when reaching the state p, and will be popped when leaving the state r. Moreover, from p to r in the run of A, the height of the stack is always larger or equal to n.

It remains to define the last component δ ′ . We define it by its restrictions on call, return and internal symbols respectively (namely

δ ′ c , δ ′ r and δ ′ ι ). Call symbols. Let (p 1 , p 2 , p 4 ) ∈ WN, c ∈ Σ c . Then ((p 1 , p 2 , p 4 ), c, (γ, p 1 , p 4 ), (q 1 , q 1 , q 2 )) ∈ δ ′
c iff the following three conditions hold:

-(p 2 , c, γ, q 1 ) ∈ δ c , -(q 1 , q 1 , q 2 ) ∈ WN,
-there exists a state p 3 and r ∈ Σ r such that (q 2 , r, γ, p 3 ) ∈ δ r , and (p 3 , p 3 , p 4 ) ∈ WN.

Return symbols. Let (q 1 , q 2 , q 2 ) ∈ WN, r ∈ Σ r . Then ((q 1 , q 2 , q 2 ), r, (γ, p 1 , p 4 ), (p 1 , p 3 , p 4 )) ∈ δ ′ r iff the following three conditions hold:

-(q 2 , r, γ, p 3 ) ∈ δ r , -(p 1 , p 3 , p 4 ) ∈ WN,
-there exists a state p 2 and c ∈ Σ c such that (p 2 , c, γ, q 1 ) ∈ δ c , and

(p 1 , p 2 , p 2 ) ∈ WN.
The situation of call/return transition is depicted on Figure 1, where w 1 , w 2 , w 3 ∈ Σ * wn , c ∈ Σ c , and r ∈ Σ r . Internal symbols.

(p1, σ) (p2, σ) (q1, σ.γ) (q2, σ.γ) (p3, σ) (p4,
Let (p 1 , q, p 2 ), (p 1 , q ′ , p 2 ) ∈ WN, a ∈ Σ ι . Then ((p 1 , q, p 2 ), a, (p 1 , q ′ , p 2 )) ∈ δ ′
ι iff the transition (q, a, q ′ ) belongs to δ ι .

Proposition 3. For any VPA A, trim(A) can be computed in polynomial time.

This result easily follows from the definition of trim(A).

Proposition 4. For any VPA A, L(A) = L(trim(A)). More precisely, there exists a mapping ϕ from transitions of trim(A) to transitions of A which induces a bijection between the accepting runs of trim(A) and those of A.

The mapping ϕ we consider is the trivial mapping obtained by considering, given a transition of A ′ , the transition of A on which it relies. To prove this result, we will first prove different lemmas.

Lemma 5. Let A be a VPA and A ′ = trim(A). Let ρ be a run of A ′ such that ρ : ((p, q, r), σ)

w -→ * ((p ′ , q ′ , r ′ ), σ), with σ ∈ Γ ′ * and w ∈ Σ * wn . Then we have p = p ′ and r = r ′ .
Proof. The proof goes by induction on the structure of the word w. It holds trivially when w is the empty word. Consider now a non-empty word w. There are two cases:

-First case: w = aw ′ , with a ∈ Σ ι , w ′ ∈ Σ *
wn and ((p 1 , q 1 , r 1 ), a, (p, q, r)) ∈ δ ′ ι . By construction of A ′ , p 1 = p and r 1 = r. We conclude by using the induction hypothesis on w ′ .

-Second case:

w = cw ′ rw ′′ , with c ∈ Σ c , r ∈ Σ r , w ′ , w ′′ ∈ Σ *
wn . There exists a transition ((p 1 , p 2 , p 4 ), c, (γ, p 1 , p 4 ), (q 1 , q 1 , q 2 )) ∈ δ ′ c which is used when reading the first letter c. There exists a state (r 1 , r 2 , r 3 ) such that the run of A ′ on w ′ goes from state (q 1 , q 1 , q 2 ) to state (r 1 , r 2 , r 3 ). As w ′ is well-nested, the induction hypothesis applied on w ′ entails that r 1 = q 1 and r 3 = q 2 . In addition, as a return transition is used after reading w ′ , the definition of δ ′ r implies that r 2 = r 3 . Thus by definition of δ ′ c and δ ′ r , a transition of the form ((q 1 , q 2 , q 2 ), r, (γ, p 1 , p 4 ), (p 1 , p 3 , p 4 )) ∈ δ ′ r for some state p 3 is used when reading the letter r. We conclude by induction hypothesis applied on w ′′ .

⊓ ⊔

We build a bijection between accepting runs of A and A ′ . First, we go from runs of A ′ to runs of A. We define the following standard projection mappings. Consider two integers 1 ≤ j ≤ k. Given a tuple s = (s 1 , s 2 , . . . , s k ), we denote by π j (s) the element s j . In addition, we extend this mapping over words on tuples, by letting π j (σ) = π j (γ 1 )π j (γ 2 ) . . . π j (γ n ) where σ = γ 1 γ 2 . . . γ n . Lemma 6. Let A be a VPA and A ′ = trim(A). For any accepting run

ρ ′ = (q ′ i , σ ′ i ) 1≤i≤k of A ′ over transitions (t ′ i ) 1≤i<k , ρ = (π 2 (q ′ i ), π 1 (σ ′ i ))
1≤i≤k is an accepting run of A over transitions (ϕ(t ′ i )) 1≤i<k . In addition, if two accepting runs ρ ′ and ρ ′′ over sequences of transitions η ′ and η ′′ are projected on the same run of A (i.e. such that ϕ(η ′ ) = ϕ(η ′′ )), then we have ρ ′ = ρ ′′ .

Proof. We prove by induction on ρ ′ that the projection run ρ defined above is a correct run of A, on the corresponding transitions. The fact that accepting runs of A ′ are projected on accepting runs of A is trivial. Finally, the fact that two accepting runs of trim(A) projected on the same run of A coincide can be proven by induction on the height of these runs.

⊓ ⊔

Conversely, considering translation of runs of A to runs of A ′ . States of A ′ extend states of A by considering starting and ending states for the current stack level, and the transitions naturally match. Therefore we prove the following lemma in which we consider a word w 2 ∈ Σ * wn embedded into a context (w 1 , w 3 ) ∈ Σ * wn × Σ * wn such that w 1 w 2 w 3 corresponds to the current stack level.

Lemma 7. Let A be a VPA and A ′ = trim(A). For all w 1 , w 2 , w 3 ∈ Σ * wn , if there exists a run ρ of the form (p, ⊥)

w1 -→ * (q, ⊥) w2 -→ * (r, ⊥) w3 -→ * (s, ⊥) in the VPA
A, such that the middle run on w 2 is over the sequence of transitions η = (t i ) 1≤i≤k , then there is a run ρ ′ of the form ((p, q, s), ⊥)

w2 -→ * ((p, r, s), ⊥) of A ′ over transitions η ′ = (t ′ i ) 1≤i≤k
, with ϕ(t ′ i ) = t i for any i. Proof. We prove this lemma by induction on the height of the word w 2 . If h(w 2 ) = 0, then w 2 ∈ Σ * ι , assuming w 2 = a 1 a 2 . . . a n , the restriction of ρ on w 2 is of the form

(q, ⊥) a1 -→ (q 1 , ⊥) . . . an -→ (q n , ⊥) with r = q n .
Observe that for all i, (p, q i , s) ∈ WN. By definition of A ′ the following is a run of A ′ on w 2 : ρ ′ = ((p, q, s), ⊥) a1 -→ ((p, q 1 , s), ⊥) . . . an -→ ((p, q n , s), ⊥) with r = q n . We now assume for the induction that the property holds when h(w 2 ) ≤ n and consider w 2 such that h(w 2 ) = n + 1. There exists a unique decomposition of w 2 as follows:

w 2 = [Π k i=1 (w int i c i w wn i r i )]w int k+1
with for all i, w int i ∈ Σ * ι , w wn i ∈ Σ * wn such that h(w wn i ) ≤ n, c i ∈ Σ c , and r i ∈ Σ r . Let w 1 , w 3 ∈ Σ * wn and ρ be a run of A on w 1 w 2 w 3 . We decompose the run ρ as follows:

-on w 1 : (p, ⊥) w1 --→ * (p 1 1 , ⊥) -on each w int i c i w wn i r i : (p 1 i , ⊥) w int i --→ * (p 2 i , ⊥) ci -→ (q 1 i , γ i ) w wn i --→ * (q 2 i , γ i ) ri -→ (p 1 i+1 , ⊥) -on w int k+1 : (p 1 k+1 , ⊥) w int k+1 ---→ * (p 2 k+1 , ⊥) -on w 3 : (p 2 k+1 , ⊥) w3 --→ * (s, ⊥)
Note that q = p 1 1 and r = p 2 k+1 . As w wn i is well-nested, there exists a run in A of the form (q 1 i , ⊥)

w wn i --→ * (q 2 i , ⊥).
By induction hypothesis, this implies that there exists a run ρ ′ i = ((q 1 i , q 1 i , q 2 i ), ⊥)

w wn i -→ * ((q 1 i , q 2 i , q 2 i ), ⊥) of A ′ on w wn i .
Again, using the fact that w wn i well-nested, we have

((q 1 i , q 1 i , q 2 i ), γ ′ i ) w wn i -→ * ((q 1 i , q 2 i , q 2 i ), γ ′ i ) in A ′ for any γ ′ i ∈ Γ ′ .
We now describe the other parts of the run ρ ′ of A ′ on w 2 .

Internal actions For all i ∈ {1, . . . , k + 1}, ((p, p 1 i , s), ⊥)

w int i -→ * ((p, p 2 i , s), ⊥) on w int
i , by the base induction with w 1 and w 3 well defined. Calls For all i ∈ {1, . . . , k}, we have (p 2 i , c i , γ i , q 1 i ) ∈ δ c in A. Thus by definition of A ′ , there exists a transition ((p, p 2 i , s), c i , (γ i , p, s), (q 1 i , q 1 i , q 2 i )) ∈ δ ′ c in A ′ . Returns For all i ∈ {1, . . . , k}, we have (q 2 i , r i , γ i , p 1 i+1 ) ∈ δ r in A. Thus by definition of A ′ there exists a transition ((q 1 i , q 2 i , q 2 i ), r i , (γ i , p, s), (p,

p 1 i+1 , s)) ∈ δ ′ r in A ′ .
One can then easily check that all the above transitions and partial runs can be gathered to obtain a run of A ′ on w 2 with the expected form.

⊓ ⊔

To conclude the proof of Proposition 4, note that Lemma 6 implies that L(trim(A)) ⊆ L(A) (more precisely, ϕ induces an injection from accepting runs of trim(A) to accepting runs of A). Conversely, using Lemma 7 for w 1 = w 3 = ǫ yields p = q ans r = s and if moreover p is initial and q is final then any accepting run in A is associated with an accepting run in trim(A). More precisely, we obtain an injection from accepting runs of A to those of trim(A). Indeed, thanks to the property of mapping ϕ, two different accepting runs of A are mapped onto two different accepting runs of trim(A). Finally, we obtain that mapping ϕ induces a bijection between runs of A and those of trim(A), as expected. In particular, we have L(A) = L(trim(A)).

Proposition 8. For any VPA A, trim(A) is trimmed.

Proof. Let A ′ be trim(A). Therefore, we first prove that any reachable configuration of A ′ is also co-reachable, and then the converse.

Let co = ((p, q, r), σ) be a reachable configuration of A ′ . There exists a run ρ of A ′ of the form ((i, i, f ), ⊥) → * co between an initial configuration ((i, i, f ), ⊥) and co. We show by induction on the height of the stack that we can reach a final configuration from co.

If |σ| = 0, by the lemma 5, we obtain p = i and r = f . In particular, this implies p ∈ I and r ∈ F . Since (p, q, r) ∈ WN, there is a run (p, ⊥) → * (q, ⊥) → * (r, ⊥) in A, thus by Lemma 7 we have a run ((p, q, r), ⊥) → * ((p, r, r), ⊥) of A ′ . This concludes this case as by the above observation, we have (p, r, r)

∈ I × F × F = F ′ .
We now assume for the induction that the property holds when |σ| ≤ n and we consider a stack σ such that |σ| = n + 1. Let denote by (γ, p ′ , r ′ ) the top symbol of σ, write σ = σ ′ .(γ, p ′ , r ′ ), and consider the first position in the run ρ that pushes this symbol onto the stack. We denote by c the associated call. More precisely, there exists a unique decomposition of ρ as follows:

((i, i, f ), ⊥) → * ((p ′ , q ′ , r ′ ), σ ′ ) c -→ ((p ′′ , p ′′ , r ′′ ), σ) → * ((p, q, r), σ)
such that the run from ((p ′′ , p ′′ , r ′′ ), σ) to ((p, q, r), σ) is associated with a well-nested word. By Lemma 5, we obtain p ′′ = p and r ′′ = r. Considering the call transition associated with c, and by definition of δ ′ c and δ ′ r , there exists a return transition ((p, r, r), r, (γ, p ′ , r ′ ), (p ′ , q ′′ , r ′ )) ∈ δ ′ r for some letter r ∈ Σ r . In addition, as (p, q, r) ∈ WN, there is a run (p, σ) → * (q, σ) → * (r, σ) in A, and thus by Lemma 7 we have a run ((p, q, r), σ) → * ((p, r, r), σ). As the top symbol of σ is (γ, p ′ , r ′ ), the above return transition can be used to reach configuration ((p ′ , q ′′ , r ′ ), σ ′ ) whose height is n. The result follows by induction hypothesis.

Conversely, let co = ((p, q, r), σ) be a co-reachable configuration of A ′ . There exists a run ρ of A ′ of the form co → * ((i, f, f ), ⊥) between co a final configuration ((i, f, f ), ⊥). We show by induction on the height of the stack that co can be reached from an initial configuration.

If |σ| = 0, by the lemma 5, we obtain p = i and r = f . In particular, this implies p ∈ I and r ∈ F . Since (p, q, r) ∈ WN, there is a run (p, ⊥) → * (q, ⊥) → * (r, ⊥) in A, thus by Lemma 7 we have a run ((p, p, r), ⊥) → * ((p, q, r), ⊥) of A ′ . This concludes this case as by the above observation, we have (p, p, r) ∈ I × I × F = I ′ .

We now assume for the induction that the property holds when |σ| ≤ n and we consider a stack σ such that |σ| = n + 1. Let denote by (γ, p ′ , r ′ ) the top symbol of σ, write σ = σ ′ .(γ, p ′ , r ′ ), and consider the first position in the run ρ that pops this symbol from the stack. We denote by r the associated return. More precisely, there exists a unique decomposition of ρ as follows:

((p, q, r), σ) → * ((p ′′ , r ′′ , r ′′ ), σ) r -→ ((p ′ , q ′ , r ′ ), σ ′ ) → * ((i, f, f ), ⊥)
such that the run from ((p, q, r), σ) to ((p ′′ , r ′′ , r ′′ ), σ) is associated with a well-nested word. By Lemma 5, we obtain p ′′ = p and r ′′ = r. Considering the return transition associated with r, and by definition of δ ′ c and δ ′ r , there exists a call transition ((p ′ , q ′′ , r ′ ), c, (γ, p ′ , r ′ ), (p, p, r)) ∈ δ ′ c for some letter c ∈ Σ c . In addition, as (p, q, r) ∈ WN, there is a run (p, σ) → * (q, σ) → * (r, σ) in A, and thus by Lemma 7 we have a run ((p, p, r), σ) → * ((p, q, r), σ). As the top symbol of σ is (γ, p ′ , r ′ ), the above call transition can be used. As a consequence, we have proven that there exists a run from configuration ((p ′ , q ′′ , r ′ ), σ ′ ) to configuration co. In particular, configuration ((p ′ , q ′′ , r ′ ), σ ′ ) is a co-reachable configuration whose height is n, and the result follows by induction hypothesis.

By construction, some useless state may remain in A ′ : indeed, A ′ may contain some state q such that for no stack σ, (q, σ) is reachable (and thus co-reachable). However, deciding whether for some stack σ, (q, σ) is reachable can be reduced to the emptiness problem of pushdown automata accepting on final states. Since this problem is decidable in polynomial time, We can easily remove useless states from A ′ . It follows that A ′ is trimmed.

⊓ ⊔

To summarize the results presented in this section, we have the following theorem:

Theorem 9. Let A be a VPA. Then:

trim(A) can be built in polynomial time, -L(A) = L(trim(A)), and more precisely, there exists a mapping from transitions of A ′ to those of A which yields a bijection between accepting runs of A ′ and those of A, -trim(A) is trimmed.

Application to VPA with weights

We show in this section that our constructions can be applied to VPA with weights, for instance visibly pushdown transducers (see [START_REF] Filiot | Properties of visibly pushdown transducers[END_REF]) where transitions are in addition labelled with output words, and VPA with multiplicities (N-VPA short), where transitions are labelled by integers.

We consider a monoid (M, •) which will be used to represent weights associated with transitions (for instance Σ * equipped with concatenation in the case of transducers and N equipped with addition for N-VPA).

Definition 10 (Weighted VPA). A weighted visibly pushdown automaton on finite words over Σ with weights in

(M, •) is a tuple A = (Q, I, F, Γ, δ) where Q is a finite set of states, I ⊆ Q is the set of initial states, F ⊆ Q the set of final states, Γ is a finite stack alphabet, δ = δ c ⊎δ r ⊎δ ι is the (finite) transition relation, with δ c ⊆ Q×Σ c ×M ×Γ ×Q, δ r ⊆ Q × Σ r × M × Γ × Q, and δ ι ⊆ Q × Σ ι × M × Q. Given a transition t ∈ δ, we denote by λ(t) ∈ M its weight.
The notions of configurations and runs are lifted from VPA to weighted VPA. Given a run ρ over a sequence of transitions η = (t i ) 1≤i≤k , we define the weight of ρ, denoted ρ , as ρ = Π i=k i=1 λ(t i ). Then, the behaviour of the weighted VPA A is represented by the formal power serie A from Σ * to multisets over M , defined by A (u) = {{ ρ | ρ ∈ Runs(u)}}.

In the sequel, we are interested in the following property of a weighted VPA:

( †) ⇐⇒    (p, c, m, γ, q), (p, c, m ′ , γ, q) ∈ δ c ⇒ m = m ′ (p, r, m, γ, q), (p, r, m ′ , γ, q) ∈ δ r ⇒ m = m ′ (p, i, m, q), (p, i, m ′ , q) ∈ δ ι ⇒ m = m ′ Intuitively, this property states that two transitions that coincide on their source and target states, input and stack symbols, have the same weight. We prove that any weighted VPA can be turned into an equivalent weighted VPA verifying this property: Proposition 11. Any weighted VPA can be turned into an equivalent weighted VPA verifying property ( †).

Proof. Let A = (Q, I, F, Γ, δ) be a weighted VPA. We build an equivalent weighted VPA A ′ = (Q ′ , I ′ , F ′ , Γ ′ , δ ′ ) that satisfies property ( †). Intuitively, the construction stores in the location the last transition that has been fired. This allows to distinguish between two transitions that are equivalent w.r.t. the underlying VPA, but which have different weights. Indeed, in this new model, they are not equivalent anymore w.r.t. the underlying VPA.

Let # be a new symbol, and δ # = δ ∪ {#}. The symbol # is used as an initialization, as no transition has been fired yet. We define A ′ as follows:

-Q ′ = Q × δ # -I ′ = I × {#} -F ′ = F × δ # -Γ ′ = Γ -δ ′ is
defined as follows: (similarly for δ ′ r , δ ′ ι ) ((p, t), c, m, γ, (q, t ′ )) ∈ δ ′ c ⇐⇒ t ′ = (p, c, m, γ, q) ∈ δ c ∧ t ∈ δ # The correctness of this construction can be proven by an induction on the length of runs.

⊓ ⊔ Property ( †) implies that the weight of a run of a weighted VPA only depends on the run of the underlying VPA. This result allows to apply the trimming procedure presented in this paper to any weighted VPA. Indeed, we have proven that there exists a mapping from transitions of trim(A) to those of A yielding a bijection between accepting runs. Thus, our construction preserves the weight associated to each word. Formally, we have: Proposition 12. Let A be a weighted VPA. We can build in polynomial time a weighted VPA A ′ that is trimmed and such that A = A ′ .

Fig. 1 .

 1 Fig. 1. Representation of call/return transitions.

We thank Géraud Sénizergues for pointing us this construction.


Rafael ; Lopez

Rafael Holdorf Lopez
email: rafael.holdorflopez@insa-rouen.fr

Didier Lemosse

José Eduardo Souza De Cursi

Jhojan Rojas

Abdelkhalak El-Hami

An Approach for the Reliability Based Design Optimization of Laminated Composites

Keywords: RBDO, Laminated Composite Plates, Optimization, PSO, Safety Factors Laminated composite, optimization, RBDO, safety factors, PSO

This paper aims at optimizing laminated composite plates taking into account uncertainties in the structural dimensions. As laminated composites require a global optimization tool, the Particle Swarm (PSO) Optimization method was employed. A new reliability based design optimization (RBDO) methodology based on safety factors is presented and coupled with the PSO. Such safety factors are derived from the Karush-Kuhn-Tucker (KKT) optimality conditions of the reliability index approach and eliminate the need of the reliability analysis in the RBDO. The plate weight minimization was the objective function of the optimization process. The results showed the coupling of the evolutionary algorithm with the safety factor method proposed in this paper successfully performed the RBDO of laminated composite structures.

Introduction

Laminated composites provide not only high structural performance, but also minimize the cost of such structures. A recent report by the US National Materials Advisory Board estimates that a 1 lb weight reduction amounts to a total saving of $200 over the 100,000 hours life of a civil transport, increasing to $1,000 in the case of military aircraft and reaching $20,000 for aerospace industry [START_REF] Kim | Special issue on optimization of aerospace structures[END_REF]. These numbers explain why structural weight is considered particularly critical in the aerospace industry. Thus, optimization techniques have been applied in order to get minimum weight structures, what corresponds to take a structure to its limit. However, the optimization of laminated composites can be classified as a non-convex and multimodal optimization problem. For such problem, the evolutionary algorithms are well-suited. Among others, the following were employed to optimize laminated composite structures: Genetic Algorithm (GA) (Le Riche and Haftka 1993, [START_REF] Nagendra | Improved genetic algorithm for the design of stiffened composite panels[END_REF], Lopez et al. 2009a,b), Particle Swarm Optimization (PSO) (Kennedy andEberhart 1995, Omkar et al. 2008), and Ant Colony Optimization (ACO) (Dorigo 1992, Aymerich and[START_REF] Aymerich | Optimization of laminate stacking sequence for maximum buckling load using the ant colony optimization (ACO) metaheuristic[END_REF]. Known advantages of the use of evolutionary algorithms include the following: (i) they do not require gradient information and can be applied to problems where the gradient is hard to obtain or simply does not exist; (ii) if correctly tuned, they do not get stuck in local minima; (iii) they can be applied to non-smooth or discontinuous functions. On the other hand, their main drawback is the extremely large number of evaluations of the objective function to achieve optimization, which can make their use nonviable depending on the computational cost of each evaluation.

In deterministic optimization, however, the uncertainties of the system (i.e. dimension, model, material, loads, etc) are not taken into account. Doing so, the resulting optimum solution may lead to a lower level of reliability and, as a consequence, a higher risk of failure. Thus, it is the objective of reliability based design optimization (RBDO) to optimize structures guaranteeing that its probability of failure is lower than a certain level chosen a priori by the designer.

This paper focus on RBDO methods that employ the first order reliability analysis (FORM) to approximate the probability of failure of the structures. Hence, other approaches such as simulation methods are not discussed in the brief review of the literature presented in the sequel.

As the reliability analysis may be an optimization procedure itself, the RBDO, in its classical version, is a double-loop strategy: structural optimization and reliability analysis. This double loop leads to a high computational cost. The reliability analysis is usually the most time consuming task in RBDO and most of the algorithms are based on the FORM using either the reliability index approach (RIA) [START_REF] Hasofer | An exact and invariant first order reliability format[END_REF] or the performance measure approach (PMA) [START_REF] Tu | A new study on reliability-based design optimization[END_REF].

To reduce the computational burden of the RBDO, several papers decoupled the structural optimization and the reliability analysis. This procedure may be divided into two groups: (i) the serial single loop methods and, (ii) the unilevel methods.

The basic idea of the serial single loop methods is to decouple the structural optimization (outer loop) and the reliability analysis (inner loop). Each method of this group utilizes a specific strategy to decouple such loops and then, perform them sequentially until some convergence criterion is achieved. Among these methods, the following may be cited: Traditional Approximation method [START_REF] Torng | An advanced reliability based optimization method for robust structural system design[END_REF], Single Loop Single variable (SLSV) [START_REF] Chen | Reliability based structural design optimization for practical applications[END_REF], Sequential Optimization and Reliability Assessment (SORA) [START_REF] Du | Sequential Optimization and Reliability Assessment method for Efficient Probabilistic Design[END_REF] and Safety Factor Approach (SFA) [START_REF] Wu | Safety-factor based approach for probability-based design optimization[END_REF]. For a comparison of such methods see references [START_REF] Yang | Experience with approximate reliability based optimization methods[END_REF] and [START_REF] Yang | Experience with approximate reliability based optimization methods II: an exhaust system problem[END_REF].

The central idea of the unilevel methods (also called monolevel) is to replace the reliability analysis by some optimality criteria of the optimum (e.g. imposing it as a constraint in the outer loop). Thus, there is a concurrent convergence of the design optimization and reliability calculation, in other words, they are sought simultaneously and independently. Examples of this approach may be found in references [START_REF] Kuschel | A new approach for structural optimization of series systems[END_REF][START_REF] Agarwal | An inverse-measure-based unilevel architecture for reliabilitybased design[END_REF][START_REF] Cheng | Sequential approximate programming strategy for reliability-based optimization[END_REF], Yi et al. 2008, Yi and Cheng 2008).

The main objective of this paper is the RBDO of laminated composite plates, what leads to the problem of coupling RBDO and global optimization techniques. Despite all these advances in reducing the computational cost of the RBDO, a few papers have dealt with global optimization [START_REF] Antonio | A hierarchical genetic algorithm with age structure for multimodal optimal design of hybrid composites[END_REF]) mainly due to its high computational cost. The coupling of standard RBDO methodologies and global optimization algorithms would lead to a huge computational cost due to the high cost of both procedures. One way to take into account uncertainties would be the use of safety factors. However, such factors are usually based on engineering experience and/or experimental work and may lead to either high cost or low reliability levels. It would be interesting to develop safety factors that achieve both the desired reliability level and optimized structure. The main advantage of such procedure is that it requires a little additional computational effort if compared to the standard deterministic optimization and at the same time it guarantees the minimum reliability level of the structure. Thus, this paper presents a new RBDO methodology based on safety factors, which are derived from the Karush-Kuhn-Tucker (KKT) optimality conditions of the RIA. It means that such factors are able to provide a final design that respects the probabilistic constraint of the RBDO problem.

Since the proposed method eliminates the need of the reliability analysis leading to a computational cost really close to the one of classical deterministic optimization methods, it is affordable to couple it with global optimization algorithms. Hence, the proposed methodology is coupled with an evolutionary algorithm: the PSO. Then, it is employed to pursue the RBDO of laminated composite plates taking into account the uncertainty on the structural dimensions.

The main contributions of the paper are: (i) the proposition of a new RBDO methodology based on safety factors derived from the KKT optimality conditions of the RIA, which eliminates the need of the reliability analysis; (ii) the coupling of such RBDO methodology with a global optimization algorithm, the PSO; and (iii) the application of the new RBDO methodology in the RBDO of laminated composite plates.

The paper is structured as follows: the laminated composite optimization problem to be solved is now presented in Section 2. The basic RBDO material is presented in Section 3. Moreover, in this section, the deterministic problem of section 2 has been converted into a RBDO problem which is the main objective of the paper. One of the main contributions of the paper, the new RBDO methodology, is fully presented in Section 4. The PSO method is briefly described in section 5. The safety factors method is demonstrated on classical studies in sections 6 and 7. Numerical examples on the laminate composites are in Section 8. Finally, comments about the extension of the methodology to more complex structures and its limitations are in Section 9, which reports the main conclusions drawn from the work.

Optimization of Laminated Composites

A laminated composite is usually tailored according to the designer's needs by choosing the thickness and orientation of the laminae. Thus, ply thickness and orientation angles are usually the design variables of a laminated composite optimization problem. In this paper, the goal is the minimization of the weight of laminated composite plates having as constraint either the first ply failure criterion of Tsai-Wu or the buckling failure factor. Thus, the general formulation of the optimization problem is presented here. The details of the mechanics of laminated composite plates are not presented in this paper, yet the interested reader is referred to [START_REF] Jones | Mechanics of composite materials[END_REF] for a basic textbook and to [START_REF] Reddy | Mechanics of Laminated Composite Plates and Shells: Theory and Analysis[END_REF]) for a more advanced material.

Objective Function

Consider a simply supported glass-epoxy laminated plate, subjected to compressive inplane loads N x and N y , as shown in Figure 1. Each layer is t i thick and the length and width of the plate are l p and w p , respectively. The elastic materials properties of the layers are: elastic modulus E 1 and E 2 , shear modulus G 12 , Poisson's ratio ν 12 and specific weight ρ. Thus, the weight of the structure is given by:

W (t) = ρ • w p • l p • Np i=1 t i (1)
Note that except t i , all variables in equation ( 1) are constant in the optimization problem. Thus, the problem is re-defined as minimizing the total thickness of the laminate. The laminate is composed by N p laminas whose orientation angles and thicknesses are θ i and t i (i = 1 to N ), respectively. Since the orientation angle of each layer plays an important role in the determination of the stiffness of the laminate, they are also considered as design variables. For convenience of notation, all the design variables (thickness and orientation of each lamina) are grouped into the design vector d = t θ = t 1 , . . . , t Np, θ 1 , . . . , θ Np .

Optimization Constraints

As commented before, two types of limit state functions are considered in this paper: (i) the buckling failure factor and (ii) the first ply failure criterion of Tsai-Wu. Both are described in the sequel.

In all the numerical analysis of this paper, the plates are analyzed using the classical lamination theory [START_REF] Jones | Mechanics of composite materials[END_REF]. Thus, the buckling failure factor is given by (see reference [START_REF] Gurdal | Design and Optimization of Laminated Composite Materials[END_REF])):

λ buckling (d) = minp,q      π D 11 (d) p lp 4 + 2 (D 12 (d) + 2D 66 (d)) p lp 2 q wp 2 + D 22 (d) q wp 4 p lp 2 Nx + q wp 2 Ny      (2)
where D ij (d) are coefficients of the laminate bending stiffness matrix, which are functions of both the thickness and the orientation angle of each lamina; p and q determine the amount of half waves in the plane of the plate, and λ buckling (d) is buckling failure factor, which is the buckling load divided by the applied load. Notice that equation (2) input requires positive values for compressive and negative values for tensile forces. The failure occurs when the λ buckling (d) is lower than one. Thus, the limit state function can be written as:

G buckling (d) = λ buckling (d) -1 (3)
where negative values imply failure. The first ply failure criterion of Tsai-Wu follows the Von Mises yield criterion adapted to orthotropic materials [START_REF] Jones | Mechanics of composite materials[END_REF]. The failure factor of the Tsai-Wu criterion is given by: where σ 1 (d) and σ 2 (d) are the normal stresses in the direction 1 and 2, respectively, τ 12 (d) is the shear stress in the elastic symmetry plane 1-2. F ij are parameters function of the strength properties X T , X C , Y T , Y C and S 12 (see reference [START_REF] Jones | Mechanics of composite materials[END_REF]). X T and X C are the tensile and compressive strengths parallel to the fibre direction, respectively, Y T and Y C are the tensile and compressive strengths normal to the fibre direction, respectively, S 12 is the shear strength. Note that X T , X C , Y T , Y C and S 12 are positive quantities.

λ T W (d) = F 11 σ 1 (d) 2 + 2F 12 σ 1 (d) σ 2 (d) + F 22 σ 2 (d) 2 + F 21 τ 12 (d) 2 + F 1 σ 1 (d) + F 2 σ 2 (d) (4
The failure occurs when λ T W (d) is higher than one. Thus, the limit state function can be written as:

G T W (d) = 1 -λ T W (d) (5)
where negative values imply failure.

Deterministic Optimization Problem

After defining the objective function and constraints, the deterministic laminated composite optimization problem is posed as:

Minimize : Weight W (d) subject to : Tsai -Wu failure criterion G T W (d) Buckling failure G buckling (d) t i ∈ R + , θ i ∈ [-90 o , 90 o ] , i = 1 to N p (6)
Thus, the optimization algorithm aims at finding the thickness and orientation angle of each one of the N P laminas that minimize the weight of the plate, not letting the structure fail accordingly to the chosen failure mode. The solution of the equation ( 6) will be noted d optimal in the sequel.

However, the uncertainties on the dimensions of the structure are taken into account in this paper. Thus, the deterministic thickness values t i are replaced by the random variables T i . For convenience of notation, such random variables are grouped into the vector X = [T ] = T 1 , . . . , T Np . In accordance with this modification, the deterministic design vector d is replaced by the reliability design vector m which is composed by the mean values m Ti of the random thicknesses T i and the deterministic orientation angles θ i of each layer of the laminate: m = m Ti , . . . , m TN p , θ 1 , . . . , θ Np T .

Hence, in the next section, the classical strategy of RBDO is presented to treat the constraint in a probabilistic sense.

Reliability Based Design Optimization

Converting the optimization problem of equation ( 6) into a RBDO problem, leads at looking for m reliable the solution of the equation ( 7): Notice that the limit state function G (m, X) is function of the random variables X. The constraint of the optimization problem is now defined in terms of the probability of not being fulfilled, the so-called probability of failure P f . Therefore, P allowed f represents the maximum allowed probability of failure of the structure and P f is given by:

Minimize : W (m) subject to : P f (G (m, X) ≤ 0) ≤ P allowed f m Ti ∈ R + , θ i ∈ [-90 o , 90 o ] , i = 1 to N p (7)
P f (m) = P f (G (m, X) ≤ 0) = G(m,X)≤0 f (X) dX (8)
where f (X) is the joint probability density function of X. The probability of failure as well as the maximum probability of failure can be approximated using the FORM of the RIA [START_REF] Hasofer | An exact and invariant first order reliability format[END_REF]. Such approximation is given by:

P f (m) ≈ Φ (-β (m)) P allowed f ≈ Φ -β target (9)
where Φ (•) is the standard normal cumulative distribution function; β (m) is the socalled reliability index, which is defined in the sequel, and β target is the target reliability index of the problem. The use of the equation ( 9) to describe the probabilistic constraint of equation ( 7), leads to:

Minimize : W (m) subject to : β target ≤ β (m) m Ti ∈ R + , θ i ∈ [-90 o , 90 o ] , i = 1 to N p (10)
To measure the reliability index β (m), one needs to transform the original random vector X (given in the so-called physical space) into a standard Gaussian vector U (given in the so-called standard space) [START_REF] Lemaire | Fiabilité des structures[END_REF]. First, vectors x and u, which are realizations of the random vectors X and U , respectively, are introduced.

Thus, the transformation between the two spaces of each realization is expressed as:

u = T (m, x) or x = T -1 (m, u) (11)
Then, the limit state function can be written as

G (m, X) = G m, T -1 (m, U ) = g (m, U ).
Notice that g (m, U ) is the limit state function in the standard space and the previous equalities relation hold for all the realizations x and u. The reliability index β (m) can be obtained from the following optimization problem in the U -space: for a given m : Minimize : u subject to :

g (m, u) ≤ 0 (12)
where the solution of equation ( 12) u * (m) is the most probable failure point (MPP) which is defined as the realization of the random vector U on the limit state surface closer to the origin of the standard space [START_REF] Hasofer | An exact and invariant first order reliability format[END_REF], and reliability index β (m) = u * (m) is defined as the distance of the origin of the standard space to the MPP. Notice that x * (m) is the equivalent of u * (m) in the physical space and it can be obtained applying the transformation of equation ( 11).

In the classical form, the RBDO is performed by nesting two optimization problems, the structural optimization and the reliability analysis. For instance, solve the equation for k = 1 to n it Minimize : W m k subject to :

β target ≤ β m k m k Ti ∈ R + , θ k i ∈ [-90 o , 90 o ] , i = 1 to N p (13)
where n it is the total number of iteration to solve the problem. In other words, for each step of the optimization problem k an entire reliability analysis (equation ( 12)) must be performed to compute the MPP u * m k and consequently β m k . As commented in the introduction of this paper, this leads to a high computational cost, especially if n it ends up being high, which is generally the case when we apply any global optimization method.

In order to overcome such problem, a new RBDO methodology based on safety factors derived from the first order KKT optimality conditions of the RIA is presented in the next section. Such methodology, as it is shown in the sequel, can be easily coupled with any global optimization algorithm and possesses a computational cost equivalent to that of the deterministic global optimization, since it eliminates the need of the reliability analysis. Hence, it is suitable to pursue the RBDO of laminated composite structures.

Proposed RBDO Methodology and its coupling with Global Optimization Algorithms

As the goal is to couple reliability analysis with global optimization algorithms to pursue the RBDO of laminated composite plates, a new RBDO methodology that works differently from the one described in the Section 3 is proposed here. Its main idea is to estimate the MPP of an optimal design (i.e., approximate u * or x * of m optimal ) obtained using any global optimization algorithm and, then, with this information, calculate safety factors S F to be applied to such point, obtaining the final design m reliable that guarantees the prescribed reliability level of the structure. Such methodology is described in the sequel.

First, the safety factors are deduced from the KKT optimality conditions of the RIA (equation ( 12)), which are given by [START_REF] Cheng | Sequential approximate programming strategy for reliability-based optimization[END_REF]:

       ∇ u ( u * (m) ) + λ∇ u g (m, u * (m)) = 0 λg (m, u * (m)) = 0 λ ≥ 0 g (m, u * (m)) ≤ 0 (14)
where λ is the Lagrange multiplier allowing to take into account of the restriction g (m, u) ≤ 0. We first assume u * (m) = 0 ( meaning β (m) > 0, i.e. a probability of failure less then 0.5), which does not impose any restriction on practical problems. Then, equation ( 14) can be rewritten as: where the gradient of the constraint is defined in the standard space. The Jacobian of the transformation T (•), which is defined in equation ( 11), may be used to obtain their values in the physical space, such as:

u * (m) u * (m) = -∇ug(m,u * (m)) ∇ug(m,u * (m)) g (m, u * (m)) = 0 (15)
∇ u g (m, u * (m)) = (∇ m x) T (∇ x G (m, x * (m))) ( 16
)
where ∇ m x is the Jacobian of the transformation between the two spaces.

In order to pursue the RBDO of a given structure, the maximum probability of failure of such structure or its target reliability index β target is defined. At the end of the RBDO process such reliability index must be achieved. Therefore, the optimum verify u * m reliable = β target . Substituting this relation, and equation ( 16), into equation ( 15), gives:

u * m reliable = -β target (∇ m x) T ∇ x G m reliable , x * m reliable (∇ m x) T (∇ x G (m reliable , x * (m reliable ))) (17)
Here, it is considered that the random design variables of the problem are Gaussian (in the case of other types of random variables, the procedure would be the same, only equation ( 18) would be the one corresponding to the transformation of such random variables to the standard normal space). The transformation from the physical to the standard normal space is given by:

u i = x i -m i s i (18)
where s i is the standard deviation of the i th random variable. Consider that x * i can be related to m i using safety factors by the following relation:

m i = S Fi x * i (19)
Now, substituting equation ( 18) and ( 19) into (17), leads to:

S Fi = 1 + β target s i x * i (m reliable ) (∇ m x) T ∇ x G m reliable , x * m reliable i (∇ m x) T (∇ x G (m reliable , x * (m reliable ))) (20)
where S Fi is the safety factor of the i th design variable (i = 1 to N p).

Assuming that the problem has only one constraint and considering uncertainties only on the design variables of the problem, the vector x * m reliable may be estimated by solving the deterministic optimization of the structural problem (equation ( 6)). In other words, it is assumed that x * m reliable ≈ x * m optimal Then, applying the safety factors to the vector x * m optimal (equation ( 19)), the result of the RBDO problem m reliable is obtained guaranteeing the target reliability of the structure. As it has been shown in the derivation of the safety factors, the presented methodology does not make use of the reliability analysis, reducing then the computational cost of the RBDO. Thus, the main steps for the implementation of the methodology are:

(1) Estimate the MPP on the physical space of the optimal design m optimal by solving the deterministic optimization of the structural problem (equation ( 6)). Any deterministic optimization algorithm may be employed to obtain x * m optimal making it possible to couple the RBDO methodology with any global optimization algorithm. In this paper the PSO is used to pursue this step.

(2) After a sensitivity analysis on x * m optimal , compute the safety factors S F using equation ( 20). (3) Calculate the optimal solution: the safety factors are applied to the vector

x * m optimal , using equation ( 19), finding then, the final design m reliable that guarantees the minimum allowed reliability level of the structure.

As mentioned before, the main advantage of this method would be that the computational effort is really close to the standard deterministic optimization. For instance, in the case of the evolutionary algorithm PSO, the extra computation effort to perform the RBDO is the one used in step 2 to pursue the sensitivity analysis. However, the methodology possesses some limitations such as: (i) only the design variables can be treated as random variables, (ii) in the form the methodology was presented, it is limited to one active probabilistic constraint and, (iii) it is limited to the cases where the precision of the FORM approach is enough.

Particle Swarm Optimization

The optimization algorithm PSO used in this paper is the same that have been employed in [START_REF] Lopez | Reliability Based Design Optimisation of Laminated Composite Plates[END_REF], where a convergence analysis of the deterministic optimization of laminated composite plates was performed. Such analysis showed that the PSO achieved a better performance when compared to other evolutionary algorithms such as the GA and the ACO. The basic concepts of the PSO method are presented in the sequel.

The social psychologist James Kennedy and the electrical engineer Russel Eberhart introduced the PSO (Kennedy and Eberhart 1995), as emerged from experiences with algorithms inspired in the social behaviour of some bird species.

Consider the following situation: a swarm of birds is searching for food around a delimited area. Suppose that there is just one place where food can be found and the birds do not know where it is. Then, if one bird is successful in its search, it can attract other birds, and as a result of this social behaviour, the others will also find the food. From the socio-cognitive viewpoint this means that mind and intelligence are social features. Following this principle, each individual learns (and contributes) primarily to the success of its neighbours. This fact requires the balance between exploration (the capacity of individual search) and exploitation (the capacity of learning from the neighbours).

The essence is the possibility of learning from the experience of other individuals. From the optimization viewpoint, finding the food is similar to reaching the optimum. In this sense, the adjustment between exploration (the act of travelling around a place in order to learn about it) and exploitation (taking advantage of someone else's success) is required. If there is little exploration, the birds will all converge on the first good place encountered. On the other hand, if there is little exploitation, the birds will never converge or they will try alone to find food.

As described before, the main idea of the PSO is to mimic the social behaviour of birds. This is achieved by modelling the flight of each particle by using a velocity vector, which 10 considers a contribution of the current velocity, as well as two other parts accounting for the self knowledge of the particle and of the knowledge of the swarm about the search space. This way, the velocity vector is used to update the position of each particle in the swarm [START_REF] Kennedy | Particle Swarm Optimization[END_REF].

The outline of a basic PSO algorithm is as follows:

(1) Define the PSO parameters (inertia, self trust, swarm trust, etc.).

(2) Create an initial swarm, randomly distributed throughout the design space.

(3) Update the velocity vector of each particle.

(4) Update the position vector of each particle.

(5) Go to step 3 and repeat until the stop criteria is achieved.

Optimum column design

This example will demonstrate the capabilities and shortcomings of the proposed strategy. A short column, having a rectangular cross section with dimensions b and h, is optimized in order to minimize its cross section. The column is subjected to bending moments M 1 = 250kN m and M 2 = 125kN m, and to an axial force F = 2500kN . A limit state function is written in terms of the design vector d = (b, h):

G (d) = 1 - 4M 1 bh 2 Y - 4M 2 hb 2 Y - F 2 (bhY ) 2 (21)
where Y = 40M P a is the yield stress of the column material. In this problem, uncertainties are considered on the dimensions b and h of the column. The variables have normal distributions with standart deviations of 0.03m. Thus, the RBDO problem may be stated as:

Minimize : f (m) = h • b subject to : P f (G (m, X) ≤ 0) ≤ P allowed f 0 ≤ b h/2 ≤ b/h ≤ 2 (22)
The design variables were assembled into the vector m and the RBDO of the column was pursued by three different methods: the proposed method, Classical RBDO based on RIA and PMA. The target reliability index β target of this structure is equal to 3. All the final designs, presented in Table 1, have been verified by a 10 6 sample MCS in order to compute the final and reference probability of failure.

The proposed method obtained a final structure whose reliability index matches with the target one. Although the final result obtained is different from the ones obtained by RBDO-RIA/PMA, their probability of failure, calculated using the MCS, are alike. However, the computational costs of the strategies, represented by the number of calls of the cost function (NCC), are very different. The proposed strategy, based on safety factors, only needs a few more evaluations after the deterministic optimization. The classical RBDO have to pursue the complete optimization several times.

Note that the result achieved by RBDO-RIA and RBDO-PMA was the same and its final area was smaller than the one yielded by the proposed method. It is explained by the fact that, although the deterministic optimisation pursued in the proposed method obtained a smaller area than the one of the MPP of the RBDO-RIA/PMA, when applying the safety factors, the final result ended up being higher than the safe design of the RBDO-RIA/PMA methods. In other words, the MPP of the RBDO-RIA/PMA designs is different from the one of the proposed method, resulting in different final designs. However, if the correction method is applied to the MPP of the RBDO-RIA/PMA, the same final result is obtained. This example has been evaluated for different values of the target reliability index β target . Results, presented in Table 2, show that the computational cost of the proposed method does not depend of the reliability target. Classical strategies may have their costs seriously impacted. However, the safety factor method always gives a higher final design area.

The following conclusions may be drawn from this example: (i) the reliability level of the final design provided by the proposed method is the same as the target reliability level; (ii) the numerical cost of the proposed method is much lower than the ones of the RBDO methods; (iii) although the method is able to provide a final design fulfilling the target reliability index of the structure, it may not yield the same optimum as RBDO based on RIA or PMA.

Reliable design of a plate

The case of a 2D square plate with a quarter of circle retired from a corner (see Figure 2) has been simulated by finite elements. The material is a steel with a Young modulus E = 200GP a and a yield limit stress σ Y = 200M P a. The plate is clamped in his lower boundary and loaded in his left boundary with a distributed load with a total magnitude of 800N . The design variables are the thickness of the plate h and the radius of the hole r. The plate is optimized in order to minimize its volume under the constraint of having an elastic behaviour, meaning a maximum stress below the yield limit.

G (h, r) = 1 - σ max σ Y (23)
In this case, uncertainties are considered on the dimensions h and r. These variables have normal distributions with standart deviations of s h = 0.1mm and s r = 4.0mm. The length of the border of the plate is fixed to l = 1m. Thus, the RBDO problem may be stated as:

Minimize : f (m) = l 2 -π•r 2 4 • h subject to : P f (G (m, X) ≤ 0) ≤ P allowed f 1mm ≤ m h 20mm ≤ m r ≤ 60mm (24)
A convergence study lead to a mesh with 1352 elments and 1458 nodes. Stress are evaluated on Gauss integration points. The normal stress in the s-direction is used for the evaluation of the limit state function G (h, r) (Figure 3). Starting from an initial design (h, r) = (1.50mm, 50.00mm), a SQP optimization algorithm lead to an optimal conception (h * , r * ) = (1.00mm, 48.00mm).

The reliability study has been pursued with a target reliability index β target equal to 3. All the final designs are presented in and PMA. However, the computational cost of the proposed strategy is really lower than the others (over 60%). It should be remarked that the cost reduction is very significant in this case due to the use of finite element analysis for the calculation of the limit state function.

Numerical Results of the composite study

In this section, two laminated composite RBDO problems are solved to demonstrate the effectiveness of the proposed methodology.

Tests are realised on a plate having the following dimensions : l p = 1.00m and w p = 1.00m. The numerical values of the material properties are: E 1 = 45000M P a, E 2 = 12000M P a, G 12 = 4500M P a, ν 12 = 0.3 and ρ = 1900kg/m 3 . The strength properties X T , X C , Y T , Y C and S 12 of the lamina are shown in Table 4.

Example 1 -Buckling Constraint

In this example, the weight of a laminated composite plate having as constraint the buckling failure factor has to be minimized. The laminate is subjected to compressive in-plane loads N x and N y equal to 500 N/mm and it is comprised by 12 laminas, thus, N p = 12. Due to the symmetric expression of the chosen failure mode, only half of the laminate are considered as variables. The problem is posed as:

Minimize : W (m) subject to : P f (G buckling (m, X) ≤ 0) ≤ P allowed f m Ti ∈ R + , θ i ∈ [-90 o , 90 o ] , i = 1 to Np 2 (25)
The probability of failure P f of the structure is assumed to be lower than 0.16%, which leads to β target = 3.00. Furthermore, it is assumed that the random design variables follow the normal distribution, such as T i ∼ N (m Ti , s Ti ), where s Ti = 0.02mm. Now, the first step to apply the proposed RBDO methodology is to pursue the deterministic optimization of the problem to estimate m optimal . Thus, the following problem is solved (it is equivalent to the problem of equation ( 6)):

Minimize : W (m) subject to : G buckling (m) ≤ 0 m Ti ∈ R + , θ i ∈ [-90 o , 90 o ] , i = 1 to Np 2 (26)
where m = m T1 , . . . , m T6 , θ 1 , . . . , θ 6 T . Notice that since the orientation angles are deterministic design variables, their final values are determined in this step of the method.

The optimization problem of equation ( 26) was solved using the PSO algorithm having as stopping criterion 3000 objective function evaluations and 20 individuals as population. The result of problem is shown in Table 5.

In that particular situation, the constraint (G buckling m optimal = 0) is saturated. Thus the optimal design corresponds to the most probable point of failure : x * m optimal = m optimal . Now that the MPP have been estimated, that allows to pursue the next step of the proposed RBDO methodology, which is the computation of the safety factors using equa- To accomplish that, a sensitivity analysis must be pursued at x * . Here, a finite difference method was employed leading to a cost of extra 10 function evaluations. The resulting safety factors are shown in Table 6.

In the last step, the final design m reliable of the structure is calculated applying the safety factors to m optimal using equation ( 19). The final design is shown in Table 7.

To validate the reliability constraint of the final design, a reliability analysis using the RIA and a Monte Carlo Simulation using 10 6 samples were pursued. The resulting reliability index and probability of failure were 3.01 and 0.16%, respectively, which agree with the prescribed reliability and the target reliability index of the problem. This example showed: (i) the step by step procedure to employ the proposed new RBDO methodology based on safety factors; (ii) the capability of the proposed RBDO method to take into account uncertainties on the design variables of the structure with a little extra computational effort if compared to the standard deterministic optimization (the 10 extra function evaluation of the sensitivity analysis); (iii) the validation of the proposed RBDO methodology applying the reliability analysis and the MCS to the final design m reliable .

Example 2 -Tsai-Wu Constraint

The problem proposed in this example is to minimize the weight of a laminated composite plate having as constraints the symmetry and balance of the laminate as well as the first ply failure criterion of Tsai-Wu. The laminate is subjected to in-plane loads N x = 2500N/mm and N y = -1500N/mm and it is comprised by 48 laminas whose thicknesses T i are all the same. In this example, the thickness is also considered as random variable, being its mean value one of the design variables of the optimization problem.

The symmetry and balance of the laminate were handled using a data structure strategy, which consists in coding only half of the laminate and making each stack of the laminate be composed by two laminas of the same orientation with opposite signs. It is a classical way to deal with such constraints, for instance, see [START_REF] Le Riche | Optimization of laminate stacking sequence for buckling load maximization by genetic algorithm[END_REF]Haftka 1993, Lopez et al. 2009a,b). The domain of the orientation angles becomes θ i ∈ [0 o , 90 o ]. Thus, the number of design variables is reduced to 13 and the design vector m = m T , θ 1 , . . . , θ 12 is composed by the mean thickness m T and the 12 deterministic orientation angles. The problem is posed as:

Minimize : W (m) subject to : P f (G T W (m, X) ≤ 0) ≤ P allowed f m T ∈ R + , θ i ∈ [0 o , 90 o ] , i = 1 to 12 (27)
Here again, it is assumed that the probability of failure P f of the structure has to be lower than 0.16%, which leads to β target = 3.00. Furthermore, it is assumed that the random design variable follows the normal distribution, such as T ∼ N (m T , s T ), where s T = 0.02mm.

The same three steps of the proposed RBDO methodology were employed here. In the first step, the deterministic optimization was pursued using the PSO algorithm with 3000 function evaluations as stopping criterion. The cost of the sensitivity analysis was 2 function evaluations. The result of the deterministic optimization m optimal , the safety factors S F as well as the final design m reliable using the PSO are shown in Table 8.

A 10 6 sample Monte Carlo Simulation of the final design was performed and their results indicate the reliability of the design around 99.78%, meaning a probability of From this example it can also be concluded that the coupling of the evolutionary optimization methods and the proposed methodology successfully performed the RBDO of the laminated composite plate taking into account uncertainties in the thickness of the structure.

Concluding Remarks

In this paper, the optimization of laminated composite plates was performed taking into account uncertainties in the thickness of the structure. Safety factors based on the KKT optimality conditions of RIA were proposed as RBDO methodology. The PSO method was applied as optimization tools due to its ability of handling global optimization problems. The proposed new RBDO methodology based on safety factor was employed in the optimization of laminated composite plates and validated.

The following conclusions can be drawn from the analysis pursued in the paper:

(1) The coupling of the PSO with the proposed safety factor method successfully performed the RBDO of the laminated composite plate, being the methodology validated using the Monte Carlo Simulation; (2) Such method is able to perform the RBDO of structures with a little extra computational effort than the deterministic optimization being suitable for the coupling with global optimization algorithms.

Although the mechanical model used in the numerical analysis of this paper is quite simple, the RBDO methodology can be directly extended to more complex laminated composite structures, using, for instance, the finite element method. However, the method is limited to the cases where the FORM approach can be applied, only the design variables can be treated as random variables and in the form the methodology was presented, it is limited to one active probabilistic constraint. To overcome such limitations further research has to be done.

F

  by any sequential approximation method gives:

  22%, which relatively agrees with the target reliability index imposed on the RBDO problem.

Figure 1 .

 1 Figure 1. Laminated composite plate subjected to in-plane loads.

Figure 2 .

 2 Figure 2. Reliable design of a plate.

Figure 3 .Figure 1 .

 31 Figure 3. Stress distribution (in M P a) in the plate.

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

	October 6, 2010 22:34 Engineering Optimization osf˙composites
	Engineering Optimization
	11
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 3 .

 3 The conclusions are the same as those of the previous example. The proposed safety factors method gives a worse design than RIA

	Engineering Optimization

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

Table 1 .

 1 RBDO results of the column problem

	o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 3 .

 3 Coupling safety factors method with finite element analysis

	β = 3		Safety Factor		RBDO-RIA	RBDO-PMA
			h	r	h	r	h	r
	x *		1.00	48.00	0.7563	39.87	0.7563	39.87
	m reliable		1.20	41.30	1.00	34.61	1.00	34.61
	volume	(mm 3 )	10395		9059		9059
	NCC		113		488		319
	P f	by MCS	0.00449		0.00455		0.00455
		Table 4. Lamina's strength properties
		XT	2062 MPa YC 240 MPa S21 105 MPa
		XC 1701 MPa YT	70 MPa

Table 5 .

 5 Result of the deterministic optimization problem of equation (26) (angles in degrees and thicknesses in mm)

	mT 1	mT 2	mT 3	mT 4	mT 5	mT 6	θ1	θ2	θ3	θ4	θ5	θ6
	m optimal 0.1036 0.1098 0.1106 0.1000 0.1236 0.1025 45 -45 45 -45 45 -45
		Table 6. Safety factors of example 1 computed using equa-
		tion (20) (thicknesses in mm)
		t1	t2	t3	t4	t5		t6
		SF 1.2363 1.2229 1.2213 1.2449 1.1980 1.2388
	Table 7. Final design of example 1 computed using equation (19) (angles in degrees and thicknesses
	in mm)
	mT 1	mT 2	mT 3	mT 4	mT 5	mT 6	θ1	θ2	θ3	θ4	θ5	θ6
	m reliable 0.1281 0.1343 0.1351 0.1244 0.1481 0.1270 45 -45 45 -45 45 -45

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

Table 8 .

 8 Results of the RBDO using PSO (population 20, 3000 FE, thickness in mm and angles in degrees) optimal 0.2012 2.67 0.839 0.966 0.0626 0.835 3.94 0.0952 1.60 3.23 0.913 0.0334 89.2 reliable 0.2616 2.67 0.839 0.966 0.0626 0.835 3.94 0.0952 1.60 3.23 0.913 0.0334 89.2

		mT	θ1	θ2	θ3	θ4	θ5	θ6	θ7	θ8	θ9	θ10	θ11	θ12
	m SF	1.30	-	-	-	-	-	-	-	-	-	-	-	-
	m

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk Engineering Optimization

October 6, 2010 22:34 Engineering Optimization osf˙composites