Discovering Chronicles with Numerical Time Constraints from Alarm Logs for Monitoring Dynamic Systems

1 Introduction

Telecommunications networks are growing in size and complexity, which means that a bigger and bigger vol­ ume of notifications needs to be handled by the man­ agement system. Most of this information is produced spontaneously by equipment (e.g., status change and dysfunction detection) and this message flow must be preprocessed to make effective management possible.

Filters based on a per-notification basis fail to perform an adequate information preprocessing required by hu­ man operators or by management application software, which are not able to process such amount of events. A preprocessing stage must decrease this information stream by suppressing superfluous notifications and/or by aggregating relevant ones.

Some papers deal with different approaches and pro­ pose more or less complex intelligent filtering: one can use some efficient rule-based languages (like in [Moller et al., 1995]), and/or object-based techniques like ECXpert (Event Correlation eXpert) which builds alarm correla­ tion trees according to some handwritten rules [Nygate,

1995]. More specific techniques are also studied to cap­ ture time constraints between alarms [Dousson et al., 1993; Jakobson and Weissman, 1995].

In any case, the problem of expertise acquisition re­ mains the same: how to feed the filtering system? Which aggregation rules are relevant? Since time information is apropos for the telecommunications alarm propagation, we also have to be able to deal with numerical time con­ straints. One way for such a knowledge acquisition is model-based approaches like [Bibas et al., 1995] or [La­ borie and Krivine, 1997], which use models to build a simulator for generating relevant faulty scenarios.

Our approach is more akin to data mining techniques: it is based on a frequency analysis of actual alarm logs of the supervised system (the telecommunications net­ work) to discover some frequent chronicles. The frequent chronicle approach is relevant to reach the aim of reduc­ ing the alarm stream: if a chronicle corresponds to a dysfunction, we aggregate the set of alarms for the hu­ man operator and if not, we only hide the corresponding alarms. At the moment, we do not use any extra knowl­ edge, so the rule qualification (aggregation or suppres­ sion) must be performed by an expert.

The original idea stands in [Mannila et al., 1995] but their work focuses only on two types of chronicles (which are called episodes): the parallel ones (alarms are not ordered) and the serial ones (alarms are completely or­ dered). Some extensions for a more complex chronicle structure are proposed (but not tested) by combining se­ rial and parallel chronicles. Moreover, only a user given upper bound of chronicle duration was allowed to be a time constraint. We extend our frequency analysis with a time representation, which is able to deal with numer­ ical time constraints.

We present in this paper a system (called FACE - Fre­ quency Analyser for Chronicle Extraction) that enables an expert to process some powerful analyses of alarm logs and to identify some recurrent phenomena. In Section 2, we expose some definitions for later use. Section 3 de­ tails the first stage of our log analyser, where frequently occurring chronicles in alarm logs are discovered; Sec­ tion 4 corresponds to the second stage where a graph of dependencies between chronicles is established. Then in Section 5, before concluding, we show some results about an experiment with an actual ATM network.

2 Representation and Definitions

2.1 Time

We based our alarm correlation system on CRS, a Chron­ icle Recognition System similar to IxTeT 1 , described in [Dousson, 1996], because of its real-time capabilities to deal with numerical time constraints.

