Nicolae Cîndea
email: cindea@iecn.u-nancy.fr

Sorin Micu
email: sdmicu@yahoo.com

Marius Tucsnak
email: marius.tucsnak@iecn.u-nancy.fr

An approximation method for exact controls of vibrating systems

Keywords: Mathematics Subject Classification (2000): 35L10, 65M60, 93B05, 93B40, 93D15 infinite dimensional systems, exact control, approximation, error estimate

We propose a new method for the approximation of exact controls of a second order infinite dimensional system with bounded input operator. The algorithm combines Russell's "stabilizability implies controllability" principle with the Galerkin's method. The main new feature brought in by this work consists in giving precise error estimates. In order to test the efficiency of the method, we consider two illustrative examples (with the finite element approximations of the wave and the beam equations) and we describe the corresponding simulations.

Introduction

The numerical study of the exact controls of infinite dimensional systems started in the 90's with a series of papers of Glowinski and Lions (see [START_REF] Glowinski | A numerical approach to the exact boundary controllability of the wave equation (i). dirichlet controls: Description of the numerical methods[END_REF][START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]) where algorithms to determine the minimal L 2 -norm exact controls (sometimes called HUM controls) are provided. Several abnormalities presented in these works stand at the origin of a large number of articles in which a great variety of numerical methods are presented and analyzed (see, for instance, [START_REF] Zuazua | Propagation, observation and control of waves approximated by finite difference methods[END_REF], [START_REF] Ervedoza | Uniformly exponentially stable approximations for a class of damped systems[END_REF] and the references therein). However, except the recent work [START_REF] Ervedoza | Hilbert uniqueness method and regularity: Applications to the order of convergence of discrete controls for the wave equation[END_REF], where the approximation of the HUM controls for the one dimensional wave equation is considered, to our knowledge, there are no results on the rate of convergence of the approximative controls.

The aim of this work is to provide an efficient numerical method for computing exact controls for a class of infinite dimensional systems modeling elastic vibrations. Our main theoretical result gives the rate of convergence of our approximations to an exact control. Moreover, to illustrate the efficiency of this approach, we apply it to several systems governed by PDE's and we describe the associated numerical simulations. Our methodology combines Russell's "stabilizability implies controllability" principle with error estimates for finite element type approximations of the considered infinite dimensional systems. We focus on the case of bounded input operators which excludes boundary control for systems governed by partial differential equations. However, the method can be partially extended to the unbounded input operator case, see Remark 2.7 below.

In order to give the precise statement of our results we need some notation. Let H be a Hilbert space and assume that A 0 : D(A 0 ) → H is a self-adjoint, strictly positive operator with compact resolvents. Then, according to classical results, the operator A 0 is diagonalizable with an orthonormal basis (ϕ k ) k 1 of eigenvectors and the corresponding family of positive eigenvalues (λ k ) k 1 satisfies lim k→∞ λ k = ∞. Moreover, we have

D(A 0 ) =    z ∈ H k 1 λ 2 k | z, ϕ k | 2 < ∞    , and
A 0 z = k 1 λ k z, ϕ k ϕ k (z ∈ D(A 0 )).
For α 0 the operator A α 0 is defined by

D(A α 0 ) =    z ∈ H k 1 λ 2α k | z, ϕ k | 2 < ∞    , (1.1)
and

A α 0 z = k 1 λ α k z, ϕ k ϕ k (z ∈ D(A α 0 )).
For every α 0 we denote by H α the space D(A α 0 ) endowed with the inner product

ϕ, ψ α = A α 0 ϕ, A α 0 ψ (ϕ, ψ ∈ H α ).
The induced norm is denoted by • α . From the above facts it follows that for every α 0 the operator A 0 is a unitary operator from H α+1 onto H α and A 0 is strictly positive on H α .

Let U be another Hilbert space and let B 0 ∈ L(U, H) be an input operator. Consider the system q(t) + A 0 q(t) + B 0 u(t) = 0 (t 0), (1.2) q(0) = q 0 , q(0) = q 1 .

(1.3)

The above system is said exactly controllable in time τ > 0 if for every q 0 ∈ H 1 2

, q 1 ∈ H there exists a control u ∈ L 2 ([0, τ ], U ) such that q(τ ) = q(τ ) = 0. In order to provide a numerical method to approximate such a control u, we need more assumptions and notation.

and that there exist θ > 0, h * > 0, C 0 > 0 such that, for every h ∈ (0, h * ),

π h ϕ -ϕ 1 2 ≤ C 0 h θ ϕ 1 (ϕ ∈ H 1 ), (1.4) π h ϕ -ϕ ≤ C 0 h θ ϕ 1 2 (ϕ ∈ H 1 2 ), (1.5)
where π h is the orthogonal projector from H 1 2 onto V h . Assumptions (1.4)-(1.5) are, in particular, satisfied when finite elements are used for the approximation of Sobolev spaces. The inner product in V h is the restriction of the inner product on H and it is still denoted by •, • . We define the linear operator A 0h ∈ L(V h ) by

A 0h ϕ h , ψ h = A 1 2 0 ϕ h , A 1 2 0 ψ h (ϕ h , ψ h ∈ V h ). (1.6)
The operator A 0h is clearly symmetric and strictly positive.

Denote U h = B * 0 V h ⊂ U and define the operators B 0h ∈ L(U, H) by B 0h u = π h B 0 u (u ∈ U ), (1.7)
where π h is the orthogonal projection of H onto V h . Note that Ran B 0h ⊂ V h . As wellknown, since it is a projector, the operator π h ∈ L(H) is self-adjoint. Moreover, from (1.5) we deduce that

ϕ -π h ϕ ϕ -π h ϕ C 0 h θ ϕ 1 2 (ϕ ∈ H 1 2
).

