Benjamin Renoust
email: renoust@gmail.com

Nlp

C L Kaist

Towards a new Vision of Emotions: Empathy

The synthesis of emotions receives a great interest in many domains. When the concept of emotions is included in a human-machine interaction, the interactivity is a lot improved: it is more entertaining for the user and the machine shows better adaptation to a social environment. In decision making and learning process also, the inclusion of emotions as a new parameter opens a way to a new heuristic process and agent's behaviors. Emotion models have been broadly studied in the past years and many models and implementations are now available. The next step in the study of emotions is also the understanding of their meaning as a mean of communication. In order to achieve such communication we need to be able to project our self in another state of mind and emotions, this is called empathy. We introduce in this paper the new ideas brought through the concept of empathy in order to find new domains of contribution.

Introduction

According to Albert Mehrabian [START_REF] Mehrabian | Silent messages: Implicit communication of emotions and attitudes[END_REF], 55% of a message in the face-to-face communication is expressed by the body language, 38% by the tone and 7% only by the words. Even if this rule has to be understood under the initial conditions of his experiments [START_REF] Mehrabian | Silent messages: Implicit communication of emotions and attitudes[END_REF], we can still understand that the emotions take an important part in the communication, especially in the non-verbal communication.

Many systems require research on the emotions, such as robotized agents, dialogues agents and also the Embodied Conversational Agents (which are usually virtual 3D agents used as attendants for virtual sales or expositions like houses). But these kinds of interactions are nowadays interesting also to the space industry to analyze and assist people especially for long missions [START_REF]Tools for Psychological Support during Exploration Missions to Mars and Moon[END_REF].

If we compare the different uses of emotions in the human-robot interaction field, we can describe three sub-domains: the expression of emotions, the reading of the emotions and the synthesis of the emotions. We are here focusing on the synthesis of the emotions which leads to the process of the emotional information.

In the human decision making process, emotions play an important role especially on the social relationships. It is a noble goal for human-robot interaction to give a heart to a robot, to allow a 04/2009 2 machine to feel emotions and interact with things in the world depending on those emotions. Interacting with emotions, a machine can integrate in a social environment a lot more efficiently, because people will start to like it (with the affective meaning of "like"). Therefore we need to simulate the emotions process, synthesize the emotions to provide the result in an artificial being.

The computing of emotions is a broad research area and a lot of research has been yet made.

We made here a survey on the different systems that aim to synthesize the emotional process, the different computational models of emotions.

Because emotions are on the basis of communication, we need also to explore the role of emotions in this communication. Every communication implies a protocol, a way that allows a message to transit from an agent A to an agent B. Empathy allows the understanding of emotions. Also, by empathy, new emotions are learnt and understood by an agent, which may be able to reproduce the emotions according to similar conditions. Empathy can be therefore seen as a process of emotions, that influences future expressions of emotions and behavior. This work aims to present and compare those models and their purpose of application in order to show the different ways on which a research contribution can be done.

The rest of the document will be organized as follows. Section 2 presents the related works on the fields of psychology and Section 3 shows some computer science solutions for emotion synthesis. Section 4 introduces the notion of empathy. We will conclude in Section 5.

Theoretical Models of Emotions

An emotional system is first based on a theoretical model that describes how emotions are processed by humans or animals. Several different models have been used already for the computation of emotions. Those models can be either psychological or physiological [START_REF] Damasio | Descartes'error: emotion, reason, and the human brain[END_REF]. Some models are based on animal behaviors (ethological basis for computing emotions) and others on human behaviors. The theoretical models are usually issued by research in psychology e.g. Paul Ekman's basic emotions [START_REF] Ekman | Basic Emotions[END_REF]. I will additionally give a particular attention to the Ortony, Clore and Collins (OCC) model [START_REF] Ortony | The Cognitive Structure of Emotions[END_REF] which has been often preferred to as the referent emotional model over all others.

Paul Ekman described the fundamental emotions [START_REF] Ekman | Basic Emotions[END_REF], basic emotions called sometimes the Big Six. The emotions that should be recognized by any human being are biologically universal. These emotions are: happiness, sadness, anger, fear, surprise and disgust. Although Ekman has extended them to fifteen [START_REF] Ekman | The repertoire of nonverbal behavior: Categories, origins, usage, and encoding[END_REF], many research work stick to those six emotions, and sometimes even more limited for those who need to overlap with the OCC model [START_REF] Song | Design of a Robot Head with Arm-type Antennae for Emotional Expression[END_REF].

Ortony, Clore and Collins

We can have a look a little bit deeper in the OCC model because of its wide use. Many researchers inspired their models from the OCC model but apply also some variation depending on their purpose of application (determining the emotions they need to express). The OCC model is a cognitive model that allows the expression of 22 emotions depending on categories that are the reactions to consequences of events, actions of agents, and aspect of objects. The model based on given knowledge (goals, standards, attitudes) computes also intensity variables such as attractiveness of an object, worthiness of an action, or desirability of an event. The OCC model is described in Figure 1 [1]. 1. Classify the consequence of an event, the action of an agent, or the aspect of an object. Depending on the knowledge basis of the model, this step allows the system to know on which category to reason. 2. Evaluate the intensity of the variable of reaction of the category chosen (desirability, attractiveness…). 3. Interact depending on the intensity on a certain category (e.g. it can be just counting the positive or negative values given by a set of rules).

04/2009 4