For complexity reasons, this system relies on time­ points as elementary primitives and considers the time as a linearly ordered set of discrete events. A time constraint between two time-points h and t 2 is repre­ sented by an interval, [J-, J+j, which corresponds to the lower and upper bounds on the temporal distance from t 1 to t 2 . We also define a time constraint graph T as a set of time-points with time constraints between them (constraint between i and j is an interval de­ noted by KT(i-+j)). We define a partial order (tighter than, denoted by~) among constraint graphs as follows:

T~T' =def V(i,j) ET, KT(i-+j) ~ KT·(i-+j)

A constraint graph may have many equivalent rep­ resentations. In particular, there is a unique equiva­ lent constraint graph, which is minimal (with respect to ~) and its computation (and its consistency check) is ensured by the well-known path consistency Floyd­ Warshall's algorithm with the complexity of O(n 3 ) [Dechter et al., 1991] . We do not allow disjunctive con­ straints since this problem becomes NP-hard.

In the following sections, we systematically apply this algorithm, and so, we always deal with the minimal time constraint graph.

2.2 Alarm

• Alarm: an alarm is a pair (A, t) where A is the alarm type and t is the time instant (i.e., occurrence date) of the alarm.

Alarm occurrence: an alarm occurrence is a time­ stamped alarm (e.g., (A, 4)).

Alarm log: an alarm log .C is a time-ordered list of alarm occurrences. For example, (A, 1)(B, 3)(A, 4) (C, 4)(A, 7)(B, 8)(C, 9)(B, 10)(B, 12).

Due to time-point primitives, an alarm has no dura­ tion. If we need some, we can introduce two alarm types corresponding to the beginning and the end of an alarm. For instance, in the telecommunications management, one usually uses a LOSactive when the alarm Loss Of Signal appears, and a LOSc1ear when it disappears.

We also suppose that alarms are correctly time­ stamped in logs (which is often the case). The message propagation delay in a network must only be taken into account during the on-line recognition stage and this fea­ ture is actually performed by CRS.

1 The main differences between them are the heuristics used during the recognition because CRS is specially devel­ oped for telecommunications networks, but it does not matter here because.we use it as a black box.

2.3 Chronicle Model and Instance

Chronicle model: a chronicle model Cis a pair (S, T) where S is a set of alarms and T is a constraint graph of their instants. We also denote eN a chron­ icle with N alarms (N is called the size of CN).

For example, Figure 1 shows a breakdown link chronicle, where LOS stands for Loss Of Signal and LOF stands for Loss Of Frame.

Unconstrained chronicle model: an unconstrained chronicle model (denoted by ( S, ·)) is a chronicle model with no time constraint and no order be­ tween alarms. We also use alarm types for the simplified notation of an unconstrained chronicle model as in the following example: ABB stands for ((A, tl), (B, t 2), (B, t3), ·) 2 .

Chronicle instance: a chronicle instance c of a chron­ icle model C is a set of alarm occurrences which is consistent with the time constraints of C. For ex­ ample, {(A, 1)(B, 3)(A, 7)} is an instance of the left chronicle of Figure 2.

Subchronicle instance: an instance c is a subchron­ icle instance of an instance c' iff c is a subset of c' (e.g., {(A,1)(C,6)} is a subchronicle instance of {(A, 1)(B, 3)(C, 6)} but not of {(A, 3)(C, 6)} ).

Subchronicle model: a model C is a subchronicle model of C' (denoted by C ~ C') iff from any in­ stance of C', we can extract a chronicle instance of C (e.g., in Figure 2 the two right chronicle models are subchronicle models of the left one). This rela­ tion defines a partial order on chronicle models.

Superchronicle: c (resp. C) is a superchronicle in­ stance (resp. model) of c' (resp. C'), which is de­ noted by c;;;;) c' (resp. C ;;;;) C'), iff c' (resp. C') is a subchronicle instance (resp. model) of c (resp. C).

Theorem 1 A chronicle model C = ( S, T) is a sub­ chronicle model of C' = ( S', T') iff S ~ S' and T 2 T'.

For brevity, hereafter chronicle stands for chronicle model and instance stands for chronicle instance.

2 0f course, ABE is equivalent to BAB or BBA.

2.4 Instance Set and Frequency

Given an alarm log C and a recognition process, we de­ note Ic(C) the set of instances of C recognized in C. Of course, this set depends strongly on the strategy imple­ mented in the used recognition tool.

For our algorithms, we only need that the strategy guarantees the following property:

This property means that an alarm occurrence can't be­ long to two instances of the same chronicle model.

For instance, with C given in Section 2.2, the instance set of the unconstrained chronicle AB could be:

• { {(A, 1)(B, 3)}, {(A, 4)(B, 8)} , {(A, 7)(B, 10)}}
• {{(A, 1)(B, 12)}, {(B, 3)(A, 7)}, {(A, 4)(B, 10)}}
• etc.

Frequency of chronicle: given an alarm log C, the frequency fq(C , C) of a chronicle C inC is the car­ dinal of Ic(C) . For example, with C given in Sec­ tion 2.2, the frequency of the unconstrained chron­ icle AB is 3.

Frequent chronicle: given a threshold fqmin, C is fre­ quent in C if fq(C, C) 2: fqmin· We suppose that the threshold f qmin is defined by the user.

As our algorithms work with only one alarm log at a time, we now use the simplified notations Ic and fq(C) instead of respectively Ic(£) and fq(C , C).

3 Discovering Frequent Chronicles

