Except for few works [START_REF] Antonie | An associative classifier based on positive and negative rules[END_REF][START_REF] Baralis | Associative text categorization exploiting negated words[END_REF], these methods use classical association rules, i.e., rules of the form X → c where X is a set of attributes and c is a class value. Such a rule is used for prediction: when the conjunction of attributes X is satisfied, then the class value c is predicted. Basically, current approaches mine all classification rules satisfying some interestingness measures (e.g., frequency, confidence), then classifiers are designed by selecting some of these candidate classification rules. Surprisingly, there are very few attempts for handling the natural generalization of association rules to rules with a disjunction in the conclusion X→ ∨Y . We will see in Section 5 that, for classification purposes, these rules can be viewed as rules with negations of attributes in the premise (i.e., rules of the form X ∧Y → c) and possibly in the conclusion (rules X ∧ Y → c). In the first case, the class c is prescribed for the objects containing X but no attribute of Y , whereas in the second case this class is excluded. In this context, a particular case of rules excluding classes is proposed in [START_REF] Antonie | An associative classifier based on positive and negative rules[END_REF]: rules are built from patterns evaluated as interesting w.r.t. classes according to a statistical measure.

Such a lack on using generalized association rules may be explained by the hard task of mining these rules. In this chapter, we propose a complete and correct algorithm mining all frequent exact generalized association rules with a minimal premise and conclusion, by using the recent developments in condensed representations of patterns and hypergraph transversals computing. Generalized rules offer an extended semantics as compared to classical rules, and it is natural to expect that they improve classification based on associations. Studying this question is the goal of this chapter. Our aim is to evaluate the impact of disjunction in classification based on association rules. For that purpose, we rewrite generalized rules into rules with negations and we investigate the impact of using such rules instead of classical ones in the classification process. This task is performed by using the CMAR classification method [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] because it is considered as a reference in the area of associative classification. We compare the results obtained with CMAR when using either classical or generalized association rules. Since only the set of rules is modified, this enables us to estimate the impact of disjunction.

The contribution of the chapter is twofold. First, we propose a method to mine the whole set of frequent exact generalized association rules with minimal premise and conclusion, possibly with exceptions. The property of minimality is a key point in building classifiers: it is well-known with classical rules [START_REF] Bayardo | The hows, whys, and whens of constraints in itemset and rule discovery[END_REF] and we will see that it is also the case for generalized association rules. Second, we study the extended semantics induced by disjunction and its impact on classification based on associations. We use the CMAR technique as a reference, adapting it for using generalized rules. We insist that our goal is not to propose the "best" classification method, but to study the interest of enhancing classification methods based on association rules with generalized rules. We evaluate this impact on numerous UCI benchmarks, and our results show that the use of disjunction is not so simple.

This chapter is organized as follows: we first recall the definition of classical association rules, then we sketch the supervised classification methods using them, and introduce generalized association rules (Section 3). Then we present a correct and complete method for extracting the set of nonredundant generalized rules (Section 4). We show how they can be used in supervised classification, and we present our experiments with CMAR enhanced with generalized rules (Section 5). Finally, based on these experiments, we discuss the impact of generalized rules (Section 6).

Association Rules and Classification

This section provides the background on association rules and classification based on associations (AR-based classification) which is required for this chapter.

Database and Patterns

A database is defined by a boolean context r = (A , O, R), where O is a set of objects, A a set of boolean attributes and R a binary relation between the objects and the attributes. Table 1 gives an example of database. An object is also a subset of A . For instance, the object o 1 = {a 1 , a 3 , a 5 } is noted a 1 a 3 a 5 . For supervised classification, each object is labelled by a single-valued class attribute c belonging to C = {c 1 ,... ,c n }, a subset of the attribute set. In our running example (cf. Table 1), the class labels are a 1 and a 2 , thus also noted c 1 and c 2 .

o 1 × × × o 2 × × × o 3 × × × o 4 × × × o 5 × × × o 6 × × × o 7 × × × o 8 × × × classes c 1 c 2 A pattern X is a subset of A , its support in r is the set of objects containing X (we note supp(X) = {o ∈ O | X ⊆ o}) and its frequency is F (X) = |supp(X)| i.e.
, the number of objects in its support. In Table 1, supp(a 2 a 3 ) = o 2 o 5 o 6 and its frequency is 3.

Association Rules

Let X and Y be two nonempty and disjoint patterns. A classical association rule [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF] is an expression X → Y , where X is called the premise and Y is called the conclusion.

In such a rule, both X and Y are interpreted conjunctively, that is, the rule is read

(x 1 ∧ ••• ∧ x k ) → (y 1 ∧ ••• ∧ y d )
where X = {x 1 ,... ,x k } and Y = {y 1 ,...,y d }, and it says that (up to its confidence) the objects which support X also support Y . The quality of such an association rule is evaluated by interestingness measures (computed relatively to a database) such as frequency

(F (X → Y ) = F (X ∪ Y )) and confidence (con f (X → Y ) = F (X ∪Y )/F (X)).
Intuitively, the frequency of a rule is the number of objects for which it fires and is true, and its confidence is the conditional probability that it is true for an object which supports X. In our example, the rule a 1 a 3 → a 5 has a frequency of 2 and its confidence is 1 (such a rule is said an exact association rule), whereas a 2 a 3 → a 6 has a frequency of 2 and its confidence is 2/3.

Classification Based on Association Rules

Supervised classification aims at building a classifier from a training set in order to predict the class attribute of unseen examples.

In supervised classification, one usually has to cope with two main issues. Overfitting is the most well-known one. A classifier is said to overfit the training set when it uses rules too specific to this set. In this case, the rules are very efficient on the training set but are not able to generalize the prediction process to unseen examples. In the area of association rules, restricting to nonredundant rules with high enough frequency limits this problem [START_REF] Bayardo | The hows, whys, and whens of constraints in itemset and rule discovery[END_REF]. The second issue is unbalanced class populations [START_REF] Gu | Association rule discovery with unbalanced class distributions[END_REF]. It happens when some classes contain many more objects than some others. In this case, classifiers often tend to focus on the prediction of the prevailing class(es). To cope with this difficulty, constraints on the coverage of the training set are introduced [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF]. For instance, with association rules, a rule is kept for classification only if it classifies at least one object which is not covered by the rules already selected.

In associative classification, each rule may contribute to the decision. Since rules with different conclusions can be triggered by a same object, a vote schema is usually used. Typically, rules are weighted by measures such as χ 2 , which evaluates the correlation between the premise and the conclusion. This technique is used for instance by the CMAR method [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF]. As there are a lot of measures on rules (e.g., frequency, confidence, conviction, χ 2 ) [START_REF] Tan | Selecting the right interestingness measure for association patterns[END_REF] and these measures may lead to different behaviors, this one difficulty is to choose the right measure.

State of the Art of AR-Based Classification

The CBA method [START_REF] Liu | Integrating classification and association rules mining[END_REF] is the pioneer proposal. This method uses the classical interestingness measures of frequency and confidence: rules are first ranked according to their confidence, then according to their frequency. Several other methods improve this rule selection process. CMAR [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] weights rules with a normalized χ 2 between the premise and the conclusion, then selects multiple rules by learning set coverage. As already said, CMAR is often considered as a reference method in associative classification. L3 [START_REF] Baralis | A lazy approach to pruning classification rules[END_REF] extends the cover principle by using the excluded rules when no selected rule is triggered. L3m [START_REF] Baralis | Majority classification by means of association rules[END_REF] improves L3 by using multiple rules. Classical methods (i.e. CBA, CMAR) avoid redundancy by selecting the rules with the best confidence. If two rules have the same confidence, then the one with the highest frequency is kept. Then, if their frequencies are the same, the rule having the shortest premise is selected 1 . These operations are performed by filtering the output of an association rule mining algorithm.

As far as we know, in the context of data mining, there has been no study on using rules with a disjunctive conclusion for classification purposes, as we do here. There have been some works, though, about the use of rules with negative attributes, which is related to disjunction (see Section 4.1). For instance, [START_REF] Antonie | An associative classifier based on positive and negative rules[END_REF] proposes a heuristic technique for mining some specific kind of rules with negations. The technique extracts rules of the form X → Y , X → Y , or X → Y when the correlation of X → Y is negative. This technique does not ensure that the complete set of rules is mined, but this issue has been solved recently in [START_REF] Wang | Mining a complete set of both positive and negative association rules from large databases[END_REF]. In [START_REF] Baralis | Associative text categorization exploiting negated words[END_REF], an enumerative approach is used to build the rules with negations by adding attributes to the premise.

Current tendencies focus on selecting the useful rules more precisely, so that the expert can access them [START_REF] Zaïane | On pruning and tuning rules for associative classifiers[END_REF]. Optimization processes also allow classifiers to learn how to choose the useful rules [START_REF] Zaïane | On pruning and tuning rules for associative classifiers[END_REF]. Since the cover principle depends on the order of the objects, HARMONY [START_REF] Wang | On mining instance-centric classification rules[END_REF] proposes an instance-centric alternative and optimizations for large datasets. Finally, since association rules mining is costly, associative classification can benefit of nonredundant rule extraction [START_REF] Pasquier | Generating a condensed representation for association rules[END_REF][START_REF] Zaki | Generating non-redundant association rules[END_REF]. A first contribution in this direction is given in [START_REF] Bouzouita | Integrated generic association rule based classifier[END_REF].

Comparing the different approaches is complex for several reasons. On the one hand, all prototypes are not available, and experiments are not always reproducible. On the other hand, the articles compare the performances to those of universal classifiers, such as C4.5, Foil, Ripper or CPAR, but not always to other contributions using association rules. In practice, the comparisons are often made according to the official scores given in the reference articles.

Generalized Association Rules

Definitions

In this chapter, we are interested in the generalization of association rules allowing disjunction in the conclusion. From a logical point of view, classical association rules can be seen as Horn rules/clauses of the form X → y, while generalized association rules can be seen as generalized rules/clauses of the form X → (y

1 ∨ ••• ∨ y d ).
So, due to the well-known fact that any propositional formula is logically equivalent to a conjunction of clauses, any association, possibly involving negative attributes and complex Boolean combinations in the premise and the conclusion, can be represented as a set of generalized association rules 2 . So, from a logical point of view, generalized association rules are fully expressive, contrary to classical rules. Of course, we will not use this expressive power to overfit the data in the training set, but instead we will select rules among this bigger set of rules.

As we shall see in more details in Section 5.1, a positive attribute in the conclusion is logically equivalent to the negation of this attribute in premise: we have

(X → y ∨ Y ) ≡ (X ∧ y → ∨Y ), and dually (X ∧ x→ ∨Y ) ≡ (X → x ∨ Y ).
In this section, though, we stick to the definition with disjunction, since both visions differ when it comes to defining support and confidence. We first defined generalized rules (they are named disjunctive rules in [START_REF] Calders | Minimal k-free representations of frequent sets[END_REF]).

Definition 1 (generalized association rule). Let X,Y be two nonempty and disjoint patterns.

A generalized association rule based on Z = X ∪ Y is an expression X→ ∨Y . Its depth is the number of attributes in Y . Given a database, the frequency of X→ ∨Y is F (X), and it is exact if every object which supports X also contains at least one attribute of Y .

Example 1. In Table 1, each object containing a 6 contains a 2 or a 4 , so the rule a 6 → a 2 ∨ a 4 is exact.

