Nathan Van De Wouw

Remco I Leine

Tracking Control for a Class of Measure Differential Inclusions

In this paper, we study the tracking problem for Lur'e-type measure differential inclusions. The framework of measure differential inclusions allows us to describe systems with discontinuities in the state evolution, such as mechanical systems with unilateral constraints. As a stepping stone, we present results on the stability of time-varying solutions of such systems in the scope of the convergence property. Next, this property is exploited to provide a solution to the tracking problem. The results are illustrated by application to a mechanical motion system with a unilateral velocity constraint.

I. INTRODUCTION

In this paper, we study the tracking problem for Lur'etype measure differential inclusions. Measure differential inclusions can be used to describe systems which expose discontinuities in the state and/or vector field [START_REF] Marques | Differential Inclusions in Nonsmooth Mechanical Systems[END_REF]- [START_REF] Acary | Higher order Moreaus sweeping process: mathematical formulation and numerical simulation[END_REF]. The differential measure of the state vector does not only consist of a part with a density with respect to the Lebesgue measure (i.e. the time-derivative of the state vector), but is also allowed to contain an atomic part. The dynamics of the system is described by an inclusion of the differential measure of the state to a state-dependent set (similar to the concept of differential inclusions). Consequently, the measure differential inclusion concept describes the continuous dynamics as well as the impulsive dynamics with a single statement in terms of an inclusion and is able to describe accumulation phenomena. An advantage of this framework over other frameworks, such as the hybrid systems formalism [START_REF] Van Der Schaft | An Introduction to Hybrid Dynamical Systems[END_REF], [START_REF] Goebel | Solutions to hybrid inclusions via set and graphical convergence with stability theory applications[END_REF], is the fact that physical interaction laws, such as friction and impact in mechanics or diode characteristics in electronics, can be formulated as set-valued force laws and be seamlessly incorporated in the formulation, see e.g. [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF], [START_REF] Leine | Stability and Convergence of Mechanical Systems with Unilateral Constraints[END_REF].

Stability properties of measure differential inclusions are essential in the control of such systems. In [START_REF] Leine | Stability and Convergence of Mechanical Systems with Unilateral Constraints[END_REF], results on the stability of stationary sets of measure differential inclusions (with a special focus on mechanical systems with unilateral constraints) are presented. In [START_REF] Brogliato | Absolute stability and the Lagrange-Dirichlet theorem with monotone multivalued mappings[END_REF], stability properties of an equilibrium of measure differential inclusions of Lur'e-type are studied. The nonlinearities in the feedback loop are required to exhibit monotonicity properties and, if additionally passivity conditions on the linear part of the system are assured, then stability of the equilibrium can be guaranteed. Note that this work studies the stability of stationary solutions. However, many control problems, such as tracking control, output regulation, synchronisation and observer design require the stability analysis of time-varying solutions. The research on the stability and stabilisation of time-varying solutions of non-smooth systems (especially with state jumps) is still in its infancy and the current paper should be placed in this context. It should be noted that the tracking control of measure differential inclusions has received very little attention in literature, see [START_REF] Bourgeot | Tracking control of complementarity Lagrangian systems[END_REF]- [START_REF] Menini | Asymptotic tracking of periodic trajectories for a simple mechanical system subject to nonsmooth impacts[END_REF] for works focusing on mechanical systems with unilateral constraints.

In order to study the stability of certain time-varying solutions we consider the framework of convergence. A system, which is excited by an input, is called convergent if it has a unique solution that is bounded on the whole time axis and this solution is globally asymptotically stable. Obviously, if such a solution does exist, then all other solutions converge to this solution, regardless of their initial conditions, and can be considered as a steady-state solution [START_REF] Demidovich | Lectures on Stability Theory[END_REF]- [START_REF]Convergent dynamics, a tribute to B.P. Demidovich[END_REF]. The property of convergence can be beneficial in the context of control. In many control problems, such as the tracking problem, it is required that controllers are designed in such a way that all solutions of the corresponding closed-loop system "forget" their initial conditions. Actually, one of the main tasks of feedback is to eliminate the dependency of solutions on initial conditions. In this case, all solutions converge to some steady-state solution that is determined only by the input of the closed-loop system. This input can be, for example, a command signal or a signal generated by a feedforward part of the controller or, as in the observer design problem, it can be the measured signal from the observed system.

In this paper, we will provide sufficient conditions for the convergence property of Lur'e-type measure differential inclusions, i.e. measure differential inclusions consisting of a linear plant and output-dependent set-valued nonlinearities in the feedback loop) and will exploit this property to tackle the tracking problem for such systems.

The outline of the paper is as follows. Section II provides a brief introduction to measure differential inclusions. Subsequently, we define the convergence property of dynamical systems in Section III. In Section IV, we present sufficient conditions for the convergence of Lur'e-type measure differential inclusions, which are exploited to provide a solution to the tracking problem in Section V. An illustrative example of a mechanical system with a unilateral constraint is discussed in detail in Section VI. Finally, Section VII presents concluding remarks.

NOTATION AND DEFINITIONS

Definition 1 (Maximal Monotone Set-valued Function)

A set-valued function F (x) : R n → R n is called monotone if its graph is monotone in the sense that for all (x, y) ∈ Graph(F ) and for all (x * , y * ) ∈ Graph(F ) it holds that (yy * ) T (xx * ) ≥ 0. In addition, if (yy * ) T (xx * ) ≥ α xx * 2 for some α > 0, then the set-valued map is strictly monotone. A monotone set-valued function F (x) is called maximal monotone if there exists no other monotone set-valued function whose graph strictly contains the graph of F . If F is strictly monotone and maximal, then it is called strictly maximal monotone.

Definition 2

The system ẋ = Ax + Bu, y = Cx or the triple (A, B, C) is said to be strictly passive if there exist an ε > 0 and a matrix P = P T > 0 such that

A T P + P A ≤ -εI, B T P = C. (1)

II. MEASURE DIFFERENTIAL INCLUSIONS

In this section, we introduce the measure differential inclusion

dx ∈ dΓ (t, x(t)) (2)
as has been proposed by Moreau [START_REF] Moreau | Bounded variation in time[END_REF]. The concept of differential inclusions has been extended to measure differential inclusions in order to allow for discontinuities in x(t), see e.g. [START_REF] Marques | Differential Inclusions in Nonsmooth Mechanical Systems[END_REF]- [START_REF] Brogliato | Nonsmooth Mechanics[END_REF]. With the differential inclusion ẋ(t) ∈ F (t, x(t)), in which F (t, x(t)) is a set-valued mapping, we are able to describe a non-smooth absolutely continuous time-evolution x(t). The solution x(t) : I → R n fulfills the differential inclusion almost everywhere, because ẋ(t) does not exist on a Lebesgue negligible set D ⊂ I of time-instances t i ∈ D related to non-smooth state evolution. Instead of using the density ẋ(t), we can also write the differential inclusion using the differential measure:

dx ∈ F (t, x(t)) dt, (3)
which yields a measure differential inclusion (with dt the Lebesgue measure). The solution x(t) fulfills the measure differential inclusion (3) for all t ∈ I because of the underlying integration process being associated with measures. Moreover, writing the dynamics in terms of a measure differential inclusion allows us to study a larger class of functions x(t), as we can let dx contain parts other than the Lebesgue integrable part. In order to describe a timeevolution of bounded variation which is discontinuous at isolated time-instances, we let the differential measure dx also have an atomic part:

dx = ẋ(t) dt + (x + (t) -x -(t)) dη, (4)
where dη is the atomic differential measure, being the sum of Dirac point measures, as defined in [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF], [START_REF] Leine | Stability and Convergence of Mechanical Systems with Unilateral Constraints[END_REF], and

x + (t) = lim τ ↓0 x(t + τ ), x -(t) = lim τ ↑0 x(t + τ ).
Therefore, we extend the measure differential inclusion (3) with an atomic part as well:

dx ∈ F (t, x(t)) dt + G(t, x -(t), x + (t)) dη.
Here, G(t, x -(t), x + (t)) is a set-valued mapping, which in general depends on t, x -(t) and x + (t). More conveniently, and with some abuse of notation, we write the measure differential inclusion as in [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF], where dΓ (t, x(t)) is a setvalued measure function defined as