4. Find for the resulting emotion an expressional emotion (determined by the needs of the system. Figure 2 shows a possible table of correspondence of Paul Ekman's basic emotions to the OCC resulting emotions [START_REF] Song | Design of a Robot Head with Arm-type Antennae for Emotional Expression[END_REF]). 5. Express the emotion (it can be done for the system by making a decision).

OCC Emotions

Swagerman and Frijda

Swagerman together with Frijda developed a computer model of emotions [START_REF] Swagerman | The Artificial Concern REalization System ACRES: A computer model of emotion[END_REF]. This model is based on the attraction by a system to a certain state of the environment. Therefore different goals might be produced to create a state of the environment that would be preferred by the system. Depending on the achievement of the goals, actually on the difficulties in the achievement, the system will produce emotions such as irritation, frustration, anger but also satisfaction. When the main goal is life, such system can even feel fear, and relief of the fear.

Figure 2 describes the model designed by Frijda [START_REF] Swagerman | Can computers feel? Theory and design of an emotional system[END_REF]. We can observe that the role of the urgency, difficulty and seriousness appraisal as a relevant activation signal to trigger a behavior. This approach is strongly related to the notion of goal achievement and here is the novel idea brought by the model. Goals are motivations for emotions, and the distance to a goal (in a multidimensional matter, such as relevance, context, urgency, difficulty) modulates an emotion.

Such system implemented in the Swagerman's Artificial Concern REalization System ACRES show extreme mood swings because the model does not include any notion of inertia and the emotional state is just switching from one state to another without transition. Also there is no process of a current emotional state, no memory of the current state either that would allow a blending of the emotions, or at least the consideration of the current emotion to process the following.

Figure 2: Frijda's model of emotions

Roseman

Solomon in [START_REF] Calhoun | What is an emotion?[END_REF] introduced a theory based on appraisals which are processes that elicits the emotions. The emotions are not raw feelings but the result of processes and judgments.

Roseman in [START_REF] Roseman | Appraisal determinants of emotions: Constructing a more accurate and comprehensive theory[END_REF] extended the theory identifying more accurate appraisals of the emotions. By statistically analysis the appraisals describes by 182 subjects, Roseman suggested the appraisals of unexpectedness, situational state, motivational state, probability, control potential, problem source, and agency causes a large number of emotions.

Depending on a nature of an event, the relation of the event with the agent and with the agent's situation, different emotions can be expressed. The figure 3 shows 17 emotions that are elicited. The polarity of the emotions depends on the consistency of the agent's wishes (whether the event is as wanted, or as improving things, or on the contrary unwanted and making things worse). Surprise seems to be a particular emotion that is induced by only the unexpectedness character of an event, which could be of any nature. Surprise has basically no polarity and could be positive or not. This model is powerful in the way it details the appraisal determinants of emotions, on which criteria can be influenced an emotion. One more time we can insist on the multidimensional nature of emotions elicitation. This model consider the orientation of the event more than does the OCC one: whether the event is caused by circumstances, others, or one's self. A novel approach is also the control potential appraisal, determined by the power of the agent on the event and situation (can the agent do or not something to change the current situation).

Because the theory states that emotions are answers to determined conditions, this model does not clearly specify any process of the current mood and/or memory of the previously felt emotions. This aspect is just stated in the probability appraisal (is it certain or uncertain to happen this way). In addition, no emotional inertia and continuous valence in intensity and time is suggested in the model: for example, it is not a repetitive action in time or a strong action that changes "dislike" to "anger".

LeDoux

LeDoux's emotional brain defends a Darwinian approach of emotions as process to optimize the survival [START_REF] Ledoux | The emotional brain[END_REF]. He states that emotions are part of a complex neural system which allowed us to survive. The learning process is made through experience and the emotional answers are processed into the brain's neural basis. The brain basically answers to some stimuli (that the brain has detected), which have to be evaluated to evaluate an emotional answer. The amygdala has a major role in the detection of the stimuli. There is actually situation pattern of the brain state that brought first the emotion, like fear in presence of a snake, which is then quickly recognized in the amygdale. The emotion felt then allows the subject to respond in an adaptive manner in the environment.

The brain first react to a new situation and evaluate it, it is the cognitive approach, conscious. But when such a pattern of a situation is recognized again (through the amygdala), the adapted behavior and emotional response will be expressed in anticipation of the cognition.

This approach does not state about the emotions and the explanation of the specific emotions but introduces the idea of a situational pattern that once recognized, is more susceptible to activate emotional states that have been already felt before. Through the example of the snake, LeDoux has shown off also that a baby monkey, natively, does not fear a snake. But the little monkey has learnt to fear snakes through his mother's experience, who were having already the fear of snakes.

This also introduces the emotions as a strong communication process for survival. It implies the notion of emotions recognition and empathy to make this communication efficient.

Implementations of the models

Several systems have implemented a computational model of emotions:

• The robot head designed in [START_REF] Song | Design of a Robot Head with Arm-type Antennae for Emotional Expression[END_REF] is a typical example of the use of the OCC model in the expression of emotions. Although the project focuses on the mechanical aspects the expression of emotions, they used both OCC models and Paul Ekman's basic emotions to choose the set of emotions they wish to express.

• BORIS and OpEd by M.G. Dyer in 1987. BORIS is natural language understanding program and focuses on understanding the emotional states of characters from a text story. It is based on the cognitive appraisal theory of Solomon. BORIS uses a symbolic representation of emotions as five-slot frames: goal situation, expectation, direction, polarity of arousal and strength of the emotion [START_REF] Dyer | BORIS --An experiment in in-depth understanding of narratives[END_REF]. OpEd is an extended version of BORIS that includes beliefs.

• The Artificial Concern Realization System (ACRES), by Fridja and Swagerman in 1987 [START_REF] Swagerman | The Artificial Concern REalization System ACRES: A computer model of emotion[END_REF] implements their theory of emotion stimulation. This implies the notions of pleasure and allows the agent to respond emotionally when he is concerned. The system is a dialogue agent that can be annoyed by the user, and also fears of being killed by displaying appropriate messages.

• Affective Reasoner started in 1992 by Clark Elliott [START_REF] Eliott | The Affective Reasoner: A Process Model of Emotions in a Multi-Agent System[END_REF] is a multi agent system based on the OCC model. Each agent has a goal, preferences, principle guiding behavior, and moods. Each agent can influence other agents' emotional state. Moods and personalities affect agents' emotional states. Agents' behaviors are corresponding to specific emotions. The system includes multimedia input and output (text-to-speech, speech recognition, cartoon-style facial expressions). The project helps to improve human-computer interaction, to test appraisal theories of emotion, and to develop more believable characters in computer games.

• The OZ project at the Carnegie Mellon University, closed in 2002. The project intended to develop tools for "highly interactive drama" and virtual worlds [START_REF]Tools for Psychological Support during Exploration Missions to Mars and Moon[END_REF][START_REF] Kelso | Dramatic Presence[END_REF]. Emotions are included as part of agents architecture, using the OCC model to cause emotional actions of the agents by threshold mechanisms. The most advanced demonstration of Oz shows creatures, the Woggles, which have individual personalities, show emotions and social behaviors, and react to their environment taking in account an extra user-controlled Woggle.

• Cognitive Systems for Cognitive Assistants (CoSy), use emotions as part of the cognition and learning of a robot [START_REF] Sloman | Beyond shallow models of emotion[END_REF]. This European project aims to give the knowledge to the robot on how and why it performed some task. The research is based on a scenario approach: The Explorer, is concerned with spatial exploration (find a way in a building), the PlayMate will manipulate of 3D structures (copy a given structure), and the Philosopher wants the robot to reason (understand a task, explain a task, describe his process).

• The Kismet robot by Cynthia Breazeal [START_REF] Breazeal | Sociable Machines: Expressive Social Exchange Between Humans and Robots[END_REF] is able of multimodal social interactions. She used the OCC model to implement the emotional behavior of Kismet. She implemented emotion drives to activate behaviors based on a threshold approach.

All these applications are inspired by the previously described computational models. They all differ in their purpose of application and thus the way they translate in variables and computer process the input of the psychologically based models. In addition they offer adapted simplifications of the models that made them fit the experiences situation. We can notice that in order to make a contribution, the tools used are certainly important, but the domain of application, the purpose of such system synthesizing emotions is capital, and brings the real contribution.

Empathy

The synthesis of the emotions is quite well advanced. The issues in the synthesis tend to concern the set of emotions that can be felt, and those are more or less extended by modifying the current main computational models of emotion, and especially by combining the different approaches proposed in the psychological and medical literature.

Definition

Another approach would be not to focus on the emotions process itself, but on the utility of emotions. It has been shown in the previous section that emotions make a strong mean of communication. Like any mean of communication, there is a message sent (by the emotions) and the message received. The reception of such message is made through empathy. We will get interested by empathy in this section.

Empathy has been started to be studied quite recently and its definition has not been fixed yet because it is first a psychological concept and it is also related to philosophy. Kohut [START_REF] Stepansky | How Does Analysis Cure?[END_REF] defines the empathy as "the capacity to think and feel oneself into the inner life of another person. " There are two main view of empathy. It can be seen as a cognitive process, allowing taking another's perspective (inference on another's feelings, Ickes, 1993), and it can be seen as an affective phenomenon (feeling with or feeling for another, Batson et al. 1997). Both views are of course not incompatible and empathy certainly assumes both roles.

There are no formal models of empathy yet studied and the research in the human-machine interaction is still at the early steps but we can pull out two directions in reasoning from the two points of views we cited:

• The cognitive aspect, by taking another's perspective is directly relation to the retrieval process (we look for the causes that make another's precise state of mind). • The affective aspect, by feeling for and with another is related to the anticipation process, and we join here previously commented LeDoux's point of view on the role of the amygdale in the emotional process, and why the baby monkey learns the fear of snake through his mother.

We can notice also the work of Mark H. Davis [START_REF] Davis | A Multidimensional Approach to Individual Differences in Empathy[END_REF] who designed a questionnaire to measure empathy in order to show differences in empathy depending on sex. The questionnaire measures four characteristics of people: fantasy, perspective-taking, empathic concern and personal distress. It will be good to remember this approach in order to validate the empathy simulated by a system.

It will be good in a future work to describe the role of each emotion in a social interaction. By empathy an agent understands a message, and each emotion transmits a specific message.