(

The adjoint

B * 0h ∈ L(H, U ) of B 0h is B * 0h ϕ = B * 0 π h ϕ (ϕ ∈ H). (1.9)
Since U h = B * 0 V h , from (1.9) it follows that Ran B * 0h = U h and that

B * 0h ϕ h , B * 0h ψ h U = B * 0 ϕ h , B * 0 ψ h U (ϕ h , ψ h ∈ V h ).
(1.10)

The above assumptions imply that, for every h * > 0, the family

B 0h L(U,H) h∈(0,h * ) is bounded.
In what follows, we give an algorithm to compute an approximation

u h ∈ C([0, τ ]; U h ) of an exact control u ∈ C([0, τ ]; U ), which drives the solution of (1.2)-(1.3) from the initial state [ q 0 q 1 ] ∈ H 1 × H 1 2
to rest in time τ . For every h > 0 and n 1 we consider the following second order ODE's :

ẅn h (t) + A 0h w n h (t) + B 0h B * 0h ẇn h (t) = 0 (t 0) (1.11) w n h (0) = π h q 0 , if n = 1 w n-1 b,h (0), if n > 1 ẇn h (0) = π h q 1 , if n = 1 ẇn-1 b,h (0), if n > 1, (1.12) and ẅn b,h (t) + A 0h w n b,h (t) -B 0h B * 0h ẇn b,h (t) = 0 (t τ ) (1.13) w n b,h (τ ) = w n h (τ ), ẇn b,h (τ ) = ẇn h (τ ). (1.14)
For every h > 0 we appropriately choose N (h) ∈ N (see Theorem 1.1 below) and we define

w 0h w 1h = π h q 0 π h q 1 + N (h) n=1 w n b,h (0) ẇn b,h (0) (1.15)
With this notation, u h is defined by

u h = B * 0h ẇh + B * 0h ẇb,h , (1.16)
where w h and w b,h are the solution of

ẅh (t) + A 0h w h (t) + B 0h B * 0h ẇh (t) = 0 (t 0) (1.17) w h (0) = w 0h , ẇh (0) = w 1h , (1.18) ẅb,h (t) + A 0h w b,h (t) -B 0h B * 0h ẇb,h (t) = 0 (t τ ) (1.19) w b,h (τ ) = w h (τ ), ẇb,h (τ ) = ẇh (τ ). (1.20)
We can now formulate the main result of this paper.

Theorem 1.1. With the above notation and assumptions, assume furthermore that the system (1.2), (1.3) is exactly controllable in some time τ > 0 and that

B 0 B * 0 ∈ L(H 1 , H 1 2
). Then there exists a constant m τ > 0 such that the sequence (u h ) h 0 of C([0, τ ]; U h ) defined in (1.16) with N (h) = θ m τ ln(h -1 ) , converges when h → 0 to an exact control in time τ of (1.2), (1.3), denoted by u, for every

Q 0 = [ q 0 q 1 ] ∈ H 3 2 × H 1 .
Moreover, there exist constants h * > 0 and C := C τ such that we have

u -u h C([0,τ ];U ) Ch θ ln 2 (h -1 ) Q 0 H 3 2 ×H 1 (0 < h < h * ).
(

We prove this theorem in Section 4. In the second section we recall some background on exact controllability and stabilizability. Section 3 provides some error estimates. In Section 5 we apply our results to the wave equation in two space dimensions and to the Euler-Bernoulli beam equation, providing numerical simulations.

Some background on exact controllability and uniform stabilization

In this section we recall, with no claim of originality, some background concerning the exact controllability and uniform stabilizability of the system (1.2), (1.3). We give, in particular, a short proof, adapted to our case, of Russell's "stabilizability implies controllability" principle. This principle has been originally stated in Russell [START_REF] Russell | Exact boundary value controllability theorems for wave and heat processes in star-complemented regions[END_REF][START_REF]Controllability and stabilizability theory for linear partial differential equations: recent progress and open questions[END_REF] (see also Chen [4]).

Consider the second order differential equation

ẅ(t) + A 0 w(t) + B 0 B * 0 ẇ(t) = 0 (t 0), (2.1)
w(0) = w 0 , ẇ(0) = w 1 . (2.2)
It is well known that the above equation defines a well posed dynamical system in the state space X = H 1 2 × H. More precisely, the solution [ w ẇ ] of (2.1), (2.2) is given by

w(t) ẇ(t) = T t w 0 w 1 w 0 w 1 ∈ X, t 0 , (2.3)
where T is the contraction semigroup on X generated by A -BB * and A : D(A) → X, B ∈ L(U, X) are defined by

D(A) = H 1 × H 1 2 , A = 0 I -A 0 0 , B = 0 B 0 .
We also consider the backwards system

ẅb (t) + A 0 w b (t) -B 0 B * 0 ẇb (t) = 0 (t τ ), (2.4
)

w b (τ ) = w(τ ), ẇb (τ ) = ẇ(τ ). (2.5)
It is not difficult to check that the solution w b ẇb of (2.4), (2.5) is given by

w b (t) ẇb (t) = S τ -t w(τ ) ẇ(τ ) (t ∈ [0, τ ]), (2.6)
where S is the contraction semigroup in X generated by -A -BB * .

We define L τ ∈ L(X) by

L τ w 0 w 1 = w b (0) ẇb (0) w 0 w 1 ∈ X . (2.7)
With the above notation, the operator L τ clearly satisfies L τ = S τ T τ .

Proposition 2.1. With the above notation, assume that the system (1.2), (1.3) is exactly controllable in some time τ > 0. Then the semigroups T and S are exponentially stable and we have T τ L(X) < 1 and S τ L(X) < 1. Moreover, the operator I -L τ is invertible and we have

(I -L τ ) -1 = n 0 L n τ .
(2.8)

Proof. The fact that T and S are exponentially stable is well-known (see, for instance, Haraux [START_REF] Haraux | Une remarque sur la stabilisation de certains systèmes du deuxième ordre en temps[END_REF] and Liu [START_REF] Liu | Locally distributed control and damping for the conservative systems[END_REF]). The more precise facts that T τ L(X) < 1 and S τ L(X) < 1 are easy to establish (see, for instance, Lemma 2.2 in Ito, Ramdani and Tucsnak [START_REF] Ito | A time reversal based algorithm for solving initial data inverse problems[END_REF]). Finally, (2.8) follows from L τ L(X) < 1.

The particular case of Russell's principle [START_REF]Controllability and stabilizability theory for linear partial differential equations: recent progress and open questions[END_REF], which we need in this work, is given by the following result:

Proposition 2.2. Assume that (1.2), (1.3) is exactly controllable in time τ > 0. Then a control u ∈ C([0, τ ]; U ) for (1.2), (1.3) steering the initial state [ q 0 q 1 ] ∈ X to rest in time τ is given by u = B * 0 ẇ + B * 0 ẇb , (2.9)
where w and w b are the solutions of (2.1)-(2.2) and (2.4)-(2.5) respectively, with

w 0 w 1 = (I -L τ ) -1 q 0 q 1 .
(2.10)

Remark 2.3. The original assumption of Russell's principle was essentially the exponential stability of the semigroups T and S, whence the name "stabilizability implies controllability". Since, according to Proposition 2.1, these stability properties are equivalent to the exact controllability of (1.2), (1.3), we made this assumption explicitly in Proposition 2.2. The essential thing retained from the original Russell's principle is the specific form (2.9) of u, obtained using the "closed loop semigroups" T and S.

Proof of Proposition 2.2. Denote

q(t) = w(t) -w b (t) (t ∈ [0, τ ]).
Then q clearly satisfies (1.2) with u given by (2.9). Moreover, from (2.10) it follows that q satisfies the initial conditions (1.3). Finally, from (2.5) it follows that q(τ ) = q(τ ) = 0.

Remark 2.4. Using the semigroup notation, an alternative way of writing (2.9) is

u(t) = B * T t w 0 w 1 + B * S τ -t T τ w 0 w 1 (t ∈ [0, τ ]), (2.11)
where w 0 , w 1 satisfy (2.10).

We need below the fact that the restrictions of T and S to

H 1 × H 1 2 and H 3 2
× H 1 are exponentially stable semigroups. Sufficient conditions for this are given in the result below.

Proposition 2.5. Assume that B 0 B * 0 ∈ L(H 1 , H 1 2
). Then the restrictions of T and S to

H 1 × H 1 2 and H 3 2
× H 1 are contraction semigroups on these spaces with generators the restrictions of A -BB * and -A -BB * to H

3 2 × H 1 and H 2 × H 3 2 respectively. Moreover, if (1.2), (1.3) is exactly controllable in time τ > 0 then T τ L(H 3 2 ×H 1 ) < 1, S τ L(H 3 2 ×H 1 ) < 1.
(2.12)

Proof. From a well-known result (see, for instance, [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF]Proposition 2.10.4]) it follows that the restriction of

T to D(A -BB * ) = H 1 × H 1 2
is a contraction semigroup on D(A -BB * ) (endowed with the graph norm) whose generator is the restriction of

A -BB * to D((A - BB * ) 2 ). Since B 0 B * 0 ∈ L(H 1 , H 1 2 ), it is easy to check that D((A -BB * ) 2 ) = H 3 2 × H 1 .
It follows that indeed the restriction of T to

H 1 × H 1 2
is a contraction semigroup on this space with generator the restriction of A -BB * to H 3 2 × H 1 . The second assertion on T can be easily obtained by iterating this argument. The corresponding assertions for S can be proved in a completely similar manner. Finally, the estimates (2.12) follow from the corresponding estimates for the norms in L(H 1 × H 1 2 ) (see Proposition 2.1) by applying again Proposition 2.10.4 in [START_REF] Tucsnak | Observation and control for operator semigroups[END_REF].

Remark 2.6. An important property of the control u constructed in (1.16) is that, under appropriate assumptions on B 0 , its regularity increases when the initial data are more regular. For instance, if

B 0 B * 0 ∈ L(H 1 , H 1 2
) and

[ q 0 q 1 ] ∈ H 3 2
× H 1 then, by Proposition 2.5,

[ w 0 w 1 ] = (I -L τ ) -1 [ q 0 q 1 ] ∈ H 3 2 × H 1 so that u ∈ C 1 ([0, τ ]; U ) and B 0 u ∈ C([0, τ ]; H 1 2
).

Remark 2.7. Russell's principle can be extended to the the case of unbounded input operators

B 0 ∈ L(U, H - 1 2
), where

H -1 2 is the dual of H 1 2
with respect to the pivot space H. In this case the system (2.1)-(2.2) is still well-posed and it keeps most of the properties holding for bounded B 0 (see, for instance, [START_REF] Weiss | How to get a conservative well-posed linear system out of thin air. Part I: Well-posedness and energy balance[END_REF], [START_REF] Tucsnak | How to get a conservative well-posed linear system out of thin air. Part II: Controllability and stability[END_REF] and references therein). For a quite general form of Russell's principle for unbounded input operators we refer to [START_REF] Rebarber | An extension of Russell's principle on exact controllability[END_REF].

An approximation result

The aim of this section is to provide error estimates for the approximations of (2.1) by finite-dimensional systems. Using the notation in Section 1 for the families of spaces (V h ) h>0 , (U h ) h>0 and the families of operators (π h ) h>0 , (A 0h ) h>0 , (B 0h ) h>0 , we consider the family of finite dimensional systems

ẅh (t) + A 0h w h (t) + B 0h B * 0h ẇh (t) = 0, (3.1)
w h (0) = π h w 0 , ẇh (0) = π h w 1 . (3.2)
In the case in which B 0 = 0 and A 0 is the Dirichlet Laplacian, it has been shown in Baker [START_REF] Baker | Error estimates for finite element methods for second order hyperbolic equations[END_REF] that, given w 0 ∈ H 3

2

, w 1 ∈ H 1 , the solutions of (3.1) converge when h → 0 to the solution of (2.1). Moreover, [START_REF] Baker | Error estimates for finite element methods for second order hyperbolic equations[END_REF] contains precise estimates of the convergence rate. The result below shows that the same error estimates hold when A 0 is an arbitrary positive operator and B 0 = 0. Throughout this section we assume that

B 0 B * 0 ∈ L(H 1 , H 1 2
).

Proposition 3.1. Let w 0 ∈ H 3 2
, w 1 ∈ H 1 and let w, w h be the corresponding solutions of (2.1), (2.2) and (3.1), (3.2). Moreover, assume that

B 0 B * 0 ∈ L(H 1 , H 1 2
). Then there exist three constants K 0 , K 1 , h * > 0 such that, for every h ∈ (0, h * ), we have

ẇ(t) -ẇh (t) + w(t) -w h (t) 1 2 (K 0 + K 1 t)h θ w 0 3 2 + w 1 1 (t 0). (3.3)
Proof. We first note that, according to Proposition 2.5, we have

w ∈ C([0, ∞); H 3 2 ) ∩ C 1 ([0, ∞); H 1 ) ∩ C 2 ([0, ∞); H 1 2 ), ẅ(t) 1 2 + ẇ(t) 1 + w(t) 3 2 w 1 1 + w 0 3 2 (t 0). (3.4) Equation (2.1) can be written ẅ, v + A 1 2 0 w, A 1 2 0 v + B * 0 ẇ, B * 0 v U = 0 (v ∈ H 1 2
), whereas, using (1.6) and (1.10), we see that (3.1) is equivalent to

ẅh , v h + A 1 2 0 w h , A 1 2 0 v h + B * 0 ẇh , B * 0 v h U = 0 (v h ∈ V h ).
Taking v = v h in the first one of the above relations and subtracting side by side it follows that

ẅ -ẅh , v h + A 1 2 0 (w -w h ), A 1 2 0 v h + B * 0 ẇ -B * 0 ẇh , B * 0 v h U = 0 (v h ∈ V h ),
which yields (recall that π h is the orthogonal projector from

H 1 2 onto V h ) that π h ẅ -ẅh , v h + A 1 2 0 (π h w -w h ), A 1 2 0 v h = π h ẅ -ẅ, v h -B * 0 ẇ -B * 0 ẇh , B * 0 v h U (v h ∈ V h ). (3.5)
We set

E h (t) = 1 2 π h ẇ -ẇh 2 + 1 2 A 1 2 0 (π h w -w h ) 2 .
Using (3.5) it follows that

Ėh (t) = π h ẅ -ẅ, π h ẇ -ẇh -B * 0 ( ẇ -ẇh ), B * 0 (π h ẇ -ẇh ) U = π h ẅ -ẅ, π h ẇ -ẇh -B * 0 (π h ẇ -ẇh ) 2 U + B 0 B * 0 (π h ẇ -ẇ), (π h ẇ -ẇh ) .
We have thus shown that

Ėh (t) M ( π h ẅ -ẅ + π h ẇ -ẇ ) π h ẇ -ẇh , where M = 1 + B 0 B * 0 . It follows that 2 E 1 2 h (t) d dt E 1 2 h (t) M √ 2 ( π h ẅ -ẅ + π h ẇ -ẇ ) E 1 2 h (t),
which yields

E 1 2 h (t) E 1 2 h (0) + M √ 2 t 0 ( π h ẅ -ẅ + π h ẇ -ẇ ) dt (t 0).
The above estimate, combined with (3.4), to the fact that E h (0) = 0 and to (1.5), implies that there exist two constants K, h * > 0 such that, for every h ∈ (0, h * ), we have

E 1 2 h (t) t Kh θ w 0 3 2 + w 1 1 dt (t 0). (3.6)
On the other hand, using (3.4), combined with (1.4) and (1.5), we have that there exists a constant h * > 0 such that, for every h ∈ (0, h * ),

ẇ(t) -ẇh (t) ẇ(t) -π h ẇ(t) + π h ẇ(t) -ẇh (t) K h θ w 0 3 2 + w 1 1 + E 1 2 h (t) , w(t) -w h (t) 1 2 w(t) -π h w(t) 1 2 + π h w(t) -w h (t) 1 2 K h θ w 0 3 2 + w 1 1 + E 1 2 h (t) ,
for some constant K > 0. The last two inequalities, combined to (3.6) yield the conclusion (3.3).

For h > 0 we denote X h = V h × V h and we consider the operators

A h = 0 I -A 0h 0 , B h = 0 B 0h . (3.7)
The discrete analogues of the semigroups T, S and of the operator L t , denoted by T h , S h and L h,t respectively, are defined, for every h > 0, by

T h,t = e t(A h -B h B * h ) , S h,t = e t(-A h -B h B * h ) , L h,t = S h,t T h,t (t 0). (3.8)
For every h > 0 we define Π h ∈ L(H

1 2 × H 1 2 , X h ) by Π h = π h 0 0 π h . (3.9)
The following two results are consequences of Proposition 3.1.

Corollary 3.2.

There exist two constants C 1 , h * > 0 such that, for every h ∈ (0, h * ) and t > 0, we have (recall that L t = S t T t for every t 0):

Π h T t Z 0 -T h,t Π h Z 0 X C 1 th θ Z 0 H 3 2 ×H 1 (Z 0 ∈ H 3 2 × H 1 ), (3.10)
Π h S t Z 0 -S h,t Π h Z 0 X C 1 th θ Z 0 H 3 2 ×H 1 (Z 0 ∈ H 3 2 × H 1 ), (3.11)
Π h L t Z 0 -L h,t Π h Z 0 X C 1 th θ Z 0 H 3 2 ×H 1 (Z 0 ∈ H 3 2 × H 1 ). (3.12)
Proof. The estimate (3.10) is nothing else but (3.6) rewritten in semigroup terms. To prove (3.11), it suffices to notice that P S t = T t P where

P w 0 w 1 = w 0 -w 1 w 0 w 1 ∈ X .
Finally, estimate (3.12) can be easily obtained from (3.10) and (3.11).

Corollary 3.3. There exist three constants C 0 , C 1 , h * > 0 such that, for every t > 0, h ∈ (0, h * ) and k ∈ N we have

L k t Z 0 -L k h,t Π h Z 0 X (C 0 + kC 1 t)h θ Z 0 H 3 2 ×H 1 (Z 0 ∈ H 3 2 × H 1 ).
Proof. We have

L k t Z 0 -L k h,t Π h Z 0 X L k t Z 0 -Π h L k t Z 0 X + Π h L k t Z 0 -L k h,t Π h Z 0 X . (3.13)
From Proposition 2.5 it follows that, for every t 0, H 3 2 × H 1 is an invariant space for L t . Using this fact combined to (1.4) and (1.5) we obtain that there exists a constant C 0 > 0 such that the first term of the right-hand side of the above inequality satisfies

L k t Z 0 -Π h L k t Z 0 X C 0 h θ Z 0 H 3 2 ×H 1 . (3.14)
For the second term of the right-hand side in (3.13) we have

Π h L k t Z 0 -L k h,t Π h Z 0 X Π h L k t Z 0 -L h,t Π h L k-1 t Z 0 X + L h,t Π h L k-1 t Z 0 -L k h,t Π h Z 0 X = Π h L t (L k-1 t Z 0 ) -L h,t Π h L k-1 t Z 0 X + L h,t (Π h L k-1 t Z 0 -L k-1 h,t Π h Z 0 ) X .
Applying (3.12), we obtain

Π h L k t Z 0 -L k h,t Π h Z 0 X C 1 th θ Z 0 H 3 2 ×H 1 + Π h L k-1 t Z 0 -L k-1 h,t Π h Z 0 X .

By an obvious induction argument it follows that

Π h L k t Z 0 -L k h,t Π h Z 0 X C 1 tkh θ Z 0 H 3 2 ×H 1 (Z 0 ∈ H 3 2 × H 1 ). (3.15)
Finally, combining (3.13)-(3.15), we obtain the conclusion of the corollary.

Proof of the main result

In this section we continue to use the notation from (3.7)-(3.9) for A h , B h , T h , S h , L h and Π h . We first give the following result:

Lemma 4.1. Suppose that the system (1.2), (1.3) is exactly controllable in time τ > 0 and that

B 0 B * 0 ∈ L(H 1 , H 1 2 ). Let Q 0 = [ q 0 q 1 ] ∈ H 3 2
× H 1 and let u be the control given by (2.11), where W 0 = [ w 0

w 1 ] is given by (2.10). Let v h : [0, τ ] → U h be defined by

v h (t) = B * h T h,t Π h W 0 + B * h S h,τ -t T h,τ Π h W 0 (t ∈ [0, τ ]). (4.1)
Then there exist three constants C 2 , C 3 , h * > 0 such that, for every h ∈ (0, h * ), we have

(u -v h )(t) U C 2 + tC 3 1 -L τ L(H 3 2 ×H 1 ) h θ Q 0 H 3 2 ×H 1 (t ∈ [0, τ ]). (4.2)
Proof. We first note that from Proposition 2.5 and the fact that

Q 0 ∈ H 3 2
× H 1 it follows that W 0 given by (2.10) still belongs to H 3 2 × H 1 . Using (2.11), (4.1), (1.9) and (3.7) we see that for every t ∈ [0, τ ] we have :

(u -v h )(t) U = B * T t W 0 + B * S τ -t T τ W 0 -B * h T h,t Π h W 0 -B * h S h,τ -t T h,τ Π h W 0 U B * T t W 0 -0 B * 0h T t W 0 U + 0 B * 0h (T t W 0 -T h,t Π h W 0 ) U + B * S τ -t T τ W 0 -0 B * 0h S τ -t T τ W 0 U + 0 B * 0h (S τ -t T τ W 0 -S h,τ -t T h,τ Π h W 0 ) U . (4.3)
Let h * > 0 be chosen like in Proposition 3.1. To bound the first term in the right hand side of (4.3) we note that since B * = 0 B * 0 and B * 0h = B * 0 π h we have that

B * T t W 0 -0 B * 0h T t W 0 U = B * 0 ( ẇ(t) -π h ẇ(t)) U B * 0 L(H,U ) ẇ(t) -π h ẇ(t) ,
where we have denoted T t W 0 = w(t) ẇ(t) . Using next (1.8) and Proposition 2.5 we obtain that there exists a constant C 0 > 0 such that

B * T t W 0 -0 B * 0h T t W 0 U C 0 h θ ẇ(t) 1 2 C 0 h θ W 0 H 3 2 ×H 1 . (4.4)
Similarly we show that the third term in the right hand side of (4.3) satisfies

B * S τ -t T τ W 0 -0 B * 0h S τ -t T τ W 0 U C 0 h θ W 0 H 3 2 ×H 1 . (4.5)
To bound the second term in the right hand side of (4.3) we use the uniform boundedness of the family of operators (B * 0h ) h∈(0,h * ) in L(H, U ) and Proposition 3.

1 to get 0 B * 0h (T t W 0 -T h,t Π h W 0 ) U (K 0 + K 1 t)h θ W 0 H 3 2 ×H 1 . (4.6)
The forth term in the right hand side of (4.3) can be estimated similarly to get

0 B * 0h (S τ -t T τ W 0 -S h,τ -t T h,τ Π h W 0 ) U (K 0 + K 1 t)h θ W 0 H 3 2 ×H 1 . (4.7) Using (4.4)-(4.7), relation (4.3) yields (u -v h )(t) U (C 2 + tC 3 )h θ W 0 H 3 2 ×H 1 ,
for some constants C 2 , C 3 > 0 and h ∈ (0, h * ). Using in the above estimate the fact, following from Proposition 2.5 and (2.10), that

W 0 H 3 2 ×H 1 1 1 -L τ L(H 3 2 ×H 1 ) Q 0 H 3 2 ×H 1 ,
we obtain the conclusion of this lemma.

We are now in a position to prove the main result of this work.

Proof of Theorem 1.1. Using the semigroup notation introduced in Section 2 we can write u h given by (1.16) as

u h (t) = B * h T h,t w 0h w 1h + B * h S h,τ -t T h,τ w 0h w 1h (t ∈ [0, τ ]), (4.8)
where

w 0h w 1h = N (h) n=0 L n h,τ Π h q 0 q 1 . (4.9) Since u -u h L 2 ([0,τ ],U ) u -v h L 2 ([0,τ ],U ) + v h -u h L 2 ([0,τ ],U ) , (4.10)
it suffices to evaluate the two terms from the right, where v h is given by (4.1).

To estimate the second term in the right-hand side of (4.10) we first note that

(v h -u h )(t) = B * h T h,t Π h W 0 + B * h S h,τ -t T h,τ Π h W 0 -B * h T h,t Π h w 0h w 1h -B * h S h,τ -t T h,τ Π h w 0h w 1h .
It follows that there exists a positive constant C with

(v h -u h )(t) U B * h T h,t Π h W 0 -B * h T h,t Π h w 0h w 1h U + B * h S h,τ -t T h,τ Π h W 0 -B * h S h,τ -t T h,τ Π h w 0h w 1h U C W 0 - w 0h w 1h X = C ∞ n=0 L n τ Q 0 - N (h) n=0 L n h,τ Π h Q 0 X C ∞ n=N (h)+1 L τ n L(X) Q 0 X + C N (h) n=0 (L n τ -L n h,τ Π h )Q 0 X .
The above estimate and Corollary 3.3 imply that there exists C > 0 such that

(v h -u h )(t) U C L τ N (h)+1 L(X) 1 -L τ L(X) Q 0 X + Ch θ N n=0 (C 0 + nC 1 τ ) Q 0 H 3 2 ×H 1 = C L τ N (h)+1 L(X) 1 -L τ L(X) Q 0 X + CN 2 (h)(1 + τ )h θ Q 0 H 3 2 ×H 1 C(1 + τ ) 1 -L τ L(X) L τ N (h) L(X) + N 2 (h)h θ Q 0 H 3 2 ×H 1 , By choosing N (h) = θ ln( Lτ L(X) ) ln(h) we deduce that (v h -u h )(t) U C(1 + τ ) (1 -L τ L(X) ) ln 2 ( L τ -1 L(X) ) ln 2 (h -1 ) h θ Q 0 H 3 2 ×H 1 .
Combining this last estimate with (4.2) and taking m τ = 1 ln( Lτ -1 L(X) ) we obtain the conclusion (1.21).

Remark 4.2. The functions u h given by (1.16) or v h from (4.1) should not be confused with the exact control ζ h , obtained by applying Russell's principle to the finite-dimensional system qh (t) + A 0h q h (t) + B 0h u = 0, (

q h (0) = π h q 0 , qh (0) = π h q 1 . 4.11)
Indeed, this control ζ h is given by the formula