dΓ (t, x(t)) = F (t, x(t)) dt + G(t, x -(t), x + (t)) dη. (5)
The measure differential inclusion (2) has to be understood in the sense of integration and its solution x(t) is a function of locally bounded variation which fulfills

x + (t) = x -(t 0 ) + I f (t, x) dt + g(t, x -, x + ) dη, for every compact interval I = [t 0 , t],
where the functions f (t, x) and g(t, x -, x + ) have to obey

f (t, x) ∈ F (t, x), g(t, x -, x + ) ∈ G(t, x -(t), x + (t)).
Note that for functions of locally bounded variation, the limits defining x + and x -exist. Substitution of (4) in the measure differential inclusion ( 2), [START_REF] Van Der Schaft | An Introduction to Hybrid Dynamical Systems[END_REF] gives

ẋ(t) dt + (x + (t) -x -(t)) dη ∈ F (t, x(t)) dt+G(t, x -(t), x + (t)
) dη, which we can separate in the Lebesgue integrable part ẋ(t) dt ∈ F (t, x(t)) dt, and atomic part (x

+ (t) -x -(t)) dη ∈ G(t, x -(t), x + (t)
) dη from which we can retrieve ẋ(t) ∈ F (t, x(t)) and the jump condition

x + (t) -x -(t) ∈ G(t, x -(t), x + (t)
). The latter formulation hints towards the relation with hybrid systems (or hybrid inclusions) as e.g. in [START_REF] Goebel | Solutions to hybrid inclusions via set and graphical convergence with stability theory applications[END_REF]. We note that here the above jump condition may generally be implicit in the sense that the map G(t, x -(t), x + (t)) actually depends not only on t, x -(t) but also on x + (t), which is typically the case when e.g. modelling mechanical systems with unilateral constraints. In mechanical system with e.g. inelastic impacts the map G may only depend on t and x + (t).

It should be noted that the state x of (2) may be confined to a so-called admissible set, which we denote by X . Here, we will assume that the measure differential inclusions under study exhibit the consistency property.

Definition 3 ( [8])

The measure differential inclusion (2) is consistent if for any initial condition taken in its admissible set, i.e. x 0 = x(t 0 ) is such that x 0 ∈ X , there exists a solution in forward time that resides in the admissible domain, i.e. x(t) ∈ X for almost all t ≥ t 0 .

Assumption 1

The measure differential inclusion (2) is consistent.

III. CONVERGENT SYSTEMS

In this section, we briefly discuss the definition of convergence. Herein, the Lyapunov stability of solutions of (2) plays a central role. For the definition of stability of timevarying solutions we refer to [START_REF] Pavlov | Uniform Output Regulation of Nonlinear Systems: A Convergent Dynamics Approach[END_REF], [START_REF] Willems | Stability theory of Dynamical Systems[END_REF], or to [START_REF] Leine | Stability and Convergence of Mechanical Systems with Unilateral Constraints[END_REF] for the specific case of measure differential inclusions. The definitions of convergence properties presented here extend the definition given in [START_REF] Demidovich | Lectures on Stability Theory[END_REF].

We consider systems of the form

dx ∈ F (x(t), k(t)) dt + G(x -(t), x + (t), K(t)) dη, (6)
with state x ∈ R n and where k(t), K(t) ∈ R d represent the non-impulsive and impulsive parts of the input, respectively.

The function G(x -(t), x + (t), K(t)) is assumed to be affine in K(t). In the following, we will consider the inputs k(t) : R → R d to be in the class PC d of piecewise continuous inputs which are bounded on R. Moreover, we will assume that K(t) : R → R d is zero almost everywhere (which means that the impulsive inputs are separated in time) and bounded on R; this class of functions will be denoted by

K(t) ∈ M d .
Let us formally define the property of convergence.

Definition 4

System ( 6) is said to be As follows from the definition of convergence, any solution of a convergent system "forgets" its initial condition and converges to some steady-state solution. In general, the steady-state solution xk (t) may be non-unique. But for any two steady-state solutions xk,1 (t) and xk,2 (t) it holds that xk,1 (t) -xk,2 (t) → 0 as t → +∞. At the same time, for exponentially convergent systems the steady-state solution is unique, as formulated below.

• exponentially convergent if, for every input k ∈ PC d , K ∈ M d ,

Property 1 ( [14])

If system (6) is exponentially convergent, then, for any input k ∈ PC d , K ∈ M d , the steady-state solution xk (t) is the only solution defined and bounded for all t ∈ R.

IV. CONVERGENCE PROPERTIES OF LUR'E-TYPE MEASURE DIFFERENTIAL INCLUSIONS

In this section we study the convergence properties for perturbed Lur'e-type measure differential inclusions of the following form:

dx = Ax dt + B dw(t) + D ds, y = Cx, -ds ∈ H(y) dt + H(y + ) dη, (7)
with

A ∈ R n×n , B ∈ R n×d , C ∈ R m×n , D ∈ R n×m and
x ∈ R n is the system state. Moroever, ds = λ dt + Λ dη and H(y) dt + H(y + ) dη is the differential measure of the nonlinearity in the feedback loop that is characterised by the set-valued maximal monotone mapping H(y) with 0 ∈ H(0). These properties of H(y) imply that y T h ≥ 0 for all h ∈ H(y) and y ∈ {y ∈ R m |y = Cx ∧ x ∈ X }, i.e. the action of H is passive. Furthermore, the inclusion in [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF] indicates that λ ∈ -H(y) and Λ ∈ -H(y + ). Finally, the differential measure of the time-dependent perturbation is decomposed as

dw(t) = k(t) dt + K(t) dη, where k(t) ∈ PC d , K(t) ∈ M d are functions that represent
the non-impulsive and impulsive parts of the perturbation, respectively.

In the following theorem, we state conditions under which system ( 7) is exponentially convergent. Later, we will exploit this property to solve the tracking problem. However, since the convergence property has been shown to be beneficial in a wider context, for example in the scope of output regulation, observer design and performance analysis for nonlinear systems, we state this result separately here.

Theorem 1

Consider a measure differential inclusion of the form [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF], which satisfies Assumption 1, with H(y) a (set-valued) maximal monotone mapping with 0 ∈ H(0). If the following conditions are satisfied:

1) the triple (A, D, C) is strictly passive. In other words, there exists a positive definite matrix P = P T > 0 and α > 0 for which the following conditions are satisfied:

A T P + P A ≤ -2αP , D T P = C. (8)
2) there exists a β ∈ R such that (x + ) T P BK(t) ≤ β for all x ∈ X and P satisfying (8); i.e. the energy input of the impulsive inputs is bounded from above, 3) the time instances t i for which the input is impulsive, i.e. for which K(t) is non-zero, are separated by the dwell-time τ ≤ t i+1 -t i , with

τ = δ 2(δ -1)α ln(1 + 2β δ 2 γ 2 ), γ := sup t∈R,λ(0)∈-H(0) Bk(t) + Dλ(0) P α , (9)
for some δ > 1. then the system [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF], with inputs k(t) and K(t), is exponentially convergent.

Proof: The proof is given in the appendix.

V. TRACKING CONTROL PROBLEM

In this section we study the tracking control problem for Lur'e-type measure differential inclusions of the following form:

dx = A ol x dt + B du + D ds, y = Cx, -ds ∈ H(y) dt + H(y + ) dη, (10)
i.e. du ff (t) can be considered to be a reference control (feedforward) generating x d (t).

When addressing the tracking problem, it is commonly split in two parts: firstly, finding the appropriate feedforward and, secondly, stabilising the desired solution. In the current paper, we primarily focus on the second problem. Note that also for smooth systems the existence of the feedforward is a natural assumption (think of the solvability of the regulator equations as a natural assumption in the scope of output regulation [START_REF] Pavlov | Uniform Output Regulation of Nonlinear Systems: A Convergent Dynamics Approach[END_REF], [START_REF] Isidori | Output regulation of nonlinear systems[END_REF]).

We propose to tackle the tracking problem by means of a combination of Lebesgue measurable linear error-feedback and a possibly impulsive feedforward control:

du = u f b (x, x d (t)) dt + du ff (t), (12)
with

u f b (x, x d (t)) = N (x -x d (t)), du ff (t) = p ff (t) dt+P ff (t) dη,
where N ∈ R d×n is the feedback gain matrix. We restrict the energy input of the impulsive control action P ff (t) to be bounded from above:

(x + ) T BP ff ≤ β.
Note that this condition puts a bound on the jumps in the desired trajectory x d (t) which can be realised. Combining the control law [START_REF] Menini | Asymptotic tracking of periodic trajectories for a simple mechanical system subject to nonsmooth impacts[END_REF] with the system dynamics (10) yields the closed-loop dynamics:

dx = Ax dt + D ds + B(-N x d (t) dt + du ff (t)), y = Cx, -ds ∈ H(y) dt + H(y + ) dη, (13)
with A = A ol + BN . In the next result, the convergence property of the closed-loop system is exploited to solve the tracking problem.

Theorem 2

Consider a measure differential inclusion of the form [START_REF] Bourgeot | Tracking control of complementarity Lagrangian systems[END_REF] Proof: Since the conditions of Theorem 1 are satisfied, all solutions of the closed-loop system (13) converge to each other exponentially, see (21) in the proof of Theorem 1. Since the desired solution is a solution of ( 13), for x(0) = x d (0), by the choice of the feedforward, see Assumption 2, the desired solution is a globally exponentially stable solution of [START_REF] Demidovich | Lectures on Stability Theory[END_REF]. described by [START_REF] Bourgeot | Tracking control of complementarity Lagrangian systems[END_REF] with

VI. EXAMPLE OF A MECHANICAL SYSTEM WITH

A ol =   0 -1 1 c m1 -b1+b2 m1 b1 m1 -c m2 b1 m2 -b1 m2   , B =   0 1 m1 0   , (14)
D T = 0 0 1 m2 and C = 0 0 1 . The state vector is given by x = q 2 -q 1 u 1 u 2 T , with q 1 and q 2 the displacements of m 1 and m 2 , respectively, and u 1 and u 2 the velocities of m 1 and m 2 , respectively. The differential measure ds = H(y) dt + H(y + ) dη of the force in the oneway clutch is characterised by the scalar set-valued maximal monotone mapping H(x) = Upr(x). The set-valued function Upr(x) is the unilateral primitive [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF]: -y ∈ Upr(x) ⇔ 0 ≤ x ⊥ y ≥ 0 ⇔ x ≥ 0, y ≥ 0, xy = 0, being a maximal monotone operator. We adopt the following system parameters:

m 1 = m 2 = 1, c = 10, b 1 = 1 and b 2 = -1.4.
The desired velocity of the second mass is a periodic sawtooth wave with period time T :

x d3 (t) =          mod (t, T ) for 0 ≤ mod (t, T ) ≤ T 4 T 2 -mod (t, T ) for T 4 ≤ mod (t, T ) ≤ T 2 0 for T 2 ≤ mod (t, T ) ≤ T ,
where these equations represent a ramp-up, ramp-down, and a deadband phase, respectively. The signal x d3 (t) for T = 1 s is shown by the dotted line in Fig. 2. The desired trajectory x d3 (t) is a periodic signal which is time-continuous but has three kinks in each period. Kinks in x d3 (t) can be achieved by applying an impulsive force on the first mass which causes an instantaneous change in the velocity x 2 = u 1 and therefore a discontinuous force in the damper b 1 . The oneway clutch on the second mass prevents negative values of x d3 and no impulsive force on the first mass is therefore necessary for the change from ramp-down to deadband. In a first step, the signals x d1 (t), x d2 (t) and ds(t) are designed such that

ẋd1 (t) = -x d2 (t) + x d3 (t) dx d3 (t) = - c m 2 x d1 (t) - b 1 m 2 -x d2 (t) + x d3 (t) dt + 1 m 2 ds(t), with -ds(t) ∈ Upr(x d3 (t)) dt + Upr(x + d3 (t)) dη, (15)
for the given periodic trajectory x d3 (t). The solution of this problem is not unique as we are free to chose ds(t) ≥ 0 for x d3 (t) = 0. By fixing ds(t) = ṡ0 dt to a constant value for x d3 (t) = 0 (i.e. ṡ0 is a constant), we obtain the following discontinuous differential equation for x d1 (t):

ẋd1 = m2 b1 (-ẋd3 (t) -c m2 x d1 ) x d3 (t) > 0, m2 b1 (-ẋd3 (t) -c m2 x d1 + 1 m2 ṡ0 ) x d3 (t) = 0. (16)
The numerical solution of x d1 (t) gives (after a transient) a periodic signal x d1 (t) and x d2 (t) = -ẋd1 (t) + x d3 (t) (see the dotted lines in Figs. 4 and5 which are mostly hidden by the solid lines). We have taken ṡ0 = 1. Subsequently, the feedforward input du ff = p ff dt + P ff dη is designed such that

du ff = m 1 dx d2 -cx d1 + b 1 (-x d2 + x d3 ) -b 2 x d2 dt (17)
and it therefore holds that

x(t) = x d (t) for t ≥ 0 if x(0) = x d (0)
, where x(t) is a solution of ( 10), [START_REF] Pavlov | Uniform Output Regulation of Nonlinear Systems: A Convergent Dynamics Approach[END_REF], with du = du ff . The feedforward input du ff / dt is shown in Fig. 6 and is equal to p ff (t) almost everywhere. Two impulsive inputs P ff (t) per period can be seen at the time-instances for which there is a change from 'ramp-up to ramp-down' and from 'deadband to ramp-up'. Next, we implement the control law (12) on system [START_REF] Bourgeot | Tracking control of complementarity Lagrangian systems[END_REF] with the feedforward du ff as in [START_REF] Willems | Stability theory of Dynamical Systems[END_REF]. We choose N = 0 -4 0 which ensures that ( 8) is satisfied with

P =   34 -10.5 0 -10.5 6 0 0 0 1   , α = 0.25. (18)
Consequently, the closed-loop system (10), ( 14), ( 12), ( 17) is exponentially convergent. Fig. 2 shows the closed-loop dynamics for which the desired periodic solution x d (t) is globally exponentially stable. Fig. 3 shows the open-loop dynamics for which there is no state-feedback. Without feedback, the desired periodic solution x d (t) is not globally attractive, not even locally, and the solution from the chosen initial condition is attracted to a stable period-2 solution. Clearly, the system without feedback is not convergent. For both cases the initial condition x(0) = 0.16 2.17 0 T was used. Figs. 4 and5 show the time-histories of x 1 (t) and x d1 (t), respectively x 2 (t) and x d2 (t), in solid and dotted lines. Jumps in the state x 2 (t) and desired state x d2 (t) can be seen on time-instances for which the feedforward input is impulsive.

VII. CONCLUSIONS

In this paper, the tracking problem for Lur'e-type measure differential inclusions is studied. The framework of measure differential inclusions allows us to describe systems with discontinuities in the state evolution, such as mechanical systems with unilateral constraints. In the scope of the tracking problem, the stability properties of time-varying solutions play a central role. Therefore, we have presented results on the stability of time-varying solutions of such systems in the terms of the convergence property. Next, this property is exploited to provide a solution to the tracking problem, where the desired solution may exhibit state jumps. The results are illustrated by application to a mechanical motion system with a unilateral velocity constraint. exponentially (i.e. the system is exponentially incrementally stable):

x + 2 (t) -x + 1 (t) ≤ λ max (P ) λ min (P ) e -α(t-t0) x - 2 (t 0 ) x - 1 (t 0 ) , (21)
for t ≥ t 0 and where λ max (P ) and λ min (P ) represent the maximum and minimum eigenvalue of P , respectively.

Let us now show that there exists a unique (steady-state) solution that is bounded on t ∈ R. Consider, hereto, the Lyapunov candidate function W = 1 2 x T P x. The differential measure of W can be decomposed as dW = Ẇ dt+(W + -W -) dη. We first evaluate the density Ẇ :

Ẇ =x T P (Dλ + Ax + Bk(t)) =x T P D(λ -λ(0)) + 1 2 x T (P A + A T P )x + x T P Bk(t) + x T P Dλ(0), (22)
with λ ∈ H(y) and λ(0) ∈ H(0). Due to the satisfaction of ( 8) and the monotonicity of H(y), we have that Ẇ ≤ -α x 2 P + x P Bk(t) + Dλ(0) P . Note that Ẇ < 0 for x satisfying x P > γ with γ defined in [START_REF] Brogliato | Absolute stability and the Lagrange-Dirichlet theorem with monotone multivalued mappings[END_REF]. Let us use the fact that the function -(1-1 δ )α x 2 P > -α x 2 P +γα x P for x P > δγ, where δ > 1 is an arbitrary constant and γ > 0. It therefore holds that