Observe in Definition 1 that the frequency of a generalized rule is not defined as for classical rules. Indeed, for a generalized rule X→ ∨Y , it would make no sense to reason on the frequency of X ∪Y , because different objects can support different subsets of Y . Note however that when Y contains only one attribute, the rule X→ ∨Y is equivalent to the classical rule X → Y in the sense that one is exact in a database if and only if the other also is, and their frequencies are the same.

We now define nonexact generalized rules. In the context of classical rules, it is well-known that exact rules are not sufficient for classification purposes, in particular because they tend to overfit the training data and do not allow to cope with noise [START_REF] Bayardo | The hows, whys, and whens of constraints in itemset and rule discovery[END_REF]. There are two main ways of defining nonexact rules. The first one is to consider rules with confidence less than 1, that is, with some probability of being false on an example, where the probability is fixed for the whole set of rules. The second way, which we follow here, is to allow a fixed number of exceptions to the rules. So, the difference between both approaches is as follows. If the confidence is fixed, then the higher the frequency of a rule, the greater the number of exceptions to it allowed. Dually, if the number of exceptions is fixed, the higher the frequency of a rule, the greater the confidence required for it.

Definition 2 (δ -approximative association rule). Let X,Y be two nonempty and disjoint patterns. The generalized association rule X → ∨Y is said to be

δ -approximative if |{o ∈ O | X ⊆ o ∧ o ∩Y = / 0}| ≤ δ .
Example 2. On the toy example (Table 1), the rule a 6 → a 2 is 1-approximative : each object supporting a 6 supports also a 2 , except o 4 .

We will discuss the impact of considering exceptions instead of confidence in Section 5.2 and 6.3. Observe however that in both definitions, an exact generalized rule already summarizes nonexact classical rules. For example (Table 1), the generalized rule a 2 a 3 → a 5 ∨ a 6 is exact (with frequency 3), and it summarizes the two classical rules a 2 a 3 → a 5 (frequency 1 and confidence 1/3) and a 2 a 3 → a 6 (frequency 2 and confidence 2/3). So, in some sense, using disjunction in the conclusion already involves some considerations of nonexactness.

We wish to emphasize here that, though a generalized rule, say, X → y 1 ∨••• ∨y d , can be seen as the rule with negation, say,

X ∧ y 1 ∧ ••• ∧ y d-1 → y d ,
this is true only from a logical point of view. Indeed, in general the frequency of both rules will be different. For our running example, the rule a 3 → ∨a 2 ∨ a 5 is exact and its frequency is 5, but the frequency of the corresponding rules with negation a 3 ∧ a 5 → a 2 is only 3. So our approach focuses on supports and exactness defined on the presence of attributes, while rules with negations consider the absence of an attribute at the same level as the presence of one.

Nonredundant Generalized Rules

We now define several notions of nonredundancy for generalized rules. Such notions (minimal, free premise) have been defined for classical rules and have proven to be useful, especially because focusing on nonredundant rules drastically reduces the number of rules (to be extracted and stored) without impacting classification [START_REF] Bouzouita | Integrated generic association rule based classifier[END_REF]. Our definitions are rather straightforward generalizations of those for classical rules.

Definition 3 (minimal conclusion).

A generalized association rule X → ∨Y is said to have a minimal conclusion in a database r if there is no rule X → ∨Y with Y ⊂ Y and admitting the same number of exceptions as X → ∨Y in r. 3Definition 4 (minimal premise). A generalized association rule X → ∨Y is said to have a minimal premise in a database r if there is no rule X → ∨Y with X ⊂ X and F r (X ) = F r (X). 4As in the classical case, it turns out that minimal premises of rules coincide with free patterns (defined below). We will use this property for reusing well-known extraction techniques in Section 4.3, using the important fact that the notion of freeness is independent from the rule under consideration. Recall that a (classical) rule is said to be based on X if it is of the form X → X with X ∪ X = X. Intuitively, a pattern is free in a database if its frequency is less than that of any of its subsets.

Definition 5 (free/key pattern [11, 25]).

A pattern X is said to be free in a database r if there is no classical rule which is based on X and exact in r. Proposition 1. An exact generalized association rule X → ∨Y in a database r has a minimal premise if and only if X is free in r.

Proof. The proof works as in the classical case. If X 1 → X 2 is an exact rule based on X in r, then every object supporting X 1 also supports X 1 ∪ X 2 = X. So F r (X 1 ) = F r (X) while X 1 X, and X→ ∨Y does not have a minimal premise.

Conversely, if X→ ∨Y does not have a minimal premise, then let X → ∨Y be a rule such that X ⊂ X and F r (X ) = F r (X). From F r (X ) = F r (X) we get that every support for X is one for X, and so that the classical rule X → X \ X is exact in r. So X is not free in r.

Based on these well-defined notions of nonredundancy, we can now define the notion of irredundant generalized rule. From the definitions above it follows that for every generalized rule X→ ∨Y in r, there is an irredundant generalized rule of the form X → ∨Y with X ⊂ X, Y ⊂ Y , and the same frequency and number as exceptions as X→ ∨Y in r. So, irredundant generalized rules cover all generalized rules, just as is the case for classical rules.

Definition 6 (irredundant generalized rule). A generalized rule X → ∨Y is said to be irredundant in a database r if it has a minimal premise and a minimal conclusion in r.

Mining Generalized Rules

In this section, we give our proposal for mining generalized (frequent, irredundant) rules from a database r. We first survey existing approaches for tasks related to this one, then give the necessary background on hypergraph transversals, and finally give our algorithm.

Existing Approaches

Mining generalized rules under a frequency constraint is a hard task. A naive approach is to add the negation of each attribute as a new attribute to the database, then compute classical rules. This leads to rules with negation (e.g., X ∧ Y → y) which in turn can be seen as disjunctive rules (X → y ∨ Y ). Nevertheless, with this approach the frequency computed is that of X ∧Y , which is different in general from that of X → y ∨Y (defined to be the frequency of X). Moreover, this approach leads to very dense databases, which are intractable for extraction of classical rules [START_REF] Boulicaut | Towards the tractable discovery of association rules with negations[END_REF].

In the same vein, one can find a lot of contributions about mining rules with negation: [START_REF] Chan | An effective algorithm for mining interesting quantitative association rules[END_REF][START_REF] Thiruvady | Mining negative rules using GRD[END_REF] restrict the conclusion to one attribute, [START_REF] Antonie | An associative classifier based on positive and negative rules[END_REF] focuses on classical rules X → Y and considers rules of the form X → Y (the conclusion is a conjunction of negative attributes), X → Y , or X → Y , depending on the correlation between X and Y in the database. [START_REF] Yuan | Mining negative association rules[END_REF] uses the same heuristic, but the rules are computed using a taxonomy of equivalent attributes. Some other approaches are restricted to a conjunction of negated attributes in the conclusion: [START_REF] Wu | Efficient mining of both positive and negative association rules[END_REF] uses an anti-monotonic measure for pruning the search space, [START_REF] Cornells | Mining positive and negative association rules from large databases[END_REF][START_REF] Wang | Mining a complete set of both positive and negative association rules from large databases[END_REF] introduce one by one the negated attributes which are not present in the premise, and [START_REF] Dong | Mining both positive and negative association rules from frequent and infrequent itemsets[END_REF] uses two frequency bounds for frequent and infrequent patterns.

To the best of our knowledge, the only approach mining generalized frequent patterns (and, more generally, arbitrary Boolean expressions) is given in [START_REF] Zhao | A framework for mining arbitrary boolean expression[END_REF], but it does not focus on generalized rules nor on classification. This work mines nonredundant patterns with the help of a closure operator related to the maximality of a pattern for the support equivalence class. Our approach is different because our notion of nonredundancy is rule-oriented, and we do not need only exact expressions. Nevertheless, we also use minimal transversals for computing nonredundant conclusions [START_REF] Rioult | Mining correct properties in incomplete databases[END_REF].

In the field of logic, efficient algorithms are available, but they are not adequate for classification based on association rules. For example, [START_REF] Zanuttini | A unified framework for structure identification[END_REF] gives a quadratic algorithm for mining a set of generalized rules with minimal premises and conclusions, from which any other rule follows by the standard resolution rule. But the resulting set gives a covering of all (exact) associations in the dataset, and so exactly fits the dataset, which is not relevant for prediction purposes.

Hypergraph Transversals

We now present hypergraph transversals (also known as hitting sets). Briefly speaking, a hypergraph is a set of patterns, and a transversal is a pattern intersecting with each element of the hypergraph. Computing minimal hypergraph transversals has been widely studied [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF] and is related to many other problems in the field of data mining [START_REF] Gunopulos | Data mining, hypergraph transversals, and machine learning[END_REF]. We use here algorithms which compute minimal transversals for computing the (nonredundant) conclusions of generalized association rules (see Section 4.3).

A hypergraph H = (V, E ) is a couple of vertices and hyperedges. This notion generalizes the notion of a graph, because hyperedges are subsets of V (instead of pairs in a graph). We define hypergraphs starting from a Boolean context.

Definition 7 (hypergraph). Let r = (A , O, R) be a Boolean context. Then r defines the hypergraph H r whose vertices are the attributes A of r and whose hyperedges are the patterns corresponding to the objects of r.

Conversely, a Boolean context r H can be defined starting from a hypergraph H .

Definition 8 (transversal). Let

H = (V, E ) be a hypergraph. A set of vertices Y ⊆ V is a transversal of H if for all E ∈ E , E ∩Y = / 0 holds. It is a minimal tranversal of H if moreover, no Y ⊂ Y is a transversal of H . It is a minimal δ -approximative transversal of H if moreover |{E ∈ E | Y ∩ E = / 0}| ≤ δ , and for no Y ⊂ Y we have |{E ∈ E | Y ∩ E = / 0}| = |{E ∈ E | Y ∩ E = / 0}|.
Example 3. The hypergraph corresponding to our example is H = (V, E ) with V = {a 1 ... a 7 } and E = {a 1 a 3 a 5 , a 2 a 3 a 5 ,... a 2 a 4 a 7 }. a 1 ...a 7 is a trivial transversal of H , but it is not minimal. a 2 a 4 a 5 is a minimal one, and a 2 a 4 is 2-approximative.

The problem of mining the minimal transversals of a hypergrah is equivalent to the MOnotone Normal Form Equivalence Test (MONET), and as such it is at the core of many practical applications in logic, graph theory, data mining, etc. [START_REF] Hagen | Algorithmic and computational complexity issues of monet[END_REF].

Its algorithmical aspects are very interesting, because it is a good candidate as a problem separating P from NP.

The main algorithm for computing the transversals of a hypergraph are detailed in [START_REF] Hagen | Algorithmic and computational complexity issues of monet[END_REF], where it is also shown that none of them is output-polynomial. Fredman-Kachyian's algorithm [START_REF] Fredman | On the complexity of dualization of monotone disjunctive normal forms[END_REF] has the best theoretical time bound (n o(log n) ), but practical experiments make it hard to choose the best algorithm overall. In this paper, we use our proposal from [START_REF] Hébert | A data mining formalization to improve hypergraph transversal computation[END_REF], called MTMINER. This algorithm is original in the way that it mines the tranversals, namely in a levelwise manner. This is an essential aspect which we need for mining special kinds of tranversals: minimal of course, but also with bounded length or with exceptions.

Mining Nonredundant Generalized Rules

We now present our method for mining nonredundant generalized association rules in a database r. To that aim, we first establish the link between these rules and the transversals of the hypergraph defined from r, and then give our algorithm.