This section presents algorithms to discover all the sets of frequent chronicles of size i (denoted by <I>i).

Lemma 3 If a chronicle C is frequent in £, all its sub­ chronicles are also frequent in C.

A chronicle Ci won't be frequent if one of its subchroni­ cles is infrequent. Otherwise, if all the sub chronicles of Ci are frequent, Ci will be a candidate for <I>i (i.e., Ci may be frequent) . For example, with the unconstrained chroni­ cle ABC, if one of its subchronicles A, B, C, AB, AC, BC is infrequent , ABC is also infrequent; otherwise, ABC may be frequent and is a candidate. In fact, if we know that AB is frequent , we also know that A and B are frequent. Thus we only need to check the frequency of AB, AC, BC (chronicles of size i - 1). We denote <I>~ the set of candidate chronicles for <I>i (<I>~ 2 <I>i).

So the intuitive solution to compute <I>~ is to generate all the possible chronicles Ci of size i from one of its frequent subchronicle of size i - 1 (if AB is infrequent, we do not need to generate AAB, ABE or ABC!) and then to check its frequency.

Based on these analyses, our main algorithm builds it­ eratively the exhaustive set of all frequent chronicles (see Figure 3). It starts by computing <I>1, which corresponds to the set of all the frequent alarms in C. At an itera­ tion i , it first computes the set <I>~ from <I>i- 1 (function generateCandidate) . It then calculates the frequency of each candidate and keeps only the frequent ones in <I>i . Its main loop ends at the iteration i where there is no frequent chronicle of size i ( i:::; ICJ).

The following sections only give algorithms for the chronicle generation stage because we use CRS to cal­ culate the frequency: chronicles are modeled into CRS, which receives C as alarm input stream and then the number of times of recognition performed by CRS for each chronicle gives us the frequency of the chronicle.

3.1 Candidate Generation

This section presents the algorithms to compute <I> ~ from <I>i-1 .

There are two subtasks to build a candidate Ci: com­ puting a set of i alarms occurring frequently together (i.e., a frequent unconstrained chronicle) and establish­ ing the time constraints between these alarms. There­ fore, in order to compute <I>~, we first compute the set W~ of the candidate unconstrained chronicles of size i that may be frequent. The set wi of frequent unconstrained chronicles of size i is then computed from "IJ!~. Eventu­ ally, we establish time constraints between alarms of wi to generate the final candidates of <I>~ (see Figure 4) .

The frequency of unconstrained chronicles is easily computed by using the following lemma:

Lemma 4 With an unconstrained chronicle C we have: fq(C)= [r,~~ ( ~f~:?) J, where N(Ai) is the number of alarms (of C) whose type is Ai . 3

3 Here, [r] stands for the greatest integer less than or equal to a real number r .

For example, with the alarm log given in Sec­ tion 2.2, the frequency of the unconstrained AAB is: [min { ~f~f = ~. ~f!? = t}] = 1.

Unconstrained Candidate Generation

First, q>i- 1 is used to construct the set r of the un­ constrained chronicles corresponding to the chronicles of q>i- 1 (obviously, r ~ IJ!i- 1 ) . We then compute the set IJ!~ from r. Lemma 3 enables us to suppress any chron­ icle including an infrequent subchronicle (see Figure 5).

For example, with the alarm log given in Section 2.2, fqmin = 2 and i = 3, we have r = {AB, AC, BC, BB} and thus, n ={A, B, C}. By adding to AB each ele­ ment of n, one by one, we generate the three candidates AAB, ABE, ABC for IJ!~, but AAB is suppressed be­ cause one of its subchronicles, AA, is infrequent. We process similarly for AC, BC, BB and finally obtain IJ!~ ={ABE, ABC, BBC} .

With this exhaustive generation, one chronicle may be generated many times from those of r before checking its candidature for IJ!~ (e.g., BBC is generated twice, from BB and from BC). To avoid this redundancy and also to reduce the number of generated chronicles, our optimized algorithm orders completely the alarm types of n (e.g. in lexical order) and only adds to a chronicle ( s, . ) of r an alarm whose type is greater than or equals to the greatest alarm type of S (see example in Figure 6) . It can be proved that this optimization reduces in half the number of chronicles for which one needs checking the candidature for IJ!~.

Establishing Time Constraints

Once IJ!i is computed, the time constraints between the alarms of its chronicles are established by using Theorem 1. The idea is that the time constraints between two alarms in the chronicles of <fl~ are deduced from the time constraints between these alarms in the chronicles of q>i- 1 (see Figure 7).

For example, suppose that in <fl 2 we have K ( t A -+t 8) = [2, 5], K(tB-+tc) = [1, 1], K(tA-+tc) = [1, 5], and the unconstrained chronicle ABC E IJ! 3 . The con­ straint graph T constructed from {A, B, C} with these constraints is consistent (see Figure 8), so ( {(A, tA), (B, t8 ) , (C, tc )} , T) is a candidate in <P~ .

3.2 Discovering Chronicles of Size 2

The time constraints for the alarms are originally es­ tablished at this stage and then are used to correlate alarms in the chronicles of size greater than 2. Using the same strategy as described above, our algorithm com­ putes firstly IJ! 2 , then establishes th~ time constraints between alarms of the chronicles of IJ! .

Based on the distinct instances of a frequent chronicle AB in the alarm log, we establish the time constraint be­ tween A and B. A constraint [J-, J+] can be accepted as the time constraint between A and B if all the instances of IAB respect [J-, J+] . But if all the instances of IAB are used, some noises may be taken into account. In or­ der to avoid noises, one should use an instance threshold itmin (O<itmin::=;l), i.e., only [itminxfq(AB)] instances of IAB should be considered.

Among these acceptable time constraints, one should use some criteria to select the good ones for A and B. In order to find only tight constraints between alarms, we select only the constraints so that their duration and the distance between A and B are as small as possible since alarm effects are rapidly propagated in telecommunica­ tions network. More concretely:

• From the acceptable constraints, select [J-, J+] so that (J+-I-) is the smallest (criterion of the tight­ est constraint) .

• From the selected constraints, select [I-, J+] so that max{II-1, IJ+I} is the smallest (criterion of the shortest distance).

Searching good constraints (at most two) can be done using the algorithm A*. These constraints can be consid­ ered as the disjunctive constraint between A and B. For example, with the instance threshold itmin = 1 and the alarm log .C =(A, 1)(B, 3)(A, 4)(B, 5)(A, 7)(B, B)(A, 10), it is easy to find that [-2, -1] and [1, 2] are two good time constraints between A and B.

In fact, CRS does not accept disjunctive constraints, therefore such ones will be unified to obtain the con­ straint for CRS. In the above example, the constraint K(tr~tB) will be [-2, 2] instead of [-2, -1] U [1, 2] for CRS. Another possibility could be to define two chron­ icles AB in CRS, one with [-2, -1] and another with [1, 2].

3.3 Discovering Frequent Chronicles with Chronicles Known by Experts

If we have some expertise, we can use it to improve the discovery process: all known chronicles of size i are added to c)}i. Moreover, in order to determine whether the chronicle C is frequent, we use Theorem 1 to check if C is a subchronicle of one of the known chronicles. If it is, we already know that C is frequent. Otherwise, we have to calculate the frequency of C. Taking this remark into account, the number of chronicles to calculate the frequency may be much reduced.

3.4 Complexity

At an iteration i, the global complexity of our algorithms is the sum of the following complexities:

Unconstrained chronicle generation (Figure 5): for each unconstrained chronicle ( S', ·) of size i, checking if one of its subchronicles of size i - 1 belongs to r can be done in time O(i.log lfl) with binary search; because ( S', ·) has i unconstrained subchronicles of size i -1, checking the candidature of (S',·) for 'll~ can be done in time O(i 2 . loglfl). The number of unconstrained chronicles to check the candidature for 'll~ is lfi.IOI. In fact, lfl can be overvalued to lwi-11, so this complexity can be overvalued to O(lwi- 1 I.IOI.i 2 . log lwi- 1 1), which is a little better than one of [Mannila et al., 1995].

• Unconstrained chronicles frequency calculation: it requires O(i) time for a unconstrained candidate of size i (Lemma 4); so this complexity is O(lw~l-i).
• Establishing time constraints (Figure 7): for each unconstrained chronicle (S, ·) of wi, establishing the time constraint for one of its i(i~ 1 ) pairs of alarms can be done in time lc)}i-11; so, constructing a constraint graph corresponding to (S, ·) requires O(i 2 .lc)}i-11) time. In addition to this complexity, checking the consistency of a constraint graph of i nodes takes O(i 3 ) time. Therefore this complexity is o(iwil.(i2.1c)}i-11 + iJ)).