We have no time and space here to describe the message transmitted through each emotion here but R. J. R. Blair describes in his work [START_REF] Blair | Responding to the emotions of others: Dissociating forms of empathy through the study of typical and psychiatric populations[END_REF] how a specific empathized emotion brings a very specific message (such as anger which express a rupture in some social law, and requires from the interlocutor to readapt her behavior). By empathizing another's emotion, an interlocutor understands the message expressed through this emotion.

04/2009 10

Applications

In computer science the investigations on empathy are very recent and only a few works has been led toward that direction.

It is interesting to know that some works aim to make the human user empathize with the artificial system (for example see [START_REF] Paiva | Feeling and Reasoning: A Computational Model for Emotional Characters[END_REF], here is described a system that allows kids to empathize with virtual agent in order to demonstrate the negative effects of bullying).

Another project deserves to be mentioned: Empathy by the Universita degli Studi di Bari [START_REF] Semeraro | Empathy: A Computational Framework for Emotion Generation[END_REF] describes a reprocess of the currently felt emotion to set the mood and smooth the expression a new felt emotion. It consists in adding the current emotional state in the inputs and influences the decision on the new emotion felt. This actually includes the notion of inertia and memory of an emotion, but it is not yet empathy.

We will focus in this part on four works that implement artificial empathy:

• Some medical treatments need the patients to be constantly watched using devices for a long term such as cardio meters. The acceptance of the system is vital for the patient, but it is quite constraining to bear them, especially for a long term interaction between the patient and the device. R. Picard [START_REF] Picard | Embedded Empathy in Continuous, Interactive Health Assessment[END_REF] offered to embed empathy in such monitoring system through a human-machine interaction as a (simple) dialogue system. The empathetic system has been strongly preferred by the patients, which shows the pertinent interest of the study of empathy in human-machine interaction.

• Delay time due to computation usually raises the user's frustration. R. Picard [START_REF] Picard | This computer responds to user frustration: Theory, design, and results[END_REF] proposed a system that responds to user's frustration by interaction. The interaction is made through dialogues (small questions/answers) and induces support when the user answers with frustration. The user is playing a very slow and annoying game, with long delay times. In parallel, the computer asks the user his emotional state through multiple answers questions, and displays some supportive messages depending on the user's answer. Results have shown that the users play the annoying game for a longer time when the computer shows empathy to her situation than when the computer does not. One more time this show the interest of empathy in collaboration between human and computers.

• In a computer version of the game of blackjack, a virtual player has been programmed as an agent with empathy. The agent interacts with the users as a player of course, but also by displaying messages and emotions through facial expressions. The agent is able to feel empathy towards the other user's situation but also his own situation. This means the agent is happy when the player wins but also when he wins himself. The set of emotions is limited to happy, sad and neutral (no expression). The messages can be supportive and complaining to the user but also self oriented. S. Brave et al. in [START_REF] Nass | Computers that care: investigating the effects of orientation of emotions exhibited by an embodied computer agent[END_REF] studied the likability, caring, trustworthiness, dominance, positive and support feelings of the agent, described by the users in the four possible situations. Results have shown in most of the cases that the agent induced measured feelings to the users when it was displaying empathy to the user

04/2009 11

and even more when it was also self oriented. This studied demonstrates once more the positive effect of empathy in human-machine interaction. • In a simple treasures hunt game McQuiggan and Lester [START_REF] Mcquiggan | Modeling and evaluating empathy in embodied companion agents[END_REF] programmed an agent that cooperates with the user. The agent is able of facial and body expression as well as text expression. Depending on the user's behavior the agent will display supporting or irritating behavior related to the treasures hunt. For example if the user takes time to find a treasure, the agent will blame the user, and even more if he is looking twice in the same place. If the user displays high skills to discover treasures, the agent will display happiness, compliments and support. If the time is limited, the agent will pressure the user. The study has demonstrated the interest of such agent in the video game area. Such character can influence the user and make the experience of the video game more entertaining.

All those works are centered on the human-computer direct interaction and the improvement of the interaction using empathy is evident. None of those works have been yet deeply understanding the user's motivations and feelings but mainly answering to the user's emotional state. Therefore we have in the study of empathy in its full definition a strong contribution that can be made. Also the fields of application are now quite limited but it makes no doubt that a lot more can be found soon (e.g. as personal advising, problem explanation or individualized interaction).

Validation and conclusion

We have described more the OCC model which is the most popular but just cited the others and given an overview of the current implementations. In this work we have also described three of the most influent computational model of emotions and added a totally new approach of the emotions through empathy.

We described the main computational models of emotions with their pros and cons, and the current implementations in computer science. There might be no best model to describe the emotions but a combination of those models brings the best answer when applied to a real situation. The best contribution that can be made in the synthesis of emotions should first come with one "on-field" application (the purpose) and the adaptation of the chosen model to the situation.

Empathy is a quite new field of research in the human machine interaction. This approach of emotions will bring a new view of programming emotions because it partly answers the question "why emotions?". Indeed, the emotions are not only a motor to express behaviors, but also a mean of expression. Through emotions are expressed the reasons that induced a specific behavior, and empathy allows to understand, learn, and answer to the emotions. It seems that there is still a huge work to do to be able to define and to understand empathetic process, as well as simulating them. Such work would benefit both psychology and artificial intelligence fields.

We have found there a new field of interest in the study of emotions. Because emotions and empathy cannot be dissociated, a research in empathy should contribute a lot in the synthesis 04/2009 12 of emotions. Maybe the approach by empathy is completing the definition emotions which stayed until now far from the real meaning of emotions. In another point of view we can imagine that the first studies conducted on emotions have always been implying empathy, but mainly from the user. We might have here the field that will bring the next generation of humanmachine interactions. The study of empathy will certainly provide the solution for new adaptive and individualized interactions between human and machines. In other words, it may lead to a real collaboration between human and machines.

Figure 1 :

 1 Figure 1: The OCC model.

Figure 3 :

 3 Figure 3: Roseman's structure of emotions

Paul Ekman's Basic Emotions

	Happy-for Gloating Joy Gratitude Admiration Pride	Love Hope Gratification Relief Satisfaction	Happiness
	Resentment Remorse Pity	Distress Shame	Sadness
	Anger Reproach	Hate	Anger
	Fear	Fear-confirmed	Fear
	N/A		Surprise
	N/A		Disgust

Table 1 :

 1 Correspondence between OCC emotions and Paul Ekman's emotionThe Table1allows to highlight the OCC model has some imperfections and does not allow the expressions of all kind of emotions.


Laurent Alonso
email: laurent.alonso@loria.fr

Edward M Reingold
email: reingold@iit.edu

Analysis of Boyer and Moore's MJRTY Algorithm

Keywords:

Given a set of n elements each of which is either red or blue, Boyer and Moore's MJRTY algorithm uses pairwise equal/not equal color comparisons to determine the majority color. We analyze the average behavior of their algorithm, proving that if all 2 n possible inputs are equally likely, the average number of color comparisons used is n -2n/π + O(1) with variance (π -2)n/π -2n/π + O(1).

Given a set {x 1 , x 2 , . . . , x n }, each element of which is colored either red or blue, we must determine an element of the majority color by making equal/not equal color comparisons x u : x v ; when n is even, we must report that there is no majority if there are equal numbers of each color. How many such questions are necessary and sufficient? It is easy to obtain an algorithm using at most n-ν(n) questions, where ν(n) denotes the number of 1-bits in the binary representation of n; furthermore, n -ν(n) is a lower bound on the number of questions needed (see [?] and [?]). In [?], the average case was investigated: Assuming all 2 n distinct colorings of the n elements are equally probable, 2n 3 -8n 9π + O(log n) comparisons are necessary and sufficient in the average case to determine the majority.