Definition 9 (pattern restriction). Let r = (A , O, R) be a boolean context. Let X be a pattern. Then the restriction of r to X, written r[X], is the database (A , O , R )

where A = A \ X, O = supp r (X), and R is the restriction of R to A × O .

Informally, the restriction of r to X is the multiset of all objects described by the pattern X such that the pattern X ∪ X describes an object in r. Proposition 2. Let r be a database and X be a pattern. The patterns Y , such that X→ ∨Y is an exact (resp. δ -approximative) generalized association rule in r, are exactly the transversals (resp. δ -approximative transversals) of the hypergraph defined from r[X].

Proof. Assume X→ ∨Y is exact in r. Then by definition of exactness, every object in r which supports X also contains at least one attribute of Y . From Definition 1, X and Y are disjoint. It follows that every object in r[X] contains at least one attribute in Y . This is equivalent to say that the hypergraph r[X] has Y as a transversal. The converse is shown similarly, and so is the case of δ -approximative rules.

Using Propositions 1 and 2, we derive the following corollary, which is at the core of our method for mining irredundant generalized association rules.

Corollary 1. Extracting the exact (resp. δ -approximative) irredundant generalized association rules with frequency at least γ in a database r amounts to:

1. extract all patterns X which are free and with frequency at least γ in r, 2. for each such X, extract the minimal transversals (resp. δ -approximative minimal transversals) Y of the restriction r[X], 3. for each such couple (X,Y ), generate the generalized association rule X → ∨Y .

Using the results above, the lδ -miner algorithm (depicted as Algorithm 1) mines the nonredundant frequent generalized classification rules. Since we will use such rules for classification purposes, the algorithm restricts to the rules which contain a class attribute in premise or in conclusion.

Algorithm 1. lδ -miner-Mining nonredundant generalized classification rules.

Data: a boolean context r, a minimum frequency threshold γ, and a maximum number of exceptions δ (δ = 0 for exact rules). Result: the set RU L E S of all generalized classification rules which are nonredundant, with frequency at least γ, and with at most δ exceptions in r.

RU L E S ← / 0; We now give details for mining the free patterns and the minimal transversals, as required by Algorithm 1.

Since freeness and frequency constraints are anti-monotonic, we use a levelwise approach for mining the premises of the rules. This strategy allows for efficient pruning conditions [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF]. The method is depicted as Algorithm 2, where apriori gen is the classical procedure for producing next-level candidates from the current-level frequent and free patterns [START_REF] Agrawal | Fast discovery of association rules[END_REF]. In a nutshell, apriori gen generates X ∪ {a, b} from X ∪ {a} and X ∪ {b} if all subsets of X ∪ {a, b} are frequent and free. As compared to the classical apriori-like frequent pattern mining algorithm [START_REF] Agrawal | Fast discovery of association rules[END_REF], Algorithm 2 only adds the freeness constraint at Step 3.

Algorithm 2. Mining free patterns.

Data: a boolean context r = (A , O, R), a minimum frequency threshold γ. Result: the set F ree of all patterns which are free and with frequency at least γ in r. k ← 1;

1 C and 1 ← {{a} | a ∈ A }; 2 repeat 3 F ree k ← {X ∈ C and k | F (X) ≥ γ ∧ (∀X X, F (X) < F (X ))}; 4 k + +; 5
C and k ← apriori gen(F ree k );

6 until F k = / 0 ; 7 return F ree = i=1..k F ree i ; 8
Mining the minimal transversals (Algorithm 3) uses the same search algorithm, but with the anti-frequency instead of the frequency constraint. Anti-frequency is defined by

F (X) = |{o ∈ O | X ∩ o = /
0}|. Details and proofs for Algorithm 3 can be found in [START_REF] Hébert | A data mining formalization to improve hypergraph transversal computation[END_REF]. Let us simply give the intuition that the anti-frequency constraint is anti-monotonic, and that when it is null the corresponding pattern is a tranversal. Generators, whose anti-frequency is not strictly less than that of any of their subsets, are not minimal and are pruned.

| 7 F (X) ≤ δ ∧ (∀X X, F (X) < F (X ))}; 8 until M inTr k = / 0 ; 9 return M inTr = i=1..k M inTr i ; 10
When compared to the classical minimal transversals algorithms, the interest of Algorithm 3 lies in the fact that it can easily provide minimal transversals with constraints. The version presented on Figure 3 integrates the constraint on the number of exceptions, but we also used this algorithm with a constraint on the length of minimal transversals/depth of generalized rules for our experiments (see Section 5.2). Indeed, since the algorithm browses the search space in a levelwise manner (where the current level is the length of the transversals generated), it can be straightforwardly restricted to a maximum length.

Using Generalized Rules in a Classification Process

This section presents our experiments and results about the impact of using generalized rules (instead of classical ones) in a classification process, such rules being provided by Algorithm 1. We first show how a generalized rule can be seen as a rule prescribing or excluding a class value, possibly with negations in the premise and/or the conclusion. It enables us to handle experiments with the CMAR method for AR-based classification.

From Generalized Rules to Classification Rules

The link from generalized rules to classification rules is done via the following definition and proposition. Say that a rule with negations of the form

Definition 10 (classification rule). Let o ∈ O be an object, X,Y be two nonempty and disjoint patterns, and let c

X ∧ Y → c (resp. X ∧ Y → c) is exact in r if all
objects in r which support all attributes of X but none of Y also support c (resp. do not support c), and similarly when exceptions are allowed. Then we have the following.

Proposition 3. Let X,Y be two nonempty and disjoint patterns, and let c / ∈ (X ∪Y ) be a class attribute. The rule X ∧Y → c (resp. X ∧Y → c) is exact in a database r if and only if the rule X→ ∨(Y ∪ {c}) (resp. (X ∪ {c})→ ∨Y ) is exact in r. The same holds for δ -approximative rules.

Proof. We consider δ -approximative rules, since exact rules are a particular case of them. The rule X ∧ Y → c has less than δ exceptions in r if and only if (by definition) we have

|{o ∈ r | X ⊆ o, o ∩Y = / 0, c / ∈ o}| ≤ δ . This is exactly the same as |{o ∈ r | X ⊆ o, X ∩(Y ∪{c}) = / 0}| ≤ δ , which is the definition of X → (Y ∪{c}) being δ -approximative in r.
Now to the case of X ∧ Y → c. This rule has less than δ exceptions in r if and

only if we have |{o ∈ r | X ⊆ o, o ∩ Y = / 0, c ∈ o}| ≤ δ , that is, |{o ∈ r | X ∪ {c} ⊆ o, o ∩Y = / 0}| ≤ δ , that is, (X ∪ {c})→ ∨Y is δ -approximative in r.

Using Generalized Rules in CMAR

We now present how we have adapted CMAR [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] in order to handle nonredundant generalized rules, seen as rules with negations prescribing or excluding a class. By only changing the type of the used rules, we can understand the impact of nonredundant generalized rules in classification. We use CMAR because this method is considered as a reference in the area of associative classification. Its performances are great, and it is technically very complete: nonredundant rules, χ 2 selection, cover principle and multiple rules vote.

For a new object, some rules prescribe or exclude one or several classes, and each rule contributes positively or negatively with its measure. In CMAR, a weighted χ 2 quantifies the correlation between the premise X and the conclusion c (in the case of a classical rule X → c). This χ 2 score is obtained from the contingency table between X and c. Now consider the case of a generalized rule X ∧Y → c. To tackle such a rule, we use a natural adaptation with a contingency table between X ∧Y and c. A rule with negations, prescribing c, will be interesting if c is predominantly present with X. In order to measure this interest, we compute a local χ 2 on the only objects containing X, between Y and c. This follows the same intuition as that for the frequencies of generalized rules, which in our approach is computed on the presence of attributes (see the end of Section 3.1).

After rules have been selected by training set coverage, the vote schema is straightforward: if an object matches the premise of a rule prescribing (resp. excluding) a class c, then this class receives a positive (resp. negative) contribution from the χ 2 . The final decision is to prescribe the class with the highest sum of contributions.

Avoiding over-fitting. Generalized rules turn out to be uninteresting for classification if their conclusion is too large: this leads to overfitting. So, in practice we only extract generalized rules of depth limited to 1 (classical rules), 2, or 3 attributes. Experiments show that larger conclusions are useless. Moreover, since the complexity of Algorithm 1 lies in computing the minimal transversals, restricting the depth of rules (the length of transversals) also lightens the computation.

Allowing exceptions in classical rules. We compare the results of CMAR with generalized rules to those with classical rules. Classical association rules are usually mined under frequency and high confidence constraints. Although we use the frequency threshold, we select (classical) rules with a small number of exceptions, rather than with high confidence. More precisely, let δ ≥ 0 be a user-specified number of tolerated exceptions (e.g. 0, 1, 2, 3 in our experiments): we select only the classical rules

X → Y such that F (X) -F (X ∪ Y ) ≤ δ (their confidence is over 1 -δ F (X)
, and thus high). Moreover, this kind of rules maximizes a large variety of interest measures, obviously the confidence, but also the lift, Laplace, Jaccard, conviction, etc. [START_REF] Hébert | A unified view of objective interestingness measures[END_REF]. The confidence is not defined for generalized rules, so we use a fixed number of exceptions instead. Section 6.3 shows that the adaptation of the confidence framework to the use of exceptions is running.

Results

Our classification method is named lδ -miner: l is the depth of the rules and δ is the number of authorized exceptions. The performances have been evaluated on UCI benchmarks [START_REF] Blake | UCI repository of machine learning databases[END_REF], the minimum frequency threshold is set to 1, 2 or 5%, δ goes from 0 to 3 and the depth l varies from 1 to 3. The lδ -miner parameters reported in Table 2 are those who gave the best score.

This table shows the classification scores after a 10-cross-validation on several benchmarks for the reference methods C4.5, CBA et CMAR and gives the results for lδ -miner and the corresponding parameters. The columns tell the characteristics of the datasets and the lδ -miner parameters for the best score over the experiments: dataset :

the name of the dataset type : the type of the rules: + for cl :

the number of classes prescribing rules, -for excluding obj :

the number of objects rules, = for the union of both attr :

the number of attributes l : the conclusion length c45 :

the C4.5 score [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] δ : the maximum number of cba :

the CBA score [START_REF] Liu | Integrating classification and association rules mining[END_REF] tolerated exceptions cmar :

the CMAR score [START_REF] Li | Cmar: Accurate and efficient classification based on multiple class-association rules[END_REF] γ : the minimum frequency threshlδ -miner: the score of our method old (in %)

The last column named time tells how much time it took for the whole crossvalidation process. This time gives an indication about the hardness of the task, which mainly lies in rule mining. This table shows that our adaptation lδ -miner of CMAR is operational and reaches similar performances. Sometimes, results can be even better than CMAR, because synergy between prescribing and excluding rules is powerful. Moreover, negations in premise (when l ≥ 2) also improve some scores.

Let us recall that our purpose does not concern the proposition of the best classification method, but aims at studying the interest of enhancing an AR-based classification methods with rules containing negations. As our method is effective, we can use it to measure the impact of the negations: the next section details this impact regarding the different type of rules. • the extraction time (top part) is exponential with the minimum support, and increasing the depth l of the rules induces an exponential increase. • the number of rules has the same behavior: it is exponential according to the depth. We did not represent the impact of the number of exceptions on the running time and the number of rules, because the number of exceptions polynomially makes the running time longer and the number of rules bigger.

Computational Aspects

These experiments confirm the intuition that the higher the depth of the rule, the huger the number of rules and the computation time. This fact can improve the traditional classification model, as shown in the next section.