ζ h (t) = B * h T h,t Z h0 + B * h S h,τ -t T h,τ Z h0 , Z h0 = (I -L h,τ ) -1 Π h [ q 0 q 1 ] , (4.13)
so that u h is obtained by "filtering" (in an appropriate sense) ζ h . Note that, since T h and S h are not, in general, uniformly exponentially stable (with respect to h), the control ζ h does not, in general, converge to u (see, for instance, [START_REF] Zuazua | Propagation, observation and control of waves approximated by finite difference methods[END_REF]).

Examples and numerical results

In this section we apply our numerical method to approximate exact controls for the two dimensional wave equation and for the Euler-Bernoulli beam equation. For both examples we consider distributed controls.

The wave equation

In this subsection we consider the approximation of an internal distributed exact control for the wave equation with homogeneous Dirichlet boundary condition.

Let Ω ⊂ R 2 be an open connected set with boundary of class C 2 or let Ω be a rectangular domain. Let O ⊂ Ω, O = Ω be an open set. We consider the control problem q(x, t) -∆q(x, t)

+ χ O (x)u(x, t) = 0, (x, t) ∈ Ω × [0, τ ] (5.1) q(x, t) = 0, (x, t) ∈ ∂Ω × [0, τ ] (5.2)
q(x, 0) = q 0 (x), q(x, 0) = q 1 (x), x ∈ Ω, (

where

χ O ∈ D(Ω) is such that χ O (x) = 1 for x ∈ O and χ O (x) 0 for x ∈ Ω.
In order to apply the method described in (1.11)- (1.20) to this case we need appropriate choices of spaces and operators. We take H = L 2 (Ω), U = H and A 0 :

D(A 0 ) → H with D(A 0 ) = H 2 (Ω) ∩ H 1 0 (Ω), A 0 ϕ = -∆ϕ (ϕ ∈ D(A 0 )),
where we use the notation H m (Ω), with m ∈ N, for the standard Sobolev spaces. It is well known that A 0 is a self-adjoint, strictly positive operator with compact resolvents. The corresponding spaces H 3

2

, H 1 and H 1 2 introduced in Section 1 are in this case given by

H 3 2 = ϕ ∈ H 3 (Ω) ∩ H 1 0 (Ω) | ∆ϕ = 0 on ∂Ω , H 1 = H 2 (Ω) ∩ H 1 0 (Ω), H 1 2 = H 1 0 (Ω).
The control operator B 0 ∈ L(H) is defined by

B 0 u = χ O u (u ∈ H).
The operator B 0 is clearly self-adjoint and

B 0 B * 0 ∈ L(H 1 , H 1 2
). Moreover, we assume that τ and O are such that the system (5.1)-(5.3) is exactly controllable in time τ , i.e., that for every [

q 0 q 1 ] ∈ H 1 0 (Ω) × L 2 (Ω) there exists a control u ∈ L 2 ([0, τ ], U
) such that q(τ ) = q(τ ) = 0. Sufficient conditions in which this assumption holds are give in various works, see Lions [START_REF] Lions | Contrôlabilité exacte, perturbations et stabilisation de systèmes distribués[END_REF], Bardos, Lebeau and Rauch [START_REF] Bardos | Sharp sufficient conditions for the observation, control, and stabilization of waves from the boundary[END_REF], Liu [START_REF] Liu | Locally distributed control and damping for the conservative systems[END_REF].

To construct an approximating family of spaces (V h ) h>0 we consider a quasi-uniform triangulation T h of Ω of diameter h, as defined, for instance, in [3, p.106]. For each h > 0 we define V h by

V h = ϕ ∈ C(Ω) ϕ |T ∈ P 1 (T ) for every T ∈ T h , ϕ |∂Ω = 0 ,
where P 1 (T ) is the set of affine functions on T . It is well-known (see, for instance, [13, p.96-97]) that the orthogonal projector π h from H 1 2 = H 1 0 (Ω) onto V h satisfies (1.4) and (1.5) for θ = 1.

We define

U h = {χ O v h |v h ∈ V h } ⊂ U and let B 0h ∈ L(H) be given by B 0h ϕ = π h (χ O ϕ) for every ϕ ∈ H. Note that B * 0h ϕ h = χ O ϕ h and B 0h B * 0h ϕ h , ψ h = χ 2 O ϕ h , ψ h for every ϕ h , ψ h ∈ V h , where •, • denotes the inner product in L 2 (Ω).
With the above choice of spaces and operators, denoting by N (h) = θ ln Lτ ln h , the first part of the general method described in (1.11)-(1.20) reduces to the computation of the families of functions (w n h )

1 n N (h) , (w n b,h ) 1 n N (h) satisfying, for every v h ∈ V h , ẅn h (t), v h + ∇w n h (t), ∇v h + χ 2 O ẇn h (t), v h = 0 (t ∈ [0, τ ]) (5.4) w n h (0) = π h q 0 , if n = 1 w n-1 b,h (0), if n > 1 ẇn h (0) = π h q 1 , if n = 1 ẇn-1 b,h (0), if n > 1, (5.5)
and ẅn b,h (t),

v h + ∇w n b,h (t), ∇v h -χ 2 O ẇn b,h (t), v h = 0 (t ∈ [0, τ ]) (5.6)
w n b,h (τ ) = w n h (τ ), ẇn b,h (τ ) = ẇn h (τ ).

(5.7)

The second part of the method described in (1.11)- (1.20) reduces to the computation of w 0h and w 1h defined by

w 0h w 1h = π h q 0 π h q 1 + N (h) n=1 w n b,h (0) ẇn b,h (0)
.

(5.8)

Finally, the approximation u h of the exact control u is given by

u h = χ O ẇh + χ O ẇb,h , (5.9)
where w h and w b,h are the solution of

ẅh (t), v h + ∇w h (t), ∇v h + χ 2 O ẇh (t), v h = 0 (v h ∈ V h , t ∈ [0, τ ]) (5.10) w h (0) = w 0h , ẇh (0) = w 1h (5.11) ẅb,h (t), v h + ∇w b,h (t), ∇v h -χ 2 O ẇb,h (t), v h = 0 (v h ∈ V h , t ∈ [0, τ ]) (5.12)
w b,h (τ ) = w h (τ ), ẇb,h (τ ) = ẇh (τ ).

(5.13) Since we checked above all the necessary assumptions, we can apply Theorem 1.1 to obtain that (u h ) converges in C([0, τ ]; L 2 (Ω)) to an exact control u such that

u -u h C([0,τ ];L 2 (Ω)) Ch ln 2 (h -1 )( q 0 H 3 (Ω) + q 1 H 2 (Ω) ) (0 < h < h * ). (5.14)
for some constants h * , C > 0.

The efficiency of the algorithm has been tested in the case Ω = [0, 1] 2 and O = [(x 1 , x 2 ) × (0, 1)] ∪ [(0, 1) × (y 1 , y 2 )], where x 1 , x 2 , y 1 , y 2 ∈ (0, 1) are such that x 1 < x 2 and y 1 < y 2 . The initial data that we want to steer to zero are the "bubble" functions q 0 (x, y) = q 1 (x, y) = x 3 y 3 (1x) 3 (1y) 3 and the control time is

τ = 2 √ 2. Note that [ q 0 q 1 ] ∈ H 3 2 × H 1 2
. We use 60 points of discretization in each space direction. For the time discretization we used a classical centered-difference implicit scheme and the CFL number is α = 1/20.

Figure 1 shows the norm decay of the solution of the discretized wave equation coresponding to (5.1)-(5.3), with a control u h given by (1.16).

The Euler-Bernoulli beam equation

This subsection is dedicated to the problem of the approximation of an internal distributed exact control for the Euler-Bernoulli beam equation.

Let Ω = (0, 1) and let O ⊂ Ω be an open and nonempty interval included in Ω. We consider the following problem q(x, t) +

∂ 4 q ∂x 4 (x, t) + χ O (x)u(x, t) = 0, (x, t) ∈ Ω × [0, τ ] (5.15) q(0, t) = ∂ 2 q ∂x 2 (0, t) = q(1, t) = ∂ 2 q ∂x 2 (1, t) = 0, t ∈ [0, τ ] (5.16)
q(x, 0) = q 0 (x), q(x, 0) = q 1 (x), x ∈ Ω, (5.17 Norm of q(t) and q(t)

q(t) H 1 (Ω) q(t) L 2 (Ω)
Figure 1: The norms of the solution of the controlled wave equation with the control u h given by (1.16). In continuous line is the norm H 1 0 of q(t) and in dashed line the norm L 2 of q(t). In order to apply the method described in this paper we need to choose appropriate spaces and operators. Let H = L 2 (Ω), U = H and consider the operator A 0 : D(A 0 ) → H, defined by

D(A 0 ) = ϕ ∈ H 4 (Ω) | ϕ(0) = d 2 ϕ dx 2 (0) = ϕ(1) = d 2 ϕ dx 2 (1) = 0 , A 0 ϕ = d 4 ϕ dx 4 (ϕ ∈ D(A 0 )).
It is well known that A 0 is a self-adjoint, strictly positive operator with compact resolvents. The corresponding spaces H 3

2

, H 1 and H 1 2 introduced in Section 1 are now given by

H 3 2 = ϕ ∈ H 6 (Ω) | ϕ(0) = ϕ(1) = d 2 ϕ dx 2 (0) = d 2 ϕ dx 2 (1) = d 4 ϕ dx 4 (0) = d 4 ϕ dx 4 (1) = 0 , H 1 = ϕ ∈ H 4 (Ω) | ϕ(0) = d 2 ϕ dx 2 (0) = ϕ(1) = d 2 ϕ dx 2 (1) = 0 , H 1 2 = H 2 (Ω) ∩ H 1 0 (Ω).
As in the case of the wave equation the control operator

B 0 ∈ L(H) is defined by B 0 u = χ O u for every u ∈ H. Clearly B 0 is self-adjoint and B 0 ∈ L(H 1 , H 1 2
).

To construct an approximating family of spaces (V h ) h>0 we consider an uniform discretization I h of the interval (0, 1) formed by N points and h = 1/(N -1). For each h > 0 we define V h by

V h = {ϕ ∈ C 1 ([0, 1]) | ϕ |I ∈ P 3 (T ) for every I ∈ I h , ϕ(0) = ϕ(1) = 0},
where P 3 (I) is the set of polynomial functions of degree 3 on I. Note that V h is the cubic Hermite finite element space. Denoting by π h the orthogonal projector from H w n b,h (τ ) = w n h (τ ), ẇn b,h (τ ) = ẇn h (τ ).

(5.21)

The second part of the method described in (1.11)-(1.20) reduces to the computation of w 0h and w 1h defined by

w 0h w 1h = π h q 0 π h q 1 + N (h) n=1
w n b,h (0) ẇn b,h (0) .

(5.22)

Finally, the approximation u h of the exact control u is given by w b,h (τ ) = w h (τ ), ẇb,h (τ ) = ẇh (τ ).

u h = χ O ẇh + χ O ẇb,h , (5.23
(5.27)

From Theorem 1.1 we obtain that (u h ) converges in C([0, τ ]; L 2 (Ω)) to an exact control u such that uu h C([0,τ ];L 2 (Ω)) Ch 2 ln 2 (h -1 )( q 0 H 6 (Ω) + q 1 H 4 (Ω) ) (0 < h < h * ). (5.28) for some constants h * , C > 0.

We tested the algorithm in the case O = ( 1 3 , 2 3 ) and the initial data that we want to steer to zero are q 0 (x) = x 5 (1x) 5 , q 1 (x) = -q 0 (x) and the control time is τ = 1. Note that [ q 0 q 1 ] ∈ H 3 2 × H 1 . We used N = 100 discretization points in space and in time an implicit centered-difference scheme with the CFL number equal to 0.1.

q(t) H 2 ∩H 1 0 q(t) L 2
Norm of q(t) and q(t)

Energy norm of q(τ ) q(τ )

Number of iterations (N )

Figure 3: (a) The norm of the solution of the controlled beam equation, with u = u h and the initial state q 0 (x) = x 5 (1x) 5 , q 1 (x) = -q 0 (x). (b) The energy of the solution of the controlled beam at time τ versus the number of terms N in the approximation of u h .

Figure 3(a) shows the norm decay of the solution of the discretized beam equation coresponding to (5.15)-(5.17), with a control u h given by (1.16). Figure 3(b) displays the dependence of the norm of the solution of (5.15)-(5.17), at the time τ , to the number N of terms used in the calculus of [ w 0h

w 1h ]. In Figure 4 is given the form of the approximate control u h corresponding to the initial data [ q 0 q 1 ] considered in the example below. Figure 4: The approximation u h with the initial state q 0 (x) = x 5 (1x) 5 , q 1 (x) = -q 0 (x) and the control time τ = 1.

Figure 2

 2 Figure 2 displays the norm of the solution of the controlled discretized wave equation, corresponding to (5.1)-(5.3), at the time τ for different values of N used in calculus of [ w 0h w 1h ].

  )

Figure 2 :

 2 Figure 2: The energy of the controlled wave equation solution at the time τ versus the number of terms N in the approximation of the control u h .

  )where w h and w b,h are the solution ofẅh (t), v h + ∂ 2 w h ∂x 2 (t), d 2 v h dx 2 + χ 2 O ẇh (t), v h = 0 (t ∈ [0, τ ]) (5.24)

		w h (0) = w 0h , ẇh (0) = w 1h		(5.25)
	ẅb,h (t), v h +	∂ 2 w b,h ∂x 2 (t),	d 2 v h dx 2 -χ 2 O ẇb,h (t), v h = 0	(t ∈ [0, τ ])	(5.26)

Acknowledgments

The authors are partially supported by the bilateral project 19600SJ, Grant 206/2009 of ANCS (Romania). The second author is partially supported by Grant MTM2008-03541 funded by MICINN (Spain).


Vladimir Popescu
email: vladimir.popescu@imag.fr

Jean Caelen
email: jean.caelen@imag.fr

A Rhetorical Structuring Model for Natural Language Generation in Human-Computer Multi-Party Dialogue

Multi-party human-computer dialogue research is still in its infancy. Most of the research in this respect either addresses dialogues between pairs of computers, or performs studies on multi-party human dialogue corpora, in order to better understand this type of interaction. Thus, there are only a few computational models for this type of linguistic interaction and this paper tries to fill this gap. However, only the issue of generating linguistically-appropriate speech turns in multi-party dialogue will be addressed here. For this, a formal framework that accounts for multi-party dialogue situations is developed. Then this model is customized, so that only the point of view of the machine is considered. Finally, several particularly interesting multi-party dialogue situations (for service-oriented systems) are enforced with algorithms for rhetorical structure updating for answer generation, in natural language, and evaluated on concrete multiparty dialogue examples.

Introduction

Even if dialogues between a computer and only one human partner are studied in a rather mature research field [McTear, 2002] and several commercial applications or systems exist in this respect, the situations where the computer is supposed to get involved in a dialogue with several humans at the same time, are still too little studied in a systematic manner.

Thus, several possibilities exist, towards multi-party human-computer dialogue:

• multi-session human-computer dialogue, where the machine gets involved in parallel dialogues with several humans; these dialogues are independent in that the speakers do not interact with each other and do not have access to the dialogues between the machine and the other speakers. This type of interaction is particularly interesting for situations involving concurrent access to a limited set of resources (e.g. meeting room reservation in a company); therefore, in this case there are several classical dialogues, on which the computer should maintain a coherent representation. Even if there is not a real multi-party dialogue, there is rather little work worldwide in this respect. For instance, the current state of the art is represented by the PVE ("Portail Vocal pour l'Entreprise") system [Nguyen and Caelen, 2005], [START_REF] Caelen | [END_REF]. In this system, multiple sessions are handled, at the dialogue control level, through a game theoretic approach, where machine contribution sequences are evaluated via gains that are dependent, at the same time, on the task context (amount of resources, speakers' roles, etc.) and on the speech acts performed by the speakers.)

• multi-party human-computer dialogue, where the machine gets involved in simultaneous dialogues with several speakers; as in multi-session dialogue, the machine has to keep a coherent view on the dialogues; yet, there is a major difference in regards to the latter situation: in multi-party interaction, the dialogues are simultaneous, all the speakers being at the same place and having access to all speakers' utterances. This is why modeling (and formalizing) this type of interaction is particularly difficult. However, since around 2000 there is more and more (substantial) research work in this respect, trying either to study the portability of models designed for traditional dialogues, to multi-party dialogue [START_REF] Ginzburg | [END_REF], or to analyze multi-party dialogue corpora in order to determine the differences between traditional and multi-party dialogues [START_REF] Popescu-Belis | [END_REF], or even to give a formal account of particular aspects of multi-party dialogue (such as dialogue control) and concerning only some issues (such as the shared context between interlocutors) [START_REF] Larson | [END_REF].

If traditional dialogue between one human and one computer boiled down to immediate applications in services dealing with user assistance in mitigating certain tasks, such as airplane ticket reservation [McTear, 2002], and even multi-session dialogue begins to reach practical interest in tasks regarding the distribution of a limited set of resources to several users, according to their wishes, multi-party dialogue modeling becomes interesting in tutoring applications, or even in services where the computer has to interact with several speakers at the same time (for instance, in a situation where several clients -a family or a group of friends, ask for a service at the same time). Hence, research in this direction is motivated at the same time from a theoretical standpoint and by practical considerations, when more natural and user-friendly dialogue systems are to be deployed.

In this context, this article addresses several issues in modeling semantic and pragmatic aspects concerning machine utterance generation in service-oriented multi-party dialogues. Thus, we first give a formal account, at a rhetorical level, of multi-party dialogues; then, several particular situations, relevant for service-oriented applications are presented in detail. For these situations, the formal framework is enhanced with a procedural account, instantiated in algorithms for driving the computation and update of the rhetorical structures that specify the dialogues. These rhetorical structures are then used to constrain the choice of appropriate linguistic forms, for a given communicative intention, specified in logical form. The algorithms lean on the framework developed by the authors for driving the process of natural language generation in traditional dialogues, with a single human speaker 1 . Thus, in this article one will address the following issues: first, a general framework for situating multi-party dialogues from a rhetorical point of view will be defined; then, two important cases will be depicted, according to the "involvement" of the speaker in conversations. This analysis will then be restricted to the machine view on the communication situation, more specifically, only the "involved" view of the machine will be taken into account. This (restricted) model is specified at a procedural level, regarding the discourse structure updating process, when a machine speech turn is due to be generated. Hence, this paper proposes an approach to natural language generation in multi-party dialogue, that tries to reuse a formal account designed for traditional, single-user dialogues. Finally, the procedural specification of the model will be demonstrated on typical multiparty dialogue examples.

General Framework

Notations

Throughout this paper a set of notational conventions will be used; these notations are provided below:

• L 1 , ..., L N , L α , L β , ... ::= human speaker (locutor) of identity i, i ∈ {1, ..., N} or α, β, etc.;

• M ::= the computer (machine);

• ν i j , ν αβ ::= conversational "vein" between speakers L i and L j (i.e., if there is a dialogue between these two speakers, then it takes place in the vein ν i j )2 ; one has that ν i j ≡ ν ji for all i and j;

• S DRS βγ α ::= segmented discourse representation structure (SDRS), expressed in the framework of Segmented Discourse Representation Theory (SDRT), for the dialogue in vein ν βγ , as it is seen by speaker L α ;

• S DRS i jk ::= union of all SDRSs seen by speaker L k on veins ν i j such that [i , j ] ⊆ [i, j];

• S DRS i j ::= ∀k S DRS i jk ;

• π(α, β) ::= label of an utterance came from L α and addressed to L β ;

• π(α, B) ::= label of an utterance came from L α and addressed to the set of speakers L β : β ∈ B;

• t(π) ::= ordinal index of the utterance labeled "π", in the sequence of utterances produced by π's emitter in the dialogue that this speaker is currently involved in;

• emitter(π) ::= emitter of the utterance labeled "π";

• equals(n, m) ::= predicate resolving to true if and only if n = m for numeric values, or n ≡ m, for other types of atoms;

• turn(π, α) ::= equals(emitter(π), L α ) ∧ t(π);

• K(π) ::= logic form expressing the semantics of the utterance labeled "π";

• S DRS α (i) ::= the discourse sub-structure corresponding only to the contribution of L α to the i-th speech turn; • MP ::= discourse "relation" denoting a multi-party dialogue situation; this relation connects the last utterance of one speaker, to the first utterance of another (the subsequent) speaker (except for the machine) in a speech turn;

L 1 L 2 L i L j L N ν 12 ν 2i ν i j ν j N ν 1N ν 1j ν 1i ν 2N ν 2j ν i N
• RR (c) MON ::= confirmation monologue (third order, see the appendix) rhetorical relation;

• RR (¬c) MON ::= contradiction monologue rhetorical relation;

• RR (c) DIAL ::= confirmation dialogue (first and second order, see the appendix) rhetorical relation;

• RR (¬c) DIAL ::= contradiction dialogue rhetorical relation; • the logical symbols ∃, ∀, ⇒, ¬, ∧, ∨ have their usual meanings;

• the mathematical symbols <, ≤, =, ≥, >, ∪, ∩, ∅, ⊆, ⊂, ⊃, ⊇, ∈, , \ have their usual meanings as well.

These notations will allow us to develop the formal account of the rhetorical view on multiparty dialogues. This will be done in the following subsection.

Multi-party Dialogue Situation

For the account given in this section, we assume that there are N speakers in multi-party dialogue situation; this is illustrated in Figure 1, where veins potentially established between (pairs of) speakers are shown.

All the accountable discourse structures for this dialogue situations are specified below:

S DRS ik = S DRS i j i ∪ S DRS ik i ∪ S DRS ji j ∪ S DRS jk j ∪ S DRS ki k ∪ S DRS k j k ∪ S DRS jk i ∪ S DRS ik j ∪ S DRS i j
k . The formal framework proposed here leans on two postulates: Postulate 1. (Common background) Any two speakers involved in a dialogue keep the same view on it. In formal terms:

∀L i , L j : equals(S DRS i j i , S DRS i j      For the particular case of three speakers, the expression becomes: S DRS ik = S DRS i j i ∪ S DRS ik i ∪ S DRS jk j ∪ S DRS jk i ∪ S DRS ik j ∪ S DRS i j k . Concerning the "views" that speakers take on the dialogue situation they are involved in, two cases can be depicted: I. "Involved" view: The speaker participates in the dialogue it accounts for (from a rhetorical perspective, i.e., the corresponding SDRS). We are concerned by discourse structures of the type S DRS αβ α , for the speaker L α that builds a representation of the dialogue she undertakes with L β . Thus, for two couples of speakers L α , L β and L ϕ , L ψ , we have two sub-cases:

1. S DRS αβ α ∩S DRS ϕψ ϕ = ∅. In this case we have several dialogues in parallel, which is reducible to the traditional dialogue (involving two speakers); hence, this case will not be given a formal account here;

2. S DRS αβ α ∩ S DRS ϕψ ϕ ∅.
In this case we have a real multi-party dialogue, hence will be analyzed in this paper. It might be argued that it is possible for a conversation with the same participants and content to take place at two different moments in time, and hence if two conversations intersect with regards of speakers and content, it does not mean that they concern the same instance of a conversation. However, this is not the case in our framework, since discourse structures are not persistent from one conversation to another, and hence if two conversations take place at different points in time, there is no relation between them, since, after each dialogue takes place, its traces are not kept.

From the point of view of a speaker involved in a real multi-party dialogue (case I.2. above), if we denote by ρ the label of a rhetorical relation, we can write in an explicit manner the SDRS that L α builds on the dialogue between herself and a certain L β :

S DRS αβ α = t speech turn (π(σ(α, β)) : equals(t(π), t)) ∪ ( t<t speech turns (ρ (π(σ(α, β)), π (σ(α, β))) : equals(t(π), t) ∧ equals(t(π ), t ))) Thus, a non-void intersection of two discourse structures boils down to the existence of common utterances (that is, utterances that one speaker addresses to several speakers):

S DRS αβ α ∩ S DRS ϕψ ϕ ∅ ⇔ α -ϕ α -β ∨ α -ψ α -β ∨ β -ϕ β -α ∨ β -ψ β -α ∨ ϕ -α ϕ -ψ ∨ ϕ -β ϕ -ψ ∨ ψ -α ψ -ϕ ∨ ψ -β ψ -ϕ
In the latter condensed notation, for three speakers L X , L Y , L Z , the following notation holds:

X -Y X -Z ::= ∃π, π : π(X, Y) ∧ π (X, Z) ∧ equals(turn(π, X), turn(π , X)) ∧ equals(K(π), K(π )).
In words, the parenthetic expression to the left means that there exists one utterance produced by a speaker (L X ), that is addressed to two different speakers (L Y and L Z ).3 II. "Exterior" view: The speaker does not participate in the dialogue it accounts for (from a rhetorical point of view), she only observes a dialogue between other two speakers. We are concerned with discourse structures of the type S DRS βγ α . Thus, for two triples of speakers (L α , L β , L γ ) and (L η , L ϕ , L ψ ) we have two sub-cases:

1. S DRS βγ α ∩S DRS ϕψ η = ∅. This case is reducible to simultaneous independent dialogues taking place in parallel, or to multi-session dialogues (if, for instance equals(L β , L ϕ )); thus, this case will not be accounted for in this paper; 2. S DRS βγ α ∩ S DRS ϕψ η ∅. This case really represents a multi-party dialogue situation, where two speakers share their views (as observers) on two other dialogues, involving other pairs of speakers. Therefore, this case will be analyzed in detail in this paper.

For speakers observing a pair of real multi-party dialogues (case II. 2 above), we can depict two more sub-cases:

1. equals((L β , L γ ), (L ϕ , L ψ )) ⇒ S DRS βγ α ∩ S DRS βγ η
∅. This is normal, since there are two different views of the same dialogue (between L β and L γ ); we have three sub-cases: (a) the two "observers" L α and L η share the "involved" view of speaker L β on the dialogue taking place on vein ν βγ : S DRS βγ α ≡ S DRS βγ η ≡ S DRS βγ β . This can happen if L α and L η share a lot of background knowledge with L β and L γ , being at the same time able to access the whole dialogue that these latter two speakers maintain; the dialogue taking place on vein ν βγ : S DRS βγ α ∩ S DRS βγ η ⊂ S DRS βγ β ; (c) the two "observers" L α and L η share a view on the dialogue between L β and L γ that has nothing to do with the view that L β and L γ share on this dialogue (by virtue of the common background postulate): S DRS βγ α ∩ S DRS βγ η ¬ ⊆ S DRS βγ β . This can happen when L α and L η do not have an appropriate background to follow "well" the dialogue taking place on vein ν βγ ; 2. only one of the speakers concerned is the same in both dialogues:

L α L η L β L γ L ψ ν β γ ν β ψ
equals(L β , L ϕ ) ∨ equals(L γ , L ψ ) ∨ equals(L β , L ψ ) ∨ equals(L γ , L ϕ ).
We suppose for instance that equals(L β , L ϕ ). Thus, case (II. 2) above becomes: S DRS βγ α ∩ S DRS βψ η ∅, that is, L α and L η both observe that L β addresses common turns to L γ and L ψ . This situation is depicted in Figure 2.

An interesting sub-case of this latter case presented above is when L α and L η share totally their views:

equals(S DRS βγ α , S DRS βγ η ) ∧ equals(S DRS βψ α , S DRS βψ η ).

This case is reducible to the first sub-case of (II. 2) in order to satisfy the two constraints listed just above; then, once these constraints are satisfied, we have that:

S DRS βγ α ∩ S DRS βψ η ∅ ⇔ S DRS βγ α ∩ S DRS βψ α ∅.
In this case, since we have only one speaker in two different dialogues, we have that:

S DRS βγ α ∩ S DRS βψ α ∅ ⇔ β -γ β -ψ ,
as seen by speaker L α .

3 Multi-party Human-Machine Dialogue

Uniqueness of the Point of View

In Section 2 we had multiple points of view on the dialogues taking place between locutors. In this section, only the point of view of one speaker will be considered, namely machine's point of view.

Thus, assuming that there are N locutors L 1 , ..., L N and the machine M, the union of the discourse structures, viewed by the machine, becomes:

S DRS 1N M = N i=1 S DRS Mi M ∪ N i=1 N
j=i+1 S DRS i j M . Moreover, the notations used in Section 2 take a particular form: S DRS αβ α → S DRS Mβ M ; S DRS βγ α → S DRS βγ M . Therefore, cases I. and II. specified in Section 2 become: I . "Involved" view of the machine: For the doubles (M, L β ) and (M, L ϕ ), we have two cases:

1. S DRS Mβ M ∩ S DRS Mϕ M = ∅.
This is a multi-session dialogue situation, where M maintains separate discourse structures for each human interlocutor. This case is not too interesting from a rhetorical point of view, presenting instead serious challenges at a dialogue control level [Nguyen and Caelen, 2005]; an example in this respect, involving the machine M and two speakers L β and L ϕ is shown below (numeric indexes specify the speech turns): ∅. This is a multi-party dialogue, where M is involved in simultaneous dialogues with users L β and L ϕ . A generalization from two speakers (L β and L ϕ ), to N speakers (L 1 to L N ) is straightforward. We present below an example of multi-party dialogue illustrating this case, for three speakers, including the machine: In this example, we have a dialogue where L β and L ϕ have a common interest that are trying to convey to the machine, in order for the latter to assist them in achieving their (common as well) goal. Nevertheless, other situations can be imagined, where the two speakers are also negotiating their interests, their goals, and the machine can act as a mediator. However, for the sequences of speech turns where the speakers negotiate their goals, the machine acts as a listener, thus adopting an "exterior" view and integrating (the SDRS that represents) this sequence of turns.

Session 1: M 1 : Hello,
M 1 : Hello,
In this latter case (I . 2.), as in Section 2, one can write that:

S DRS Mβ M = t speech turn (π(σ(M, β)) : equals(t(π), t)) ∪ ( t<t speech turns (ρ(π(σ(M, β)), π (σ(M, β))) : equals(t(π), t) ∧ equals(t(π ), t ))).
Therefore, we have that:

S DRS Mβ M ∩ S DRS Mϕ M ∅ ⇔ M -β M -ϕ ∨ β -M β -ϕ ∨ ϕ -M ϕ -β . But: (i) M -β M -ϕ ⇒ S DRS Mβ M ∩ S DRS Mϕ M ∅; (ii) β -M β -ϕ ⇒ S DRS βϕ M ∩ S DRS Mβ M ∅; (iii) ϕ -M ϕ -β ⇒ S DRS βϕ M ∩ S DRS Mϕ M ∅.
Cases (ii) and (iii) are included in case (II ), presented below, hence the only situation interesting here is where

M -β M -ϕ
, that is, M produces an utterance addressed at the same time to L β and L ϕ .

II . "Exterior" view of the machine: For the triples (M, L β , L γ ) and (M, L ϕ , L ψ ), where the computer is only an observer of dialogues between different speakers, we have the two cases:

1. S DRS βγ M ∩ S DRS ϕψ M = ∅.
In this case M's view on the dialogues taking place on veins ν βγ and ν ϕψ do not have anything to do together. In fact, the machine observes two independent dialogues taking place in parallel; this can be useful in tuning M's utterances, addressed to an L λ ∈ {L β , L γ , L ϕ , L ψ } (refer to the next section for further details in these regards);

2. S DRS βγ M ∩ S DRS ϕψ M ∅.
In this case M observes two dialogues having some speech turns in common4 . Here, there are two more "reasonable" (that is, not in contradiction with common sense) sub-cases:

(a) equals((L β , L γ ), (L ϕ , L ψ ))
. This is a trivial sub-case, since it implies that:

S DRS βγ M ∩ S DRS βγ M ∅; (b) equals(L β , L ϕ ) ∨ equals(L γ , L ψ ) ∨ equals(L β , L ψ ) ∨ equals(L γ , L ϕ ).
For simplicity, we assume that equals(L β , L ϕ ), which boils down to:

S DRS βγ M ∩ S DRS βϕ M ∅ ⇔ β -γ β -ϕ
, as seen by the machine.

Since these latter situations concern dialogues between humans, not directly involving the machine, we will not give examples here.

Relevant Human-Computer Multi-Party Dialogue Situations

All the multi-party dialogue situations that have been previously presented in this paper have to be detailed further, up to an algorithmic level. Thus, we will specify in the first place the rhetorical structure updating mechanism, when the machine is about to generate a speech turn. More specifically, we will have to specify the discourse structure updating mechanism for S DRS Mi M i=1,...,N , taking into account S DRS i j M i j;i, j=1,...,N . Thus, we consider two service-oriented dialogue situations, involving the machine and several (N) users (i.e., human locutors):

A. Service-oriented dialogue whereby the machine (for instance, a librarian or a train ticket seller) talks simultaneously to several clients that don't talk to each other; this dialogue type is appropriate for tutoring contexts as well. In this latter type of interaction, one speaker is the tutor, whereas the other speakers do not talk to anyone else except for the tutor, who in turn takes into account one or several (or all) speakers' knowledge.

Formally, the discourse context as seen by M is:

S DRS 1N M = N i=1 S DRS Mi M .
For updating this discourse context, the machine has to produce a speech turn. This turn is first computed in a logic form, by the dialogue controller [Nguyen and Caelen, 2005]:

K(π(M, I)) = Act( i∈I dest(L i ) ∧ K(π(M, I))).
In this equation, Act is the speech act type used to convey the contents of the utterance to be generated [Nguyen and Caelen, 2005], [Popescu et al., 2007b]; the utterance thus specified in logic form is addressed to speakers L i for i ∈ I, where I ⊆ {1, ..., N}. The predicate dest/1 specifies that the utterance π is addressed to a speaker that is argument of this predicate.

B. Service-oriented dialogue (as in case (A.) above), whereby the machine talks to a unique user (viz. the tutor or librarian), yet listening to the conversations between this user and the other users involved in the (multi-party) conversation. An example of such a situation is when the machine is a client or a student (for tutoring dialogues) that talks to a unique (main) speaker -e.g. the tutor and, at the same time, listens to the conversations between other speakers and the main speaker. This results in the machine adopting two behaviors: either it listens to conversations between other speakers, or it talks to one (main) speaker. This involves that type B. dialogus are subject to the restriction that no overlapping speech turns are produced in conversation; more precisely, that when the machine is talking to the main speaker, the other speakers are not engaged in distinct conversations at the same time. This constraint is quite reasonable in dialogues with a certain degree of formality (e.g. the tutor-students conversations, or even conversation between a group of people and a more distant main speaker).

Formally, the discourse context as seen by M is: S DRS 1N M = S DRS Mi 0 M ∪ N j=1; j i 0 S DRS i 0 j M . In this equation, L i 0 is the "central" speaker, providing the service (viz. the librarian or tutor). For updating the discourse context, the machine has to realize in linguistic form a communicative intention (produced in logic form by the dialogue controller) of the type:

K(π(M, i 0 )) = Act(dest(L i 0 ) ∧ K(π(M, i 0 ))).
Here, the set I specifying the recipients of utterance π is reduced to a singleton, i 0 , for the "central" speaker L i 0 . The predicate dest/1 making part of the semantic content of π(M, i 0 ) indicates that this utterance is addressed to a certain speaker (L i 0 ). However, this does not mean that this utterance is actually heard by this speaker; it means only that the utterance is addressed to this speaker, who might be aware of this or not.

The logic form K(π(M, i 0 )) has to be added to the discourse structure S DRS Mi0 M , taking into account the discourse structures S DRS i 0 j M , j ∈ {1, N} \ {i 0 }.

These two particular dialogue situations are illustrated in Figure 3. In case A., the machine is always an "involved" speaker, therefore in situation (I .), whereas in case B., the machine is either an involved speaker, or about to make the transition from an "observer" speaker to an "involved" one -when the "central" user had been talking to another 11

- + L 2 L i L L N case B. M L i 0 0 1 i 0 1 L 1 L 2 L i L j L N M case A.

Discourse Structure Updating

In order to specify the discourse structure updating process in an algorithmic manner, we lean our attention only on the situation whereby the machine is about to produce a speech turn, which is due to be added to the discourse structures concerned. Moreover, we limit ourselves to the cases A. and B. presented in the previous section. Thus, we have: Case A. The discourse structures due to be updated are:

S DRS 1N M = N i=1 S DRS Mi M .
The logic form (come from the dialogue controller) to be added to these discourse structures is denoted by K(π(M, I)) and has the expression presented in the previous subsection.

In this context, the discourse structure updating algorithm is specified below:

for a communicative intention K(π(M, I)):

1. find the set I of recipients of the communicative intention:

I = SubsetOf(dest(L i ), K(π(M,I))) arg (dest(L i )).
In words, this equation states that the set of the addressess of the communicative intention is determined by grouping all the (distinct) arguments of the dest/1 predicate instantiations in this communicative intention.

2. choose the discourse structures to be updated: i∈I S DRS Mi M . That is, the machine updates the SDRSs of the dialogues that it maintains with the speakers it is talking to (i.e., determined by the set I).

3. extract the semantic content from the communicative intention:

(a) Act( i∈I dest(L i ) ∧ K(π(M, I))) → Act( i∈I dest(L i )) ∧ Act(K(π(M, I))) → i∈I Act(dest(L i )) ∧ Act(K(π(M, I))); (b) i∈I Act(dest(L i ))∧Act(K(π(M, I)))∨¬ i∈I Act(dest(L i )) → i∈I (Act(dest(L i )) ∨ ¬Act(dest(L i )))∧ Act(K(π(M, I))) → Act(K(π(M, I))); (c) Act(K(π(M, I))) → Act(K(π));
In words, this step of the algorithm separates, in the semantic form of the utterance, the part that specifies the addressees of this utterance, from the part that states its propositional content (i.e., literal meaning).

4. for i ∈ I: simple_update Act(K(π)), S DRS Mi M .

In this algorithm, the function simple_update/2 performs the updating of a discourse structure (given as the second argument), with a logic form, expressing an utterance (given as the first argument), in the case of a traditional dialogue, between two speakers (out of which one is the machine). This procedure, suited for rhetorical structuring in traditional human-computer dialogue, has been extensively described in [Popescu et al., 2007a, Popescu et al., 2007b].

Case B. The discourse structure to be updated is:

S DRS 1N M = S DRS Mi 0 M . In fact, S DRS Mi 0
M is updated with the semantic content Act(K(π)) extracted from the communicative intention K(π(M, i 0 )) by taking into account the discourse structures S DRS i 0 j M j=1,...,N; j i 0 . This means that the speech act due to be currently generated is connected to the utterances in the SDRS due to be updated, by taking into account the incidences regarding these utterances. In turn, these incidences are produced through dialogues with the other locutors. Thus, if an utterance in the SDRS concerned (S DRS Mi 0 M ) is connected, via a "contradiction" rhetorical relation (please refer to the Appendix for further details in this respect), to a subsequent utterance in another discourse structure (of the type S DRS i 0 j M ), then the speech act due to be generated may be connected to the first utterance (in S DRS Mi 0 M ) in either of the following ways:

• via a contradiction rhetorical relation, with respect to the utterance in S DRS i 0 j M , followed by a confirmation rhetorical relation, with respect to the initial utterance in S DRS Mi 0 M , by inserting in S DRS Mi 0 M the fragment in S DRS i 0 j M having realized the contradiction with the first utterance, provided that this utterance had not been committed to by his emitter;

• via an elaboration rhetorical relation (cf. [Asher and Lascarides, 2003], [Popescu et al., 2007a]), with respect to an optional sequence of utterances in structures of the type S DRS i 0 j M , utterances that elaborate in turn on the utterance concerned, in S DRS Mi 0 M ;

• by default, if there is no constraint induced by discourse structures of the type S DRS i 0 j M , on the utterance concerned, in S DRS Mi 0 M .

In view of these elements, a discourse structure updating algorithm is presented below:

for a communicative intention K(π(M, i 0 )):

1. identify the discourse structure to be updated: S DRS Mi 0 M ;

2. find the rhetorical structures to be taken into account in the updating process: M , since if an utterance had been discarded (as a non-candidate for π), then it would not have been a member in a composition with another SDRS; 4. compute the discourse structure to be updated with the utterance due to be generated:

S DRS i 0 j M j {i 0 ,M} ; L 2 L 2 L case B. M L L 1 L M case A.
S DRS Mi 0 M ← k:π k ∈S DRS Mi 0 M S DRS Mi 0 M (k);
5. extract the semantics for the communicative intention, due to be generated in linguistic form: K(π(M, i 0 )) → Act(K(π));

6. simple_update(Act(K(π)), S DRS Mi 0 M ).

In the two conversation situations A. and B., the main issue concerning multi-party dialogue stems from choosing the discourse structure(s) to update: in situation A., the choice is guided by the set of recipients for the communicative intention due to be generated, whereas in situation B., the choice is driven by the representation that the computer builds on the dialogues that the recipient of the utterance due to be generated establishes with the other speakers. Hence, while in situation A. the choice of the discourse structures is rather obvious and fixed by the dialogue controller, in situation B. the discourse structure to be updated is built in an iterative manner, as the dialogue progresses.

Multi-Party Human-Computer Dialogue Example

The discourse structure updating mechanism presented in Section 3. will be illustrated for a humancomputer dialogue involving three human speakers, in situations A. and B. (see Section 3.), when a speech turn is to be produced by the machine. The situation is shown in Figure 4.

For each situation there are several particular cases, according to the addressees of the speech turn due to be produced by the machine: M , S DRS 13 M taken into account}; 2. K(π(M, 1)) ∧ {S DRS 13 M taken into account}; 3. K(π(M, 1)) ∧ { no other discourse structure taken into account}.

Situations A.1, A.2 and A.3 are driven by the dialogue controller (via the predicates "dest/1" in K(π(M, I))), while situations B.1, B.2 and B.3 are driven by the multi-party dialogue context, in fact by the conversations involving L 1 , L 2 and L 3 . Thus, a typical human-computer dialogue involving the machine and three human locutors will be analyzed in detail. Here, it will be shown how M can switch automatically from situation A. to situation B. and vice versa, along the same dialogue.

The dialogue concerns a book research and reservation in a library, where the computer is the librarian and L 1 , L 2 and L 3 are the clients. It is M that opens the dialogue, introducing itself. The dialogue is annotated in terms of speakers, speech turns and utterances, in the following form: M j : utterance π ji 0 ... utterance π ji 1 ; L j k : utterance π j(i 1 +1) ... utterance π ji 2 .

Here, j is the index of the speech turn, k is the index of the human speaker, and π js denotes the s-th utterance in the j-th speech turn.

Thus, the dialogue is listed (in annotated form) below:

M 1 : Hello, I am Groplan π 11 , I can provide you with assistance in searching for a document in our library. π 12 You can, at any time, ask for information on the availability of a certain book, CD or DVD. This dialogue combines the dialogue situations A. and B. specified above, since M, although it remains the "server" (i.e., the librarian), listens to the speech turns whereby the human locutors complete themselves in order to refine their requests. However, the dialogue remains mainly in case A., with fragments where the machine switches to case B. In the subsequent lines we will present a complete trace of the process whereby the discourse structures accounting for this dialogue are updated, with each speech turn produced by the computer.

Yet, before developing the trace on this example, we have to specify the dialogue situation switching process (that is, the way whereby M switches from dialogue situation A. to dialogue situation B. and the other way round). The essential information in this respect resides in the existence or non-existence of MP relations in discourse structures corresponding to multi-party human speech turns. This is formally specified below:

for any speech turn i:

if ∃ρ ∈ S DRS (¬M) (i) : equals(ρ, MP) dialogue_situation ← B.; else dialogue_situation ← A.
In words, the dialogue situation assumed by default by the machine is A., and, if in the current speech turn there is an MP relation in the SDRS accounting for a multi-party dialogue between human users, then the dialogue situation is switched to B. The decision regarding the current dialogue context is made for each speech turn.

These elements being given, the rhetorical structuring of the dialogue shown above takes place as the dialogue progresses: )), then Elab q (π 42 , π 43 ); finally, this sub-structure is appended to the dialogue history via Background q (π 41 , π 42 ) and Elab q (π 41 , π 43 );

