Damien Nouvel
email: damien.nouvel@univ-tours.fr

Jean-Yves Antoine
email: jean-yves.antoine@univ-tours.fr

Nathalie Friburger
email: nathalie.friburger@univ-tours.fr

Pattern Mining for Named Entity Recognition

Many evaluation campaigns have shown that knowledge-based and data-driven approaches remain equally competitive for Named Entity Recognition. Our research team has developed CasEN, a symbolic system based on finite state tranducers, which achieved promising results during the Ester2 French-speaking evaluation campaign. Despite these encouraging results, manually extending the coverage of such a hand-crafted system is a difficult task. In this paper, we present a novel approach based on pattern mining for NER and to supplement our system's knowledge base. The system, mXS, exhaustively searches for hierarchical sequential patterns, that aim at detecting Named Entity boundaries. We assess their efficiency by using such patterns in a standalone mode and in combination with our existing system.

Introduction

Named Entity Recognition (NER) is an information extraction task that aims at extracting and categorizing specific entities (proper names or dedicated linguistic units as time expressions, amounts, etc.) in texts. These texts can be produced in diverse conditions. In particular, they may correspond to either electronic written documents [START_REF] Marsh | Muc-7 evaluation of ie technology: Overview of results[END_REF] or more recently speech transcripts provided by a human expert or an automatic speech recognition (ASR) system [START_REF] Galliano | The ester 2 evaluation campaign for the rich transcription of french radio broadcasts[END_REF]. The recognized entities may later be used by higher-level tasks for different purposes such as Information Retrieval or Open-Domain Question-Answering [START_REF] Voorhees | International Speech Communication Association (INTERSPEECH'09)[END_REF]. While NER is often considered as quite a simple task, there is still room for improvement when it is confronted to difficult contexts. For instance, NER systems may have to cope with noisy data such as speech recognition errors or speech disfluences. In addition, NER is no more circumscribed to proper names, but may also involve common nouns (e.g., "the judge") or complex multi-word expressions with embedded NEs (e.g. "the Computer Science Department of the New York University"). These complementary needs for robust and detailed processing explain that knowledgebased and data-driven approaches remain equally competitive on NER tasks as shown by many evaluation campaigns. For instance, the French-speaking Ester2 and Etape evaluation campaigns on radio broadcasts [START_REF] Galliano | The ester 2 evaluation campaign for the rich transcription of french radio broadcasts[END_REF] has shown that knowledge-based approaches outperformed data-driven ones on manual transcriptions. However, despite their advantageous precision, symbolic systems need significant efforts when confronted to new NE types or when the system has to be adadpted to diverse mdalities (written vs oral transcripts). In this paper, we present an original approach, based on the adaptation of pattern mining techniques as a machine learning process (automatic training on corpora to reach a large coverage), while remaining in the framework of symbolic resources (extraction of intelligible rules of NE recognition). The performances of the resulting system (mXs) on the Etape French-speaking evaluation compaign shows that this novel approach bears comparison with standard machine learning techniques (CRFs). Besides, coupling this system with CasEN [START_REF] Friburger | Finite-state transducer cascades to extract named entities in texts[END_REF], our knowledge-based system, provides us with promising results.

In Sect. 2 we present and compare approaches for NER. Sections 3 and 4, we describe how lexico-syntactic patterns may be extracted from annotated corpora and used as a standalone system. Finally, Sect. 5 and 6 reports experimental results on French oral corpora.

Related Work

In the 90's and until now, several symbolic systems have been designed that, often, make intensive use of regular expressions formalism to describe NEs. Those systems often combine external and internal evidences [START_REF] David | Internal and external evidence in the identification and semantic categorization of proper names[END_REF], as patterns describing contextual clues and lists of proper names by NE categories. Those systems achieve high accuracy, but, as stated by [START_REF] Mikheev | Named entity recognition without gazetteers[END_REF], because they depend on the hand-crafted definition of lexical ressources and detection rules, their coverage remains an issue.

Machine learning introduced new approaches to address NER. The problem is then stated as categorizing words that belong to a NE, taking into account various clues (features) in a model that is automatically parametrized by leveraging statistics from a training corpus. Among these methods, some only focus on the current word under examination (maximum entropy, SVM) [START_REF] Borthwick | Exploiting diverse knowledge sources via maximum entropy in named entity recognition[END_REF], while others also evaluate stochastic dependencies (HMM, CRF) [START_REF] Mccallum | Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons[END_REF]. Most of the time, these approaches output the most probable sequence of labels for a given sentence. This is generally known as the "labeling problem", applied to NER.

Many approaches [START_REF] Nadeau | A survey of named entity recognition and classification[END_REF] rely on pre-processing steps that provide additional information about data, often Part-Of-speech (POS) tagging and proper names lists, to determine how to automatically tag a text, resulting in an annotated text. Some make use of data mining techniques [START_REF] Freitag | Boosted wrapper induction[END_REF][START_REF] Etzioni | Unsupervised namedentity extraction from the web: An experimental study[END_REF], but we are not aware of work that goes beyond the step of extracting patterns for NER: no model has emerged for using those patterns to recognize NEs.

In this paper, we propose a system that adapts text mining techniques to the NER problem. The benefits of text mining techniques are twofold. On the one hand, pattern mining techniques are data driven and may be combined with standard machine learning approaches. On the other hand, pattern mining allows to extract NER detection rules (e.g. transducers) which are intelligible for a human expert and can be used by a symbolic system. To the best of our knowledge, this way of combining symbolic and machine learning approaches is completely original in the framework of NER.

Besides, our pattern mining system, mXS, focuses on boundaries of NEs, as begin-

D

Sent.

Patterns from L I s 1

The american <pers> president Barack Obama </pers> has arrived in <loc> Moscou </loc>. s 2

There he has seen the former <pers> chancelor Michelle Bachelet </pers>. s 3

The <pers> president Dimitri Medvedev </pers> was not present on the beautiful <loc> square Vladimir Lenine </loc>.

Table 1: sentences from an annotated corpus ning or ending markers that we would like to be inserted at correct positions. To this end, we extract patterns [START_REF] Nouvel | Recognizing named entities using automatically extracted transduction rules[END_REF][START_REF] Nouvel | Reconnaissance des entités nommées par exploration de règles d'annotation[END_REF] that are correlated to those markers. Those patterns, casted as "annotation rules", are not constrained to necessarily recognize both boundaries of NEs. Basically, the system detects each boundary of NEs separately. This strategy is expected to present a more robust behaviour on noisy data such as ASR recognition errors or speech disfluences. They are evaluated as a standalone system or coupled with our existing knowledge-based system.

3 Mining Hierarchical and Sequential Patterns

Extracting Patterns

We use data mining techniques to process natural language. In this context, what is detected as a sentence will be considered as a sequence of items, precluding the extraction of patterns accross sentences. Two alphabets are defined: W , words from natural language, and M as markers, e.g. the tags delimiting NE categories (e.g. person, location, amount). The annotated corpus D is a multiset of sequences based on items from W ∪ M . Table 1 exemplifies this with W = {The, president, Obama, . . . } and M = {<pers>, </pers>, <loc>, </loc>, <time>, . . . , <org>, . . . }.

Like most systems, the mining process relies as a first step on linguistic analysis of input data. Those preprocessing steps extend the language W to W * by lemmatizing, applying a Part-Of-Speech (POS) tagger and recognizing expressions from lexical resources provided by the ProlexBase [START_REF] Bouchou | Prolexbase et lmf : vers un standard pour les ressources lexicales sur les noms propres[END_REF] database (890K entries). Those additional elements are inserted as a hierarchical representation of tokens: each may gradually be generalized to its lemma, POS or semantic type. For instance in Table 1, the pattern language contains items {arrive, see, VER, JJ, DET, NN, NPP . . . }. The POS tagger distinguishes common nouns (NN) from proper names (NPP). Note that we only keep semantic information for proper names, to avoid extracting patterns that would contain instances of proper names. Figure 1 illustrates how POS categories are organized as a hierarchy and what patterns may be mined through an example of a sequence. We exhaustively extract contiguous patterns over this language. For instance, in Fig. 1, patterns such as 'VER in <loc> NPP' or 'NPP </loc> with' are extracted. The hierarchy and the properties of sequential patterns allow to partially order them. This use of the hierarchy as a modular description of language enables fine-grained generalizations for items inside patterns: extracting accurate patterns relies both on the data that is mined and on specifying a relevant hierarchy for NER.

Filtering Patterns as Annotation Rules

We mine a large annotated corpus to find generalized patterns that co-occur with NE markers. As usual in data mining, we set thresholds during extraction based on two interestingness measures: support and confidence. The support of a pattern P is its number of occurrences in D, denoted by supp(P, D). The greater the support of P, the more general the pattern P. To estimate empirically how much P is accurate to detect markers, we calculate its confidence. A function suppNoMark(P) returns the support of P when markers are omitted both in the rule and in the data. Thus, the confidence of P is:

con f (P, D) = supp(P, D) suppNoMark(P, D) (1)
As we are only interested in patterns correlated with NE markers, we extract patterns containing at least one marker as rules. For instance, consider the rule R = 'the JJ <pers> NN NPP' in Table 1. Its support is 2 (sentences s 1 and s 2 ). But its support without considering markers is 3, since sentence s 3 matches the rule when markers (<pers> in rule and <loc> in "the beautiful <loc> square Vladimir") are omitted. Thus the confidence of R is only 2/3.

The collection of transduction rules exceeding minimal support and confidence thresholds is used as a knowledge-base. In practice, the number of discovered rules remains very large (especially when minimal support threshold is low). Thus, we decide to filter-out the redundant rules. We consider two rules to be redundant if they are related by a generalization relation and if they have same support: they cover same sequences in data. Over a set of redundant rules, we only select the most specific ones, that we will actually use for NER. Those are named "Annotation Rules".

NER using Annotation Rules

We now aim at determining when transduction rules should insert markers in texts. Using rules as features, we are able estimate probabilities for marker's presence as a trained model, as we will present in Sect. 4.1. The rules and the model are provided to a simple beam search algorithm described in Sect. 4.2 to actually annotate texts.

Estimating Likelihood of Annotated Sentences

As previously mentioned, instead of assigning a category to words (or tokens), our annotation rules insert markers at diverse positions in sentences. At a given position of a sentence, a decision should choose between adding any number of beginning or ending markers for NE categories (e.g. <pers>, </pers>, <loc>, etc.) or not to do so, what we denote by inserting a 'void marker" ( / 0). We train as many binary classifiers as distinct markers to estimate local probabilities for each individual markers. The probability of the presence of a single marker m ∈ M at a given position i is a random variable conditioned by the set of rules that have been triggered at current position:

P(m ∈ M i |R 1 , R 2 . . . R k ) that we note P(m ∈ M i ).
Combining those separate probabilities allows a direct computation for the probability of having multiple markers, as a multilabel problem:

P(M i = {m 1 , m 2 }) = ∏ m∈{m 1 ,m 2 } P(m ∈ M i ) ∏ m∈M -{m 1 ,m 2 } (1 -P(m ∈ M i )) (2)
Finally, we use those local probabilities of the sequences1 of markers (including the void marker / 0) to compute the likelihood of any annotation as n independent decisions over a sentence:

P(M 1 , M 2 . . . M n ) = ∏ i=1...n P(M i ) (3)
Indeed, what is considered as the most likely annotation within possible ones has to maximize that measure.

Decoding Step

The probability model may lead to an invalid sequence of markers according to the considered annotation scheme. The decoding algorithm must therefore consider only the valid proposals of the model. Depending on the dataset, we'll expect to be able to generate flat (no embeddings) or strutured xml-like (Etape) annotations. Those constraints are implemented into the sequential algorithm, as a simple grammar to be checked while decoding. The latter uses a beam search approach 2 , where adding a marker is considered as making a transition: for instance, inserting a <loc> marker at the beginning of a sentence moves from a "not inside any NE" state to a "in loc" state.

The algorithm starts from the beginning of a sequence and, for any position, generates new annotation hypothesis at this point by taking into account probabilities, possible marker sequences and annotation scheme constraints. Annotation hypothesis are then ordered and selected depending on their likelihood. Note that only the best hypothesis is kept for any given state, and that the number of states may be finite (flat annotation schemes) or infinite (when embeddings are allowed without depth restrictions). At the end of the sentence, the resulting annotation is the hypothesis that ends up with a "not inside any NE" state.

Ester2 and Etape French Evaluation Campaigns

Our system, mXs, has initially been developed for the Ester2 campaign. Sub-sections 5.2 and 5.3 present detailed experimental results conducted on this corpus. They give a better insight of the system behaviour and assess the influence of the support and confidence thresholds. Then, Sect. 5.4 presents the official performances during the Etape evaluation campaign, which was a follow up of Ester2.

Data: French Radio Transcripts

Our system participated to the Ester2 and Etape evaluation campaigns, which involved the French-speaking research community on the problematic of NER on radio transcripts. This task is much more challenging on this kind of noisy data, due to speech disfluences, speech recognition repairs and absence of sentence boundaries. This accordingly lowers performance of POS tagging and, at a higher level, requires a much more robust approach to find entities. The French Ester2 and Etape evaluation campaigns included NER on transcribed texts [START_REF] Galliano | The ester 2 evaluation campaign for the rich transcription of french radio broadcasts[END_REF]. The competing systems had to recognize persons, locations, organizations, products, amounts, time and positions. Entitites were manually annotated for evaluation purposes. As reported by [START_REF] Nouvel | An analysis of the performances of the casen named entities recognition system in the ester2 evaluation campaign[END_REF], the Ester2 reference corpus contains many annotation inconsistencies. This is why we have decided to re-annotate consistantly one half of the corpus. This gold corpus will be named Ester2-corr while the second part was held out (Ester2-held). Such inconsistencies were avoided in the Etape corpus. Its annotation scheme is an extended version of Ester2's: evaluation is fine-grained and substructures of NEs are annotated as "components" [START_REF] Galibert | Structured and extended named entity evaluation in automatic speech transcriptions[END_REF]. Quantitative characteristics of those corpora are presented in Table 2.

Annotation Rules Extraction for Ester2

Corpora Ester2-dev and Ester2-held are merged to extract patterns. We used Tree-Tagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF] for robustly tokenizing, POS-tagging and lemmatizing words (on French written texts, this tool provides high accuracy, more than 90% but, as far as we know, no evaluation has been made over oral transcriptions). The mining task requires many optimizations [START_REF] Nouvel | Reconnaissance des entités nommées par exploration de règles d'annotation[END_REF] and we used a level-wise algorithm [START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF] which leverages the generalization over patterns to mine frequent ones. Table 3 reports the number of rules, the number of non-redundant rules and the gain (i.e., the ratio between the number of rules and that of non-redundant ones). This elimination of redundant rules leads to a very significant reduction without loss of information from train corpus, what is very important for using this collection as a knowledge-base.