Discussion about the Semantics of the Generalized Rules

The contribution of the negations for the supervised classification is discussed through three axis:

1. What is the interest of class excluding rules? These rules stem from the generalized rules containing a class attribute in premise. 2. Is the use of rules with negations in premise advantageous? Varying the depth of the generalized rules allows to study the contribution of the negations in premise. 3. Are the δ -approximative rules useful and better than exact rules ? We compare the results obtained with various values of δ .

Contribution of Rules Excluding Classes

Figure 2 compares the scores for the rules prescribing the classes (noted lδ -miner +), the rules excluding the classes (lδ -miner -) or the rules combining both types (lδ -miner =). This figure plots the gap between the best scores for each method and the reference score of lδ -miner (Table 2). This kind of presentation allows to better show the contribution of each type of rule. We first notice that the three types of rules lead to similar results, but classical rules prescribing classes are the best in average. This confirms the intuition that the useful knowledge simultaneously lies in rules prescribing or excluding classes. The gap between the results can be explained by the lack of optimization dedicated to the method using rules excluding classes, and refers to our perspectives. In particular, minimum support should be adapted.

The rules excluding classes give lower scores, but sometimes slightly improve the classical rules: breast (0.5%), sonar (0.5%), vehicle (2.1%) and wine (0.8%). In these cases, combining both types of rules may lead to better scores.

We can conclude that focusing on classical rules prescribing classes is enough, because their expressive power enhances the available knowledge that they are able to translate. This knowledge is similar as the one obtained by involving excluding classes. On a computation point of view, let us remark that rules excluding classes are not harder to mine than rules prescribing classes. If they improve the process, one should not worth ignore them. The classical rule mining algorithm has indeed not to be updated, the method should just focus on the rules containing a class attribute in premise.

Impact of Negation in Premise

Figure 3 shows the impact of the conclusion length for the generalized rules, i.e. the number of negations in the premise. It plots the gap between the best scores for l = 1, 2, 3, δ = 0 and the reference score of Table 2. l = 1 corresponds to the classical exact association rules, and when l = 2 (resp. 3) there are one (resp. two) negation in the premise. We can see that the classical exact rules (l = 1) often give the best score, compared to the rules with l = 2 or l = 3. This score does not always reach the reference score, because the latter can be obtained by allowing some exceptions in the rule (δ = 1, 2, 3, see Table 2 for details). It shows that the exact rules are not sufficient for the best scores.

On some datasets, one or two negations in the premise allow to improve the results of classical rules and the contribution is more significative than with a negation in conclusion: anneal (7.7%), glass (0.8%), iris (2.1%), sonar (2.3%) and zoo (1.8%).

In some cases, the expressive power of the rules with negations in premise is better than without negation. It then allows to find rules that do not fit to the classical rules. Moreover, there are much more generalized rules (or rules with negations in premise) than classical rules. This can be useful when the dataset is small (few objects and attributes). In the other cases, the presence of negations lowers the scores, probably because of over-fitting: these rules are too strict and they are not enough generalized. It seems difficult to improve the performances with larger conclusions, because such rules become always more specific. Moreover, the computation time grows quickly with the conclusion length. We conclude that exact rules with negations in premise are hard to enhance but sometimes significantly improve the method.

Impact of the Exceptions for Generalized Rules

We end this discussion with studying the impact of approximative rules compared to exact rules. Figure 4 shows on three charts for l = 1, l = 2 and l = 3 the maximum scores of prescribing rules with δ varying from 0 to 3. The plain line gives the best score for the exact rules.

Except for some datasets (glass, tic-tac-toe, wine and zoo), allowing exceptions in the rules gives better scores than exact rules. This corresponds to the intuition that exact rules over-fit the data and a good classifier needs approximative rules. In classical approaches, approximative rules are obtained with a confidence threshold, below 1. For generalized association rules, confidence has no really sense, but our experiments show that using δ -approximative rules can replace the confidence framework.

Conclusion and Perspectives

In this paper, we have studied the impact of generalized association rules in classification processes, i.e. rules containing negations in premise and prescribing or excluding classes. For that purpose, we have proposed an algorithm to mine the whole set of frequent exact generalized association rules with minimal premise and conclusion, possibly with exceptions. This algorithm takes benefit from recent notions coming from condensed representations of patterns and hypergraph transversals area. We have provided a method to evaluate the impact of such rules and proposed a classifier lδ -miner using rules prescribing and/or excluding classes.

The contribution of generalized association rules in classification is shy: they can improve the scores on a few benchmarks, but classical rules are often sufficient. Using generalized rules for classification is then sensitive. The class excluding rules are easy to mine and do not need any modification for the rule mining algorithm; they can give a slight improvement. The generalized rules with more than one attribute in the conclusion are hard to mine, but can reveal to be very useful when the dataset is small.

Our perspectives focus on two points: first, the optimization of the classification process for rules excluding classes, so that it can fit to the scores with rules prescribing classes. Second, we would like to further investigate rules with negations in premise on large datasets. For that purpose, the exception threshold has to be relative to the number of objects (for example 1 0 / 00 ) or a fraction of the frequency threshold leading to a value close to the notion of confidence. In this chapter, we used fixed values (1..3) that are not well-suited for thousands of objects.

1 foreach pattern X frequent and free in r do 2 if ∃c ∈ C | c ∈ X then 3 foreach 4 add 8 c

 12348 Y minimal δ -approximative transversal of H r[X] do X→ ∨Y to RU L E S ; δ -approximative transversal of H r[X] containing ∈ C do add X→ ∨Y to RU L E S ;

Algorithm 3 .

 3 Mining minimal transversals.Data: a hypergraph H = (V, E ) and a maximum number of exceptions δ (δ = 0 for usual transversals). Result: the set M inTr of δ -approximative minimal transversals of H . k ← 1;

1 r 2 C 3 repeat 4 M 5 k + +; 6 C

 123456 H = (a, O, R) ← the Boolean context deduced from H ; and 1 ← {{a} | a ∈ A }; inTr k ← {X ∈ C and k | F (X) ≤ δ }; and k ← apriori gen({X ∈ C and k-1

  / ∈ (X ∪ Y ) be a class value. The generalized rule X ∪ {c}→ ∨Y is said to exclude the class c for o if X ⊆ o and o ∩ Y = / 0. The generalized rule X→ ∨(Y ∪ {c}) is said to prescribe the class c for o if X ⊆ o and o ∩Y = / 0.

Figure 1

 1 Figure 1 details two computational aspects of mining generalized rules. The results come from the dataset anneal but the experiments on other benchmarks lead to the same shapes.

Fig. 1

 1 Fig. 1 Computational aspects of the depth of the rules. The top charts shows the execution time, the bottom one shows the number of rules, for a depth of l = 1..3.

Fig. 2

 2 Fig. 2 Contribution of class excluding rules

Fig. 3

 3 Fig. 3 Impact of the conclusion length for the generalized rules

Fig. 4

 4 Fig. 4 Impact of δ -approximative generalized rules

Table 1

 1 Example of boolean context r attributes objects a 1 a 2 a 3 a 4 a 5 a 6 a 7

Table 2

 2 Classification scores

		characteristics reference methods	lδ -parameters	time
	dataset cl obj attr c45 cba cmar miner type l δ γ	(sec.)
	anneal 6 898 73 94.8 97.9 97.3	93.5 = 2 0 1	200
	austral 2 69 55 84.7 84.9 86.1	87.5 + 1 1 2	65
	auto	5 202 137 80.1 78.3 78.1	81.6 = 1 0 1	1064
	breast 2 699 26 95.0 96.3 96.4	95.4 + 2 3 1	10
	cleve 2 5 303 43 78.2 82.8 82.2	83.8 + 1 2 5	11
	crx	2 690 59 84.9 84.7 84.9	86.5 + 1 1 1	189
	german 2 1000 76 72.3 73.4 74.9	74.5 + 1 1 1	1930
	glass 6 6 214 34 68.7 73.9 70.1	67.7 = 3 3 5	30
	heart	2 270 38 80.8 81.9 82.2	84.3 + 2 2 5	83
	horse	2 368 75 82.6 82.1 82.6	83.7 + 1 0 5	23
	hypo	2 3163 47 99.2 98.9 98.4	95.1 + 2 2 5	66201
	iono	2 351 100 90.0 92.3 91.5	93.2 = 1 2 2	1885
	iris	3 150 15 95.3 94.7 94.0	95.8 + 2 1 5	7
	lymph 4 148 63 73.5 77.8 83.1	86.2 = 3 0 5	400
	pima	2 768 26 75.5 72.9 75.1	74.3 + 2 2 1	12
	sonar	2 208 234 70.2 77.5 79.4	81.4 = 2 2 5 197091
	tic-tac 2 958 29 99.4 99.6 99.2 100.0 + 1 0 1	32
	vehicle 4 846 58 72.6 68.7 68.8	68.5 -2 0 2	921
	wine	3 178 45 92.7 95.0 95.0	95.3 + 3 2 1	802
	zoo	7 101 43 92.2 96.8 97.1	97.8 = 3 0 5	237
		average	84.14 85.52 85.82	86.3

This order is referred to as CSA (Confidence, Support, size of Antecedent) in[START_REF] Wang | Hybrid rule ordering in classification association rule mining[END_REF].

Observe that the transformation of an arbitrary association into a set of general rules may yield an exponential increase in size.

Observe that by definition of frequency for generalized rules, X→ ∨Y and X→ ∨Y always have the same frequency.

Observe that by definition, if there was such a rule, then the objects supporting X and X would be the same and so, rules X→ ∨Y and X → ∨Y would have the same number of exceptions.


Lars Grüne
email: lars.gruene@uni-bayreuth.de.

Christopher M Kellett
email: chris.kellett@newcastle.edu.au.

ISS-Lyapunov Functions for Discontinuous Discrete-Time Systems

Keywords: Input-to-State Stability (ISS), Lyapunov Methods, Discrete-Time Systems I

Input-to-State Stability (ISS) and the ISS-Lyapunov function have proved to be useful tools for the analysis and design of nonlinear systems in a variety of contexts. Motivated by the fact that many feedback control laws, such as model predictive control or event-based control, lead to discontinuous discrete-time dynamics, we investigate ISS-Lyapunov functions for such systems. ISS-Lyapunov functions were originally introduced in a so-called implication form and, in many cases, this has been shown to be equivalent to an ISS-Lyapunov function of dissipative form. However, for discontinuous dynamics, we demonstrate via an example that this equivalence no longer holds. We therefore propose a stronger implication form ISS-Lyapunov function and provide a complete characterization of ISS-Lyapunov functions for discrete-time systems with discontinuous dynamics.

nonlinear stability theory of the last decades. In this paper we will focus on the ISS property and one of its most useful characterizations: the ISS-Lyapunov function, introduced in [START_REF] Sontag | On characterizations of the input-to-state stability property[END_REF].

Originally formulated in continuous time, the ISS concept and the basic results were soon adapted to discrete time systems. In this paper, we consider discrete-time nonlinear systems given by

x + = f (x, w) (1)
where x ∈ R n , w ∈ R m , and f : R n × R m → R n . We take as inputs those sequences that are locally bounded and we denote this space by W. We denote solutions of (1) by φ :

Z ≥0 × R n × W → R n .
Many of the continuous-time ISS results carry over to the discrete-time setting if the discrete time dynamics are continuous, see [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF]. However, this statement is no longer true when discontinuous dynamics are considered and in this paper we will not impose any regularity assumptions on f (•, •). Besides the fact that certain models naturally lead to discontinuous dynamics, our main motivation for considering discontinuous f are controller design techniques leading to discontinuous dynamics. Indeed, even if the controlled dynamics x + = g(x, u, w) with control input u ∈ U is continuous, the use of a discontinuous controller u : R n → U leads to a discontinuous closed loop system x + = g(x, u(x), w) =: f (x, w) of the form (1). Among modern controller design techniques, optimization based techniques like model predictive control (MPC) naturally lead to discontinuous feedback laws and, in the presence of state constraints, even the corresponding Lyapunov function is typically discontinuous, cf. [START_REF] Grimm | Examples when nonlinear model predictive control is nonrobust[END_REF], [START_REF] Picasso | Robust stability analysis of nonlinear discrete-time systems with application to MPC[END_REF] or [START_REF] Grüne | Nonlinear Model Predictive Control. Theory and Algorithms[END_REF]. Similarly, quantized [START_REF] Nešić | A unified framework for design and analysis of networked and quantized control systems[END_REF], [START_REF] Grüne | Global optimal control of quantized systems[END_REF] or event-based [START_REF] Aström | Event based control[END_REF], [START_REF] Lunze | A state-feedback approach to event-based control[END_REF] feedback laws naturally lead to discontinuous closed loop dynamics.

It was observed before that additional assumptions are required in order to make the usual ISS-Lyapunov function arguments work for discontinuous discrete time systems, see, e.g., [START_REF] Grüne | Numerical ISS controller design via a dynamic game approach[END_REF]Assumptions 7 and 8]. Also, it is known that discontinuities may affect the usual inherent robustness properties of, e.g., asymptotic [START_REF] Kellett | Smooth Lyapunov functions and robustness of stability for difference inclusions[END_REF] or exponential stability [START_REF] Lazar | Lyapunov functions, stability and input-to-state stability subtleties for discrete-time discontinuous systems[END_REF]. It is the goal of this paper to give a comprehensive and rigorous collection of results on ISS-Lyapunov functions for discontinuous systems. Particularly, we present necessary and sufficient Lyapunov function characterizations of ISS, discuss the equivalence of different types of decay estimates for ISS Lyapunov functions, and introduce a stronger variant of an implication-form Lyapunov function

July 30, 2013 DRAFT that is demonstrated to be better suited to the discontinuous setting.

The paper is organized as follows. In Section II we recall the definitions of input-to-state stability (ISS) and dissipative-form ISS-Lyapunov functions and discuss the relation between these concepts as well as different decay properties of the Lyapunov functions in the discontinuous setting. In Section III we recall the standard definition of an implication-form ISS-Lyapunov function and show that in the presence of discontinuities additional conditions are needed in order to conclude ISS from the existence of these Lyapunov functions. In Section IV we present and analyze our new stronger implication-form ISS-Lyapunov function. We show that the existence of such a function is indeed equivalent to the ISS property for discontinuous systems and illustrate the usefulness of this concept by proving two propositions yielding sufficient conditions for ISS.

Conclusions are presented in Section V and proofs of the main results can be found in Section VI.

II. ISS AND DISSIPATIVE-FORM ISS-LYAPUNOV FUNCTIONS

In the sequel, we will denote the class of continuous positive definite functions ρ : R ≥0 → R ≥0 by P. We will also make use of the standard function classes K, K ∞ , L, and KL (see [START_REF] Hahn | Stability of Motion[END_REF] or [START_REF] Kellett | A compendium of comparsion function results[END_REF]).

Definition 2.1: The system (1) is input-to-state stable (ISS) if there exist

β ∈ KL, γ ∈ K such that |φ(k, x, w)| ≤ max β(|x|, k), sup i∈Z [0,k-1] γ(|w(i)|) (2)
for all x ∈ R n , w ∈ W, and k ∈ Z ≥0 .

Definition 2.2:

An ISS-Lyapunov function for (1) is a function V : R n → R ≥0 such that there exist α 1 , α 2 , α ∈ K ∞ and σ ∈ K so that, for all x ∈ R n and w ∈ R m α 1 (|x|) ≤ V (x) ≤ α 2 (|x|) (3)
V (f (x, w)) -V (x) ≤ -α(|x|) + σ(|w|). (4)
An implicit constraint in this definition is that α(|x|) ≤ V (x) for all x ∈ R n .

In [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF]Lemma 3.5] it was shown that the existence of an ISS-Lyapunov function implies ISS. Though the authors of [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF] consider systems described by continuous dynamics and also In the remainder of this section, we discuss several ways to modify the assumption that α ∈ K ∞ in Definition 2.2. We start by observing that this assumption can be weakened to α ∈ K provided an additional compatibility condition between α and σ holds. 3) and ( 4). If