In this note we analyze the average performance of an inferior, but historically important majority algorithm, that of Boyer and Moore [?], first described in 1980 as an example of the logic supported by the Boyer-Moore Theorem Prover (1971;see [?]). The algorithm, Algorithm 1, is subtle in that it works correctly even when there are arbitarily many colors as long as the set is known to have an element that occurs more than half the time (in this multi-color case, if the set is not known to have a majority element, a second pass over all n elements is necessary). It is Algorithm 1, called MJRTY in [?], that led to an intensive study of the matter; see [?, sec. 5.8] and [?] for historical details.

Algorithm 1 Boyer and Moore's MJRTY algorithm [?].

1: c ← 0 2: for i ← 1 to n do 3:

// if c = 0 there are equal numbers of red/blue items among 4:

// x 1 , . . . , x i-1 ; otherwise there are c more of the color of x j 5:

if c = 0 then 6:

j ← i 7: c ← 1 8: else if x i = x j then 9: c ← c + 1 10: else 11: c ← c -1 12:
end if 13: end for 14: if c = 0 then 15:

No majority 16: else 17:

Majority is color of x j 18: end if

In the two-color case, the number of color comparisons in line 8 of MJRTY is equal to n less the number of times the algorithm finds c = 0 in line 5, so we focus on counting that number of times. But c = 0 at line 5 can happen only when i is odd, which happens at least once (when i = 1) and at most ⌈n/2⌉ times. It happens when i = 2k + 1 if x 1 , . . . , x 2k contains k copies of each of the two colors, which happens with probability 2k k /2 2k if all 2 n two-colorings of x 1 , . . . , x n are equally probable. Let m = ⌈n/2⌉; the average number of times that c = 0 in line 5 is thus

m-1 k=0 2k k /2 2k , (1)
partial sums of the central binomial coefficients, divided by corresponding powers of 4. The generating function for the central binomial coefficients is C(z) = 1/ √ 1 -4z, so the generating function for the partial sums in (1) is

C(z/4)/(1 - z) = 2C ′ (z/4); hence m-1 k=0 2k k /2 2k = m 2m m /2 2m-1 , (2)
where m 2m m are called Apéry numbers [?, A005430]. By Stirling's formula, the righthand side of (2) is 2n/π + O(1) for m = ⌈n/2⌉. It follows that in the two-color case Boyer and Moore's MJRTY algorithm uses at least ⌊n/2⌋ and at most n -1 color comparisons, and an average of

n -2n/π -O(1) (3)
color comparisons.

We now compute the variance. Let S(n) be the set of all possible 2 n twocolor input sequences to MJRTY. For I ∈ S(n) and 1 ≤ i ≤ n, let c i (I) = 1 if c = 0 in line 5 at iteration i for input I, 0 otherwise, and let S i (n) ⊆ S(n) be the set of input sequences I such that c = 0 at iteration i for input I; and hence c i (I) = 1 for all I ∈ S i (n). With this notation, our derivation of the average (3) is

I∈S(n) n - n i=1 c i (I) Pr(I) = n - I∈S(n) n i=1 c i (I) Pr(I) = n -2n/π -O(1). ( 4
)
The variance is

I∈S(n) n - n i=1 c i (I) 2 Pr(I) -   I∈S(n) n - n i=1 c i (I) Pr(I)   2 = I∈S(n) n i=1 c i (I) 2 Pr(I) -   I∈S(n) n i=1 c i (I) Pr(I)   2 , (5)
c i (I)   n j=1 c j (I)   , = 2 -n n i=1 I∈Si(n)   n j=1 c j (I)   3 because c i (I) is 1 if I ∈ S i (n) and 0 otherwise, = 2 -n n i=1 ||S i (n)||, ( 6
)
where ||S i (n)|| is the total number of times that c = 0 at line 5 over all inputs I ∈ S i (n).

Note that for m ≥ 1, in the input sequence x 1 , . . . , x 2m , the two possible choices for the color of x 2m do not affect the number of times that c = 0 at line 5 (because x 1 , . . . , x 2m-1 must contain a majority color, hence c = 0 in line 5 for i = 2m). we need only compute

||S i (n)|| for odd n because ||S i (2m)|| = 2||S i (2m -1)||.
We can view an arbitrary odd-length input sequence x 1 , . . . , x n ∈ S 2k+1 (n), n = 2m -1, as being composed of two contiguous subsequences: a even-length front part x 1 , . . . , x 2k , in which there is no majority color, and an odd-length rear part x 2k+1 , . . . , x n . These subsequences are independent, so we can count the number times c = 0 in each separately.

First, consider the possible front parts, sequences x 1 , . . . , x 2k with no majority color. The total number of times that c = 0 at line 5 over all such sequences is

f k = k-1 j=0 2j j 2(k -j) k -j = k j=0 2j j 2(k -j) k -j - 2k k , (7)
because if c = 0 happens at line 5 for i = 2j + 1 (with j < k), neither of the subsequences: x 1 , . . . , x 2j and x 2j+1 , . . . , x 2k (which is not empty) contains a majority color. Observing that the sum in ( 7) is a convolution of the central binomial numbers with themselves, the generating function for this sum is C(z) 2 = 1/(1 -4z) and hence

f k = 4 k - 2k k .
Now consider the rear part, an arbitrary odd-length input sequence x 1 , . . . , x 2k+1 . The total number of times that c = 0 in line 5 over all such sequences is

r k = k j=0 2j j 2 2(k-j)+1 = 2 2k+1 k j=0 2j j /2 2j ,
because c = 0 at line 5 for i = 2j + 1 if x 1 , . . . , x 2j contains j elements of each color and the remaining 2(k -j) + 1 elements are colored arbitrarily,

= (k + 1) 2k + 2 k + 1 , evaluated as in (2).
Finally, because each possible front word occurs 2 2m-1-2k times as first part of a word in S 2k+1 (2m -1), and each rear word occurs 2k k times, we obtain

||S 2k+1 (2m -1)|| = 2 2m-1-2k f k + 2k k r m-1-k .
Therefore,

||S 2k+1 (2m -1)|| = 2 2m-1 -2 2m-1 2k k /2 2k + 2k k (m -k) 2(m -k) m -k ,
and so we have

2 -2m+1 2m-1 i=1 ||S i (2m -1)|| = 2 -2m+1 m-1 k=0 ||S 2k+1 (2m -1)|| = m-1 k=0 1 - m-1 k=0 2k k /2 2k +2 -2m+1 n-1 k=0 2k k (m -k) 2m -2k m -k .
We can simplify the second sum as in (2); for the third sum, we note that it is a convolution,

because

  Var(x -y) = Var(x) + Var(y) -2CoVar(x, y) and we have x = n which is constant. Thus we need the value of Pr(I) = 1/|S(n)| = 2 -n , and by distributivity,

  have m = ⌈n/2⌉, so putting together (2), (5), (6), and (8), Stirling's formula gives the variance of the number of color comparisons in line 8 of MJRTY,


Aneel Tanwani
email: aneel.tanwani@inria.fr

Bernard Brogliato
email: bernard.brogliato@inria.fr

Christophe Prieur
email: christophe.prieur@gipsa-lab.fr

On Stability of Measure Driven Differential Equations

We consider the problem of stability in a class of differential equations which are driven by a differential measure associated with the inputs of locally bounded variation. After discussing some existing notions of solution for such systems, we derive conditions on the system's vector fields for asymptotic stability under a specific class of inputs. These conditions present a trade-off between the Lebesgue-integrable and the measure-driven components of the system. In case the system is not asymptotically stable, we derive weaker conditions such that the norm of the resulting trajectory is bounded by some function of the total variation of the input, which generalizes the notion of integral input-to-state stability in measure-driven systems.

INTRODUCTION

In the theory of dynamical systems, a large class of nonlinear systems are modeled by the following ordinary differential equation:

dx dt (t) = f (x(t)) + g(x(t))u(t) (1)
where f, g : R n → R n are the vector fields and u : [t 0 , ∞) → R is the scalar input. If f (•) and g(•) are locally Lipschitz then there exists an interval over which system (1) admits a unique absolutely continuous solution x(•) for every Lebesgue-measurable function u(•), where the resulting solution satisfies (1) almost everywhere (with respect to the Lebesgue measure) on the interval where the solution exists. Under further regularity assumptions, say f (•), g(•) satisfy a linear growth condition, the solution is defined for all times, in which case we say that f (•), g(•) are forward complete.

In this paper, we consider measure differential equations (MDEs) modeled as: dx = f (x)dt + g(x)du.

(2) Just like (1) is driven by an input u(•), the dynamics of system (2) can be seen as driven by the "derivative" of u(•). However, to achieve generality, we assume that u(•) is a right-continuous function with locally bounded variation (locally RCBV), so its generalized derivative, or the so-called differential measure, is represented by du. If u(•) is absolutely continuous, then the derivative of u(•) is a Lebesgue-measurable function. In that case, we take du = udt, where u represents the classical derivative, and system (2) is equivalent to (1) with u(•) replaced by u(•). The framework of system (2) can be used to model the dynamics of a rich class of state trajectories. If u(•) is considered to be a piecewise constant function, then du is a sum of Dirac impulses, in which case (2) models discontinuities in the state trajectory. Another advantage of considering MDEs is that we can possibly model Zeno trajectories because u(•) as a function of bounded variation may exhibit infinitely many discontinuities in a finite interval. This also makes the simulation of Zeno trajectories possible as one no longer uses the classical eventbased schemes to model discontinuities but rather a timestepping algorithm is employed as demonstrated in [START_REF] Acary | Higher order Moreau's sweeping process: Mathematical formulation and numerical simulation[END_REF]. Other than the discontinuities, singularly continuous inputs (such as a random process with continuous sample path) may also be considered. Certain applications of such mathematical models for modelling of mechanical systems are discussed in [START_REF] Brogliato | Nonsmooth Mechanics[END_REF].

The solution theory for such systems could be traced back to the work of [START_REF] Kurzweil | Generalized ordinary differential equations[END_REF], where he approximated the integral version of (2) with a sequence of integrals associated with ordinary differential equations to develop existence conditions for a generalized solution. In the context of optimal control, measure differential equations were studied by [START_REF] Schmaedeke | Optimal control theory for nonlinear vector differential equations containing measures[END_REF], where he also generalized Caratheodory's concept of solution for systems of form (2) with g(•) being time-dependent only. [START_REF] Sussmann | On the gap between deterministic and stochastic ordinary differential equations[END_REF] studied such differential equations to develop solution concept for a class of stochastic differential equations using the theory of ordinary differential equations, but only considered singularly continuous inputs. Based on his work, [START_REF] Bressan | On differential systems with impulsive controls[END_REF] and later Bressan Jr. and Rampazzo [1991] generalized the idea to consider discontinuous inputs, and in general, the functions of bounded variation.

From stability point of view, the work of [START_REF] Code | Closed loop stability of measure-driven impulsive control systems[END_REF] talks about stabilization in terms of existence of an input function that makes some Lyapunov function decrease along the trajectories of the system (2).

In our work, we will adopt the solution framework proposed by [START_REF] Sussmann | On the gap between deterministic and stochastic ordinary differential equations[END_REF] and later developed by [START_REF] Bressan | Impulsive control systems with commutative vector fields[END_REF]. A brief account of this solution methodology is collected in Section 3 which we would also use in deriving conditions for stability of the system. Our approach towards the problem of stability is different from any of the work mentioned before. We study two different notions of stability for system (2) and provide related sufficient conditions. The first one relates to the convergence of the state trajectories towards the equilibrium. Since the stability would in general be affected by the inputs, in the proposed sufficient condition, we specify a class of inputs for which the system admits asymptotically convergent behavior.

The other notion of stability considered in this paper relates to input-to-state stability (ISS) pioneered by [START_REF] Sontag | Smooth stabilization implies coprime factorization[END_REF]. The basic idea is to study weather the norm of the state trajectories is bounded by some increasing function of the norm of the input. In this regard, for system (2), we compare the supremum norm of the state trajectories with the total variation of the input. Since the total variation of a function equals the integral of the absolute value of the derivative of the function (when the function is differentiable), the considered problem is a generalization of the integral variant of ISS studied in [START_REF] Sontag | Comments on integral variants of ISS[END_REF].

PRELIMINARIES

We recall some preliminary results related to functions of bounded variation which will be used later on. For a function f : [s, t] → R n , the total variation is a non-decreasing function and is defined for τ ∈ [s, t] as

var f (τ ) = sup k i=1 |f (t i )-f (t i-1 )|
, where the supremum is taken over all integers k, and all possible choices of the sequence

{t i } such that s = t 0 < t 1 < • • • < t k = τ . The function f (•) is said to be of bounded variation (BV) on [a, b] if var f (b) < ∞.
If it is right continuous with bounded variation we denote it as RCBV. It is locally [a, b] then it has at most a countable number of jump discontinuities. Moreover, it has right and left limits everywhere. The right and left limits of a function at t are denoted as f (t + ) := lim sցt f (s) and f (t -) := lim sրt f (s), respectively, and are well defined for BV functions. In this notation, right continuity of f (•) in t, means that f (t + ) = f (t).

RCBV if this holds for any compact interval [a, b] ⊂ R. If f (•) is BV on
For an interval I ⊆ R, we denote by L 1 (I, R n ; ν) and L 1 loc (I, R n ; ν) the space of integrable and locally integrable functions, respectively, from I to R n with respect to the measure ν. If the measure is not specified then the integration is with respect to the Lebesgue measure. Similarly,

C 1 (R, R n ) denotes the set of continuously differentiable functions from R to R n .
For a non-decreasing, right-continuous function u(•) of bounded variation, we can associate a Lebesgue-Stieltjes measure µ = du such that µ((s, t]) = u(t) -u(s). It is well-known that every RCBV function could be written as a difference of two right-continuous non-decreasing functions, that is, there exist some functions u + and u - (both non-decreasing) such that u = u + -u -. We can then associate the Lebesgue-Stieltjes measure with each of these functions and denote them by µ + and µ -, respectively. Thus, if µ denotes the Lebesgue-Stieltjes measure associated with an RCBV function u(•), then µ = µ + -µ -.

The total variation of this measure is denoted by |µ|, and is equal to µ + +µ -. We will use the notation |µ| [t0,t] to denote the total variation of the measure µ over the interval [t 0 , t] and it is seen that |µ| [t0,t] = var u (t).

The distributional derivative du (also called the differential measure) introduced in (2) could be seen as a generalized notion of derivative and satisfies the following relation:

µ((s, t]) = u(t) -u(s) = (s,t] du.
One may verify that, for absolutely continuous functions, if we let du = udt with u(•) a Lebesgue-measurable function denoting the classical derivative of u(•), then the above relation is obtained simply from the fundamental theorem of calculus. It is noted that the RCBV function u(•) is decreasing (or, non-decreasing) over an interval if du < 0 (resp., du ≤ 0).

We also recall that the function u(•), being locally RCBV, has countably many discontinuities over the interval [t 0 , ∞), and we let I denote a countable set that indexes the discontinuities of u(•). The measure µ associated with u(•) admits the following decomposition: µ = µ ac + µ sing + µ d , where µ ac is absolutely continuous with respect to Lebesgue measure, µ sing is associated with a singular function which is continuous everywhere and differentiable almost everywhere with zero derivative (e.g., the Cantor function). We use the notation µ c := µ ac + µ sing to denote the continuous part of µ. The discontinuous part is given by µ d := i∈I µ({t i }), where µ({t i }) denotes the jump discontinuity at time t i . To clarify some notation later and better understand the definition of the measure µ,

note that if u(•) is RCBV on an interval [s, t] with a single discontinuity at t i , s < t i < t, then µ d ([s, t]) = µ({t i }) = u(t + i ) -u(t - i ), and µ c ([s, t]) = µ([s, t]) -µ d ([s, t]).