mXS Performance for Ester2

To assess efficiency of patterns for NER, we use Ester2-dev and Ester2-held merged to extract patterns and learn model, Ester2-corr to evaluate accuracy of the predicted markers. We train as many binary classifiers as necessary, using extracted rules as features to feed the logistic regression algorithm of SciKit toolkit [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] 3 . In order to retrieve a set of rules that covers as much as possible actual markers in texts, we hereby extract rules at low support (3) and confidence (0.3) thresholds. With this exhaustive set of rules, only 52 markers out of 5196 (1%) are undetectable by the model because no rules are triggered at the considered position. Table 4 presents global score Slot Error Rate (SER) [START_REF] Makhoul | Performance measures for information extraction[END_REF] for diverse support and confidence thresholds. Those are computed by counting typed errors: insertions, deletions, types, extents. Results show that, for any support threshold, the model obtains better results at low confidence: even very generic (and thus less confident) rules are to be Table 7: error differences on CasEN with extracted rules performances close to state-of-the-art systems when correctly set up. Our latest experiences that hybridates mXS and CasEN for Etape obtains 32.9 SER (compared with the performance of the best system, CasEN: 35.2). Generally, our experiments suggest that our system is efficient for combining other systems outputs, we plan to conduct more experimentation on this topic in future.