Proposition 2.4: Suppose V : R n → R ≥0 , α 1 , α 2 ∈ K ∞ and α, σ ∈ K satisfy (
sup α > sup σ, then system (1) is ISS.
This follows from results on changing supply functions for ISS systems presented in [START_REF] Sontag | Changing supply functions in input/state stable systems[END_REF] for continuous time and in [START_REF] Nešić | Changing supply functions in input to state stable systems: The discrete-time case[END_REF] for discrete-time. We provide the proof in Section VI-B.

Next we investigate the special case in which α(|x|) in ( 4) can be replaced by λV (x) for some λ ∈ (0, 1). Since this formulation implies exponential decay of V for w ≡ 0, a V with this property is called exponential ISS-Lyapunov function.

Definition 2.5: An exponential ISS-Lyapunov function for (1) is a function V : R n → R >0 such that there exist λ ∈ [0, 1) and α 1 , α 2 ∈ K ∞ and σ ∈ K so that, for all x ∈ R n and w ∈ R m ,

(3) holds and

V (f (x, w)) ≤ λV (x) + σ(|w|). (5)
Despite the lack of any regularity assumptions on either the system dynamics (1) or the ISS-Lyapunov function (3)-(4), we may prove the following converse to Lemma 2.3 which shows that ISS always implies the existence of an exponential ISS-Lyapunov function.

Theorem 2.6: Fix λ ∈ (0, 1) and suppose system (1) is ISS. Then there exists an exponential ISS-Lyapunov function for [START_REF] Angeli | A characterization of integral input-to-state stability[END_REF] with the decrease rate of (5) given by λ.

This result differs from [8, Theorem 1] in three respects. The first is that the obtained ISS-Lyapunov function does not possess any guaranteed regularity properties. This is inevitable since f does not possess any regularity properties, either. The second is that we observe that an ISS-Lyapunov function exists for any desired decrease rate λ ∈ (0, 1). The third is that, while the proof is similar, the proof of [8, Theorem 1] relies on the equivalence of ISS-Lyapunov functions of the form (3)-( 4), what we will call dissipative-form ISS-Lyapunov functions, and the implication-form ISS-Lyapunov functions defined in the next section. In Example 3.7 we will demonstrate that this equivalence does not hold if the system dynamics (1) are not continuous. 4), then, for any λ ∈ (0, 1), there exists a function V : R n → R ≥0 and functions α1 , α2 ∈ K ∞ and σ ∈ K so that

α1 (|x|) ≤ V (x) ≤ α2 (|x|) V (f (x, w)) ≤ λ V (x) + σ(|w|)
for all x ∈ R n and w ∈ R m .

Proof: By Lemma 2.3, an ISS-Lyapunov function implies that (1) is ISS. Theorem 2.6 then yields that, for any λ ∈ (0, 1) there exists an exponential ISS-Lyapunov function.

We will see later in Remark 4.6 that V can in fact be explicitly derived from V as V = α(V )

for some α ∈ K ∞ .

III. IMPLICATION-FORM ISS-LYAPUNOV FUNCTIONS

As an alternate to the "dissipative-form" decrease condition (4), the following "implicationform" ISS-Lyapunov function has frequently been used in the literature: Definition 3.1: An implication-form ISS-Lyapunov function for (1) is a function V : R n → R ≥0 such that there exists α 1 , α 2 ∈ K ∞ , χ ∈ K, and ρ ∈ P so that, for all x ∈ R n and w ∈ R m , (3) holds and

|x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ -ρ(|x|). (6)
As before, there is an implicit constraint that ρ(|x|) ≤ V (x).

Having a merely positive definite decrease rate ρ as in ( 6) is not necessarily convenient for calculations. In many cases, rather than [START_REF] Grüne | Numerical ISS controller design via a dynamic game approach[END_REF] it is useful to have the following class-K ∞ decrease rate: let

V : R n → R ≥0 and α 1 , α 2 , α ∈ K ∞ and χ ∈ K satisfy (3) and |x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ -α(|x|). (7)
A further potentially useful refinement is the following exponential decrease rate: let V :

R n → R ≥0 and α 1 , α 2 ∈ K ∞ , λ ∈ (0, 1), and χ ∈ K satisfy (3) and

|x| ≥ χ(|w|) ⇒ V (f (x, w)) ≤ λV (x). (8)
July 30, 2013 DRAFT

We can demonstrate the following relationship between these three implication-form ISS-Lyapunov functions.

Theorem 3.2:

The following are equivalent:

(i) There exists a ρ ∈ P and an implication-form ISS-Lyapunov function V satisfying ( 6);

(ii) There exists an α ∈ K ∞ and an implication-form ISS-Lyapunov function V satisfying ( 7);

(iii) For any given λ ∈ (0, 1) there exists an implication-form ISS-Lyapunov function V satisfying [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF].

Moreover, for V satisfying (i) there exist α and α ∈ K ∞ such that V in (ii) and V in (iii) can be written in the form V = α(V ) and V = α(V ).

The equivalence of (i) and (ii) was stated in [8, Remark 3.3] and the proof follows as in [START_REF] Jiang | A converse Lyapunov theorem for discrete-time systems with disturbances[END_REF]Lemma 2.8]. The equivalence of (ii) and (iii) follows an argument in the proof of [START_REF] Kellett | Discrete-time asymptotic controllability implies smooth control-Lyapunov function[END_REF]Theorem 6]. The complete proof is provided in Section VI-A.

We now turn to the relationship between dissipative-form ISS-Lyapunov functions (4) and implication-form ISS-Lyapunov functions [START_REF] Hahn | Stability of Motion[END_REF]. While, by Theorem 3.2, we could as easily refer to decrease conditions given by ( 6) or ( 8), our interest here is in demonstrating quantitative equivalences, and hence we will examine the decrease rates given by ( 4) and [START_REF] Hahn | Stability of Motion[END_REF]. We first observe that a dissipative form ISS-Lyapunov function is always an implication form ISS-Lyapunov function.

Proposition 3.3: If there exists a function V : R n → R ≥0 and functions α 1 , α 2 , α ∈ K ∞ and σ ∈ K satisfying (3) and ( 4) then V satisfies [START_REF] Hahn | Stability of Motion[END_REF] with χ .

= α -1 • 2σ ∈ K and α = 1 2 α ∈ K ∞ . Proof: We rewrite (4) as V (f (x, w)) -V (x) ≤ - 1 2 α(|x|) - 1 2 α(|x|) + σ(|w|). (9)
Therefore, with χ .

= α -1 • 2σ ∈ K and α . = 1 2 α ∈ K ∞ we immediately see that |x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ - 1 2 α(|x|). ( 10
)
Remark 3.4: We observe that we can trade off the decrease rate, α and the input-dependent level set defined by χ. In particular, for any ρ ∈ P and ϕ ∈ K ∞ such that ρ(s) + ϕ(s) ≤ α(s),