9. The rhetorical structuring component in M's generator, seeing the MP relation previously computed, switches to dialogue situation B.; then, it aggregates the dialogue intention came from the dialogue controller, into utterances π 51 and π 52 , that it rhetorically connects via the relation Contrast(π 51 , π 52 ); then, these utterances are appended to the dialogue history via the relations P-Corr(π 43 , π 51 ) and QAP(π 42 , π 52 ); 10. The pragmatic interpreter in M first computes MP(π 53 , π 54 ), then Elaboration(π 54 , π 55 ), then it connects these utterances to the dialogue history, via the relations ACK(π 52 , π 53 ) and ACK(π 52 , Elaboration(π 54 , π 55 ));

11. The rhetorical structuring component in M's generator first sees the MP relation just computed by the pragmatic interpreter, therefore it switches to dialogue situation B., then it connects utterance π 61 (that corresponds, for the moment, to a communicative intent came from the dialogue controller and expressed in logic form) to the dialogue history: Elab q (π 53 , π 61 ) and Elab q (Elaboration(π 54 , π 55 ), π 61 );

12. The pragmatic interpreter in M first connects π 62 to the dialogue history via Q-Elab(π 61 , π 62 ), then computes MP(π 62 , π 63 ) since these utterances have different emitters; finally, P-Elab(π 62 , π 63 ) is computed as well;