Conclusion

In this paper, we reported experimentations on the use of pattern mining techniques to automatically enrich a knowledge-based NER system. We implemented a prototype which extracts patterns correlated to NE markers. The system exhaustively looks for annotation rules from a training corpus and filters out those of interest. During the mining process, the text is represented as a sequence of items, which may be generalized using a hierarchy through POS categories, and where the beginning or ending markers of NEs may be separately mined. The quality of patterns and their potential to recognize entites has been assessed and allowed us to state which are the most efficient and what markers categories remain to be improved. These experiments also investigated the idea of separately evaluating the probability to begin or end an entity, a beam search being afterwards responsible for finding the most likely and valid annotation. The resulting system was used coupled with a symbolic system, showing significant improvement of the performance. This work provides us with some interesting directions to improve a symbolic NER system, including in its foundations.

Acknowledgement

We'd like to thank Springer for allowing authors to share this authored version of the article published with reference LTC 2011, LNAI 8387 (Chapter 19, 978-3-319-08957-7, 328129 1 En).

Figure 1 :

 1 Figure 1: POS hierarchy and example of tagged sentence

Table 2 :

 2 characteristics of Ester2 and Etape corpora

	Corpus Tokens Sentences	NEs
	Ester2-dev	73 386	2 491	5 326
	Ester2-held	48 143	1 683	3 074
	Ester2-corr	40 167	1 300	2 798
	Total 128 477	4 283	8 670
	Etape-train 355 975	14 989	46 259
	Etape-dev 115 530	5 724	14 112
	Etape-test 123 221	6 770	13 055
	Total 594 726	27 483	73 426

Table 3 :

 3 extraction over Ester2 corpus at support and confidence thresholds

Each set of markers is mapped to a predetermined number of corresponding markers sequences, e.g. P({m 1 , m

}) = P(< m 1 , m 2 >) = P(< m 2 , m 1 >) = P(< m 1 , m 2 , m 1 >)

It limits the search space by considering at any position N most probable solutions

With regularization parameter C=4.

included as potentially relevant features. Globaly, using those rules as a standalone system remains unsufficient compared to state-of-the-art, but opens up great possibilities for coupling.

mXS performance for Etape

The Etape evaluation campaign extends Ester2 by considering TV broadcasts (including debates) and adding both fine grained and recursivity: NER is more difficult and requires robust approaches. Besides, the systems are now expected to recognize "componants" inside NEs [START_REF] Galibert | Structured and extended named entity evaluation in automatic speech transcriptions[END_REF], e.g. first names and last names for persons, day, month and year for dates, etc. As reported in Table 5, mXS is ranked 4th after one knowledgebased and two data-driven systems. Results show that the former have better performance for entities, while the latter are more accurate for componants. Despite being a data-driven system, mXS exhibits a behaviour similar to knowledge-based ones. The detailed results by NE types of Table 6 indicates that our system obtains good results for product category, which is the most difficult one. Conversely, it seems less efficient for recognizing organizations, which are known to be very ambiguous [START_REF] Nouvel | Recognizing named entities using automatically extracted transduction rules[END_REF]. This points out that pattern mining is accurate for detecting new NE types, but lacks fine-tuning for more traditional ones. We aim at improving performances of the existing system, CasEN, with the extracted patterns. Our symbolic system is precise, but lacks coverage because it would have to describe all regular expressions that may constitute a NE. Our idea is that automatically extracted patterns may supplement the symbolic system. We test this coupling by making CasEN's output a feature provided to mXS's input. Table 7 reports the initial symbolic system's results, the differences of errors by NE categories and the resulting coupled system's performance. The symbolic system alone outperforms our standalone system using rules (28 vs 38 SER). By coupling systems, we observe a significant improvement of the symbolic system's output. The insertion of a small amount (2) of false-positive (Ins. total) is the counterpart for the correction of 26 type errors made by the symbolic system. This mainly concern amounts and the balancing between location and organizations (which are known to be very amibiguous).