for all s ∈ R ≥0 we see that V satisfies (6) with ρ . = ρ and χ . = ϕ -1 • σ.
The converse of Proposition 3.3, i.e., moving from an implication-form ISS-Lyapunov function to a dissipative-form ISS-Lyapunov function requires additional assumptions. We present two sufficient conditions.

Proposition 3.5: Assume system (1) satisfies the ISS-estimate [START_REF] Aström | Event based control[END_REF]. If there exists a function 3) and ( 7), then V satisfies (4) with α . = min{α, α 1 } and σ(s) . = α 2 (β(χ(s), 1) + γ(s)) for all s ∈ R ≥0 .

V : R n → R ≥0 and functions α 1 , α 2 , α ∈ K ∞ and χ ∈ K satisfying (
The proof makes explicit use of the ISS-estimate to ensure that the potential increase in the ISS-Lyapunov function is bounded for states below the level set defined by χ(|w|). This is similar to the final argument at the end of the proof of Theorem 2.6 and we thus omit the details.

We observe that Proposition 3.3 and Proposition 3.5 do not rely on the regularity of either the system dynamics or the ISS-Lyapunov functions. We also note that the assumption of ISS

(r) . = max{V (f (x, w)) -V (x) + α • χ(|w|) : |w| ≤ r, |x| ≤ χ(r)}. ( 11
)
Proof: The proof follows the same argument as in [START_REF] Sontag | On characterizations of the input-to-state stability property[END_REF]Remark 2.4].

That the maximum in ( 11) is well-defined follows from the fact that the function being maximized is a continuous function by the assumptions on V (•) and f (•, •) and the fact that the domain being maximized over is compact. It is then straightforward to see that

σ(|w|) = sup |w|=r (V (f (x, w)) -V (x) + α • χ(|w|) ≥ V (f (x, w)) -V (x) + α(|x|),
yielding the desired result.

July 30, 2013 DRAFT

This proposition shows that, under the assumption of continuous system dynamics, the existence of a continuous ISS-Lyapunov function satisfying (3) and ( 7) implies ISS. The following example shows that in the absence of continuous system dynamics this implication no longer holds.

Example 3.7: Consider the system

x + = f (x, w) = ν(w)κ(x) (12)
where

κ(x) . =          0 , x = 0 1 |x| , |x| ∈ (0, 1) 1 2|x| , |x| ≥ 1 (13)
and

ν(w) . =          0 , w = 0 1 2 |w| 2 , |w| ∈ (0, 1) 1 , |w| ≥ 1. (14)
Take V (x) . = |x| so that both the upper and lower bounds of (3) can be trivially taken as |x|.

We observe that if |x| ≥ |w| then for |x| ∈ (0, 1)

|f (x, w)| = |w| 2 2|x| ≤ |x| 2 2|x| = |x| 2 and for |x| ≥ 1 |f (x, w)| = ν(w) 1 2|x| ≤ 1 2|x| ≤ |x| 2 .
Therefore, with α(s) . = 1 2 s we see that

|x| ≥ |w| ⇒ V (f (x, w)) -V (x) ≤ -α(|x|).
However, it is straightforward to see that the system ( 12) is not ISS. Take w ≡ 1 and any initial condition x ∈ (0, 1). Then we see that

φ(2k + 1, x) = 2 2k 1 x , ∀k ∈ Z ≥0 .
In other words, every other time step the solution increases so that the ISS estimate (2) can never be satisfied.

We note that, as an interim step in the proof of Theorem 2.6, we demonstrate that ISS implies the existence of an implication-form ISS-Lyapunov function satisfying (3) and [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF]. However, July 30, 2013 DRAFT the above example demonstrates that the converse is not true. Hence, this indicates that neither the implication-form of (8), nor the equivalent forms demonstrated by Theorem 3.2, are useful when one allows discontinuous system dynamics since (3) and ( 7) do not imply ISS of (1).

This motivates a new definition for implication-form ISS-Lyapunov functions in the following section.

IV. AN ALTERNATIVE IMPLICATION FORM ISS-LYAPUNOV FUNCTION

As we have seen, in the discontinuous setting the existence of an ISS-Lyapunov function in the implication form (3), [START_REF] Hahn | Stability of Motion[END_REF] does not imply ISS and is not equivalent to the existence of an ISS-Lyapunov function in dissipation form (3), [START_REF] Grüne | Global optimal control of quantized systems[END_REF]. In this section, we propose the following stronger alternative to the implication (6) which fixes these problems. R n → R ≥0 such that there exist functions α 1 , α 2 ∈ K ∞ , φ, χ ∈ K, and ρ ∈ P so that, for all

x ∈ R n and w ∈ R m , V satisfies (3) and

|x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ -ρ(|x|) (15)
|x| < χ(|w|) ⇒ V (f (x, w)) ≤ φ(|w|). ( 16
)
This definition is motivated by the ISS Lyapunov functions in implication form in continuous time, which will always satisfy the second implication on time intervals on which w is constant.

Similar to Theorem 3.2, we can demonstrate that the strong implication-form ISS-Lyapunov function ( 3)-( 15)-( 16) implies the existence of a strong implication-form ISS-Lyapunov function with [START_REF] Lunze | A state-feedback approach to event-based control[END_REF]

replaced with α ∈ K ∞ such that |x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ -α(|x|) (17)
or with λ ∈ (0, 1) such that (iii) For any given λ ∈ (0, 1) there exists a strong implication-form ISS-Lyapunov function V satisfying [START_REF] Picasso | Robust stability analysis of nonlinear discrete-time systems with application to MPC[END_REF].

|x| ≥ χ(|w|) ⇒ V (f (x, w)) ≤ λV (x). (18
Moreover, for V satisfying (i) there exist α and α ∈ K ∞ such that V in (ii) and V in (iii) can be written in the form V = α(V ) and V = α(V ).

The proof follows exactly as that for Theorem 3.2, where ϕ ∈ K is scaled along with V . The details are provided in Section VI-A.

The next theorem shows that the strong implication-form ISS-Lyapunov function ( 16)-( 17)

is equivalent to the dissipative-form ISS-Lyapunov function (4). This then overcomes the gap observed between a dissipative-form ISS-Lyapunov function and the classical implication-form ISS-Lyapunov function [START_REF] Hahn | Stability of Motion[END_REF] when considering discontinuous systems and ISS-Lyapunov functions.

An immediate consequence is that the existence of a strong implication form ISS-Lyapunov function is equivalent to the system being ISS. This is formulated in a subsequent corollary. (ii) If V together with functions α ∈ K ∞ and χ, φ ∈ K satisfies ( 17) and ( 16), then V also satisfies (4) with α . = min{α, α 1 } and σ = φ.

Proof: (i) We rewrite (4) as

V (f (x, w)) -V (x) ≤ - 1 2 α(|x|) - 1 2 α(|x|) + σ(|w|). (19)
Therefore, with χ .

= α -1 • 2σ ∈ K and α . = 1 2 α ∈ K ∞ we immediately see that |x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ - 1 2 α(|x|) = -α(|x|) (20)
and

|x| < χ(|w|) ⇒ V (f (x, w)) ≤ V (x) -α(|x|) + σ(|w|) ≤ α 2 (|x|) -α(|x|) + σ(|w|) ≤ γ(|x|) + σ(|w|) ≤ γ(χ(|w|)) + σ(|w|) = φ(|w|). (21)
(ii) If |x| ≥ χ(|w|) then we get

V (f (x, w)) -V (x) ≤ -α(|x|) ≤ -α(|x|) + σ(|w|). (22)
In case |x| < χ(|w|), using (3) we obtain

V (f (x, w)) -V (x) ≤ φ(|w|) -α 1 (|x|) ≤ -α(|x|) + σ(|w|). (23)
Hence, the stronger implication form ( 17) is equivalent to the dissipation form (4). As a consequence, the existence of a strong implication-form ISS-Lyapunov function is equivalent to ISS, as stated in the following corollary. this is also a dissipative-form ISS-Lyapunov function which by Lemma 2.3 implies ISS of system [START_REF] Angeli | A characterization of integral input-to-state stability[END_REF].

We note that we can prove a result similar to Theorem 4.3 for the relationship between dissipative-form and strong implication-form ISS Lyapunov functions when we have an exponential decrease.

Theorem 4.5: Let V : R n → R ≥0 be a function satisfying (3) for α 1 , α 2 ∈ K ∞ .

(i) If V together with λ ∈ (0, 1) and σ ∈ K satisfies (5), then V also satisfies ( 16) and ( 18)

with λ . = λ + ε satisfying λ + ε < 1, χ . = α -1 1 ( 1 ε σ), and φ . = λα 2 • χ + σ.
(ii) If V together with λ ∈ (0, 1), χ, φ ∈ K satisfies ( 16) and ( 18), then V also satisfies [START_REF] Grüne | Nonlinear Model Predictive Control. Theory and Algorithms[END_REF] with λ . = λ and σ . = φ.

Proof: (i) Since λ ∈ (0, 1) there exists ε > 0 such that λ + ε ∈ (0, 1). We may then rewrite [START_REF] Grüne | Nonlinear Model Predictive Control. Theory and Algorithms[END_REF] as

V (f (x, w)) ≤ (λ + ε)V (x) -εV (x) + σ(|w|) ≤ λV (x) -εα 1 (|x|) + σ(|w|)
July 30, 2013 DRAFT which yields the implication [START_REF] Picasso | Robust stability analysis of nonlinear discrete-time systems with application to MPC[END_REF]. The implication [START_REF] Nešić | A unified framework for design and analysis of networked and quantized control systems[END_REF] follows from the upper bound on V and the condition |x| < χ(|w|) as

V (f (x, w)) ≤ λα 2 (|x|) + σ(|w|) ≤ λα 2 • χ(|w|) + σ(|w|).
The proof of (i) is immediate by inspection. Theorem 4.3 can be used in order to pass from the (weak) implication form [START_REF] Hahn | Stability of Motion[END_REF] to the dissipation form (4) under a weaker continuity assumption than in Proposition 3.6. Particularly, we only require continuity of f at w = 0 (uniformly in x) and continuity of V at x = 0. Note that the continuity of V at x = 0 is a consequence of the bounds (3).

Proposition 4.7: Let V be a function satisfying ( 3) and ( 7) for appropriate α 1 , α 2 , α ∈ K ∞ and χ ∈ K. Assume that f is continuous in w = 0 uniformly in x in the following sense:

For each r > 0 there is γ r ∈ K ∞ such that for all |x| ≤ r, |w| ≤ r the inequality

|f (x, w) -f (x, 0)| ≤ γ r (|w|)
holds.

Then there exists φ ∈ K so that V satisfies [START_REF] Nešić | A unified framework for design and analysis of networked and quantized control systems[END_REF] and thus also [START_REF] Grüne | Global optimal control of quantized systems[END_REF].

Proof: First, consider w ≡ 0. Then we observe that

|f (x, 0)| ≤ α -1 1 (V (f (x, 0))) ≤ α -1 1 (V (x) -α(|x|)) ≤ α -1 1 (α 2 (|x|) -α(|x|)) . ( 24
)
Since by ( 7) α(|x|) ≤ V (x) ≤ α 2 (|x|) for all x ∈ R n , with equality if and only if x = 0, the

function α -1 1 (α 2 (s) -α(s)) is positive definite. Define γ ∈ K ∞ by γ(s) . = max s, α -1 1 (α 2 (s) -α(s)) , ∀s ∈ R ≥0 (25) so that |f (x, 0)| ≤ γ(|x|), ∀x ∈ R n . ( 26
)
July 30, 2013 DRAFT Now, if for all r > 0 we define

γ(r) . = sup{|f (x, w) -f (x, 0)| : |x| ≤ r, |w| ≤ r},
then for all r 1 ≥ r we obtain γ(r) ≤ γ r 1 (r) which implies γ(r) → 0 as r → 0. Moreover, γ(r)

is finite for all r > 0. Hence, we may overbound γ with a function γ ∈ K ∞ .

It is now sufficient to show that there exists ϕ ∈ K ∞ such that the implication in ( 16) holds.

To this end, let |x| < χ(|w|). Then we have

|f (x, w)| = |f (x, w) -f (x, 0) + f (x, 0)| ≤ γ(max{|w|, χ(|w|)}) + γ(|x|) ≤ γ(max{|w|, χ(|w|)}) + γ(χ(|w|)) =: γ(|w|) implying V (f (x, w)) ≤ α 2 (|f (x, w)|) ≤ α 2 (γ(|w|)).
This shows the desired inequality with ϕ(r) . = α 2 (γ(|w|)).

We note that the map f (x, w) = ν(w)κ(x) in ( 12) of Example 3.7 does not satisfy the required continuity property of Proposition 4.7. To see this, we first observe that

|f (x, w) -f (x, 0)| = |f (x, w)|.
Choose r = 1 and any γ 1 ∈ K ∞ . Then, with w = 1, we see that

|f (x, 1)| = 1 |x| , ∀x ∈ (-1, 1)\{0} so that |f (x, 1)| > γ 1 (1)
for some x ∈ (0, 1).

Using a strong implication-form ISS-Lyapunov function allows us to prove a variant of Proposition 2.4. 3) and ( 4). If there exists ρ ∈ P such that α(s) = ρ(s) + σ(s) for all s ∈ R ≥0 then V satisfies ( 15) and [START_REF] Nešić | A unified framework for design and analysis of networked and quantized control systems[END_REF] with χ . = id, ρ . = ρ, and φ . = γ + σ where γ ∈ K is such that γ > α 2 -α, and hence (1) is ISS.

Proposition 4.8: Suppose V : R n → R ≥0 , α 1 , α 2 ∈ K ∞ and α, σ ∈ K satisfy (
Proof: By assumption, we have

V (f (x, w)) -V (x) ≤ -ρ(|x|) -σ(|x|) + σ(|w|). (27)
Therefore

|x| ≥ |w| ⇒ V (f (x, w)) -V (x) ≤ -ρ(|x|) (28)
July 30, 2013 DRAFT and

|x| < |w| ⇒ V (f (x, w)) ≤ V (x) -α(|x|) + σ(|w|) ≤ α 2 (|x|) -α(|x|) + σ(|w|) ≤ γ(|w|) + σ(|w|). (29)
Therefore, by Theorem 4.2 there exists a strong implication form ISS-Lyapunov function satisfying [START_REF] Nešić | Changing supply functions in input to state stable systems: The discrete-time case[END_REF] so that Theorem 4.3 implies the existence of a dissipative form ISS-Lyapunov function and Lemma 2.3 yields ISS of (1).

We note that the assumptions of Propositions 2.

V. CONCLUSIONS

In this paper we have provided a complete characterization of ISS-Lyapunov functions for discrete-time systems with discontinuous dynamics. In contrast to the original definition of an ISS-Lyapunov function in [START_REF] Sontag | On characterizations of the input-to-state stability property[END_REF], we here observed that an implication-form ISS-Lyapunov function does not necessarily imply ISS of the system (1). In order to counter this difficulty, we proposed an alternative strong implication-form ISS-Lyapunov function and demonstrated that this ISS-Lyapunov function satisfies many of the desirable properties that hold in a more classical setting such as equivalence to an ISS-Lyapunov function in dissipative form and that this strong implication-form ISS-Lyapunov function is both necessary and sufficient for ISS of discrete-time systems with discontinuous dynamics.

In addition, we have presented results on the nonlinear scaling of such strong implicationform ISS-Lyapunov functions and have demonstrated that it is always possible to move between decrease rates that are given by positive definite functions, functions of class-K ∞ , or even an exponential decrease. In all cases, we have explicitly shown how these various functions are related to each other in a quantitative manner. In this appendix we will prove Theorem 3.2. Theorem 4.2 follows exactly the same argument with appropriate scalings on the bound ( 16) and we include these scalings in remarks in what follows. We observe that for both Theorems the implications (iii) ⇒ (ii) ⇒ (i) are trivial.

1) Positive Definite to K ∞ : (i) ⇒ (ii): We start from an ISS-Lyapunov function with a positive definite decrease rate; i.e., V : R n → R ≥0 , α 1 , α 2 ∈ K ∞ , χ ∈ K, and ρ ∈ P satisfying

(3) and [START_REF] Grüne | Numerical ISS controller design via a dynamic game approach[END_REF].

For ρ ∈ P, [1, Lemma IV.1] ([10, Lemma 12]) yields α ∈ K ∞ and σ ∈ L so that

ρ(s) ≥ α(s)σ(s), ∀s ∈ R ≥0 . (30)
Using the bounds (3) we see that, for all

x ∈ R n |x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ -ρ(|x|) ≤ -α(|x|)σ(|x|) ≤ -α • α -1 2 (V (x))σ • α -1 1 (V (x)) = -ρ(V (x)) (31)
where ρ(s) . = α -1 2 (s)σ • α -1 1 (s) for all s ∈ R ≥0 is positive definite. From here, we follow [START_REF] Jiang | A converse Lyapunov theorem for discrete-time systems with disturbances[END_REF]Lemma 2.8]. Let ᾱ ∈ K ∞ be such that