Constrained chronicle frequency calculation :

[Dousson, 1996] had shown that: for a chronicle of size i , the propagation when one of its alarms arrives requires O(i 2 ) time; so we have a complexity of 0 ( i 3 ) for the chronicle; as the internal mechanism of CRS generates on average i instances for one recognized (and i 2 in the worst case) , the average complexity of the frequency calculation is 0( i 4 ) (and O(i 5 ) in the worst case). So this complexity is O(lc)}~l.i 4 ) (and O(lc)}~l.i 5 ) in the worst case) .

4 Dependency Filtering

The number of frequent chronicles is always great. Thus, once these chronicles are discovered, one should filter them to find the relevant ones. What should be the cri­ teria of relevance? Recall that our goal is to discover ex­ pertise for monitoring, so the discovered chronicles have to be able to identify phenomena produced during the functioning of the system. The question here is: does a chronicle signify itself a phenomenon or is it always included in a more complex one? For instance, is AB a phenomenon or does AB always come with other alarms (and so, the relevant chronicles may be ABC or ABB)?

We base the dependency relationship between a chron­ icle and one of its subchronicles on the alarms of the subchronicle that are not included in any instance of the superchronicle.

We define the independent instance set between two chronicles C and C' as follows:

And so, the independent frequency fq*(Cr;;;.C') is defined as the number of elements of Ieee'.

In term of dependency level,- one can say that the chronicle C' depends completely on all its subchronicles, i.e., the phenomenon corresponding to C' included the phenomena corresponding to all its subchronicles. If there is C so that fq*(C r;;;.C') is high, one can say that the influence of C is not only showed in C', but also out­ side C'. Therefore, if C' is a relevant chronicle, C is also relevant. On the other hand, if fq*(C r;;_ C') is low, one can say that outside C', the influence of C is not remark­ able. In other words, C should only be considered as an excerpt of C'.

Proof: This is due to the fact that for any instance ci of Ci (Ci is superchronicle of C), there is at least one dependent instance c of C (i.e., c C ci)· 0

Corollary 6 The following recursive formula gives an upper bound of fq*(C r;;_ C'):

Proof: Recursively: suppose that the formula is true for any superchronicle C', Theorem 5 gives it for C. 0

Let us suppose that the recognition process is con­ tructed so that the instances of chronicles are recognized as soon as possible (first-coming instances). Namely, the process guarantees the following property (CRS does):

Property 7 For any chronicle C, its instance set Ic is totally ordered by the relation ~ (before) between two instances of C, where ~ is defined as follows:

For example, with the alarm log given in Sec­ tion 2.2, the instance set IAB is the following: {{(A.' 1)(B, 3)}, {~A, 4)(B, 8)}, {(A, 7)(B, 10)} }.

W1th our algonthms, we can prove the following the­ orem:

Theorem 8 For any frequent chronicle C' with distinct alarm types and C one of its subchronicles, if Ic has Property 7, we have: fq(C ~ C') = fq*(C ~ C').

Thanks to Theorem 8, we can easily calculate the in­ dependent frequencies for chronicles with distinct alarm types. For the other kind of chronicles 4 , we can cal­ culate their independent frequencies by exhaustive al­ gorithm (i.e., using the definition) and/or calculate the upper bounds for estimating purposes.

Output of the Filtering Process

Based on the above analyses, the output of the filtering process is a graph G representing the dependency rela­ tionship between the frequent chronicles. There will be a link from C' to C if C ~C' and fq*(C ~C') = 0. 5

A chronicle C is considered as independent if its in­ dependent frequencies against all its independent super­ chronicles greater than zero, i.e., C has no links with its independent superchronicles in G. All the chronicles that have no superchronicle are independent.

Figure 10 shows the dependency graph, which is com­ puted from the alarm log C given in Section 2.2 with fqmin = 2. We exhibit here four independent chronicles ABB, AB, ABC and BBC (to simplify the figure, the corresponding constraint graphs are not shown).

4 Fortunately, first experimental results show that this kind of chronicles is relatively rare.

5 0ne can define a dependency threshold for filtering.

5 Experiment and Results

The first experiment of our approach was with the data from the French packet switching telecommunications network. The input data was a log of 2900 alarms of 36 different types and corresponded to a duration of 20 hours. One run of our algorithms (i.e., for one given value of fqmin) took about 2 minutes, and many runs ex­ hibited a dozen of independent relevant chronicles .(due to the size of the input, frequent phenomena are rela­ tively rare). Since the network is well known, this was more a validation experiment than an actual knowledge acquisition. In spite of that, one of the discovered chron­ icles was unknown but relevant to experts. Moreover, it was a non-trivial chronicle in the sense that it was out of usual monitoring knowledge: this chronicle showed the influence of a non-telecom unit- a secondary power supply failure - with an alarm indicating the too high temperature on an equipment (the reason is that the air conditionning system was out of order since it was plugged on the secondary power supply).

The second application is related to the first exper­ imental national ATM (Asynchronous Transfer Mode) network. As this network is more recent, the challenge for our algorithms is to help efficiently experts with mon­ itoring knowledge acquisition. The amount of data is more significant since we have a one month log with about forty thousand alarms dispatched through about 3800 different types. For this application, an alarm type consists of the actual alarm type and its localisation: for instance, if telecommunications equipment are able to emit a LOS (Loss of Signal), we define a LOS_Lyon for the Lyon switch, a LOSYaris for the Paris switch and so on 6 . Figure 11 shows some experimental results. Moreover, we can notice that we have very few chronicles containing twice the same alarm type or more; hence, Theorem 8 (Section 4) gives us the exact independent frequency.

At this stage, we already know that some of them are relevant and some others must be filtered dur­ ing on-line monitoring. Figure 1 (at the beginning of the paper) shows such a discovered chronicle: the first group (LOFctear, LOSctear, LinkUp) corresponds to the connection re-establishment and the second group (LOFactive 1 LOSactive, LinkDown) indicates a connec­ tion breakdown; this chronicle signifies an unstable con­ nection link, which fails in the 10 seconds following the re-establishment; this is a particular chronicle of the net­ work and it is unpredictable according to the rules of rec­ ommendations of telecommunications management since it is a recurrent malfunctionning phenomenon. However, to improve the results, we need more investigations with telecommunications monitoring experts.

6 Conclusion

We present a chronicle discovery process that is very helpful for experts to discover monitoring knowledge from alarm logs. It is based on the key idea that a chron­ icle is frequent only if its subchronicles are frequent (like the work of [Mannila et al., 1995] but the chronicle for­ malism is more expressive than their episode-rule struc­ ture). Our process is also able to take into account and to establish numerical time constraints between alarms since this information could be discrepant for the fault detection.

The use of the same chronicle recognition system and the same chronicle model guarantees that semantics of recognition remains the same during the off-line (knowl­ edge acquisition) and on-line processing (monitoring).

We also propose a method for sorting the discovered chronicles and exhibiting the most relevant ones. The main advantage is to focus the attention of an expert on few (about one third) discovered chronicles to under­ stand and to be categorized for the monitoring process.

The first experiments show that our algorithms are able to deal with an amount of data compatible with the requirement of a discovery process and the prelimi­ nary results are quite promising since many discovered chronicles could be explained by the corresponding ITU 7 recommendations. We will interact with equipment ex­ perts to validate more chronicles but we already know that this is a good way to acquire knowledge for mon­ itoring a telecommunications network (like ATM). We noticed that the approach also exhibits some non-trivial scenarios, which are very rarely modelled by experts.

6 This is a limitation of our algorithms: we only discover chronicles that correspond to the phenomena repeating on the same equipment. In future work, we will introduce vari­ ables in chronicles to capture similar phenomena occuring on different places in the network.

7 1nternational Telecommunication Union

Future work will focus on addition of variables in dis­ covered chronicles and on introduction of some knowl­ edge in the telecommunications domain to ease the chronicle generation stage. Experiments with the ATM network will also be pursued and another test on a SDH (Synchronous Digital Hierarchy) network is planned.

7 Acknowledgements

Thang Vu Duong is currently a Ph.D. student at the CNET (R&D centre of France Telecom), and is grateful to his advisor, Malik Ghallab (LAAS/CNRS, Toulouse) , for helpful suggestions.

The authors would like to thank Thierry Vidal (ENIT, Tarbes) , the GASPAR project team for useful dis­ cussions and especially, Philippe Dague (LIPN/CNRS, Paris) for valuable comments on this paper.