We also isolated and manually examined rules that were responsible for the decrease of errors (coverage). Most of these rules are short and generalized rules, and quite frequently inserting only one marker (for instance 'from <pers> NPP NPP' or 'to <loc> NPP'). Interestingly, two time expressions have been found thanks to the separate detection of the beginning and the ending markers using local clues: 'for <time>' and 'years </time>' (recognizing "for a few years" for instance). How those shallow rules may be taken into account by the knowledge base of the symbolic system remains to be investigated.

Due to lack of space, we do not report other configurations and coupling strategies that has been successfully experimented, those are reported in [START_REF] Nouvel | Coupling knowledge-based and data-driven systems for named entity recognition[END_REF]. They achieve


Mirko Fiacchini
email: mirko.fiacchini@gipsa-lab.fr

Irinel-Constantin Morȃrescu
email: constantin.morarescu@univ-lorraine.fr.

Set theory conditions for stability of linear impulsive systems 1

In this paper we give tractable necessary and sufficient condition for the global exponential stability of a linear impulsive system. The reset rule considered in the paper is quasi-periodic and the stability analysis is based on a standard tool in set theory that is Minkowski functional. Firstly, we reformulate the problem in term of discretetime parametric uncertain system with the state matrix belonging to a compact but non-convex set. Secondly, we provide a tractable algorithm for testing the stability and computing the associated polyhedral Lyapunov function when the system is stable. The main result is an algorithm whose computational effort is analogous to that of classical algorithms for contractive polytopes computation for discrete-time parametric uncertain systems with the state matrix belonging to a polytopic set. This is just a report meant to briefly present our results. For a full version of this work, containing proofs, discussions and numerical implementations please contact the authors.

Introduction

In order to overcome performance limitations of classical controllers Clegg introduced an integrator with state reset (see [START_REF] Clegg | A nonlinear integrator for servomechanisms[END_REF]). This idea received an increasing attention and recent works have been dedicated to stability and performances of reset control systems [START_REF] Beker | Fundamental properties of reset control systems[END_REF][START_REF] Nesić | Stability properties of reset systems[END_REF]. These systems are a class of hybrid systems since they are subject to both continuous-time and discrete-time dynamics. A particular class of reset systems is the continuous-time linear systems whose state undergoes finite jumps at some discretetime instants [START_REF] Beker | Plant with an integrator: an example of reset control overcoming limitations of linear feedback[END_REF][START_REF] Aangenent | Performance analysis of reset control systems[END_REF], also referred to as impulsive systems. The rule defining the jump instants is often time-depending (see [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] and the reference therein) and is motivated by the analysis of sampled-data systems ( [START_REF] Hespanha | Lyapunov conditions for input-to-state stability of impulsive systems[END_REF]) as well as periodic triggered stabilization ( [START_REF] Heemels | Periodic event-triggered control for linear systems[END_REF][START_REF] Postoyan | Periodic eventtriggered control for nonlinear systems[END_REF]).

The present paper deals with the stability analysis of linear impulsive systems by means of set theoretic techniques. As in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF], we consider that two consecutive reset instants are separated by an uncertain time. Instead of searching ellipsoidal Lyapunov functions that give sufficient condition for stability, we are searching polyhedral ones leading (as explained later) to necessary and sufficient stability conditions. The stability analysis is based on a standard tool in set theory that is Minkowski functional. Our concern is also to design an algorithm that is able to decide in finite time if a linear impulsive system is globally exponentially stable (GES) or not. In the former case it will also compute in finite time the polyhedral Lyapunov function guaranteeing the stability of the system.

Firstly, we reformulate the problem in term of discrete-time parametric uncertain system with the state matrix belonging to a compact but non-convex set. Secondly, we provide a tractable algorithm for testing the stability and computing the associated polyhedral Lyapunov function when the system is stable. The result is an algorithm whose computational effort is analogous to that of the standard algorithm for computing contractive polytopes for discrete-time polytopic parametric uncertain systems.

Notation. The set of real numbers is denoted by R while N stands for the set of positive integer numbers. We denote N n {i ∈ N, i ≤ n}. For any function x defined on R we denote x(t + ) lim τ →t,τ>t

x(τ) if the limit exists. A C-set is a convex and compact set containing the origin in its interior. For any real λ and any set S we define λ S {λ x | x ∈ S}. The unitary ball in R n with respect to norm • p is B n p {x ∈ R n : x p ≤ 1}, its analogous in the space of matrices is defined in the following.

Set-theory for nearly-periodic reset systems

Given the interval ∆ = [τ m , τ M ] with 0 < τ m < τ M ∈ R, we define the set of admissible reset sequences as

Θ(∆) = {t k } k∈N : t k+1 = t k + δ k , δ k ∈ ∆, ∀k ∈ N . (1)
The aim of this paper is to give tractable necessary and sufficient conditions for the stability of the following linear reset system

   ẋ(t) = A c x(t), ∀t ∈ R + -T , x(t + ) = A r x(t), ∀t ∈ T , x(0) = x 0 ∈ R n , (2)
where x ∈ R n is the state of the system and T ∈ Θ(∆), see [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF]. By definition

t k+1 -t k ∈ [τ m , τ M ],
∀k ∈ N so we avoid Zeno phenomenon (τ m > 0) but an infinite number of reset instants occurs (τ M < ∞). The state at time t ∈ (t k , t k+1 ], for a given initial state x 0 and a reset sequence T ∈ Θ(∆) is given by

x(t) = e A c (t-t k ) A r x(t k ), ∀t ∈ (t k , t k+1 ] (3)
thus, the dynamics between two successive resets is given by the following discrete dynamics