ᾱ s 2 ρ(s) ≥ s, ∀s ≥ 1 (32) and define α ∈ K ∞ by α(s) . = s + s 0 ᾱ(r)dr, ∀s ∈ R ≥0 . (33)
We observe that α ∈ K ∞ and α′ (s) = 1 + ᾱ(s), ∀s ∈ R >0 (34) so that α′ is strictly increasing.

Define V (x) . = α(V (x)) for all x ∈ R n and observe that with the K ∞ functions α1 .

= +α • α 1 and α2 . = α • α 2 we have α1 (|x|) ≤ V (x) ≤ α2 (|x|). ( 35
)
2) K ∞ to Exponential: (ii) ⇒ (iii): Since every K ∞ -function is also positive definite, we can follow the first part of the proof to conclude (35) and (43) which imply

|x| ≥ χ(|w|) ⇒ V (f (x, w)) -V (x) ≤ -α(|x|) ≤ -α • α-1 2 ( V (x)). (44) Define µ ∈ K ∞ by µ(s) . = min α • α-1 2 (s), s 2 (45)
and note that id -µ ∈ K ∞ and

|x| ≥ χ(|w|) ⇒ V (f (x, w)) ≤ V (x) -µ( V (x)) = (id -µ)( V (x)). (46)
Select any λ ∈ (0, 1). Then [10, Corollary 1] yields μ ∈ K ∞ so that

μ • (id -µ)(s) = λμ(s), ∀s ∈ R ≥0 . ( 47
) Define V . = μ( V ) and note that, with K ∞ functions ᾱ1 . = μ • α1 and ᾱ2 . = μ • α2 , ᾱ1 (|x|) ≤ V (x) ≤ ᾱ2 (|x|). (48)
Furthermore,

|x| ≥ χ(|w|) ⇒ V (f (x, w)) = μ( V (f (x, w))) ≤ μ • (id -µ)( V (x)) = λμ( V (x)) = λ V (x). (49)
Finally, the form V = α(V ) follows by combining both parts of the proof and setting α = μ • α.

Remark 6.2:

To additionally demonstrate (ii) ⇒ (iii) in Theorem 4.2, define φ ∈ K by

φ . = μ • φ so that, for |x| < χ(|w|), V (f (x, w)) = μ( V (f (x, w))) ≤ μ • φ(|w|) = φ(|w|). (50
We observe that ϕ ∈ K ∞ and, for V . = ϕ(V )

V + -V = ϕ(V + ) -ϕ(V ) = α(V + -θ(V + -V ))(V + -V ) (53)
for some θ ∈ (0, 1).

Consider V + ≤ V 2 .
Then we may write

ϕ(V + ) -ϕ(V ) ≤ ϕ V 2 -ϕ(V ) ≤ α V 2 V 2 -V ≤ -α V 2 V 2 + σ(|w|). (54)
Now consider V + > V 2 and examine two cases. The first case is when

1 c α(V ) > σ(|w|). Then ϕ(V + ) -ϕ(V ) ≤ α(V + )(V + -V ) ≤ α(V + ) -α(V ) + 1 c α(V ) ≤ -α V 2 1 - 1 c α(V ) ≤ -α V 2 1 - 1 c α(V ) + σ(|w|). (55)
Finally, consider V + > V 2 and 1 c α(V ) ≤ σ(|w|). Since c sup σ < sup α, we see that α -1 (s) exists for all s ∈ [0, c sup σ] and hence we have that

α(V + ) ≤ α(V + σ(|w|)) ≤ α α -1 (cσ(|w|)) + σ(|w|) . ( 56
) Define γ(s) . = α(α -1 (cσ(s)) + σ(s)). Then ϕ(V + ) -ϕ(V ) ≤ α(V + )(V + -V ) ≤ α(V + )(-α(V ) + σ(|w|)) ≤ -α(V + )α(V ) + γ(|w|)σ(|w|) ≤ -α V 2 α(V ) + γ(|w|)σ(|w|). (57)
Therefore, with

ᾱ(s) . = min α s 2 s 2 , α s 2 1 - 1 c α(s), α s 2 α(s) σ(s) . = max{σ(s), γ(s)σ(s)} (58)
and noting that ᾱ ∈ K ∞ and σ ∈ K,

V (f (x, w)) -V (x) ≤ -ᾱ(V (x)) + σ(|w|) ≤ -ᾱ • α 1 (|x|) + σ(|w|)
so that (1) is ISS.

C. Proof of Theorem 2.6

Our proof relies on a converse Lyapunov theorem for difference inclusions. We denote the set of solutions to the difference inclusion

x + ∈ F (x), x ∈ R n (59)
defined by the set-valued mapping F : R n ⇒ R n and from an initial condition x ∈ R n by

S(x). A solution φ ∈ S(x) is a function φ : Z ≥0 × R n → R n such that φ(0, x) = x and φ(k + 1, x) ∈ F (φ(k, x)) for all k ∈ Z ≥0 .
Definition 6.3: The difference inclusion (59) is said to be KL-stable if there exists β ∈ KL so that

|φ(k, x)| ≤ β(|x|, k), ∀x ∈ R n , φ ∈ S(x), k ∈ Z ≥0 . (60)
Theorem 6.4: If the difference inclusion (59) is KL-stable then, for any given λ ∈ (0, 1) there exists an exponential-decrease Lyapunov function; i.e., there exist functions V : R n → R ≥0 and

α 1 , α 2 ∈ K ∞ so that α 1 (|x|) ≤ V (x) ≤ α 2 (|x|) (61) V (φ(1, x)) ≤ λV (x) (62)
for all x ∈ R n and φ(1, x) ∈ F (x).

Proof: The proof follows that of [START_REF] Kellett | On the robustness of KL-stability for difference inclusions: Smooth discrete-time Lyapunov functions[END_REF]Theorem 2.7] where, here, we need not worry about regularity of the Lyapunov function.