SOLUTION CONCEPTS

As stated in the introduction, the solution of system (2) is well-defined for an absolutely continuous input u(•). However, in this paper, it is assumed that the function u(•) is only locally RCBV in which case the term du denotes the differential measure associated with u(•). When g(•) is assumed to be a continuous function of time only, and not of state, there is no ambiguity in the interpretation of the solution. In that case, Carathédory's notion of solution for ordinary differential equation has been extended to arrive at similar conditions for existence and uniqueness of solution to system (2) in the class of locally RCBV functions, see [START_REF] Schmaedeke | Optimal control theory for nonlinear vector differential equations containing measures[END_REF]. However, with the vector field g(•) considered as a function of the state variable, the notion of solution is not so straight forward. The following example illustrates some degree of difficulty in obtaining the solution to MDE (2).

Example 1. Consider system (2) with f (x) = 0, g(x) = x, and u(t) = c 1 H(t), where c 1 > 0, and

H(t) = 0, t 0 < t < t 1 1, t 1 ≤ t < ∞
. This gives du = c 1 δ t1 , where δ t1 denotes the Dirac impulse at time t 1 . It is clear that x(t) = x(t 0 ), for t 0 ≤ t < t 1 . For t ≥ t 1 , if we pick x(t) = (1 + c 1 )x(t 0 ) then the equation {t1} dx = x(t - 1 ) {t1} du holds; however, the solution x(t) = x(t 0 )/(1 -c 1 ) satisfies {t1} dx = x(t + 1 ) {t1} du. Another solution is obtained by approximating u(•) with a sequence {u k } ∞ k=1 of continuously differentiable functions. Then for each element of the sequence, the resulting solution is obtained by solving ẋk x = uk (t), which leads to x k (t) = x(t 0 )e u k (t) . One then takes x(•) to be the limit of the sequence {x k } ∞ k=1 and let x(t) = x(t 0 )e u(t) to be the solution. In terms of the original system description in differential form, this last solution satisfies {t1} dx = x {t1} du, for some

x ∈ [x(t - 1 ), x(t + 1 )].
It is seen that the first two notions of solutions considered in the example are not continuous with respect to the inputs. In general, such solutions won't be unique either. However, the last solution obtained by approximating u(•) with continuously differentiable functions has some nice properties and we will develop results on stability with respect to such solutions. Formally, the solution to system (2) is defined as follows: Definition 1. For a given locally RCBV input u

: [t 0 , ∞) → R, a locally RCBV function x(u, •) : [t 0 , ∞) → R n is called a solution of (2) if there exists a sequence of controls u k ∈ C 1 ([t 0 , ∞), R) such that u k (t 0 ) = u(t 0 ), u k → u in L 1 -norm on every compact interval I ⊂ [t 0 , ∞) and the corresponding trajectories x(u k , •) → x(u, •) in L 1 -norm on I.
In order to prove the existence of solution in the sense of Definition 1, we recall the work of [START_REF] Sussmann | On the gap between deterministic and stochastic ordinary differential equations[END_REF] and [START_REF] Bressan | Impulsive control systems with commutative vector fields[END_REF]. Towards that end, let Φ g (s; x 0 ) denote the Carathéodory solution of the ordinary differential equation ẋ = g(x) at time s with initial condition x 0 , i.e., Φ g (0; x 0 ) = x 0 . It is seen that Φ -1 g (s; x 0 ) = Φ g (-s; x 0 ). Now, consider the state transformation ϕ : R n+1 → R n+1 defined as: ȳ := (y, y u ) := ϕ(x, u) := (Φ g (-u; x), u).

(3) The system dynamics in these coordinates are then given by: ẏ = F (y, y u ), y(t 0 ) = Φ g (-u(t 0 ); x(t 0 )), (4a)

dy u = du, y u (t 0 ) = u(t 0 ). ( 4b
)
where F (y, y u ) = ∂Φg(-u,x) ∂x (x,u)=(Φg(yu;y),yu)

•f (Φ g (y u ; y)).

In (4), it is important to note that there is no discontinuous function multiplying the measure du, which makes it easier to study the solution of this transformed system.

To formally prove the existence of solution to system (2) in the sense of Definition 1, a sequence of solutions {ȳ k } is first obtained from continuously differentiable functions u k . The limit of the sequence {ȳ k }, let's say ȳ, is then mapped under the map ϕ -1 to obtain the solution x(•).

We thus have the following result: Proposition 2. Assume that the equation (4a) has a solution on every compact interval [t 0 , T ], then x(t) = Φ g (u(t); y(t)), ∀ t ∈ [t 0 , T ] is the solution of (2) in the sense of Definition 1.

It is important to note that the forward completeness of the vector fields f (•) and g(•) is not sufficient to guarantee that the solution of (4a) is forward complete. While working with continuous inputs, a counterexample has been given in [Sussmann, 1978, Section 8]. In the same paper in Theorem 2, he presented sufficient conditions (which roughly state that f (•) satisfies a linear growth condition and g(•) ∈ C 1 (R n , R n ) with ∂g ∂x uniformly bounded) that guarantee the existence and uniqueness of the solutions to (4) with u(•) being continuous. Later, it was shown in [Bressan and Rampazzo, 1993, Theorem 2.1] that these conditions are sufficient for existence of global (in time) solutions of (4a). Without imposing such conditions on system vector fields, we work under the following assumption in the remainder of the paper so that the solution of system (2) is considered according to Proposition 2. Assumption 1. There exists a unique solution to the ordinary differential equation (4a) on every compact interval for each RCBV function y u (•).

An interesting outcome of the coordinate transformation introduced in (3) is that the solution x(•) at the discontinuities is characterized as follows: Proposition 3. At the atoms {t i } of µ, we have

x(t + i ) = Φ g (u(t + i ) -u(t - i ); x(t - i )).
To see this, note that from Proposition 2 we have,

x(t + i ) = Φ g (u(t + i ); y(t + i )), where y(t + i ) = y(t - i ) = Φ g (-u(t - i ); x(t - i ))
. Since Φ g satisfies the group action properties, we get Φ g (u(t

+ i ); Φ g (-u(t - i ); x(t - i ))) = Φ g (u(t + i ) -u(t - i ); x(t - i )).
Revisiting Example 1: To get a good understanding of the foregoing discussion, let us apply the coordinate transformation in (3) to the system considered in Example 1. In that case, Φ g (-u; x) = xe -u , so that ȳ = ϕ(x, u) = (xe -u , u). Since, f (x) ≡ 0, we simply get ẏ = e -u -xe -u 0 1

x 1 du = 0 1 du.

Thus, y(t) ≡ y(t 0 ) = x(t 0 )e -u(t0) remains constant, whereas y u (t) = u(t). Applying the inverse transformation, we get x(t) = e u(t)-u(t0) x(t 0 ), which coincides with our earlier observation.

STABILITY RESULTS

We now study the stability properties of system (2) with respect to the origin. It is assumed that f (0) = 0, so that the origin is indeed an equilibrium point of the unforced system. Two variants of the stability notions will be considered. The first one relates to the attractivity of the state trajectories towards the origin for a specific class of inputs and is studied in Section 4.1. Then, in Section 4.2, we derive weaker conditions to establish the boundedness of the state trajectories in terms of the total variation of the input.

Before stating the main result, we recall some standard definitions: A function α : [0, ∞) → [0, ∞) belongs to class K if it is continuous, strictly increasing, and α(0

) = 0. If, in addition, α is unbounded then α belongs to class K ∞ . A function β : [0, ∞) × [0, ∞) → [0, ∞) belongs to class KL if β(•, t) ∈ K for each t ≥ 0, β(r,
•) is strictly decreasing for each r ≥ 0 and β(r, t) → 0 as t → ∞.

Asymptotic Stability