x(t k+1 ) = e A c (t k+1 -t k ) A r x(t k ) = e A c (δ k ) A r x(t k ), (4)
where δ k = t k+1t k ∈ ∆. Thus, denoting A(∆) = {e A c δ A r : δ ∈ ∆}, the problem of stability of the linear impulsive system (2) rewrites in terms of stability of the following discrete-time parametric uncertain system

x + = A(δ )x, x(0) = x 0 ∈ R n , (5)
where A(δ ) ∈ A(∆). Let us recall the definition of GES for the system [START_REF] Aangenent | Performance analysis of reset control systems[END_REF].

Definition 1 The system (5) is GES if there exist positive scalars c ∈ R and λ ∈ [0, 1) such that x(k) ≤ cλ k x 0 ( 6
)
for every x 0 ∈ R n and k ∈ N.

It is noteworthy that systems (2) is GES if and only if [START_REF] Aangenent | Performance analysis of reset control systems[END_REF] is GES. Notice that the set A(∆) is not convex in general but it is compact, while the set in which the parameter δ lies, i.e. the interval ∆, is trivially convex and compact. Then, using the classical result from invariance and set-induced Lyapunov functions for linear (uncertain) discretetime systems, see for instance [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encountered in control theory[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF][START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF], a necessary and sufficient condition for GES can be given, as follows.

Theorem 2 ( [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encountered in control theory[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF]) There exists a Lyapunov function for a linear parametric uncertain system if and only if there exists a polyhedral Lyapunov function for the system.

The theorem above is less conservative than Theorem 1 in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF], since it gives not only sufficient but also necessary condition for GES. It claims that the search of the candidate Lyapunov function can be limited to the family of functions which are induced by polytopes.

Remark 3 It is noteworthy that the functions considered in Theorem 2 are convex, positive definite and homogeneous as in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] (the fact that they are homogenous of order one and not of order two does not induce any loss of generality). Nevertheless, polyhedral Lyapunov functions are determined by a finite number of generators (the facets of the polytope they are induced by), then they form a set of functions strictly contained in the one considered in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF]. Therefore, the condition in Theorem 2 is less conservative and leads to necessary and sufficient conditions for stability which are computationally affordable, as shown in the sequel.

We also recall another result, concerning set theory and its application to the problem of stability of linear uncertain systems. Given a C-set Ω ⊆ R n , consider the following sequence of sets

Ω 0 = Ω, Ω k+1 = Q λ (Ω k , A(∆)) ∩ Ω, (7)
where

Q λ (S, A ) = {x ∈ R n : Ax ∈ λ S, ∀A ∈ A } = A∈A A -1 (λ S). ( 8
)
with S ⊆ R n and A ⊆ R n×n .

Lemma 4 Given λ ∈ R n , Ω, Γ ⊆ R n and A , B ⊆ R n×n then a) A ⊆ B ⇒ Q λ (Ω, A ) ⊇ Q λ (Ω, B). b) Ω ⊆ Γ ⇒ Q λ (Ω, A ) ⊆ Q λ (Γ, A ). c) If Ω is convex, then Q λ (Ω, A ) = Q λ (Ω, co(A )).
d) If the Ω and A are polytopes, i.e.

Ω = {x ∈ R n : Hx ≤ b}, A = {A ∈ R n×n : A = ∑ i∈N a α i A i , α i ≥ 0, ∑ i∈N a α i = 1}, then Q λ (Ω, A ) is a polytope too.
Proof: The proof requires just some careful but straightforward mathematical manipulations which are not presented here. A journal version containing detailed proof is in preparation.

Definition 5 For any λ ∈ [0, 1) we say the set S is λ -contractive w.r.t. dynamics (5) if and only if

A(δ )x ∈ λ S, ∀x ∈ S, δ ∈ ∆.
As proven in [START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF], the maximal λ -contractive set w.r.t. dynamics [START_REF] Aangenent | Performance analysis of reset control systems[END_REF], which is contained in Ω, is given by

Ω λ = k∈N Ω k , (9)
where Ω k are defined by [START_REF] Hespanha | Lyapunov conditions for input-to-state stability of impulsive systems[END_REF]. We note that, due to the linearity of ( 5), Ω λ is compact and convex as far as Ω is a C-set. However, Ω λ is not always a C-set since, for some values of λ , it can be reduced to the origin. In the following we denote λ * the infimum in [0, 1) for which Ω λ * is a C-set.

Theorem 6 (Theorem 3.2 in [START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF]) For λ ∈ [0, 1) let us assume that Ω λ defined by ( 7) and ( 9) is a C-set. Then, for every µ ∈ (λ , 1] there exists j such that Ω k is µ-contractive for all k ≥ j.

Remark 7 From Theorem 6, it follows that, for any µ > λ * we can obtain a µcontractive C-set w.r.t. dynamics (5) by iterating [START_REF] Hespanha | Lyapunov conditions for input-to-state stability of impulsive systems[END_REF] a finite number of times with λ ∈ [λ * , µ).

Therefore, the iteration [START_REF] Hespanha | Lyapunov conditions for input-to-state stability of impulsive systems[END_REF] together with an appropriate stop condition, represents one version of the basic algorithm for obtaining a λ -contractive set w.r.t. [START_REF] Aangenent | Performance analysis of reset control systems[END_REF]. Moreover, the algorithm terminates in a finite number of steps provided λ is adequately chosen.

Definition 8 Given a C-set S ⊆ R n , its Minkowski functional Ψ S : R n → R is defined as Ψ S (x) = min α≥0 {α ∈ R : x ∈ αS}. ( 10
)
Proposition 9 The linear parametric uncertain system ( 5) is GES if and only if for every C-set Ω there exists λ ∈ [0, 1) such that for all µ ∈ (λ , 1)

there is k = k(λ , µ) ∈ N such that Ω k ⊆ Q µ (Ω k , A(∆)), ( 11
)
with Ω k as in [START_REF] Hespanha | Lyapunov conditions for input-to-state stability of impulsive systems[END_REF]. Moreover, Ψ Ω k (x) is a global exponential Lyapunov function for [START_REF] Aangenent | Performance analysis of reset control systems[END_REF].

Proof: The result comes directly from Theorem 6 and the fact that the condition ( 11) is equivalent to µ-contractivity of the set Ω k (see [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF][START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]). Indeed, ( 11) is equivalent to the fact that for all x ∈ Ω k , x belongs also to Q µ (Ω k , A(∆)) which means, by definition [START_REF] Heemels | Periodic event-triggered control for linear systems[END_REF], that A(δ )x ∈ µΩ k for every δ ∈ ∆, definition of µ-contractivity of Ω k .