Given β ∈ KL and λ ∈ (0, 1), Sontag's lemma on KL-estimates [21, Proposition 7] yields

α 1 , α 2 ∈ K ∞ so that α 1 (β(s, k)) ≤ α 2 (s)λ k , ∀s ∈ R ≥0 , k ∈ Z ≥0 . (63)
For all x ∈ R n , define

V (x) . = sup k∈Z ≥0 sup φ∈S(x) α 1 (|φ(k, x)|)λ -k . ( 64
) July 30, 2013 DRAFT Then V (x) ≥ sup φ∈S(x) α 1 (|φ(0, x)|)λ 0 = α 1 (|x|) and V (x) ≤ sup k∈Z ≥0 α 1 (β(|x|, k))λ -k ≤ sup k∈Z ≥0 α 2 (|x|)λ k λ -k = α 2 (|x|)
so that V (x) satisfies the desired upper and lower bounds (61). The desired decrease condition follows as

V (φ(1, x)) = sup k∈Z ≥0 sup ψ∈S(φ(1,x)) α 1 (|ψ(k, φ(1, x))|)λ -k ≤ sup k∈Z ≥1 sup φ∈S(x) α 1 (|φ(k, x)|)λ -k+1 ≤ sup k∈Z ≥0 sup φ∈S(x) α 1 (|φ(k, x)|)λ -k+1 = λV (x)
for all x ∈ R n .

In order to demonstrate that ISS implies the existence of an ISS-Lyapunov function, we follow the standard argument as in [START_REF] Sontag | On characterizations of the input-to-state stability property[END_REF] and [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF]. Denote the closed unit ball in R m by B m . We show that there exists a µ ∈ K ∞ such that the differential inclusion defined by

x(k + 1) ∈ f (x(k), µ(|x(k)|)B m ) (65)
is KL-stable, allowing us to appeal to Theorem 6.4 to obtain an ISS-Lyapunov function. We denote the solution set of (65) from an initial condition x ∈ R n by S µ (x).

Proposition 6.5: [13, Proposition 2.2.] The following are equivalent:

1) The difference inclusion x(k + 1) ∈ F (x(k)) is KL-stable.

2) The following hold: Since β ∈ KL, for each r ∈ R ≥0 there exists a finite T (r) ∈ Z ≥1 so that β(r, k) ≤ 1 2 r for all k ∈ Z ≥T (r) . Therefore, for all |x| ≤ r we have |φ(k, x)| ≤ 1 2 r for all φ ∈ S µ (x) and k ∈ Z ≥T (r) . Fix any ε ∈ R >0 and let k ∈ Z ≥1 be such that 2 -k r ≤ ε. Define r 1 . = r, r i . = 1 2 r i-1 for all i ∈ Z ≥2 , and K(r, ε) . = k i=1 T (r i ). Then |φ(k, x)| ≤ 2 -k r ≤ ε, ∀|x| ≤ r, ∀φ ∈ S µ (x), ∀k ∈ Z ≥K(r,ε) .

Therefore, the difference inclusion (65) is KL-stable.

We now complete the proof of Theorem 2.6. Since (1) is ISS, the difference inclusion (65) is KL-stable, and by Theorem 6.4, for any λ ∈ R (0,1) , there exist functions V : R n → R ≥0 and α 1 , α 2 ∈ K ∞ so that (61) and (62) hold for the difference inclusion given by (65). This then

July 30, 2013 DRAFT

  immediately yields a dissipative form ISS-Lyapunov function (by Theorem 2.6) and consequently, the only novelty of Proposition 3.5 is that the specific given implication-form ISS-Lyapunov function V (•) is also a dissipative-form ISS-Lyapunov function.Rather than assuming that system (1) is ISS to show the result of Proposition 3.5, we may assume continuity of both the ISS-Lyapunov function and the system dynamics. This was already stated in[START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF] Remark 3.3] without proof. Proposition 3.6: Assume f (•, •) is continuous. If there exists a continuous function V : R n → R ≥0 and functions α 1 , α 2 ∈ K ∞ and α, χ ∈ K satisfying (3) and (7), then V satisfies (4) with α . = α and σ

Definition 4 . 1 :

 41 A strong implication-form ISS-Lyapunov function for (1) is a function V :

) Theorem 4 . 2 :

 42 The following are equivalent: (i) There exists a ρ ∈ P and a strong implication-form ISS-Lyapunov function V satisfying (15); July 30, 2013 DRAFT (ii) There exists an α ∈ K ∞ and a strong implication-form ISS-Lyapunov function V satisfying (17);

Theorem 4 . 3 :

 43 Let V : R n → R ≥0 be a function satisfying (3) for α 1 , α 2 ∈ K ∞ .(i) If V together with functions α ∈ K ∞ and σ ∈ K satisfies (4) then V also satisfies[START_REF] Nešić | Changing supply functions in input to state stable systems: The discrete-time case[END_REF] with α . = α/2, χ . = α -1 • 2σ and satisfies[START_REF] Nešić | A unified framework for design and analysis of networked and quantized control systems[END_REF] with φ . = γ • χ + σ, where γ ∈ K ∞ is arbitrary with γ ≥ α 2 -α.

Corollary 4 . 4 :

 44 System (1) is ISS if and only if there exists a strong implication-form ISS-Lyapunov function in the sense of Definition 4.1. Proof: If the system is ISS, then by Theorem 2.6 there exists a dissipative-form ISS-Lyapunov function which by Theorem 4.3 is also a strong implication-form ISS-Lyapunov function. Conversely, if there exists a strong implication-form ISS-Lyapunov function then by Theorem 4.3

Remark 4 . 6 :

 46 Theorems 4.2, 4.3 and 4.5 imply that we can explicitly choose the function V in Theorem 2.7 in the form V = α(V ) for some α ∈ K ∞ . Indeed, by Theorem 4.3 the dissipative-form ISS-Lyapunov function V in the assumption of Theorem 2.7 is also a strong implication-form ISS-Lyapunov function. Theorem 4.2 then shows that by rescaling with α ∈ K ∞ we can turn this V into an exponential strong implication-form ISS-Lyapunov function which, by Theorem 4.5(ii), is also an exponential ISS-Lyapunov function in dissipative form.

  4 and 4.8 do not imply each other. Clearly, sup α > sup σ does not imply α(r) > σ(r) for all r > 0. Conversely, one checks that the functions σ(s) = s 1 + s and α(s) = σ(s) + ρ(s) with ρ(s) = min s, satisfy the assumption of 4.8 although sup α = 1 = sup σ. From a quantitative point of view, Proposition 4.8 provides a stronger statement than Proposition 2.4, as it maintains the functions of the given ISS-Lyapunov function without requiring a rescaling of the ISS-Lyapunov function.

) B. Proof of Proposition 2. 4

 4 The proof closely follows [17,Lemma 1]. The condition sup α > sup σ implies there exists c > 1 so that sup α > c sup σ.

  a) (Uniform stability): There exists γ ∈ K ∞ so that, for each x ∈ R n , all solutionsφ ∈ S(x) satisfy |φ(k, x)| ≤ γ(|x|), ∀k ∈ Z ≥0 . b) (Uniform global attractivity): For each r, ε ∈ R >0 , there exists K(r, ε) > 0 so that, for each x ∈ R n , all solutions φ ∈ S(x) satisfy |x| ≤ r, k ∈ Z ≥K(r,ε) ⇒ |φ(k, x)| ≤ ε. Lemma 6.6: If (1) is ISS then there exists µ ∈ K ∞ such that the difference inclusion (65) is KL-stable.July 30, 2013 DRAFT Uniform stability follows using (2), (66), and the fact that γ(s) ≥ s as|φ(k, x)| ≤ max β(|x|, k), max i∈Z [0,k-1] γ(|µ(|φ(i, x)|)B m ) ≤ max β(|x|, 0), max i∈Z [0,k-1] γ(|µ(|φ(i, x)|)) ≤ max β(|x|, 0), 1 2 |x| ≤ max β(|x|, 0), 1 2 γ(|x|) = α(|x|).(70)To establish uniform global attractivity, as above we note that, for all x ∈ R n , φ ∈ S µ (x), andk ∈ Z ≥0 , |φ(k, x)| ≤ max β(|x|, k), 1 2 |x| .

  implies that |w| ≤ µ(|x|) ⇒ V (φ(1, x, w)) ≤ λV (x)(71)for all x ∈ R n , w ∈ R m , and φ(1, x, w) = f (x, w).It remains to show that the function V satisfies[START_REF] Grüne | Nonlinear Model Predictive Control. Theory and Algorithms[END_REF]. Let β ∈ KL and γ ∈ K ∞ come from the ISS-estimate (2) and α 2 ∈ K ∞ the upper bound in (61). Define σ ∈ K byσ(s) . = α 2 (β(µ -1 (s), 1) + γ(s)), ∀s ∈ R ≥0 .For |w| > µ(|x|) we haveV (f (x, w)) ≤ α 2 (|f (x, w)|) ≤ α 2 (β(|x|, 1) + γ(|w|))≤ α 2 β(µ -1 (|w|), 1) + γ(|w|) = σ(|w|).

  If there exists a function V : R n → R ≥0 and functions α 1 , α 2 , α ∈ K ∞ and

	Using the above results, we can demonstrate the following discrete-time version of [19,
	Proposition 8]:
	Theorem 2.7: σ ∈ K satisfying (3)-(
	July 30, 2013	DRAFT

July 30, 2013 DRAFT

Together with (71) we then have

ACKNOWLEDGEMENT

The authors are grateful to Rob Gielen for helpful discussions on the result of Theorem 2.6.

Remark 6.1: In order to prove (i) ⇒ (ii) in Theorem 4.2, additionally let φ ∈ K be given by φ . = α • ϕ so that [START_REF] Nešić | A unified framework for design and analysis of networked and quantized control systems[END_REF] implies, for |x| < χ(|w|), V (f (x, w)) = α(V (f (x, w))) ≤ α • ϕ(|w|) = φ(|w|).

(36)

To simplify the notation, we use

In what follows we assume |x| ≥ χ(|w|).

Since α is differentiable, the mean value theorem yields the existence of θ ∈ (0, 1) so that

Note that, as a consequence of (31), V + -V ≤ 0.

We first restrict attention to V ≥ 1 and consider two cases. First, we assume V + ≤ V 2 and note that α′ (s) ≥ 1 for all s ∈ R ≥0 . Then

In this case, using V -V + ≥ 0 and (34), we have

Therefore, for V ≥ 1, using (39), (31), and (32) we obtain

Combining ( 38) and (40) we see that, for V ≥ 1,

For V ≤ 1, we note that by definition (33) and (31) we have

Finally, let α ∈ K ∞ be defined as α .

July 30, 2013 DRAFT Proof: Without loss of generality, we assume that γ ∈ K from (2) satisfies γ(r) ≥ r. Define

for all s ∈ R ≥0 .

Claim 6.7: For any x ∈ R n and φ ∈ S µ (x) we have

Proof: By the definition of α we have |x| ≤ β(|x|, 0) ≤ α(|x|) so that

Let

and note that (67) implies k 1 ∈ Z ≥1 . In order to obtain a contradiction, assume Then, using the definition of µ, the ISS-estimate (2), and (68), we have

which contradicts the definition of k 1 and hence proves the claim.

We now prove KL-stability of difference inclusion (65) by proving uniform stability and uniform global attractivity and then appeal to Proposition 6.5.

July 30, 2013 DRAFT