We call the system (2) uniformly asymptotically stable over a set of inputs U if there exists a class KL function β such that every state trajectory x(•) resulting from the input u ∈ U as a solution of (2) satisfies |x(t)| ≤ β(|x(t 0 )|, t-t 0 ). Theorem 4. Assume that there exists a continuously differentiable function V : R n → R + , some class K ∞ functions α 1 , α 2 , and some constants a, b, b ∈ R such that the following holds for each x ∈ R n :

α 1 (|x|) ≤ V (x) ≤ α 2 (|x|), (5a) ∇V (x), f (x) ≤ aV (x), (5b) b V (x) ≤ ∇V (x), g(x) ≤ b V (x).
(5c) Let U c,θ denote the class of inputs satisfying: 6) for some c > 0 and θ ∈ K ∞ . Then, system (2) is uniformly asymptotically stable over U c,θ .

a(t -t 0 ) + bµ + ([t 0 , t]) -bµ -([t 0 , t]) ≤ c -θ(t -t 0 ) (
Proof. Consider the Lyapunov function V (•) satisfying the hypothesis in the statement of the theorem. Since V (•) is continuously differentiable and the solution x(•) is locally RCBV, the composition function V (x(t)) is also locally RCBV [Moreau and Valadier, 1987, Theorem 3]. Over an interval (t i , t i+1 ) between the two discontinuities of the input u(•), the state trajectory x(•) is continuous and the differential measure of V (•) is computed by dV = ∇V (x), f (x) dt + ∇V (x), g(x) du Writing u = u + -u -and using (5b), (5c), we get dV ≤ aV dt + bV du + -bV du -.

(7) For t ∈ (t i , t i+1 ), let m(t) := a(t -t i ) + bµ + ((t i , t))bµ -((t i , t)), and W (t) := e -m(t) V (t). The use of product rule and chain rule for differential of bounded variation functions (recalled from [Monteiro Marques, 1993, Page 8] and [Moreau and Valadier, 1987, Theorem 3]) and inequality (7) yield: dW = V (t)e -m(t) -adt -bdu + + bdu -+ e -m(t) dV ≤ 0. Thus, W (•) is non-increasing on the interval (t i , t i+1 ) for each i ∈ I, and since W (t) is right-continuous, W (t) ≤ W (t i ), which implies that

V (t) ≤ e m(t) V (t i ). (8) If {t i } is an atom of the measure µ, then from Proposi- tion 3, x(t + i ) is obtained by the solution of the differential equation ż(s) = g(z(s)) at time s = µ({t i }) = µ + ({t i }) - µ -({t - i }) with the initial condition z(0) = x(t - i ). Equiv- alently, one can solve ż(s) = g(z(s)) for s ∈ [0, µ + ({t i })] and ż(s) = -g(z(s)) over the interval [µ + ({t i }), µ + ({t i })+ µ -({t i })] with z(0) = x(t - i ). Let v(s) = V (z(s)), then for each s ∈ [0, µ + ({t i })], v(s) = ∇V (z), g(z) ≤ bv(s)
, and the comparison lemma [Khalil, 2002, Lemma 3.4]

yields v(µ + ({t i })) ≤ e bµ + ({ti}) v(0). For the interval [µ + ({t i }), µ + ({t i }) + µ -({t i })], we have v(s) = ∇V (z), -g(z) ≤ -bv(s) which, using comparison lemma, leads to v(µ + ({t i }) + µ -({t i })) ≤ e -bµ -({ti}) v(µ + ({t i })) ≤ e bµ + ({ti})-bµ -({ti}) v(0).
Substituting the value of v and using x(t

+ i ) = z(µ + ({t i })+ µ -({t i })), we get V (x(t + i )) ≤ e bµ + ({ti})-bµ -({ti}) V (x(t - i )). (9)
Combining ( 8) with ( 9) and using the countable additivity of the measure µ(•), we get:

V (t) ≤ e a(t-t0)+ bµ + ([t0,t])-bµ -([t0,t]) V (t 0 ) ≤ e c-θ(t-t0) V (t 0 )
where we used (6) to obtain the last inequality. Using (5a) and letting β(r, t) := α -1 1 (e c α 2 (r))e -θ(t) , we obtain |x(t)| ≤ β(|x(t 0 )|, t -t 0 ), which proves the desired result since β ∈ KL. ✷ Remark 5. For impulsive systems, the result of Theorem 4 could be seen as a generalization of [Hespanha et al., 2008, Theorem 1] where the authors give conditions on frequency of impulsive times depending on margin of stability/instability in continuous and discrete dynamics.

We now address a special case of Theorem 4 for a specific class of inputs. Let U M denote the class of inputs for which |µ| [t0,∞) ≤ M , that is, the total variation of the inputs is bounded by some constant M > 0. The following corollary shows that U M ⊂ U c,θ for some c > 0, and θ ∈ K ∞ . Corollary 6. Suppose that the hypotheses of Theorem 4 hold with a < 0 in (5b). Then, system (2) is uniformly asymptotically stable over U M .

Proof. To prove the desired result, we derive the constant c and function θ in (6). Letting b := max{ b, |b|}, we note that bµ

+ ([t 0 , t]) -bµ -([t 0 , t]) ≤ b(µ + ([t 0 , t]) + µ -([t 0 , t])) = b|µ| [t0,t] .
Since the total variation is non-decreasing with t and is bounded by M for all t ≥ t 0 , we can choose c := bM and θ(t) := -at to see that the inequality (6) indeed holds. ✷ Example 2. Consider a bilinear system

dx = Axdt + Bxdu (10)
with the matrix A assumed to be Hurwitz. There exists a symmetric positive definite matrix P > 0 such that

A ⊤ P + P A = -aP for some a > 0. With V = x ⊤ P x, this gives ∇V (x), Ax ≤ -aV (x) for all x ∈ R n . Moreover, we have bV (x) ≤ ∇V (x), Bx ≤ bV (x) for b = λmin( B) λmax(P ) , b = λmax( B)
λmin(P ) , where B = P B + B ⊤ P , and λ max (•), λ min (•) denote the maximum and minimum eigenvalues of a matrix, respectively. If λ min ( B) > 0 and U ed comprises of inputs that are eventually non-increasing 1 then system (10) is asymptotically stable over U ed because, for each u(•) ∈ U ed , the term µ + ([t 0 , t]) becomes constant after some large t.

Similarly, if λ max ( B) < 0 and U ei comprises of inputs that are eventually non-decreasing then system (10) is asymptotically stable over U ei because µ -([t 0 , t]) becomes constant after some t large enough, for each u(•) ∈ U ei .

Input-to-State Stability with Variation

In contrast to asymptotic stability for a specific class of inputs, we are now interested in studying another notion of stability for system (2). The motivation is to consider systems which are not necessarily asymptotically stable but the maximum value of the state trajectories depends on some norm of the driving input. This may be particularly interesting when u(

Next, we present sufficient conditions under which the property (11) holds. Theorem 8. Suppose that there exist a continuously differentiable function V : R n → R + , some class K ∞ functions α 1 , α 2 , and some positive constants a, b, c > 0 such that for each x ∈ R n :

α 1 (|x|) ≤ V (x) ≤ α 2 (|x|), (12a) ∇V (x), f (x) ≤ -aV (x), (12b) -bV (x) -c ≤ ∇V (x), g(x) ≤ bV (x) + c, (12c)
then system (2) is ISS with respect to the variation of u(•).

Proof. Over an interval (t i , t i+1 ) between two discontinuities of the input u(•), we have dV = ∇V (x), f (x) dt + ∇V (x), g(x) du ≤ -aV dt + bV du + c du. Using Lemma 10 in Appendix A, the following holds for each t ∈ (t i , t i+1 ): t) |µ| [ti,t) .

V (t) ≤ e -a(t-ti)+b|µ| [t i ,t) V (t i ) + ce b|µ| [t i ,
To obtain an upper bound on V (t + i ) at a jump instant t i , we follow the same arguments as in the proof of Theorem 4 and use the fact that x(t 12c), and the comparison lemma yields:

+ i ) = z(µ + ({t i })+µ -({t i })) where z(•) is such that ż(s) = g(z(s)) for s ∈ [0, µ + ({t i })] and ż(s) = -g(z(s)) for z ∈ [µ + ({t i }), µ + ({t i }) + µ -({t i })], with initial condition z(0) = x(t - i ). Letting v(s) = V (z(s)), we have v(s) ≤ bv(s) + c for s ∈ [0, µ + ({t i }) + µ -({t i })] using (
v(|µ| {ti} ) ≤ e b|µ| {t i } v(0) + c b e b|µ| {t i } -1
where we recall that |µ| {ti} = µ + ({t i }) + µ -({t i }). This, in turn gives

V (t + i ) ≤ e b|µ| {t i } V (t - i ) + c b e b|µ| {t i } -1 .
Using these expressions for continuous and discrete flow of the function V (•), it is observed that for any t ∈ (t i , t i+1 ), i ≥ 1, we have

V (t) ≤ V ic (t) + V uc (t) + V u d (t), ( 13
) where V ic (•) denotes the evolution of V (•) due to the initial condition V (t 0 ), V uc (•) denotes the evolution due to continuous part of the input between discontinuities, and V u d denotes the evolution due to jumps in the input. The values of these three functions are given by:

V ic (t) = e -a(t-t0)+b|µ| [t 0 ,t) V (t 0 ) V uc (t) = c i-1 k=0 e -a(t-t k+1 )+b|µ| (t k ,t) |µ| (t k ,t k+1 ) + ce b|µ| (t i ,t) |µ| (ti,t) (14) V u d (t) = c b i k=1 e -a(t-t k )+b|µ| (t k ,t) e b|µ| {t k } -1 .
Using e -a(t-t k ) ≤ 1 and e b|µ| (t k ,t) ≤ e b|µ| [t 0 ,t] for each k ≤ i, we obtain

V u d ≤ c b e b|µ| [t 0 ,t] i k=1 (e b|µ| {t k } -1). ( 15
)
To obtain similar bound for V uc (t), we multiply and divide ( 14) by b, and in addition use the fact r ≤ e r -1, for r ≥ 0, to get

V uc (t) ≤ c b e b|µ| [t 0 ,t] i-1 k=0 (e b|µ| (t k ,t k+1 ) -1)
+ (e b|µ| (t i ,t) -1) ( 16)

Adding ( 15) and ( 16), and using the fact (e r1 -1) + (e r2 -1) ≤ e r1+r2 -1, we have

V uc (t) + V u d (t) ≤ c b e b|µ| [t 0 ,t] e b|µ| [t 0 ,t] -1 . (17)
Finally, the upper bound on V ic (t) is obtained as follows:

V ic (t) = e -a(t-t0) V (t 0 ) + e -a(t-t0) (e b|µ| [t 0 ,t] -1)V (t 0 ) ≤ e -a(t-t0) V (t 0 ) + 1 2 (e -a(t-t0) V (t 0 )) 2 + 1 2 (e b|µ| [t 0 ,t] -1) 2 . ( 18
)
The estimate as in (11) can now be computed by introducing the following functions:

β(r, t) := α -1 1 ( θ(e -at α 2 (r))) (19)
where θ(r) := r + 1 2 r 2 is a class K ∞ function, and γ(s) := 1 2 (e bs -1) 2 + c b e bs (e bs -1). ( 20)

Plugging ( 17), ( 18) in ( 13) and noting that V (x(t 0 )) ≤ α 2 (|x(t 0 )|) and |x(t)| ≤ α -1 1 (V (x(t))), the desired result (11) is obtained with β and γ defined in ( 19) and (20), respectively. ✷ Remark 9. For absolutely continuous functions, the variation is equal to L 1 -norm of the derivative of that function. Since system (2), in that case, could be thought of as driven by the derivative of the input, the notion of ISS given in Definition 7 coincides with the notion of integral ISS dicussed in [START_REF] Sontag | Comments on integral variants of ISS[END_REF]. Comparing our sufficient conditions with the ones presented in that paper, we chose to work with a linear multiple of the norm of the input instead of an arbitrary class K ∞ function so that the resulting inequalities involving measures could be explicitly solved. Example 3. Consider the MDE dx = -x + du with the Lyapunov function V (x) = 1 2 x 2 . It is easy to see that the inequalities (12) hold with α 1 (r) = α 2 (r) = 1 2 r 2 , and the constants a = b = 2, c = 1. Thus the system is ISS with respect to variation. Example 4. Consider the following bilinear system: dx = Axdt + (B 1 x + B 2 )du with A being a Hurwitz matrix. We show that this system is ISS with respect to variation of the input. To see this, we consider the Lyapunov function V = x ⊤ P x where P is a symmetric positive definite matrix satisfying A ⊤ P + P A = -aP for some a > 0. Thus, (12a) and (12b) hold.

To find the desired constants in (12c), note that 2P x, B 1 x ≤ 2 P B

CONCLUSION

In this paper, we studied the problem of stability in a class of differential equations driven linearly by differential measures associated with functions of locally bounded variation. Sufficient conditions based on Lyapunov function were given for uniform asymptotic stability over a certain class of inputs. We then studied a generalized notion of integral ISS in measure driven systems and presented sufficient conditions under which the supremum norm of the state is bounded by the total variation of the measure associated with input.

  )|, t -t 0 ) + γ(|µ| [t0,t] ) t ≥ t 0 .

	•) models additive noise or
	there are undesired impulsive perturbations in the state
	trajectory.
	Definition 7. System (2) is called input-to-state stable
	(ISS) with respect to variation of the input u(•) if there
	exist a class KL function β and a class K ∞ function γ
	such that
	|x(t)| ≤ β(|x(t 0

  1 • |x| 2 where P B 1 denotes the induced Euclidean norm of the matrix P B 1 . Also, 2P x, B 2 ≤ 2 P B 2 • |x| ≤ P B 2 2 + |x| 2 Similarly, by using the Cauchy-Schwarz inequality in other direction, we get 2P x, B 1 x + B 2 ≥ -(2 P B 1 + 1)|x| 2 -P B 2 2 .

	Using the fact |x| 2 ≤	1 λmin(P ) V (x), it is observed that (12c)
	holds with
	b =	2 P B 1 + 1 λ min (P )	,	c = P B 2	2 .

A function h : R → R is called eventually non-increasing if there exists T such that for every ε

> ε 1 ≥ 0, it holds that h(T + ε 2 ) ≤ h(T + ε 1 ). Similarly, h(•) is called eventually non-decreasing if -h(•) is eventually non-increasing.

Appendix A. GENERALIZED COMPARISON LEMMA Lemma 10. Consider a continuous function V (•) that satisfies dV ≤ -aV dt + bV dµ + cdµ (A.1) on an interval [t 0 , t 1 ), then for each t ∈ [t 0 , t 1 )

Proof. We split the proof in two steps:

Step 1. Consider a continuous function W such that dW = -aW dt

of continuously differentiable functions converging to u(•) with respect to L 1 -norm and let W k represent the solution of (A.2) obtained by replacing dµ with uk dt. Then

From [Ambrosio et al., 2000, Theorem 3.9], one can pick the sequence u k (•) converging to u(•) in L 1 -norm such that uk[t0,t) 1 converges to |µ| [t0,t) . Hence, t) |µ| [t0,t) .

Step 2. We now show that V (t) ≤ W (t) for each t ∈ [t 0 , t 1 ), from which the desired result follows. Indeed, if V and W satisfy (A.1) and (A.2), then W := V -W satisfies dW ≤ -aW dt + bW dµ where W (t 0 ) = 0. Using the same arguments as in the proof of Theorem 4, we obtain W (t) ≤ e -a(t-t0)+bµ ([t0,t]) W (t 0 ) so that W (t) ≤ 0, or equivalently V (t) ≤ W (t).