Alternative, but analogous, formulations of the stop conditions are given in literature, see [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]. Thus, summarizing, classical literature results on invariance and set-induced Lyapunov functions permit to assert that the class of positive definite polyhedral Lyapunov functions, that is, the Minkowski functions of polytopic C-sets, forms a universal class of Lyapunov functions for assessing GES for parametric uncertain linear systems. Moreover, algorithms exist such that contractive sets (and then also the related set-induced Lyapunov function) can be obtained after a finite number of iterations for exponentially stable parametric uncertain systems.

Problem 10 Given an exponentially stable uncertain system [START_REF] Aangenent | Performance analysis of reset control systems[END_REF], an initial polytopic C-set and a λ such that a C-set λ -contractive exists, does the recursion [START_REF] Hespanha | Lyapunov conditions for input-to-state stability of impulsive systems[END_REF] with stop condition [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF] provide a λ -contractive polytope?

The answer depends on the assumptions on A(∆). It has been proven that if A(∆) is a polytope, then the algorithm provides λ -contractive polytopes [START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF][START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]. Such results follow directly from the fact that Q λ (•, A(∆)) maps polytopes into polytopes provided that A(∆) is a polytope in R n×n . Nevertheless, supposing that A(∆) is just a compact set, such property is no more ensured in general.

Example 11 Consider the discrete-time linear uncertain system (5) with A(δ

) = αR(δ ) where R(δ ) is the rotation matrix, i.e. R(δ ) = cos(δ ) -sin(δ ) sin(δ ) cos(δ ) , ( 12
)
with δ ∈ ∆ = [0, π/4] and α ∈ (0, 1), which ensures robust asymptotic stability. The set A(∆) is not a polytope, neither a convex set, in R 2×2 . Notice, the A(δ ) is related to a contraction and turn dynamics. Given a set Ω, the set of successor and predecessor states of x ∈ Ω for the system [START_REF] Aangenent | Performance analysis of reset control systems[END_REF] are

A(∆)Ω = δ ∈∆ A(δ )Ω = δ ∈∆ αR(δ )Ω = {x ∈ R 2 : x = αR(δ )z, z ∈ Ω, ∀δ ∈ ∆}, A(∆) -1 Ω = δ ∈∆ A(δ ) -1 Ω = δ ∈∆ α -1 R(-δ )Ω = δ ∈∆ {x ∈ R 2 : x = α -1 R(-δ )z, z ∈ Ω} = δ ∈∆ {x ∈ R 2 : αR(δ )x ∈ Ω} = {x ∈ R 2 : αR(δ )x ∈ Ω, ∀δ ∈ ∆} = Q 1 (Ω, A(∆)).
Geometrically it means that, for every Ω ⊆ R n , the set Q λ (Ω, A(∆)) is given by the intersection of α -1 Ω rotated by -δ , for every δ ∈ [0, π/4]. Therefore the set Q λ (Ω, A(∆)) is not, in general, a polytope, neither for polytopic Ω. Then there is no insurance that the λ -invariant set potentially provided by the recursion ( 7) is a polytope. In fact, we have that

Ω k+1 = {x ∈ Ω 0 : αR(δ )x ∈ λ Ω k , ∀δ ∈ ∆} = {x ∈ Ω 0 : R(δ )x ∈ α -1 λ Ω k , ∀δ ∈ ∆},
which is given by the intersection of an infinite number of sets, one for every δ ∈ ∆.

Consider, for instance the case of α = 0.9 and apply the recursion with Ω 0 = B 2 ∞ and λ = 0.9. We obtain, at the first step, Ω 1 depicted in Figure 1 (left), non-polytopic.

1: Ω 0 and Q λ (Ω, A(∆)) for α = 0.9 (left) and α = 0.5 (right).

Nevertheless, if we choose α small enough for the contraction to compensate the rotation due to the uncertainty, then a λ -contractive polytope is obtained at the first step. Figure 1 at right represents Ω 0 and Q λ (Ω, A(∆)) for α = 0.5. It is obvious that Ω 1 = Ω 0 and that it is a λ -contractive polytope.

Our main objective is to provide a variation of the classical recursive algorithm for contractive sets computation, such that a polytopic contractive set, and then a polyhedral set-induced Lyapunov functions, can be obtained in finite time. Moreover, such algorithm should have a computional complexity analogous to the classical one. The algorithm is afterward adapted to the case of study of nearly-periodic reset systems.

Minkowski functional formalism

In this section we present more details on the Minkowski functional, which is main tool used in the sequel to obtain necessary and sufficient condition for GES of [START_REF] Aangenent | Performance analysis of reset control systems[END_REF]. Due to space limitations we do not provide the proofs of the instrumental lemmas in this section. A journal version containing detailed proof is in preparation.

Definition 12 Given a C-set Ω ⊆ R n , define:

• Minkowski functional of a compact set S ⊆ R n×n :

Ψ Ω (S) = max x∈S Ψ Ω (x),
• Minkowski functional of a matrix A ∈ R n×n , as induced by the functional for a vector:

Ψ Ω (A) = max x∈Ω Ψ Ω (Ax).
• Minkowski functional of compact sets of matrices A ⊆ R n×n , as induced by the functional for a matrix:

Ψ Ω (A ) = max A∈A Ψ Ω (A).
Notice: if Ω is a symmetric C-set, then Ψ Ω (x) is a vector norm ( [START_REF] Luenberger | Optimization by vector space methods[END_REF][START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]).

Definition 13 The (Hausdorff) distance induced by the Minkowski functional of the

C-set Γ ⊆ R n in the space of matrices R n×n is defined d Γ (A , B) inf{α ≥ 0 : A ⊆ B + αB n×n Γ , B ⊆ A + αB n×n Γ } where B n×n Γ {A ∈ R n×n : Ψ Γ (A) ≤ 1} = {A ∈ R n×n : Ψ Γ (Ax) ≤ Ψ Γ (x)}.

Lemma 14

If Ω is a symmetric C-set, then Ψ Ω (x) is a vector norm and Ψ Ω (A) is the induced operator norm.

Remark 15 Given the C-set Ω ⊆ R n , one has

Ψ Ω (A x) ≤ Ψ Ω (A )Ψ Ω (x)
The next lemma follows from convexity of Ω.

Lemma 16 Given the C-set