Ẇ ≤ -2 1 - 1 δ αW for x P ≥ δγ, δ > 1. (23)
Subsequently, we consider the jump W + -W -of W : W + -W -= 1 2 (x + +x -) T P (x +x -), with x + -x -= DΛ+ BK(t) and Λ ∈ -H(Cx + ). Elimination of x -, exploiting the passivity of H(y) and using the matrix equality in [START_REF] Leine | Stability and Convergence of Mechanical Systems with Unilateral Constraints[END_REF] gives

W + -W -= 1 2 (2x + -DΛ -BK(t)) T P (DΛ + BK(t)) = (x + ) T (P DΛ + P BK(t)) - 1 2 DΛ + BK(t) 2 P ≤ y + T Λ + x + T P BK(t) ≤ β, (24)
in which we used condition 2 in the theorem. Then, due to (23), for the non-impulsive part of the motion it holds that if x(t 0 ) P ≤ δγ then x(t) P ≤ δγ for all t ∈ [t 0 , t * ] (if no state resets occur in this time interval). Moreover, as far as the state resets are concerned, (24) shows that a state reset from a state

x -(t i ) ∈ V with V = {x ∈ X | x P ≤ δγ} can only occur to x + (t i ) such that W (x + (t i )) := 1 2 x + (t i ) 2 P ≤ W (x -(t i ))+β ≤ 1 2 δ 2 γ 2 +β.
During the following open time-interval (t i , t i+1 ) for which K(t) = 0, the function W evolves as W (x -(t i+1 )) = W (x + (t i )) + (ti,ti+1) dW , which may involve impulsive motion due to dissipative impulses Λ. Let t V ∈ (t i , t i+1 ) be the time-instance for which x -(t V ) P = δγ. The function W will necessarily decrease during the time-interval (t i , t V ) due to (23) and W + -W -= (x + ) T (P DΛ)- 1 2 DΛ 2 P ≤ 0 (the state-dependent impulses are passive due to passivity of H(y)). It therefore holds that

W (x -(t V )) ≤ e -2(1-1 δ )α(tV -ti) W (x + (t i )), (25)
because dW ≤ -2(1 -1 δ )αW dt + (W + -W -) dη ≤ -2(1 -1 δ )αW dt for positive measures. Using W (x -(t V )) = 1 2 δ 2 γ 2 and W (x + (t i )) ≤ 1 2 δ 2 γ 2 + β in the exponential decrease (25) gives

W = x ∈ X | 1 2 x 2 P ≤ 1 2 δ 2 γ 2 + β (26)
is a compact positively invariant set. Since the size of this positively invariant set is of no concern we can take the limit of the expression for τ in (9) for δ → ∞: lim δ→∞ δ 2(δ-1)α ln(1 + 2β δ 2 γ 2 ) = 0, which indicates that the dwell-time can be taken arbitrarily small. It therefore suffices to assume that the impulsive inputs K(t) are separated in time (as required in the theorem) to conclude that the system exhibits a compact positively invariant set, defined in (26). Now, we use Lemma 2 in [START_REF] Yakubovich | Matrix inequalities method in stability theory for nonlinear control systems: I. absolute stability of forced vibrations[END_REF], which formulates that if a dynamic system exhibits a compact positively invariant set, then the existence of a solution that is bounded for t ∈ R is guaranteed. We will denote this 'steady-state' solution by x(t). The original lemma is formulated for differential equations (possibly with discontinuities, therewith including differential inclusions, with bounded right-hand sides). Here, we use this lemma for measure differential inclusions and would like to note that the proof of the lemma allows for such extensions if we only require continuous dependence on initial conditions. The latter is guaranteed for the Lur'etype measure differential inclusions under study, because the system is exponentially incrementally stable (as shown in the first part of the proof), which implies continuous dependence on initial conditions.

The combination of the fact that all solutions are exponentially stable with the fact that there exists a (steady-state) solution x(t), of locally bounded variation, which is bounded for t ∈ R for which it is defined, completes the proof of the fact that the system (7) is exponentially convergent according to Definition 4.

Fig. 1 :

 1 Fig. 1: Motor-load configuration with one-way clutch and impulsive actuation.

Fig. 2 :

 2 Fig. 2: x3(t) (solid) and x d3 (t) (dotted) for the case of feedback and feedforward control.

Fig. 3 :

 3 Fig. 3: x3(t) (solid) and x d3 (t) (dotted) for the case of only feedforward control.

Fig. 4 :

 4 Fig. 4: x1(t) (solid) and x d1 (t) (dotted) for the case of feedback and feedforward control.

Fig. 5 :Fig. 6 :

 56 Fig. 5: x2(t) (solid) and x d2 (t) (dotted) for the case of feedback and feedforward control.

  there exists a solution xk (t) satisfying the following conditions: (i) xk (t) is defined for almost all t ∈ R (ii) xk (t) is bounded for all t ∈ R for which it is defined, (iii) xk (t) is globally exponentially stable.The solution xk (t) is called a steady-state solution (where the subscript emphasizes the fact that the steady-state solution depends on the input, characterised by k(t) and K(t)).

  The desired trajectory x d (t) is a function of locally bounded variation and there exists du ff (t) = p ff (t) dt + P ff (t) dη, with both p ff (t) ∈ PC d and P ff (t) ∈ M d , such that x d (t) satisfies dx d (t) = A ol x d (t) dt + B du ff (t) + D ds,

	the differential The tracking problem considered in this work is formalised measure of the control action. as follows: Tracking problem: Design a control law for du that, based on infor-mation on the desired state trajectory x -ds ∈ dH(Cx d (t)) dt + H(Cx + d (t)) dη,