13. The computations performed in this discourse structure updating process are presented in a concise manner in Table 1, where we denote by ¬M the set of speakers other than M.

× RR (c) MON 2. 1 × RR (c) MON + 1 × RR (c) DIAL + 1 × MP 3. (B): 2 × RR (c) MON + 2 × RR (c) DIAL 4. 2 × RR (c) DIAL + 1 × RR (¬c) DIAL + 1 × MP 5. (B): 1 × RR (¬c) MON + 1 × RR (c) MON + 2 × RR (¬c) DIAL 6. 2 × RR (c) DIAL 7. (A): 1 × RR (c) DIAL 8. 3 × RR (c) DIAL + 1 × MP 9. (B): 1 × RR (¬c) MON + 1 × RR (¬c) DIAL + 1 × RR (c) DIAL 10. 1 × RR (c) MON + 2 × RR (c) DIAL + 1 × MP 11. (B): 2 × RR (c) DIAL 12. 2 × RR (c) DIAL + 1 × MP 13. (B): 1 × RR (c) MON + 2 × RR (¬c) DIAL 14. 3 × RR (c) DIAL 15. (B): 1 × RR (¬c) MON + 1 × RR (c) MON + 3 × RR (c) DIAL 16. 1 × RR (c) MON + 2 × RR (¬c) MON + 3 × RR (c) DIAL + 2 × MP 17. (B): 1 × RR (c) MON + 1 × RR (c
For a more intuitive outlook on the trace on the discourse updating process, we present in Figure 5 the discourse structure built for the multi-party dialogue, emphasizing the sub-SDRSs as well. In this article we have proposed a formal framework that accounts for multi-party dialogue situations. These specifications are applied to human-computer interaction and illustrated through relevant examples. Thus, although there are limits to the account (such as the inability to handle general multi-party dialogues, i.e., where the interaction is not guided by any "protocol"), the algorithms that lean on this framework, on the one hand, allow the computer to handle more flexible and complex interactions than traditional two-party dialogues, and, on the other hand, give a rather formal and systematic view on real human multi-party dialogues. However, several issues remain open to research in the near future: (i) the algorithms proposed in this article should be first ran on real multi-party human dialogues (for instance, on theatrical plays where appropriate task ontologies would have been built) and validated on them, (ii) then, these methods should be integrated in a multi-party dialogue architecture (such as extensions performed to TRINDI Kit), in order to drive the answer generation component, (iii) after this step, all the multi-party dialogue situations described in the article should be instantiated in procedural descriptions and then applied to real multi-party dialogues.

In the longer term, the framework presented in this article might form the basis for more complex applications, involving at the same time interactions between artificial agents and humans, in computer games, or applications in the more recent strand related to interactive storytelling [START_REF] Cavazza | [END_REF], where one (or several) human subject(s) interacts with several artificial agents in a multimodal manner, including natural language. Thus, in this type of applications, the way whereby interacting locutors exchange speech turns is particularly relevant for an entertaining and natural interaction [START_REF] Thue | [END_REF].

Last but not least, the formal framework proposed in this paper would be useful in driving decisions regarding the fine-tuning of the utterances to be produced by the machine in multi-party dialogue, such as the pronominal anaphora generation process (a mechanism in this respect, concerning only two-party human-computer dialogues, is presented in [Popescu, 2007]), in order to render the utterances generated more relevant to the dialogue situation and to the addresses.

Appendix: A Fragment of SDRT for Language Generation in Human-Computer Dialogue

Even if SDRT is a rather mature formal account of the rhetorical structure of discourse, it remains a theory of discourse interpretation. Thus, in order to lean on SDRT for generation purposes, several adaptation need to be performed. First of all, the communicative goal "behind" an utterance (called "Speech Act Related Goal" -SARG in SDRT) is given as input for generation (since it is computed by the dialogue controller), whereas in interpretation this is a big issue to be carried out by the theory [Asher and Lascarides, 2003]. On the contrary, in generation, the big issue, from a rhetorical structuring perspective, resides in stating a way whereby the (already known) SARG constrains its rhetorical potential, that is, the set of rhetorical relations that connect it to previous utterances in the discourse [Popescu et al., 2007a].

Thus, out of the around 35 rhetorical relations proposed in vanilla SDRT (in the 2003 version [Asher and Lascarides, 2003]), a subset of 17 have been chosen. These rhetorical relations, considered particularly useful for human-computer dialogue purposes, are clustered in three types:

• first-order rhetorical relations -Q-Elab, IQAP, P-Corr and P-Elab, with informal semantics as in [Asher and Lascarides, 2003], that are strongly related to temporal aspects in dialogue, hence used in an approximate manner, specific to the type of dialogue concerned (i.e., conversations involving negotiations on time intervals of resource availability, as in Verbmobil corpus [Schlangen et al., 2001]);

• second-order rhetorical relations -Background q , Elab q , Narration q , QAP, ACK and NEI, with informal semantics as in [Asher and Lascarides, 2003], that are less constrained by the temporal aspects of the dialogues concerned, hence used in a manner closer to that specified in vanilla SDRT;

• third-order rhetorical relations, specific to monologues and used to relate utterances within a speech turn, generated by one of the speakers (either the human or the machine) -Alternation, Background, Consequence, Elaboration, Narration, Contrast and Parallel, with semantics as in vanilla SDRT [Asher and Lascarides, 2003].

Furthermore, in order to enhance the semantics of these rhetorical relations with pragmatic aspects, we group them in two categories:

• confirmation rhetorical relations -Q-Elab, P-Elab, Elab q , Narration q , QAP, ACK and IQAP, Background, Consequence, Elab, Narration and Parallel; via these rhetorical relations the current utterance (appearing a the second argument in these relations) does not question the previous utterance (appearing as the first argument in the relations);

• contradiction rhetorical relations -P-Corr, Background q , NEI, Alternation and Contrast.

We illustrate below, via appropriate human-computer interaction examples, each rhetorical relation, emphasizing its type, category and informal semantics; here, U and M designate a human user and a machine, respectively, whereas π i , designate utterances:

1. Q-Elab(π 1 , π 2 ) ("Question Elaboration"):

• Type: first order;

• Category: confirmation;

• Informal semantics: π 2 is a question to which any answer elaborates a plan for achieving the SARG conveyed by π 1 ;

• Example: π 1 : U: I will read this book on Monday. π 2 : M: Is it OK for you at 2 o'clock PM?

2. IQAP(π 1 , π 2 ) ("Indirect Question-Answer Pair"):

• Type: first order;

• Category: confirmation;

• Informal semantics: π 1 is a question and π 2 is an answer that provides information allowing π 1 's emitter to infer an answer to π 1 ;

• Example: π 1 : U: Could I have this book for next week? π 2 : M: The book is due to be returned back to the library this Wednesday.

3. P-Corr (π 1 , π 2 ) ("Plan Correction"):

• Type: first-order;

• Category: contradiction;

• Informal semantics: π 2 's emitter refutes the SARG conveyed by π 1 ;

• Example: π 1 : U: Could I have this book for next week? π 2 : M: The book is already reserved by another customer since the 16th until the 25th.

4. P-Elab (π 1 , π 2 ) ("Plan Elaboration"):

• Type: first order;

• Category: confirmation;

• Informal semantics: π 2 elaborates a plan for achieving the SARG conveyed by π 1 ;

• Example: π 1 : U: Could I have this book for next week? π 2 : M: To have it, you have to go at our headquarters Street 'X', to reserve it there, in the beginning of next week.

5. Background q (π 1 , π 2 ):

• Type: second order;

• Category: contradiction;

• Informal semantics: π 2 is a question to which any answer is in a Background relation to π 1 ;

• Example: π 1 : M: This book has already been reserved by another customer. π 2 : U: Are there other clients having looked for this book as well?

6. Elaboration q (π 1 , π 2 ):

• Type: second order;

• Category: confirmation;

• Informal semantics: akin to that of Background q ;

• Example: π 1 : M: We have received new books on your field of interest. π 2 : U: Could you give me some titles, please?

7. Narration q (π 1 , π 2 ):

• Type: second order;

• Category: confirmation;

• Informal semantics: akin to that of Background q ;

• Example: π 1 : M: You can start with book 'X'. π 2 : U: And then, what do you recommend me?

8. QAP(π 1 , π 2 ) ("Question-Answer Pair"):

• Type: second order;

• Category: confirmation;

• Informal semantics: π 1 is a question and π 2 is a direct answer to this question;

• Example: π 1 : U: Where can I find the book with registration number 'xyz'? π 2 : M: The second floor, to the right. 9. ACK(π 1 , π 2 ) ("Acknowledgment"):

• Type: second order;

• Category: confirmation;

• Informal semantics: π 1 is an utterance and π 2 is another utterance, produced by another speaker that π 1 's emitter, whereby π 1 is confirmed;

• Example: π 1 : M: Are these books OK for you? π 2 : U: Yes.

10. NEI(π 1 , π 2 ) ("Not Enough Information"):

• Type: second order;

• Category: contradiction;

• Informal semantics: π 2 is an utterance that expresses the fact that its emitter does not have enough information to answer the question π 1 ;

• Example: π 1 : M: What author are you interested in in this field? π 2 : U: I don't know; what do you have?

11. Alternation(π 1 , π 2 ):

• Type: third order;

• Category: confirmation;

• Informal semantics: this relation is equivalent to the logical "OR";

• Example: π 1 : M: I can either lend you the book 'X', π 2 : M: or show you the DVD 'Y', on this subject.

12. Background(π 1 , π 2 ):

• Type: third order;

• Category: confirmation;

• Informal semantics: π 2 gives background information with respect to π 1 ;

• Example: π 1 : M: I can lend you this book 'X'. π 2 : M: You can make up to three reservation at one time.

13. Consequence(π 1 , π 2 ):

• Type: third order;

• Category: confirmation;

• Informal semantics: this relation is equivalent to the logical implication;

• Example: π 1 : M: If we give you the book 'X', π 2 : M: then, the library will not have any more copy of it left.

14. Elaboration(π 1 , π 2 ):

• Type: third order;

• Category: confirmation;

• Informal semantics: π 2 elaborates on π 1 , so that they share the same topic;

• Example: π 1 : M: I cannot lend you book 'X'. π 2 : M: It is the only one copy in the library.

15. Narration(π 1 , π 2 ):

• Type: third order;

• Category: confirmation;

• Informal semantics: π 2 temporally follows π 1 , in the same discourse;

• Example: π 1 : M: You reach the hall entitled "Scandinavian literature". π 2 : M: Then, you go to shelf "Andersen".

16. Contrast(π 1 , π 2 ):

• Type: third order;

• Category: contradiction;

• Informal semantics: π 1 and π 2 share the same topic, but present a contrastive element, one with respect to the other;

• Example: π 1 : M: I can give you book 'X'. π 2 : M: However, book 'Y' is available only for local access.

17. Parallel(π 1 , π 2 ):

• Type: third order;

• Category: confirmation;

• Informal semantics: π 1 and π 2 have the same semantic structure and topic;

• Example:

π 1 : M: I can give you book 'X'.

π 2 : M: I can give book 'Y' as well.

In order to render this fragment of SDRT operational from a human-computer interaction perspective, the semantics of the 17 rhetorical relations chosen have been expressed in a first-order logic approximation of those provided in vanilla SDRT. This endeavour is motivated by the need to obtain a computationally tractable rhetorical structuring component for utterance generation in dialogue. The main idea resides in using a set of task-independent discourse predicates for expressing the semantics of the rhetorical relations. The formal aspects of the rhetorical structuring component are presented in [Popescu et al., 2007a, Popescu et al., 2007b]. In these papers, detailed examples illustrating the approach and the mechanism for updating the SDRS reflecting the dialogue between a user and a computer are provided. This is why a description of these aspects will not be given here.

As for the manner whereby the discourse structure is updated (i.e., the simple_update/2 procedure), this is described in thorough details in several papers: in [Popescu et al., 2007a] we provide a baseline rhetorical structure updating algorithm, quadratic in the number of utterances already produced in dialogue; in [Popescu et al., 2007b] we provide an optimized version of the baseline algorithm, whereby constraints induced by speech acts are used to yield rhetorical structures that are more in accord to SDRT specifications and human intuitions.

Figure 1 :

 1 Figure 1: Multi-party dialogue situation

Figure 2 :

 2 Figure 2: Shared view on speech turns simultaneously addressed to two speakers

Figure 3 :

 3 Figure 3: Relevant human-computer multi-party dialogue situations

Figure 4 :

 4 Figure 4: Particular cases (N = 3) for the dialogue situations concerned

•

  Case A.: 1. K(π(M, I)) ∧ I = {1, 2, 3}; 2. K(π(M, I)) ∧ I = {2, 3} (or no matter what double); 3. K(π(M, I)) ∧ I = {3} (or no matter what singleton); • Case B.: 1. K(π(M, 1)) ∧ {S DRS 12

Figure 5 :

 5 Figure 5: The discourse structure for a multi-party dialogue

  Sir, what can I do for you? L 1 M 3 : Well, actually we have one, but it has just been given to another customer. It will be available in two weeks... L 3

β : Hello, I'd like some DVDs on Kilimanjaro's eruptions... M 2 : OK... let me see... Here it is: I have found one, on Kilimanjaro's eruption from one hundred thousand years ago. Should I put it on your card? L 2 β : Yes, please! Thanks a lot, good bye! Session 2: M 1 : Hello, Sir, what can I do for you? L 1 ϕ : Hi, there! Well, I'd like something on... Kilimanjaro mountain... Can you give me something with pictures or images? M 2 : Let me see... Well, I have found a touristic leaflet, there are many maps and nice pictures inside... L 2 ϕ : Well, actually I'd like something more like a movie or something... I don't know, do you have a DVD on it? ϕ : Hum... OK, so can you put in on my reservations list, please? M 4 : Of course! OK... done! Meanwhile, can I give you something else? For instance, we have another DVD, on volcanoes in Africa, and there is something on Kilimanjaro too! L 4 ϕ : That's perfect, put it on my card right now, please! Thanks, bye! 2. S DRS Mβ M ∩ S DRS Mϕ M

  what can I do for you? L 1 ϕ : Hi, well, we'd like some book or so, on contemporary French theatre... M 2 : Can you please give further specifications, for example on the topic or the author? L 2 ϕ : Well, something from the seventeenth century... like Molière or so... L 2 β : Actually, we'd like something on gamblers... gambler psychology or something... M 3 : So, you would like a seventeenth century play on gambling and gambler psychology, is that right? L 3 β : Yes, that's right! L 3 ϕ : Actually, it needn't be Molière, I mean something lighter will do as well... M 4 : OK, so here it is what I found: "The Player" by Regnard, written in 1696.

	Would that do?
	L 4

β : Well, what's it about? L 4 ϕ : Is it moralistic, with a gambler that ends up badly, because of its vice? M 5 : Yes, it is about a gambler, Valère, who trades his mistress's love for gambling, and ends up lonely and broke. Would this do for you? L 5 ϕ : Well, this sounds pretty moralistic for me... L 5 β : And that's precisely what we're looking for: moralistic French seventeenth century theatre on vices such as gambling! M 6 : So, should I put it on your cards? Would a single copy suffice for you, or you would rather like separate copies? L 6 β : I'd like a separate copy! You can put it on my card! M 7 : OK, so, I put a separate copy for each of you. Is this all right? L 7 ϕ : Yes, it's OK, thanks, bye! L 7 β : Yeah, thanks, bye bye!

  π 13 What can I do for you? π 14 L 1 1 : Hello π 15 , well, we would like a theatre play, on an incest... π 16 L 1 2 : An ancient tragedy or something like that... π 17 M 2 : Just a minute... here it is: π 21 I found eight ancient tragedies where an incest occurs. π 22 Can you give further specifications, for instance on the author? π 23 Oh yeah, an opera, I think that this will do perfectly! π 63 M 7 : Yes, indeed, I can give you an opera with Luciano Pavarotti and conducted by Riccardo Muti, played on March 1974 at the theatre Scala of Milan. π 71 Is this OK for you? π 72 Yes, it's OK with me! π 75 M 8 : So, I'll lend you "Oedipus the King" at the Hachette Publishers, 1972 edition, and a DVD with the opera with the same title, played at the theatre Scala of Milan, in 1974. π 81 A single copy of each document will do for you π 82 , or maybe you'd like a separate copy for each of you? π 83 L 8 3 : I would like a separate copy of the book for me. π 84 Still, for the DVD, we'll watch it together. π 85 L 8 1 : The same for me with the DVD π 86 , however for the book, it's OK for me to read it together with my wife (L 2 -n.a.) π 87 , so we can have both of us the same copy of the book. π 88 L 8 2 : Yes, I agree! π 89 M 9 : OK, so, well, I'm lending you one copy for the DVD and two copies for the book. π 91 It this what you want? π 92 104 M 11 : OK. π 111 So, here it is... π 112 Thank you for having used our service, see you soon, good bye! π 113 Have a nice day! π 114

	L 2 1 : Aristophanes? π 24 L 2 3 : Or else, Vergilius? π 25 2 : What do you have by Sophocles? π 34 M 4 : Well, for instance "Oedipus the King"... π 41 M L 3 L 4 1 : What's this play about? π 42 L 4 3 : Is there a brother-sister incest? π 43 M 5 : Actually, there is no brother-sister incest in "Oedipus the King" π 51 , but it's essen-tially about a parricide, followed by a mother-son incest... π 52 L 5 2 : Oh yes, this sounds good! π 53 L 5 1 : So, it's like in the movie "My Mother" with Isabelle Huppert. π 54 I loved that movie! π 55 M 6 : So, is this tragedy good for you? π 61 L 6 3 : Do you have interpretations on DVD as well, for this play? π 62 L 6 1 : L 7 1 : Yes, it's fine for me! π 73 L 7 3 : For me, too! π 74 L 7 2 : L 9 1 : Yes, that's it! π 93 L 9 3 : Right! π 94 L 9 2 : Yeah, yeah... OK! π 95 2 : You have a nice day too! π 115 L 11 3 : Good bye! π 116 M L 11 L 11 1 : Good bye, see you soon! π 117

3 : There is no ancient tragedy written by Aristophanes or Vergilius and involving an incest π 31 . Nevertheless, I found three tragedies by Sophocles, one tragedy by Aeschylus and one tragedy by Euripides, where an incest occurs π 32 . Would you like to choose one of these authors, find out about other relevant authors, or perform a new search? π 33 10 : OK π 101 , so, tell me please, on what name should I make the reservations? π 102 L 10 1 : Well, I think that we can put a copy of the book on my card, as well as the DVD. π 103 L 10 3 : And the other copy of the book, you can put it on my card. π

  1. The rhetorical structuring component in the M's natural language generation module places itself by default in dialogue situation A. and builds an SDRS composed of utterances π 11 , π 12 , π 13 and π 14 and of the rhetorical relations Elaboration(π 11 , π 12 ), Consequence(π 12 , π 13 ) and Background(π 13 , π 14 ); 2. The pragmatic interpreter module in M appends human users' utterances π 15 , π 16 and π 17 to the SDRS computed at step 1.; thus, the interpreter first computes Elaboration(π 15 , π 16 ), then it computes QAP(π 14 , Elaboration(π 15 , π 16 )), QAP(π 14 , π 17 ) and finally, given the multi-party dialogue context, MP(π 16 , π 17 ); first aggregates its communicative intention into utterances π 21 , π 22 and π 23 , then computes the relations Elaboration(π 21 , π 22 ) and Consequence(π 22 , π 23 ); finally, π 21 is attached to the dialogue history via the relations P-Elab(Elaboration(π 15 , π 16 ), π 21 ) and P-Elab(π 17 , π 21 ); 4. The pragmatic interpreter first appends π 24 and π 25 to the dialogue history via the relations IQAP(π 23 , π 24 ) and IQAP(π 23 , π 25 ); then, it determines the relations MP(π 24 , π 25 ) and P-Corr(π 24 , π 25 ), hence MP ∧ P -Corr(π 24 , π 25 ); 5. The rhetorical structuring component in M's generator finds an MP relation between utterπ 24 and π 25 , hence it remains in dialogue situation B.; then, it computes the attachment points π 24 and π 25 ; then, the current M's speech turn is structured, computing the monologue relations Contrast(π 31 , π 32 ) and Consequence(π 32 , π 33 ); then, this turn is appended to the dialogue history via the relations P-Corr(π 24 , π 31 ) and P-Corr(π 25 , π 31 ); 6. The pragmatic interpreter in M appends user utterance π 34 to the dialogue history via the relations Elab q (π 32 , π 34 ) and IQAP(π 33 , π 34 ); 7. The rhetorical structuring component in M's generator, not seeing any MP relation in the previous human speech turn, switches to dialogue situation A., hence, by virtue of the corresponding discourse updating algorithm, appends π 41 to the dialogue context, via the relation QAP(π 34 , π 41 ); 8. The pragmatic interpreter in M first computes MP(π 42 , π 43 ), since ¬equals(emitter(π 42 ), emitter(π 43

Table 1 :

 1 The rhetorical structuring component in M's generator first switches to dialogue situation B., since an MP was computed in the previous speech turn, then it aggregates the communicative intention into utterances π 71 and π 72 , connected via Consequence(π 71 , π 72 ); finally, this discourse sub-structure is appended to the dialogue history via QAP(π 62 , π 71 ) and QAP(π 63 , π 71 ); 14. The pragmatic interpreter in M first computes two MP relations between utterances came from the three human users: MP(π 73 , π 74 ) and MP(π 74 , π 75 ); then, it connects these utterances to the dialogue history, via the discourse relations ACK(π 72 , π 73 ), ACK(π 72 , π 74 ) and ACK(π 72 , π 75 ); 15. The rhetorical structuring component in M's generator first finds the two MP relations previously computed, therefore it switches to dialogue situation B. and, by virtue of the corresponding algorithm it establishes the list of possible antecedents in the dialogue history: utterances π 73 , π 74 and π 75 ; then, at a monologue level, the machine aggregates the communicative intention into utterances π 81 , π 82 and π 83 , rhetorically connected thus: Contrast(π 82 , π 83 ) and Elaboration(π 81 , Contrast(π 82 , π 83 )); finally, this discourse sub-structure is connected to the possible antecedents in the dialogue history, via the rhetorical relations P-Elab(π 73 , π 81 ), P-Elab(π 74 , π 81 ) and P-Elab(π 75 , π 81 ); 16. The pragmatic interpreter in M first computes two MP relations, MP(π 85 , π 86 ) and MP(π 88 , π 89 ), then, it structures the speech turns of each human locutor: Contrast(π 84 , π 85 ) for speaker L 3 , Contrast(π 86 , π 87 ) and Consequence(π 87 , π 88 ) for speaker L 1 and π 89 for speaker L 2 ; then, the dialogue rhetorical relation ACK(π 88 , π 89 ) is computed; finally, this discourse sub-structure is appended to the dialogue history, via QAP (Contrast(π 82 , π 83 ), Contrast(π 84 , π 85 )) and QAP(Contrast(π 82 , π 83 ), Contrast(π 86 , π 87 )); we denote the discourse structure computed at this step (and containing utterances π 84 to π 89 ) by Π; 17. The rhetorical structuring component in M's generator first switches to dialogue situation B. (seeing the MP relations computed in the previous step), then aggregates the communicative intention came from the dialogue controller into utterances π 91 and π 92 connected via Consequence(π 91 , π 92 ); finally, it appends this sub-structure to the dialogue history via P-Elab(Π, π 91 ); 18. The pragmatic interpreter in M computes two MP relations: MP(π 93 , π 94 ) and MP(π 94 , π 95 ), then it appends these three utterances to the dialogue history, via QAP(π 92 , π 93 ), QAP(π 92 , π 94 ) and QAP(π 92 , π 95 ); 19. The rhetorical structuring component in M's generator first switches to dialogue situation B. (seeing the MP relations), then aggregates the communicative intent came from the dialogue controller into utterances π 101 and π 102 that it connects via Elaboration(π 101 , π 102 ); finally, it appends this sub-structure to the dialogue history, via ACK(π 93 , π 101 ), ACK(π 94 , π 101 ) and ACK(π 95 , π 101 ); 20. The pragmatic interpreter in M first computes MP(π 103 , π 104 ), then it connects these two utterances via P-Elab(π 103 , π 104 ); finally, it appends these utterances to the dialogue context, via QAP(π 102 , π 103 ) and QAP(π 102 , π 104 ); 21. The rhetorical structuring component in M's generator first switches to dialogue context B. (seeing the MP relation computed in the previous step), then aggregates the communicative Computations performed in the discourse structure updating process

	Step no. M (Pragmatic generation component) Step no. ¬M (Pragmatic interpretation component)
	1.	(A): 3

  ) MP intention came from the dialogue controller, into utterances π 111 , π 112 , π 113 and π 114 , that it connects via the monologue rhetorical relations Elaboration(π 111 , π 112 ), Consequence(π 112 , π 113 ) and Elaboration(π 113 , π 114 ); finally, it appends this discourse sub-structure to the dialogue context, via ACK(π 103 , π 111 ) and ACK(π 104 , π 111 ); 22. The pragmatic interpretation component in M first computes the MP relations MP(π 115 , π 116 ) and MP(π 116 , π 117 ), then it appends these utterances to the dialogue history via the dialogue rhetorical relations ACK(π 114 , π 115 ), ACK(π 114 , π 116 ) and ACK(π 114 , π 117 ).

	19. 21.	DIAL MON + 3 × RR (c) (B): 1 × RR (c) DIAL (B): 3 × RR (c) MON + 2 × RR (c) DIAL	18. 20. 22.	3 × RR (c) DIAL + 2 × MP 3 × RR (c) DIAL + 1 × MP 3 × RR (c) DIAL + 2 ×

This framework has been presented in several papers, such as[Popescu et al.,

2007a, Popescu et al., 2007b, Popescu, 2007].

There is no relationship between our notion of "vein" and the homonym one in D. Cristea's Veins Theory[START_REF] Cristea | [END_REF]].

In fact, the meaning of the logic form expressed above is that there exist two utterances labeled π and π , so that π is produced by L X and addressed to L Y , and π is produced by speaker L X and addressed to L Z , so that π and π are produced at the very same time by L X , and their semantics are identical.

Please refer to Section 2 in order to see to what stems the fact that two discourse structures have something in common.

The rhetorical structuring component in M's language generator finds the MP relation previously computed, hence it switches to dialogue situation B.; then, the SDRS composed of utterances π 15 and π 16 , along with the Elaboration relation between them, and utterance π 17 are selected as candidate attachment points for the current M's turn; hence, the machine

3. for any utterance π k already in S DRS Mi 0 M :

(a) for any j ∈ {1, ..., N} \ {i 0 }: i. check whether there exists an utterance π k not produced by emitter(π k ) in S DRS i 0 j M , so that there exists a rhetorical relation ρ(π k , π k ) in S DRS i 0 j M as well: A. if yes (ρ exists), then: A1) if ρ is a contradiction relation, then: I) check whether there exists an utterance π k not produced by emitter(π k ) in S DRS i 0 j M , so that there exists a rhetorical relation ρ (π k , π k ) in S DRS i 0 j M : I.1) if yes, then:

I.1.1) if ρ is a confirmation rhetorical relation, then mark π k as noncandidate utterance for π (which implies that a rhetorical relation between π and π k will not be calculated); I.1.2) else, keep π k in the candidates list for π; I.2) else continue on step I., iterating over k = arg(π k : [Asher and Lascarides, 2003], [Popescu et al., 2007a] then: I) mark K(π k ) ∧ K(π k ) as a candidate utterance for K(π(M, i 0 )); II) update the list of compound candidates:

in this structure we have the label of utterance π k , along with the semantics of utterance π k and with the labels of the rhetorical relations connecting these two utterances (the semantics of these rhetorical relations are encoded in the simple_update/2 procedure [Popescu et al., 2007a]