Ω ⊆ R n , Ψ Ω (A ) is such that Ψ Ω (A ) = Ψ Ω (co(A )). ( 13
)
Remark 17 Given the C-set Ω ⊆ R n and A , B ⊆ R n×n such that A ⊆ co(B) then Ψ Ω (A ) ≤ Ψ Ω (B). The inverse implication is not true in general: consider for instance A = {0} and B = {0}. Then Ψ Ω (A ) = 0 < Ψ Ω (B) but A co(B).

Stability analysis for linear impulsive systems

In this section we provide tractable necessary and sufficient condition for stability of (5) and present the algorithm that allows computing the associated polyhedral Lyapunov function.

Tractable necessary and sufficient condition

First we provide a necessary condition, together with its implication, for a set to be λ -contractive for the linear uncertain system (5).

Proposition 18 If the linear parametric uncertain system ( 5) is GES then for every C-set Ω and for all A ⊆ co(A(∆)) there exists λ ∈ [0, 1) such that for all µ ∈ (λ , 1) there is p = p(λ , µ) ∈ N such that condition

Ω k ⊆ Q µ (Ω k , A ), ∀k ≥ p, ( 14
)
holds, with Ω k given by

Ω 0 = Ω, Ω i+1 = Q λ (Ω i , A ) ∩ Ω. ( 15
)
Moreover, if Ω is a polytope in R n and co(A ) a polytope in R n×n then Ω k are polytopes and Ψ Ω k (x) is a polyhedral global exponential Lyapunov function for the system x + ∈ A x.

Proof: The result follows directly from Theorem 6 and the fact that if

x + ∈ A(∆)x is GES, also x + ∈ A x is GES.
The Proposition 18 substantially claims that if one replaces the uncertainty set A(∆) with a set which is either polytopic or finite and contained in co(A(∆)), then the recursion generates sequences of polytopes and terminates with a polytopic contractive set, if the system is exponentially stable. Notice that this entails a relaxion of the uncertainty bounds and then to an only necessary condition. On the other hand, this leads to a first computationally tractable recursion for obtaining approximation of the polytopic contractive set for [START_REF] Aangenent | Performance analysis of reset control systems[END_REF].

Corollary 19

Given Ω ⊆ R n polytope with 0 ∈ int (Ω) and A = {A i } N i=1 ⊆ co(A(∆)), then the recursion [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF] with stop condition [START_REF] Luenberger | Optimization by vector space methods[END_REF] terminates in finite steps for appropriate values of λ ∈ [0, 1) and µ ∈ (λ , 1) if the system ( 5) is GES.

Then, provided the system is GES, every finite selection of matrices in co(A(∆)) gives in finite time a polytopic contractive set and a polyhedral Lyapunov function, for adequate λ and µ. This also means that, if one proves that no contractive set exists for an uncertain system whose matrices forms a subset of co(A(∆)), then the system is not exponentially stable. andµ ∈ (λ , 1) such that the stop condition [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF] holds for recursion [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF], then the system ( 5) is not GES.

Corollary 20 Given Ω ⊆ R n polytope with 0 ∈ int (Ω) and A = {A i } N i=1 ⊆ co(A(∆)), if there are not λ ∈ [0, 1)
The main practical drawback of the latter result is that, in general, it is not trivial to prove that no such pair of λ and µ exists.

Let us consider an increasing sequence of inner approximations of the set co(A(∆)) (for everyone of which a contractive set exists, from Corollary 19) that converges to co(A(∆)). Let us also consider the corresponding sequence of contractive sets obtained by means of ( 14) and [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF]. The main idea is to prove that the latter sequence converges to a polytopic contractive set for system [START_REF] Aangenent | Performance analysis of reset control systems[END_REF], if and only ( 5) is GES.

Remark 21

The metric space of the compact sets of R n×n equipped with the Hausdorff distance (determined by the unitary ball with respect to a matricial induced norm) is complete, see [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF][START_REF] Rockafellar | Variational analysis[END_REF].

Theorem 22 The linear parametric uncertain system [START_REF] Aangenent | Performance analysis of reset control systems[END_REF] is GES if and only if for every C-set Ω and every increasing sequence of compact convex sets {A ( j) } j∈N such that A ( j) ⊆ co(A(∆)) and

lim j→∞ co(A ( j) ) = co(A(∆)), ( 16
)
there exists λ ∈ [0, 1), ν ∈ (λ , 1), k = k(λ , ν) ∈ N and h = h(λ , ν) ∈ N such that condition Ω (h) k ⊆ Q ν (Ω (h) k , A(∆)) (17)
holds, with the sequence of sets Ω ( j) k given by

Ω ( j) 0 = Ω, Ω ( j) i+1 = Q λ (Ω ( j) i , A ( j) ) ∩ Ω. (18)
Moreover, if Ω is a polytope in R n and co(A ( j) ) are polytopes in R n×n then Ω ( j) k are polytopes and Ψ Ω (h) k (x) is a polyhedral global exponential Lyapunov function for [START_REF] Aangenent | Performance analysis of reset control systems[END_REF].

Remark 23 Notice that λ and k do not necessarily depend on A ( j) , whereas ν and h do. Moreover, from the practical point of view, it is worth noting that the value of µ, ρ and h don't have to be computed. Theorem 22 claims that, by choosing appropriate λ ∈ [0, 1) and ν ∈ (λ , 1), the sets Ω ( j) k are ν-contractive for all j big enough. Thus, the computational complexity is analogous to that of classical algorithm for contractive sets computation. The shape of the computed contractive sets could be complex, but this is related to the complexity of the problem itself.

Thus, any sequence of compact sets A ( j) whose convex hull converges from the interior to the convex hull of A(∆) generates a sequence of C-sets Ω ( j) k that converges to a contractive set for [START_REF] Aangenent | Performance analysis of reset control systems[END_REF]. Remarkably, if the sets A ( j) are polytopes or finite sets (and Ω is a polytope), the sets Ω ( j) k are also polytopes.

Corollary 24 Let the linear parametric uncertain system (5) be GES and consider λ ∈ [0, 1), µ ∈ (λ , 1), k = k(λ , µ) ∈ N such that Ω k is µ-contractive. Then, for every ν ∈ (µ, 1) and every increasing sequence of compact convex sets {A ( j) } j∈N such that A ( j) ⊆ co(A(∆) with ( 16) there exists h = h(λ , ν) such that Ω ( j) k given by ( 18) is νcontractive for ( 5) for all j ≥ h.

Computation of contractive polytopes and polyhedral Lyapunov functions

The basic idea for certifying a nearly periodic reset system is GES, is to generate appropriate inner approximations of the set A(∆) and use it to compute a contractive C-set. Since every sequence A ( j) whose convex hull converges to the one of A(∆) eventually lead to a contractive C-set for (5), we can restrict our attention to finite sets A ( j) . This, together with polytopic Ω would lead to sequences of polytopic Ω ( j) k , thus numerically suitable.

Remark 25 An important computational implication of considering inner approximations of co(A(∆)) rather than outer ones, as for instance in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF], is that they are much easier to be obtained. In fact, every finite set A contained in co(A(∆)) is an inner approximation. Moreover, adding a matrix A / ∈ A such that A ∈ co(A(∆)) to A leads to a tighter approximation of co(A(∆)). Then, the sequences A ( j) can be easily genarated by adequately selecting points on the boundary of co(A(∆)). Hence no relevant computational effort is required to generate the sequence A ( j) .