with A ol ∈ R n×n and du = p dt + P dη is d (t) and the measured state x, renders x(t) → x d (t) as t → ∞ and the states of the closed-loop system are bounded. To solve this problem, we adopt the following assumption: Assumption 2

  , which satisfies Assumption 1, with H(y) a (set-valued) maximal monotone mapping with 0 ∈ H(0). Suppose the desired trajectory x d (t) satisfies Assumption 2 with du ff (t) being the corresponding feedforward. If the conditions in Theorem 1 are satisfied, with k(t) := -Kx d (t) + p ff (t) and K(t) := P ff (t), then the desired solution x d (t) is a globally exponentially stable solution of the closed-loop system (13), i.e. the tracking problem is solved.

  1 2 δ 2 γ 2 ≤ e -2(1-1 δ )α(tV -ti) ( 1 2 δ 2 γ 2 + β) or t V -t i ≤ ).Consequently, if the next impulsive time-instance t i+1 of the input is after t V , then x(t) has enough time to reach V. Hence, if the impulsive time-instance of the input are separated by the dwell-time τ given in (9), i.e. t i+1 -t i ≥ τ , then the set

	2β	δ 2(δ-1)α ln(1 +
	δ 2 γ 2

APPENDIX

In this proof, we will show that system [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF] is exponentially convergent. Hereto, we first show that the all solutions of the system converge to each other exponentially. The next step in the proof of exponential convergence is to show that there exists a unique (steady-state) solution that is bounded on t ∈ R.

Consider two solutions x 1 (t) and x 2 (t) of the closedloop system [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF] and a Lyapunov candidate function V = 1 2 x 2x 1 2 P , where we adopt the notation ξ 2 P = ξ T P ξ. Consequently, the differential measure of V satisfies: dV =

The differential measure of V has a density V with respect to the Lebesgue measure dt and a density V + -V -with respect to the atomic differential measure dη, i.e. dV = V dt + (V + -V -) dη. We first evaluate the density V :

where we used that both solutions x 1 and x 2 correspond to the same perturbation dw(t), the fact that ( 8) is satisfied and the fact that the mapping H(y) is monotone. Subsequently, we consider the jump

1 and x - 2 and exploiting the monotonicity of H(y) gives

where we used the matrix equality in [START_REF] Leine | Stability and Convergence of Mechanical Systems with Unilateral Constraints[END_REF]. Using [START_REF] Yakubovich | Matrix inequalities method in stability theory for nonlinear control systems: I. absolute stability of forced vibrations[END_REF] and (20), the differential measure of V satisfies dV ≤ -2αV dt, along solutions of [START_REF] Ch | Set-Valued Force Laws, Dynamics of Non-Smooth Systems[END_REF]. It therefore holds that V strictly decreases (exponentially) over every Lebesgue non-negligible time-interval as long as x 2 = x 1 . In turn, this implies that all solutions of (7) converge to each other


Veronica Dahl
email: veronica@cs.sfu.ca

Philippe Blache

Extracting Selected Phrases through Constraint Satisfaction

Keywords: Constituency Const = {N, Det, Adv, Adj, Prep, NP} Linearity Prep; Prep ≺ NP

We present in this paper a CHR based parsing methodology for parsing Property Grammars. This approach constitutes a flexible parsing technology in which the notions of derivation and hierarchy give way to the more flexible notion of constraint satisfaction between categories. It becomes then possible to describe the syntactic characteristics of a category in terms of satisfied and violated constraints. Different applications can take advantage of such flexibility, in particular in the case where information comes from part of the input and requires the identification of selected phrases such as NP, PP, etc. Our method presents two main advantages: first, there is no need to build an entire syntactic structure, only the selected phrases can be extracted. Moreover, such extraction can be done even from incomplete or erroneous text: indication of possible kinds of error or incompleteness can be given together with the proposed analysis for the phrases being sought.

Introduction

Extracting selected phrases from written or spoken text is an important step for many useful applications of language processing. For instance, concept extraction or text summarization can benefit from a preliminary identification of all noun phrases or verbs, to be further processed, e.g. through consulting a concept hierarchy; question answering can focus on noun phrases or verbs at least for the replies to be given; command oriented systems might focus on verb phrases; temporal systems, on time adverbial phrases, etc.

Ideally we want to be able to extract concepts from text produced in real life conversation, which typically is incomplete, often not perfectly grammatical, and sometimes erroneous. Imperfections can result from normal human error in actual speech, or be introduced by machines, as in the case of text produced from speech recognition systems, which are renowned for their error-proneness.

Flexible parsing techniques offer great advantages in this perspective. Among possible solutions, constraint-based approaches allow us to use the same parsing mechanism (constraint satisfaction) whether the grammar is incomplete, heterogeneous, etc. Moreover, provided that no extra mechanisms than satisfaction are used, constraints can be relaxed in accordance to user-defined criteria. In particular, this can be done selectively (for some sentences but not others). For instance, we may want to express that a noun requires a determiner inside a noun phrase, unless we are dealing with a generic statement, as in "Lions sleep". To this effect, we can test the conditions relevant to genericity in the body of the rule that relaxes the constraint imposing a determiner, so that only upon them being satisfied will the constraint be relaxed.

Property-based linguistic models (see [START_REF] Bès | Propriétés et analyse d'un langage[END_REF][START_REF] Bès | La phrase verbale noyau en francais[END_REF], [START_REF] Blache | Property Grammars: A Fully Constraint-Based Theory[END_REF]) view linguistic constraints as properties between sets of categories, rather than in the more traditional terms of properties on hierarchical representations of completely parsed sentences. This view has several advantages, such as allowing for mistakes to be detected and pointed out rather than blocking the analysis altogether, and facilitates dynamic processing of text produced on the fly, as needed for the growing number of applications involving speech.

In this paper we refine a methodology for Property Grammars (cf. [START_REF] Blache | Property Grammars: A Fully Constraint-Based Theory[END_REF]) first proposed in [START_REF] Dahl | Directly Executable Constraint Based Grammars[END_REF] which relies exclusively on constraints. It controls the parse through head-driven analysis, provides a direct interpretation of this formalism while preserving all its theoretical properties at the implementation level, and can focus on specific phrases-in the case of our toy implementation, noun phrases-as mandated by a user's modular and easy to change command. As the implementation language, we use a specialized grammatical formalism called CHRG (Constraint Handling Rule Grammars) described in [START_REF] Christiansen | CHR as grammar formalism, a first report[END_REF] on top of CHR [START_REF] Frühwirth | Theory and Practice of Constraint Handling Rules[END_REF].

Representing syntax with constraints

The basic idea of Property Grammars is to represent different kinds of syntactic information separately. In this approach, syntactic structure is not expressed in terms of hierarchy, but only by means of relations between categories. We describe in this section how to represent such relations in terms of constraints and take advantage of this in the perspective of a direct constraint-based implementation.

Background: Property Grammars

In our approach, syntactic properties rely on relations that do not have specific topological constraints (they can for example be crossed). Categories are described by means of such relations. As a consequence, the notion of constituency is no longer crucial for the description process: a category is specified by a set of properties rather than by a set of constituents. The fact that several categories belong to a network of relations indicates that they characterize an upper-level category. A syntactic category is then described by a set of properties which represent relations between other categories (lexical or syntactic).

In this approach, the goal is to make explicit all the different relations that can exist. We distinguish in this perspective the following types of information:

linear precedence, which is an order relation between categories, -subcategorization, which indicates coocurrence relations between categories or sets of categories, -the impossibility of cooccurrence between categories, -the impossibility for a category to be repeated, -the minimal set of obligatory constituents (usually one single constituent) which is the head, -semantic relations between categories, in terms of dependency.

These different kinds of information correspond to different properties, respectively: linearity, requirement, exclusion, unicity, obligation, dependency. Such information can always be expressed in terms of relations between categories, as shown in the following examples:

-Linear precedence: Det ≺ N (a determiner precedes the noun) -Dependency: AP ❀ N (an adjectival phrase depends on the noun) -Requirement: V[inf ] ⇒ to (an infinitive comes with to) -Exclusion: seems ⇔ ThatClause[subj] (the verb seems cannot have That clause subjects)

All syntactic categories are characterized by a set of relations that forms a connected graph. The syntactic description of a language consists of all the different relations that can be expressed between categories. A relation (also called a property) can be conceived as a constraint on the set of categories. A grammar is then a set of constraints and satisfiability becomes the core of the parsing process (see [START_REF] Blache | Property Grammars: a Flexible Constraint-Based Approach to Parsing[END_REF]). What is interesting in this approach is that no implicit information, for example under the form of a specific mechanism, is needed. In particular, there is no need to build a structure before being able to verify its properties as it is the case with classical generative approaches (although for convenience given what researchers are used to, we do provide a tree as well as a side effect of parsing). Moreover, using satisfiability alone has important consequences in the conception of the syntactic structure. Evaluating a constraint system for a given set of categories allows us to specify precisely the set of properties that are verified. In the same way, in the case of ill-formed input, such evaluation identifies precisely the set of satisfied and violated constraints. Such a result is then of deep interest in the sense that it identifies precisely all the specificities of an input. In Property Grammars this information constitutes the output of a parse, which is but the status of the constraint system after evaluation.

The parsing schema

The basic mechanism in constraint satisfaction problems is to find, for a given set of variables, an assignment that satisfies the constraint system. In the problem addressed here, the variables are taken from the set of categories. An assignment is given from an input (i.e. the sentence to be parsed). Starting from the set of lexical categories corresponding to the words of the sentence, all possible assignments (i.e. subsets of categories) are evaluated. When a syntactic category is characterized, it is added to the set of categories to be evaluated. This approach is basically incremental in the sense that any subset of categories can be evaluated. This means that an assignment A can be completed by adding other categories. When syntactic categories are inferred after the first step of the process, it is then possible to complete the first assignments (made with lexical categories) with new syntactic ones.

We have seen that in Property Grammars, a category is described by a set of constraints. But reciprocally, it is possible to identify a category from a given property. This is typically the case with properties expressing relationships between categories, such as linearity, requirement, obligation and dependency. Evaluating such properties makes it possible to infer that the syntactic category to which the property is attached is being characterized. We have referred to these properties under the collective name of selection constraints.

The role of selection constraints is central to our approach. The reason such constraints allow us to select the characterized category is that they are local to this category. Moreover, in some cases they have a global scope over the category : their satisfiability value (i.e. satisfied or violated) cannot change for a given category whatever the subset of constituents. As soon as the constraint can be evaluated, this value is permanent. For example, when a linearity or a dependency constraint is satisfied, adding new constituents to the category cannot change this fact. Other kinds of constraints have to be re-evaluated at each stage. For instance, when adding a new category, we need to verify that unicity and exclusion are still satisfied. In all that follows, we call the latter filtering constraints. Contrary to selection constraints, one cannot infer the materialization of a syntactic category from their evaluation. They play a filtering role in the sense that they rule out some construction. Yet another type of constraint, which we call recoverable constraints can succeed by the incorporation of one more category into a given phrase for which, without this added category, the constraint failed.

Let us examine what the consequences are on constraint evaluation. As explained above, the principle consists in completing original assignments with new categories when they are inferred. Insofar as the evaluation of selection constraints (as soon as this evaluation can be performed) is valid through a complete assignment, whatever its constituents, it is not necessary to re-calculate it. In other words, when an assignment A is made by completing another assignment A ′ , the set of selection constraints of A ′ is inherited by A. We describe in the next section the different types of properties and their consequence for new assign-ments in more detail, with respect to a specific instance of the general parsing schema we present here.

In the following, we note selection and filtering constraints as R select (C, XP ) and R f ilter (C, XP ) in which C is the constraint and XP the syntactic category to which the constraint is associated. For some assignment A, a constraint is relevant (or can be evaluated) when the categories of A are a subset of the categories involved in C. We note the fact that A can be evaluated for some constraint as follows: A/R select (C, XP ). We note the set of filtering and selection constraints for a given category XP by R(C, XP ) = R select (C, XP )∪R f ilter (C, XP ). Finally, we note the state of the constraint system Σ for an assignment A after evaluation by SAT (A, Σ). Each category is indexed by its boundaries, noted c (i,j) .

Let K be the set of categories, noted c i , let i, j, k some indexes such that i < j < k:

1. A ← {c i , ..., c j } 2. if A/R select (C, XP ) 3. instantiate XP (i,j) 4. Σ = R(C, XP ) 5. Char(A) ← SAT (A, Σ) 6. while SAT (A, Σ) acceptable 7. A ← A ∪ {c k } 8. Σ = R(C, XP ) 9. Char(A) ← SAT (A, Σ) 10. k ← k + 1
In this algorithm schema, the mechanism consists in evaluating the characterization of all sequences of categories. The specificity of selection constraints is used as a control device: when a selection constraint is satisfied, the described category XP is instantiated and the related set of constraints Σ is activated. It is interesting to notice that a syntactic category can be projected by any selection constraint, independently from any constituency information (especially the head). Each new assignment, built by adding new juxtaposed categories to the initial set, is then evaluated. Such a completion of the initial assignment is possible when the satisfiability of Σ for this new assignment is acceptable (cf. line 7). This notion implements the parser flexibility. When we need to build only grammatical structures, acceptability is reduced to satisfiability. But for more flexible parsing needs (e.g. spoken language), constraints can be relaxed. The set of constraints to be relaxed, their number, etc. is indicated at this point. Finally, the general process is repeated until no new category can be added.

This parsing schema proposes a general framework in which constraints can be integrated. Each property is implemented by a constraint solver. The mechanism consists in building a characterization for each possible assignment (i.e. any subset of categories). The particularity of selection constraints plays an important role in this schema. In a classical bottom-up technique, the mechanism consists in finding a handle which links a set of categories with a non-terminal. Such a relation in our approach is established between a set of properties and a category. In contrast with phrase-structure techniques, the notion of constituency does not play any particular role. As soon as a selection constraint is evaluated, the corresponding syntactic category is added to the set of categories and all the constraints participating in its description are activated. Concretely, all the selection constraints can be evaluated with no need to know the upper-level category, in contrast to filtering constraints which have to be activated.

Different strategies can be applied according to the needs of the parse. A restricted application stipulates that all constraints have to be satisfied. In this case, only grammatical characterization are built, all ill-formed structures are ruled out. For more flexible applications, typically in the case of parsing spoken language material, constraints have to be relaxed. In this case, characterizations can contain violated constraints. We next describe how CFGs are used in our approach to achieve direct interpretation in these kinds of flexible applications.

Direct interpretation in CHR

Our methodology for Property Grammar parsing has been designed to provide direct interpretation of Property Grammar rules. This is an interesting contribution with respect to Property Grammars themselves, but also a novel and important proof-of-concept that can lead the way for any constraint-based parsing formalism which relates categories contextually through their properties. To the best of our knowledge, our methodology is the first one that permits an expression of such parsing constraints which is directly and efficiently executable. Thus, we can say that our approach represents for grammars based on contextual properties what DCGs represent for context-free grammars, in the sense that they are as directly executable descriptive formalisms as DCGs3 .

In this section we describe the different components of our methodology : the notion of extended categories, which includes not only traditional information such as category names and features, but also the category's characterization in terms of satisfied and unsatisfied constraints; the modular notation through which a user defines the properties of a given grammar, the single rule through which parsing proceeds, and the analysis of property inheritance which is used in our system.

Extended Categories

Extended categories are of the form: cat(Name, Features, Graph, Sat, Unsat) where Name is the category name, Features a list of features associated with the category (which may be used to check some of the properties between categories), Graph is a parse tree which is obtained as a side effect of parsing (which is built even in those cases of incorrect input), and Sat and Unsat are respectively, the list of satisfied and unsatisfied properties that the immediate daughters of Name inside the Graph verify between them. In the case of single word categories, the Sat and Unsat lists will be empty. These categories are created automatically from user's lexical definitions, which are done in terms of CHRG. For instance, a user's entry:

[the] ::> cat(det, [singular, masculin]).

(1) compiles into:

[the] ::> cat(det, [singular, masculin], det(the), [], []).

(2) Because these are CHRG rules (i.e., grammar rules, as opposed to plain CHR rules), word boundaries are carried invisibly. If needed, we can retrieve them in a grammar rule by adding :(Start,End) after the category, which will unify Start to the starting point of the category, and End to its end point, or we can write a plain CHR rule that looks at cat/5 not as a grammar rule, but as the CHR constraint it compiles into, in which case Start and End can be retrieved as the two first arguments of the corresponding constraint, cat/7.

User defined properties

Our system allows the user to enter the specific linear precedence, dependency, requirement, exclusion, constituency and unicity properties that apply to the grammar being defined, through simple primitive predicates which are respectively prec/3,dep/3,req/3, exclude/3, cons/2, and one/2. Figure 3.2 exemplifies for a simplified noun phrase.

Linear precedence Dependence

Constituency prec(det,n,sn). dep(det,n,sn). cons(sn,[det,adj,sa,n]). prec(det,sa,sn). dep(n,sa,sn). cons(sa,adj]). prec(n,sa,sn).

Unicity

Exclusion Requirement Phrases one(det,sn). exclude(sa,sup,sn). req(n,det,sn). xp(sn).

xp(sa).

Fig. 1. User defined properties

It is to be noted that while the user's definition of constituency is not rigorously needed (since, as we have seen, when selection properties are verified, the determination of constituency follows as a side effect), having it explicitly defined results in improved efficiency. Likewise, phrase definitions can be inferred from any of the other properties, but defining them explicitly makes the system easier and more readable. The user's definitions of properties will be called from system predicates which verify each of these properties on a given set of categories, as we shall see next.

A single rule for inferring all new categories

Conceptually, little more than a single rule is enough for a string's complete bottom-up parse from contiguous constituents. This rule combines two consecutive categories (one of which is of type XP or obligatory) into a third, by testing each of the properties on the pair and creating the new property lists through property inheritance (cf. next section). Its form is described in Fig. 2.

Fig. 2. New Category Inference

This rule tests that one of the two categories (left or right) is a kernel (a phrase head) and the other one of its extension (i.e., complement or adjunct), and then assigns the corresponding features. It then successively tests each of the PG properties among those categories, incrementally building as it goes along the lists of satisfied and unsatisfied properties. Finally, it infers a new category of type XP spanning both these categories, with the finally obtained Sat and Unsat lists as its characterization. In practice, this rule unfolds into two symmetric parts, to accommodate the situation in which the XP category appears before the category Cat which is to be incorporated into it.

Constituents with discontinuities must also be allowed, for completeness. In this case we consider two categories where the end node of the first does not coincide with the start node of the second. Our current research does not yet include discontinuous constituents, for which further linguistic constraints for avoiding combinatorial explosion need to be incorporated.

The parser here described includes as well a sophisticated analysis of types of properties which helps determine how the properties that have been found to hold (fail) in a given phrase are inherited or not by the new phrase comprising that phrase plus a category being incorporated into it. Knowing whether a given property needs to be simply inherited (in which case it just remains as is in the new list of properties) or affects previously recognized properties, and how, allows us an efficient way to move from one list of properties to the next. This analysis is beyond the scope of the present paper. Complete details can be found in [START_REF] Dahl | Directly Executable Constraint Based Grammars[END_REF]. The same work proposes a detailed analysis on how to refine the notion of characterization. For our purposes here, let us just say that the user can declare certain properties as relaxed, which results in sentences containing errors related to those properties to be accepted nevertheless, while indication of their failure is given in the output (in the form of a list of unsatisfied properties).

One of the interests of our approach lies in its flexibility. The kind of parsing techniques presented above makes it possible to parse substructures as well as subpart of the input. This functionality is useful to deal with part of the input for which no information can be built. It is for example the case with possibly long lists of juxtaposed NP, frequent in spoken languages but for which no specific syntactic relation can be given. But it is also interesting for some applications in which the entire syntactic structure or, in other words, the description of all possible syntactic categories is necessary. This is the case for question-answering, information extraction, or terminological applications based on NP recognition. In these systems, the knowledge of the argument structure, or the precise description of the relations between the different categories is not necessary. We basically need to know what are the NP s of the input and, if possible, their contents. Several techniques can be applied for this (see [START_REF] Osborne | MDL-based DCG Induction for NP Identification[END_REF], [START_REF] Kim | Applying System Combination to Base Noun Phrase Identification[END_REF]) that usually rely on the specification of patterns defining base NP s. In such approaches, it is difficult or even impossible to identify the kind of relations that links the different constituents of the NP. In other words, it is not possible to choose the granularity level. In PG, this possibility exists, simply by stipulating the constraints that have to be satisfied among the entire constraint system that forms the grammar. This means that any category can be extracted. Moreover, the description granularity of the extracted category can also be chosen, according to the needs.

Implementation details

Concretely, all irrelevant information is simply not taken into account. For example, the categories that do not participate to a NP are ignored. The only special mechanism needed to skip them is a filtering set of predicates which ensures that every category different from NP is deleted from the constraint store upon the parse having finished, as first proposed in [START_REF] Christiansen | CHR Grammars" in the International Journal on Theory and Practice of Logic Programming[END_REF]. For the case of noun phrases, we need to define a constraint we will call cleanup, which we will call after the analysis of any phrase, and, for every category X different from an NP, a simpagation rule of the form: cat(X, , , , ), !cleanup <:> true.

(3)

The exclamation mark combined with the rewrite symbol shown indicate sympagation in CHRG: once the parse is completed and cleanup is put in the store, the above rule removes from the store the matching category, and the constraint cleanup remains for further use, in order to remove all categories different from np.

The generation of such rules can be automated from a user's command to declare what phrases to focus on, e.g.:

: -focus(np). (4) Similarly, we can include a mechanism for only leaving the outermost NP s in the case of embedded ones. This option can be specified by the user through the command : -outermost(np).

(5) It is also possible to imagine an easy reuse from a language to another, simply by adapting the properties. In the case of basic NP s, very close properties are used for French and English.

Experiment

We did some experiments in applying this technique to a French medical corpus. The following example illustrates the identification of some noun phrases, extracted together with their syntactic characterizations. In these examples, the output contains the type of the phrase (in this experiment, the noun phrase), its morphosyntactic properties, its constituents and its characterization. This last part of the output, as explained in the second section, is formed by the set of satisfied and violated properties.

The example (6) illustrates the case of a simple NP, formed with a determiner and a noun. Its characterization shows for example the satisfaction of a precedence constraint between the determiner and the noun, some uniqueness relations for these constituents as well as a mandatory cooccurrency between the determiner and the noun.

Input les cellules (the cells)

Output cat(np,[plu,masc], sn(det(les),n(cellules)), [prec(det,n), dep(det,n), unicity(det), unicity(n), exige(n,det), exclude(name,det), exclude(name,n)],[])

(6)
The second example, presented in (7), shows the integration of an embedded AP. In this example, the AP (composed with a single adjective) has been identified separately. The characterization of the NP works exactly in the same way as before (as explained in the presentation of the algorithm). In this example too, all constraints belonging to the characterization are satisfied: precedence, exclusion, unicity, etc. One can also remark the stipulation of a dependency relation between the AP and the noun, that illustrates the capacity of the technique to identify syntactico-semantic relations.

Input les meilleures stratégies (the best strategies)

Output cat(np,[plu,masc], np(det(les), ap(adj(meilleures)), n(stratégies)), [dep(ap,n), unicity(n), exclude(name,n), exclude(name,ap), exclude(ap,sup), prec(det,n), dep(det,n), unicity(det), exige(n,det), exclude(name,det)],[])

(7)
The example (8) presents the case of a complex NP. More precisely, this is the case of an ill-formed input, due to a wrong POS-tagging: in this case, the last adjectives of the list have been tagged as noun instead of adjectives. However, the NP has been recognized, due to the possibility of relaxing constraints. In this case, the uniqueness constraint applied to the noun has been violated. This constraint belongs to the second part of the characterization in a separate list of violated properties.

Input

Towards semantics

Using such a symbolic robust approach to XP extraction makes it possible to consider integrating semantic information. This is a great advantage in comparison to other methods. Some dependencies can be included in the description so that the extraction can come with different kinds of information, for example concerning the argument structure or the roles of the possible arguments. We develop in the following the example of NP extraction, illustrating how such task is implemented in order to identify NP s together with their main modifiers. Basically, the kind of information that is needed in applications mentioned above concerns the noun itself plus its different modifications. This means its quantification (if any) and its classical direct modifiers. In the system described here, the semantic structure of a NP is described by its head (the noun itself), its specifier (the determiner) and two possible modifiers (AP and PP ). Building such structure from a PG parser is direct. A minimal set of properties has to be checked in order to identify the NP and build the structure. In order to simplify the description and improve the efficiency of the system, we do not take into account relative clauses here. Moreover, also in a simplification perspective, we do not build embedded phrases. The only authorized one is the NP itself. In the end, we obtain a description of the NP which is more complete than the classical definition of a "base NP" (see [START_REF] Osborne | MDL-based DCG Induction for NP Identification[END_REF]) and moreover makes it possible to directly identify the relations inside the NP. The properties are then the following:

In PG, the entire representation of an objects (see [START_REF] Blache | Property Grammars: A Fully Constraint-Based Theory[END_REF]) contains on the one hand its properties, and on the other hand, its local information represented in terms of features. The final description of the NP we use in the perspective of the NP extraction system is then: (10)

The extraction mechanism consists then in satisfying the set of constraints defined in the property part of the NP object. When, a sequence of words from the input satisfies this set of constraints, the corresponding structure (called form) is built. By means of unification, the respective arguments of the structure will be instantiated with the desired values.

Discussion, Conclusion

In our approach, as we have seen, syntactic categories are inferred from the evaluation of properties, without any need of constituency information.

This aspect has important consequences on the role of constraints in the parsing process. One of the problems with constraint-based approaches is that constraints are usually expressed over high-level objects or structures. This is the case for example in HPSG, in which complex feature-structures must first be built before constraints can be evaluated. Similarly, Optimality Theory also generates a set of structures (or candidate structures) and then uses constraints to filter this set. In our approach, any constraint can be evaluated at any time for any set of categories. Such evaluation, as explained above, dynamically adds new information: the satisfaction of a selection constraint instantiates the syntactic category it describes. But this instantiation is conceived almost as a side effect of evaluation: satisfying constraints does not rely on the knowledge of the upper-level category. In other words, the hierarchical information is no longer preponderant in the parsing process. This means that one can evaluate subsets of constraints, for example in the case of applications that only need NP recognition. In this approach, the conception of the relationship between grammar and language becomes very different from that of the generative paradigm. In the latter, a language is conceived as being generated by a grammar. In Property Grammars, a grammar is only used as a characterization device of the language properties.

As a consequence, instead of restricting the role of parsing to the evaluation of the input's grammaticality, we can propose a more flexible vision, in which a parser's output is the description of all the properties of the input. Concretely, such a description consists in the state of the constraint system after evaluationin other words, the set of satisfied and violated constraints. We call such state a characterization of the input. In some cases, a characterization only contains satisfied constraints, but it can also be the case that some constraints can be violated, especially when parsing real life corpora. In most cases, such violations do not have consequences on the acceptability of the input.

One other formalism that shares the aims and some of the features of Property Grammars are Dependency Grammars (cf. [START_REF] Tesnière | El/'ements de syntaxe structurale[END_REF] and on this point [Mel'čuk88]), a purely equational system in which the notion of generation, or derivation between an abstract structure and a given string, is also absent. However, whereas in Dependency Grammars, as their name indicates, the property of dependence plays a fundamental role, in the framework we are considering it is but one of the many properties contributing to a category's characterization. Perhaps the work that most relates to ours is Morawietz's [START_REF] Morawietz | Chart parsing as contraint propagation[END_REF], which implements deductive parsing [START_REF] Shieber | Principles and implementation of deductive parsing[END_REF] in CHR, and proposes different types of parsing strategies (including one for Property Grammars) as specializations of a general bottom-up parser. Efficiency however is not addressed beyond a general discussion of possible improvements, so while theoretically interesting, this methodology is in practice unusable due to combinatorial explosion. Moreover, it produces all properties that apply for each pair of categories without keeping track of how these categories are formed in terms of their subcategories, so there is no easy way to make sense of the output in terms of a complete analysis of a given input string.