Thus, generating an appropriate sequence A ( j) with j ∈ N such that ( 16) is satisfied is a tractable problem in general, even for non-polytopic and nonconvex sets A(∆). Then, the only main computational issue for the practical application of the result of Theorem 22 is checking whether the condition (17) is satisfied, i.e. if Ax ∈ νΩ

( j) k , ∀A ∈ A(∆), x ∈ Ω ( j) k ⇔ AΩ ( j) k ⊆ νΩ ( j) k , ∀A ∈ A(∆).
Indeed, if the set A(∆) is not polytopic (in which case a finite number of matrices A ∈ A(∆) should suffice to be checked), condition (17) concerns an uncountable number of matrices in A(∆). A possible approach could consist in evaluating the condition for an outer polytopic set A , i.e. for A ∈ A with A polytopic and co(A(∆)) ⊆ A . Nevertheless, once more, the computation of outer approximations of co(A(∆)) could be numerically inefficient, besides of introducing a certain conservatism.

The following considerations are aimed at providing tractable conditions to check whether (17) is satisfied.

Given the two generic sets Λ ⊆ R p×n and A ⊆ R n×m define

ΛA = Γ∈Λ ΓA = Γ∈Λ Σ∈A ΓΣ.
Proposition 26 Suppose that A ⊆ R n×n compact is such that for every C-set Ω there exists λ ∈ [0, 1) such that for all µ ∈ (λ , 1) there is k = k(λ , µ) ∈ N such that condition [START_REF] Luenberger | Optimization by vector space methods[END_REF] holds, with Ω k given by the sequence of sets given by [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF].

If Λ ⊆ R n×n is such that A(∆) ⊆ Λ co(A ), (19)
with

Ψ Ω k (Λ) < µ -1 , (20)
then the linear parametric uncertain system ( 5) is GES and Ψ Ω k (x) is a global exponential Lyapunov function for [START_REF] Aangenent | Performance analysis of reset control systems[END_REF].

Theorem 27 The system ( 5) is GES if and only if for every two sequences of compact sets {A ( j) } j∈N , increasing, and {Λ ( j) } j∈N such that

A ( j) ⊆ co(A(∆)) ⊆ Λ ( j) co(A ( j) ), (21)
and

lim j→+∞ Λ ( j) = I, ( 22
)
there exist λ ∈ [0, 1), ν ∈ (λ , 1), k ∈ N and h ∈ N such that Ω (h)
k , given by ( 18) is ν-contractive for x + ∈ A (h) x and

Ψ Ω (h) k (Λ ( j) ) < ν -1 .
(23)

Finitely determined polytopic Lyapunov functions

We sketch here the procedure for obtaining polyhedral exponential Lyapunov functions, and thus for checking if the nearly-periodic reset system is GES. Many important computational issues, that would deserve to be deeply analysed, are the objective of our current and future research. The first step concern a possible method to generate the sequence of sets in the space of matrices Λ ( j) and A ( j) , with j ∈ N such that conditions (21) and ( 22) hold. Precisely, the sequences of sets Λ ( j) and A ( j) , with j ∈ N satisfying (21) and ( 22) can be constructed as follows:

A ( j) = j i=0 e A c τ ( j) i A m , τ ( j) = (τ M -τ m ) j -1 , ∆ ( j) = [0, τ ( j) ], Λ ( j) = δ ∈∆ ( j) e A c δ , (24)
with A m = e A c τ m A r .

Then, the testing procedure consists in iterating through j ∈ N to obtain the structures in (24). For every j, a polytope Ω ( j) k that is robustly contractive for A ( j) is computed (where k depends on j) and then condition (23) is checked. If it holds, then the polytope Ω ( j) k is contractive also in presence of the uncertainty induced by Λ ( j) and thus the impulsive system is GES and the function induced by Ω and ∆ = [0.5, 1.5]. Notice that, whereas the discrete-time transition matrix A r is Schur, A c has two complex conjugate poles with positive real part and then e A c t = e 0.1t cos(t) -e 0.1t sin(t) e 0.1t sin(t) e 0.1t cos(t) , thus, the continuous-time trajectories are diverging spirals. Such divergence must be compensated by the reset action to have stability. Notice that A(∆) is neither a polytope nor a convex set. Applying the procedure illustrated in Section 0.4.3 we proved that the system is GES. For different values of j we computed Ω ( j) k for an appropriate λ and then check if (23) holds (with, in our case, λ = ν). We found that for different values of j > 1, the condition can be satisfied whereas is not for j = 1. Some numerical results are summarized in Table 1. Thus, the impulsive system with (25) is GES. Although the analysis with j = 2 would have been sufficient to asses GES, we wanted to stress that the procedure can be applied for much higher j highlighting the computational flexibility of the approach.

Conclusions

In this paper we employ set theory to provide a tractable method for testing whether an impulsive linear system is globally exponentially stable. The reset rule considered in this paper is assumed to be nearly-periodic. We provide a method for obtaining a polyhedral Lyapunov function, whose existence is necessary and sufficient for the system to be GES. The approach is particularly suitable since the computational burden is analogous to that required for linear uncertain polytopic systems. Many issues related to the computational aspects are among the objectives of our current research.

Table 1 :

 1

		j = 1	j = 2	j = 5	j = 10 j = 12 j = 15
	λ	0.874	0.88	0.90	0.91	0.91	0.92
	k	4	10	9	9	9	9
	Ψ Ω µ -1 ( j) k	1.1554 1.1149 1.0234 1.0128 1.0175 1.0190 1.1442 1.1364 1.1111 1.0989 1.0989 1.0870

 [START_REF] Clegg | A nonlinear integrator for servomechanisms[END_REF]The work of I.-C. Morȃrescu was funded by the ANR project COMPACS-"Computation Aware Control Systems", ANR-13-BS03-004-02.