The idea of throwing away the traditional, hierarchical parsing scheme in favour of a view of parsing which involves properties on categories rather than rewriting schemes first materialized in the 5P formalism (cf. [START_REF] Bès | Propriétés et analyse d'un langage[END_REF][START_REF] Bès | La phrase verbale noyau en francais[END_REF]). Preliminary work re. the advisability of a direct implementation of such an approach had yielded pessimistic results : [START_REF] Blache | Constraint Logic Programming for Natural Language Processing[END_REF] showed that the mechanism of verification of a constraint system for syntactic analysis could be very expensive, given that the satisfiability of the system had to be verified in each stage. In the present work, however, we have moved beyond that obstacle by our analysis of property inheritance, which removes the need to recalculate all properties at each stage, allowing us to inherit at each stage most of the previous stage's properties, while calculating only the minimally necessary new properties and updating the previous properties along the lines of our property inheritance analysis. Thus, our work has validated the model of property-centered parsing with respect to efficiency, while preserving the level of generality of this theory. In addition, a direct interpretation guarantees a better evolution of the initial system: it can better adjust to changes in the theory and to experimental stages.

We hope to have convincingly argued that direct renditions of flexible, constraint based parsing formalisms can be made to run efficiently while preserving a one to one correspondence between the conceptual and the representational levels, including for such non traditional formalisms as Property Grammars, in which category inference does not depend on hierarchical or even constituency notions.

The representations allowed by our methodology, while extremely close to the computer-independent, conceptual representations of these formalisms, are directly executable, and moreover non-deterministic. This is satisfying with respect to logic programming's original aims of declarativeness and higher level expressiveness. Together with the advantages of this approach, we are able to even produce hierarchical depictions of the parse history of any category, including "incorrect" or incomplete ones. This is not important in itself, but is provided as an easy side effect, in the interest of historic comfort : we are all used to thinking in terms of parse trees or graphs, so showing a parse record in graph form may prove convenient to some users.

It is interesting to note that the parsing methodology we describe here has been generalised into a concept formation system which provides a cognitive sciences view of problem solving [START_REF] Dahl | Concept Formation Rules: an executable cognitive model of knowledge construction[END_REF].

  cat(X,Y,L,TL,RL,SL,UL), cat(Y,Z,R,TR,RR,SR,UR) ==> (k or xp(R,XP) -> (Ext=L, TE=TR, RE=RR, Sat0=SR, Unsat0=UR); (k or xp(L,XP) -> (Ext=R, TE=TL, RE=RL, Sat0=SL, Unsat0=UL); fail) ), !, ok in(XP,Ext), sat properties(L,TL,RL,R,TR,RR,XP,Sat0,Unsat0,T,Sat,Unsat) | cat(X,Z,XP,TE,T,Sat,Unsat).

  ,Adj,Prep, Adv, NP o Det ≺ Adv; Det ≺ N; Adv ≺ Adj; etc. Adv ⇒ Adj; NP ⇒ Prep

Of course, DCGs do permit context sensitive parsing as well, but the context sensitivity cannot be directly expressed through symbol contiguity, it has to be indirectly expressed in extra arguments or through other extra devices such as linear implication.

Acknowledgements

This research was made possible by V. Dahl's NSERC Discovery and Equipment grants and P. Blache's CNRS-SdI grant. Thanks are due to Baohua Gu for his help with testing and debugging the parser.


Aim

• The purpose of this study was to evaluate the prototype of a magnetic probe for accurate location of the position of the endoscope, allowing the relocalisation of this position in a further endoscopy. • We report the results of a feasibility study in pig and a preliminary study in 8 patients with BE

Conclusion:

• Both the experimental study in pig and the clinical study demonstrated the feasability of the EMS prototype during gasroscopies and it's usefullness to relocate the biopsy sites. • The clinical usefulness of this system should be further evaluated during the follow-up of patients with BE.

Electromagnetic device

• The electromagnetic tracking system (EMS) (NDI, Aurora) consists of an electromagnetic (EM) field transmitter and an EM probe. • The EM probe is inserted through the operating channel of a double channel gastroscope. The EM field generator is positionned above the patient chest wall.

Electromagnetic probe in a working channel of a dual channel gastroscope

Electromagnetic field transmitter

Method: ① First experimentation in pig

• During the first endoscopy, ten markings were made with a coagulation forceps in the distal oespohagus. • The position of each marking was recorded by the magnetic system.

• A second operator blinded to the results of this first endoscopy performed a second endoscopy on the same pigs, guided by the magnetic system to relocate the markings. ② Second experimentation with 8 gastroenterologists in pig

• We obtained two recordings of a pig oesophagus with the magnetic system one without markings and one with markings created by a coagulation forceps.

• The experiments were performed in two phases.

o In a first step, each endoscopist received a picture of a marked zone and was informed of its endoscopic coordinates.The endoscopist was then asked to retrieve this area on the recording without markings.

o During as second test, each endoscopist had to retrieve the same area based on the informations provided by the synchronisation software. ③ Clinical experience in 8 patients with Barrett's oesophagus • During the same procedure, a first examination of the oesophagus allowed the selection of areas identified by visual criteria. After withdrawal of the endoscope, the endoscopist was asked to retrieve these areas, based on the informations provided by the magnetic system. • Coordinates generated by the magnetic system during the two examinations of the oesophageal mucosa were then compared to verify the adequacy of the repositionning of the endoscope.

• The rotation of the endoscope is also recorded, allowing the precise repositionning of the endoscope during the second procedure. • The synchronization software (IRCAD®) records 3D coordinates point by point during the first procedure and then re-synchronizes these 3D coordinates in real time during the second procedure. • At the end of the first examination, the software automatically generates a numeric chart of the biopsies sites in a PDF file.

Results

① First experimentation in pigs

• After withdrawal of the endoscope, the second operator correctly relocated 48 of the 50 markings (96%) using the guidance system. • The repositionning of the endoscope provided by the EMS system was within a 2mm range from the initial positionning. ③ Clinical study in patients with Barrett's oesophagus

• In 4 patients, the oesophagus was normal but we recorded spots defined by anatomical landmarks with the EMS system during the first examination. • In 4 patients, a BE was diagnosed and multiple biopsy sites were recorded with the EMS system during the first examination. • In the 8 patients, all spots defined during the first examinations were correctly recognized during the second examination, after the withdrawal of the endoscope, according to the informations provided by the EMS system. • The electromagnetic sensors and the transmitter enable 3D location of the recorded points during the procedure Electromagnetic sensors

Introduction

• The incidence of Barrett's oesophagus (BE) is increasing.

• The risk of progression to oesophageal adenocarcinoma is also increased in BE.

• Guidelines recommend an endoscopic surveillance for biopsies in patients with dyplastic changes detected by biospies, according to the Seattle protocol. • During the surveillance biopsies need to be repeated and targeted to the mucosal areas with dysplastic changes. The main difficulty is to clearly identify theses aeras from one endoscopy to the other.

② Second experimentation in pigs