Elie Akiki

Sara Nassar

Haithem Ghileb

Ali Wehbe

Ramy Kazan

Rita Assaf

Rawad Wakim

Anthony Al Laffe

Georges Chehade

Houssein Mattar

Said Melhem

Charbel Ephrem

Chrisitan Hachem

Toni Badr

Toni Mhanna

Abdel Alim

E L Dennawi

Mazen Israel

Andrew Abi Rached

Mohammad Mays

Elias Alam

Claude Le Gallic

François Boustani

Stability of constrained switched systems driven by ω-regular languages

Keywords: Switched systems, Observer, Lyapunov functions, Büchi automaton, Stability

for providing me with an exciting history book during my thesis journey at LMF. A warm thanks also goes to Maryelle Fradin for her enormous support throughout my doctoral journey! I would also like to thank Valérie Le Port for designing tips.

Last but most importantly, I extend my deepest gratitude to my parents, whose unwavering love and support have been the seeds from which my

Titre: Stabilité des systèmes commutés contraints par des langages ω-réguliers Mots clés: Systèmes commutés, Observateur, Fonctions de Lyapunov, automate de Büchi, Stabilité.

Résumé: Les systèmes commutés sont des systèmes dynamiques comportant plusieurs modes de fonctionnement, chaque mode étant décrit par une équation différentielle (temps continu) ou une équation aux différences (temps discret). Le mode de fonctionnement actif est déterminé à tout moment par un signal de commutation. Les systèmes commutés sont très utiles en pratique pour décrire précisément l'exécution d'algorithmes de contrôle sur des infrastructures informatiques distribuées et ainsi pour prendre en compte les contraintes liées à l'utilisation de ressources informatiques et de communication partagées. De plus, les systèmes commutés présentent des propriétés inattendues (un comportement instable peut par exemple résulter d'une commutation entre des modes de fonctionnement stables) qui justifient le développement d'outils théoriques spécifiques pour leur étude. Les premiers travaux sur la stabilité des systèmes commutés se sont concentrés sur la stabilité des signaux de commutation arbitraires ou satisfaisant certaines conditions de temps de séjour (minimum ou moyen). Plus récemment, plusieurs travaux se sont penchés sur le problème de la preuve de la stabilité de sous-ensembles de signaux de commutation. En général, de tels signaux de commutation sont supposés être générés par un automate à états finis et la stabilité est caractérisée soit en terme de rayon spectral conjoint contraint, soit à l'aide de fonctions de Lyapunov. Cependant, certains sous-ensembles de signaux de commutation ne peuvent pas être spécifiés à l'aide d'automates à états finis classiques. Les exemples sont les signaux de commutation appartenant à certaines langues oméga-régulières qui sont définies par des formules de logique tem-porelle linéaire (LTL). Ils sont souvent utilisés pour spécifier les protocoles de planification et de communication. Un exemple représentatif de langage oméga-régulier est l'ensemble des signaux de commutation de type "shuffle" : un signal de commutation est dit de type "shuffle" si et seulement si tous les modes sont activés une infiniment souvent. Dans une étude préliminaire, la stabilité des systèmes commutés sous signaux de commutation de ce type de contrainte a été caractérisée au moyen des fonctions de Lyapunov. Cette thèse vise à développer des outils théoriques et numériques pour analyser la stabilité des systèmes commutés sous signaux de commutation de type "shuffle" et plus généralement sous contraintes données par un langage oméga-régulier. Nous définissons une notion de rayon spectral joint "shuffled" qui nous permet de quantifier la vitesse de convergence du système commuté sous des signaux de commutation de type "shuffle". Nous développons des algorithmes numériques basés sur les inégalités matricielles linéaires (IML) et des techniques théoriques des automates pour calculer des approximations du rayon spectral joint "shuffled". Dans la deuxième partie de la thèse, nous étendons ces résultats à des classes plus générales de signaux de commutation tels que ceux spécifiés par les langages omégaréguliers. Ces langages peuvent toujours être caractérisés par des automates de Büchi. Enfin, nous présenterons une conception d'observateur pour systèmes commutés basée sur les automates de Büchi et les séquences reconstructibles, c'està-dire des séquences permettant d'estimer l'état du système. Cette conception consiste en une application de nos résultats théoriques.

Abstract: Switched systems are dynamical systems with several operating modes, each mode being described by a differential (continuous time) or difference (discrete time) equation. At all times, the active operating mode is determined by a switching signal. Switched systems are very useful in practice for accurately describing the execution of control algorithms on distributed computing infrastructures and thus for taking into account the constraints linked to the use of shared computing and communication resources. Furthermore, switched systems have unexpected properties (unstable behavior can for example result from switching between stable operating modes) that justify the development of specific theoretical tools for their study. Early work on stability of switched systems has focused on stability for switching signals that are arbitrary or that satisfy some (minimum or average) dwell-time condition. More recently, several works have considered the problem of proving stability for subsets of switching signals. In general, such switching signals are assumed to be generated by some finite state automaton and stability is characterized either in term of constrained joint spectral radius or using Lyapunov functions. However, there are some subsets of switching signals that cannot be specified using classical finite state automata. Examples are switching signals belonging to some omega-regular languages e.g. defined by Linear Temporal Logic (LTL) formu-las, which are often used to specify scheduling and communication protocols. A representative example of omega-regular language is the set of shuffled switching signals: a switching signal is shuffled if and only if all the modes are activated infinitely often. In a preliminary study, the stability of switched systems under shuffled switching signals was characterized by means of Lyapunov functions. This thesis aims at developing theoretical and numerical tools to analyze the stability of switched systems under shuffled switching signals and more generally under constraints given by an omega-regular language. We define a notion of shuffled joint spectral radius that allows us to quantify the speed of convergence of the switched system under shuffled switching signals. We develop numerical algorithms based on Linear Matrix Inequalities (LMIs) and automata theoretic techniques to compute approximations of the shuffled joint spectral radius. In the second part of the thesis, we extend these results to more general classes of switching signals such as those specified by omega-regular languages. These languages can always be characterized by Büchi automata. Finally, we will present an observer design for switched systems based on the Büchi automata and reconstructible sequences, i.e. sequences allowing to estimate the state of the system. This design consists of an application of our theoretical results.

To my parents, the Constants in My Equation of Life

Above all, I am deeply thankful to my supervisor Antoine Girard for his trust in me. Antoine let me see things from another perspective. I learned a lot from him. His perfectionism and rigor have been a source of inspiration, and I am grateful for the opportunities for intellectual growth that he provided.

I would also like to express my gratitude from all my heart to Patricia Bouyer-Decitre and my coadvisor Laurent Fribourg, for giving me a chance to thrive for three years in the Laboratoire Méthodes Formelles (LMF). I thank Laurent for all his guidance and encouragement during my thesis. His support and advice led to fruitful discussions on computer science topics. Thanks Laurent for making my journey in ENS-Paris-Saclay as easy as ever.

Besides, I would like to acknowledge my co-advisor Luca Greco, whose discussions and explanations have been invaluable in shaping the direction of my research. I would also like to extend my appreciation to my (non-official) co-advisor Paolo Mason. Working with Paolo takes another level of enthusiasm. He helped boost and deepen my critical thinking.

I convey my gratitude to the members of my jury for their careful reading and constructive feedback on my work. Their thoughtful input and expertise have greatly enriched the quality of this work. In particular, I want to express my sincere gratitude to Prof. Raphaël Jungers and Prof. Jamal Daafouz for their profound reading and invaluable comments on my manuscript. I am also profoundly thankful for your contributions in control theory field. In addition, I am truly grateful to Elena Panteley, Aneel Tanwani and Carolina Albea Sanchez for their interesting questions and remarks.

I would also like to (re)thank Prof. Raphaël Jungers for an exceptional opportunity to visit his team and give a seminar at the UCLouvain in October 2022. During my five-day stay, I enjoyed many interesting discussions on the joint spectral radius and control theory topics with amazing people. Adrien, Matteo, Virginie... it was an incredibly enriching experience to share the same wavelength with you! Let me also thank Sami Tliba for granting me the chance to teach. Teaching at Université Paris-Saclay was a great experience I will never forget. I'm also grateful to Sami for deep conversations, awakening, and boosting my curiosity in major life fields! My journey at the ENS and the LMF was truly unique, thanks to all my colleagues with whom I shared unforgettable moments: Thomas, Fatemeh, Dietmar, Amrita, Gayathri, Andrei, Houda, Eugénie, Marie-France, Tiphanie, Rebecca, Anas, Charles... Special thanks to Thomas Chevet for the everlasting discussions in the control theory (and life) field. I am grateful for the financial support provided by Université Paris-Saclay. This support has enabled me to focus on my research and has been crucial to the successful completion of this thesis.

I should not forget the influence of my initial university, the Lebanese university, on the limitless knowledge that had aroused me besides the network I formed there. As the proverb wisely states, "He who has no past has no present." I'm very grateful to the professors and staff I encountered there.

I owe a debt of gratitude not only to my colleagues at work but also to numerous friends and people beyond my academic sphere. Their immense support and encouragement were vital wellspring of mo- -ln(λ) : top -switching signal θ; center -discrete state of the switched observer q, red circles indicate return instants; bottom -norm of the estimation error e in logarithmic scale for both type of gains. . . . . . . . . . . . . . . . . . . . . . . 5.3 Simulations for the case γ θ < ln(ρ)

List of Figures

-ln(λ) : top -switching signal θ; center -discrete state of the switched observer q, red circles indicate return instants; bottom -norm of the estimation error e in logarithmic scale for both type of gains. . . . . . . . . . . . . . . . . . . . . . . 5.4 Multicellular converter with an inductive load. . . . . . . . . . . . 5.5 Adjacency relations between modes describing the constraints on the switching signal θ. When a mode change occurs in the switching signal θ, the new mode must be adjacent to the previous one. . . 5.6 DBA B3 that generates switching sequences satisfying the adjacency constraints shown in Figure 5. 5 the set of all finite words over the alphabet Σ exempted from the empty word ϵ Σ ω the set of all infinite words over the alphabet Σ ker(M ) the kernel of a matrix M rank(M ) the rank of a matrix M M -⊤ the transpose of the inverse of an invertible matrix M i.e.

M -⊤ = (M -1 ) ⊤ diag(v)
the n × n diagonal matrix whose diagonal elements are equal to a vector

v ∈ R n M 1 ≤ M 2 M 2 -M 1 being positive semi-definite for symmetric matrices M 1 , M 2 M 1 < M 2 M 2 -M 1 being positive definite for symmetric matrices M 1 , M 2 K
the set of continuous, strictly increasing functions λ :

R + 0 → R + 0 satisfying λ(0) = 0 K ∞
the set of continuous, strictly increasing functions λ :

R + 0 → R + 0 satisfying λ(0) = 0 and lim r→∞ λ(r) = ∞ iii iv Notations 1 -Introduction 1.1 .

Stability of switched systems

Background Switched dynamical systems have been a wide domain of research for several decades. In the recent years, they have earned significant attention across diverse fields such as engineering or mathematics. Switched systems involve dynamic transitions between different modes of operation where each mode is described by a differential (continuous-time) or difference (discrete-time) equation. At each instant, the so-called switching signal dictates the active mode or subsystem. Their applications span various domains, including control theory, robotics, biology... Especially, a broad domain in control theory is that of cyber-physical systems, where switched systems can be used to describe faithfully the interaction between the physical dynamics and the cyber components such as shared computing resources and communication networks (see e.g. [START_REF] Donkers | Stability analysis of networked control systems using a switched linear systems approach[END_REF]8,[START_REF] Majumdar | Performance-aware scheduler synthesis for control systems[END_REF]).

Arbitrary switching signals

Several works focused on understanding the behavior of switched systems. Originally these works were interested in stability for switching signals that are arbitrary i.e. no constraints are imposed on the switching signal [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF][START_REF] Theys | Joint spectral radius : theory and approximations[END_REF]. For the class of discrete-time switched linear systems with arbitrary switching signals, a powerful notion for analyzing stability is that of Joint Spectral Radius (JSR) which was introduced by Rota and Strang in the 60s, [START_REF] Rota | A note on the joint spectral radius[END_REF]. This quantity characterizes the maximal exponential growth rate considering all possible switching sequences. The JSR encompasses several applications in control theory, especially those related to synchronization phenomena in networked systems. In fact, by characterizing the JSR of interconnected nodes, one can identify optimal network topologies that enhance synchronization [START_REF] Kozyakin | Consensus in asynchronous multiagent systems. ii. method of joint spectral radius[END_REF][START_REF] Crespi | The theory of trackability with applications to sensor networks[END_REF]. Another intriguing application of the JSR is that of continuity of wavelets [START_REF] Heil | Continuity Of The Joint Spectral Radius: Application To Wavelets[END_REF][START_REF] Daubechies | Ten Lectures on Wavelets[END_REF]. However, computing the JSR is, in general, a difficult task [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF]. In particular, it is shown that the joint spectral radius of a pair of matrices is not polynomial-time approximable (see Tsitsiklis and Blondel, [START_REF] John | The Lyapunov exponent and joint spectral radius of pairs of matrices are hard -when not impossible -to compute and to approximate[END_REF]). Several methods have been proposed to compute tight lower and upper bounds [START_REF] Gripenberg | Computing the joint spectral radius[END_REF][START_REF] Vankeerberghen | JSR: A toolbox to compute the joint spectral radius[END_REF]. Also, it is shown that the JSR can be approximated with arbitrary high accuracy [START_REF] Vincent | Computationally efficient approximations of the joint spectral radius[END_REF].

CHAPTER 1. INTRODUCTION

Constrained switching signals

Another notion that arises in this context is that of constrained systems, these systems are no longer driven by arbitrary switching signals, instead they are subject to constraints. These constraints might be given in terms of logic formulas on the switching signals such as fairness constraints [START_REF] Belta | Formal Methods for Discrete-Time Dynamical Systems[END_REF], or some dwelltime constraints [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF][START_REF] Liberzon | Switching in systems and control[END_REF]. In a dwell-time constrained system, the switching signal cannot leave some modes before some duration has elapsed. Moreover, these constraints can be given in terms of a finite state automaton, where the switching signal must describe a path on the automaton [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF][START_REF] Lothaire | Finite and Infinite Words[END_REF]. In the latter case, several methods for handling such constraints through Lyapunov functions have been presented in several works [START_REF] Lee | Uniformly stabilizing sets of switching sequences for switched linear systems[END_REF][START_REF] Victor Kozyakin | The Berger-Wang formula for the Markovian joint spectral radius[END_REF][START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF][START_REF] Pepe | Converse Lyapunov theorems for discrete-time switching systems with given switches digraphs[END_REF][START_REF] Athanasopoulos | Stability analysis of switched linear systems defined by graphs[END_REF]. An alternative approach to analyze stability with such constrained switching signals is by computing the so-called constrained joint spectral radius introduced in 2012 [START_REF] Dai | A Gel'fand-type spectral radius formula and stability of linear constrained switching systems[END_REF][START_REF] Victor Kozyakin | The Berger-Wang formula for the Markovian joint spectral radius[END_REF][START_REF] Xu | Approximation of the constrained joint spectral radius via algebraic lifting[END_REF]. In our work, we will focus on 2 classes of constrained switched systems, the shuffled switched systems and those driven by ω-regular languages.

Shuffled switching signals

There are classes of constrained switching signals that cannot be described using classical finite-state automata, in particular that of the shuffled switching signals. A switching signal is said to be shuffled if each mode of the switched system is activated an infinite number of times. A shuffled switching signal can be seen as an arbitrary switching signal satisfying some fairness properties. Intuitively, a fairness property here imposes that no mode is prioritized on the others i.e. every mode gets activated infinitely often. It is known from formal language theory (see the book of Baier and Katoen, [START_REF] Baier | Principles of model checking[END_REF]) that the set of shuffled switching signals, cannot be characterized using classical finite state automata. To the best of our knowledge, the term 'shuffle' was introduced first at 90s in [START_REF] Gurvits | Stability of discrete linear inclusion[END_REF] and it has first been studied in [START_REF] Vs Kozyakin | Algebraic unsolvability of problem of absolute stability of desynchronized systems[END_REF] where it is proved that the set of stable shuffled switched linear systems is not semi-algebraic. However, no further characterization of shuffled stability is provided in that paper. A necessary and sufficient condition can be found in [START_REF] Gurvits | Stability of discrete linear inclusion[END_REF] in terms of the maximal spectral radius of an infinite set of matrices. However, its computation is non-trivial and not discussed in that paper, which therefore does not provide any practical way to check shuffled stability. In [START_REF] Wang | Stability analysis of switched linear systems defined by regular languages[END_REF], it is shown that a notion of robust shuffled stability is equivalent to stability for arbitrary switching signals. In [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF], a Lyapunov characterization of shuffled stability and a converse Lyapunov result have been established.

Stability analysis of shuffled switched systems is also interesting from the point of view of applications. An example of such applications is multi-agent consensus with switching communication topologies. Consider a symmetric and connected communication graph where only one edge is active at each time instant and is selected by a switching signal. If one uses a shuffled switching signal, then each edge is activated infinitely often so that the union of future communication graphs is connected at all time, and it is well-known (see e.g. [START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF][START_REF] Vincent D Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF]) that the consensus is asymptotically reached. On the contrary, if some edges are never activated the union of future communication graphs may be disconnected and the consensus is not attainable. Another potential application is the design of observers for switched systems where the dynamics in each mode is unobservable. Clearly, the dynamics of the estimation error cannot be stable for arbitrary switching signals, since keeping the same mode activated all the time makes the system unobservable (see e.g. [START_REF] Sun | Switched linear systems: control and design[END_REF]). However, considering shuffled switching signals, it may be possible to design asymptotically convergent observers [START_REF] Tanwani | Observability for switched linear systems: characterization and observer design[END_REF]. This type of observer design problems is natural when considering a system with distributed sensors communication over a shared network. More generally, shuffled switching signals are of interest to describe applications where multiple components rely on a shared resource and where the access to this resource must be granted to each of the component infinitely often.

ω-regular language constrained signals The shuffled signals described before, provide an example of an ω-regular language which can always be characterized using Büchi automata [START_REF] Baier | Principles of model checking[END_REF]. A Büchi automaton is a finite state automaton where some particular statescalled accepting states -must be visited infinitely often.

In scheduling algorithms or communication protocols, ω-regular languages are frequently used to specify some properties. For instance, these languages can describe fairness constraints through Linear Temporal Logic (LTL) specifications. These LTL specifications can be always characterized by Büchi automata [START_REF] Vardi | An automata-theoretic approach to automatic program verification[END_REF], [START_REF] Vardi | Reasoning about infinite computations[END_REF]. Moreover, efficient methods for this construction are given in [START_REF] Gastin | Fast ltl to büchi automata translation[END_REF] and [START_REF] Babiak | LTL to büchi automata translation: Fast and more deterministic[END_REF]. Therefore, it is of interest for some cyber-physical systems applications -where multiple components must be granted access to a shared resource infinitely often -to analyze the stability of switched systems driven by switching signals belonging to a given ω-regular language [START_REF] Tabuada | Linear time logic control of discretetime linear systems[END_REF][START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF].

Moreover, a practical application of systems driven by ω-regular languages is consensus/synchronization over time-varying (undirected) graphs, which can be seen as a switched system. It is well known (see e.g. [START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF][START_REF] Vincent D Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF]) that consensus/synchronization can be reached if and only if, at every time instant, the union of future interaction graphs is connected. This connectivity condition cannot be described using finite state automata as in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF] but can be specified using Büchi automata as it will be shown in an example later.

The stability analysis of discrete-time switched linear systems constrained by ω-regular languages have already been considered in the literature in [START_REF] Wang | Stability analysis of switched linear systems defined by regular languages[END_REF] where it is shown that the stability is equivalent to the stability of a lifted system driven by shuffled switching signals. However, this result relies on a transformation and cannot be used directly on the original state-space. A main contribution of this thesis is to have a dedicated stability analysis of such ω-regular language driven systems.

. An illustrating example

Let us consider a discrete-time switched system of the following form:

x(t + 1) = A θ(t) x(t), t ∈ N where A 1 = 2 0 0 1 2 and A 2 = 1 5 0 0 1 and θ : N → {1, 2} is a switching signal.
In the case of arbitrary switching signals, it is easy to see that the system is unstable. Indeed if we keep activating the mode 1 the trajectories will diverge. However, let us constrain the switching signal such that we cannot have a consecutive repetition on mode 1. This can be represented in the second automaton in Figure 1.1. In this case, the worst switching case is when mode 2 is always activated and the system is marginally stable, that is, we have no divergence and some trajectories do not converge to zero. Yet if we consider now that the state "a" on the last automaton has to be visited infinitely often, then we get that the system is stable for any such constrained switching signal. Indeed, the matrix

A 1 A n 2 is stable for any n ≥ 1. a a b a b 1,2 2 1 2 2 2 1 Figure 1.1:
The automaton at the left corresponds to arbitrary switching, the middle excludes the occurrence of -11-and in the last automaton the state "a" should be visited infinitely often.

In this example, we have dealt with a system that is unstable for arbitrary switching, marginally stable for a switching signal generated by a finite state

CONTRIBUTIONS

automaton and stable for a switching signals generated by a Büchi automaton. A main goal of this thesis is to have a dedicated stability study for such constrained systems.

. Contributions

In this thesis, we provide a new tool to analyze shuffled stability of discretetime switched linear systems. We also give sufficient and necessary stability conditions for systems driven by ω-regular languages generated by Büchi automata. Moreover, from the latter we present an approach for designing asymptotic observers for discrete-time switched linear systems.

The ρ-SJSR

We begin Chapter 3 by introducing the shuffled joint spectral radius (SJSR), which intuitively measures how much the state of the system contracts each time the signal shuffles (i.e. each time all modes have been activated). We establish several properties of the SJSR and show how it relates to stability properties of switched systems driven by shuffled switching signals (Theorem 3.2.1). In particular, we show that some switched systems that are unstable for arbitrary switching signals can be stabilized by using switching signals that shuffle sufficiently fast, the minimal shuffling rate being related to both the JSR and the SJSR (Corollary 3.3.1). We also present two approaches to compute approximation of the SJSR. The first approach is based on the JSR of a finite set of matrices and allows us to compute asymptotically tight lower and upper bounds (Section 3.4.1). The second approach is based on Lyapunov functions and automata theoretic techniques and allows us to compute upper bounds (Sections 3.4.2, 3.4.3).

The ω-regular stability

In Chapter 4 we deal with the stability of a discrete-time switched linear systems whose switching signals are generated by a given Büchi automaton. We establish sufficient stability conditions using Lyapunov functions (Theorem 4.2.2). For a particular class of such systems with invertible matrices, we show that these conditions are also necessary with a converse Lyapunov result (Theorem 4.2.10). Furthermore, we generalize most of the results of Chapter 3 to the case when the switching signal is generated through Büchi automata. For instance, we introduce the ω-Regular Joint Spectral Radius (ω-RJSR). Intuitively, this quantity measures how much the system contracts each time some accepting states on the automaton are visited. We also relate the ω-RJSR with the stability of switched systems driven by a given Büchi automaton (Theorem 4.3.7). Moreover, we show how this quantity can lead us to characterize a class of stabilizing switching signals (Corollary 4.3.8). We also present a Lyapunov-based method for computing upper bounds ω-RJSR.

An observer design

Finally, we propose a switched observer based on the reconstructible sets i.e. switching sequences allowing to asymptotically estimate the state of the system. These observers have an internal discrete state variable whose dynamics are given by the transition map of a Büchi automaton. The latter is calculated through a dedicated algorithm. We present two approaches to design observer gains where the observer is convergent for all switching signals whose occurrence rate of reconstructible sequences is higher than a tunable threshold. The first approach gives an explicit construction of the observer gains while the second one is based on linear matrix inequalities (Proposition 5.3.10). For switched systems with invertible state matrices, we show that the proposed observer structure is universal in the sense that it is always possible to design an observer of the proposed form (Theorem 5.3.9). We use a simple example to illustrate our methodology and then consider a case study in which we design an observer for a multicellular converter. 2 -A review of some results on switched systems

Book chapters

. Joint spectral radius

The joint spectral radius of a set of matrices, is a generalization of the notion of the spectral radius of a matrix. It characterizes the maximal asymptotic growth rate of products of matrices taken in a set A. The formal definition of the joint spectral radius was first introduced in the 60s (see [START_REF] Rota | A note on the joint spectral radius[END_REF]). Since then, this notion has received a lot of interest, it appears in several contexts and has many applications. In this section, we introduce the main ingredients that we will be using to introduce our results. The preliminary theorems are presented without proofs and can be found in [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF], [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF] and the references therein.

. Definition

We consider a set A of matrices A i ∈ R n×n :

A = {A i : i ∈ I},
where I = {1, • • • , m} is the set of indices. The spectral radius of a matrix A ∈ R n×n is defined by:

ρ(A) = lim k→∞ ∥A k ∥ 1/k . (2.1)
To define the joint spectral radius (JSR for short), we must first introduce the quantity:

ρ k (A, ∥.∥) = sup k i=1 M i : M i ∈ A for 1 ≤ i ≤ k , (2.2)
where

k i=1 M i = M k • • • M 1 , ∥.
∥ here is any submultiplicative matrix norm, and ρ k (A) represents the largest possible norm of all products of k matrices taken in the set A. The defined quantity relates to the JSR by the following relation:

ρ(A, ∥.∥) = lim sup k→∞ (ρ k (A, ∥.∥)) 1/k . (2.3)
Thus, the JSR is the maximal asymptotic norm of the products of matrices that can be constructed and taken in the set A, the 1/k exponent can be seen as a normalization factor and allows for the JSR to be interpreted as a growth rate of the norm. From the equivalence of norms in R n , one can show that the JSR is independent from the norm, and from now on we shall replace ρ(A, ∥.∥) by ρ(A).

10

CHAPTER 2. SOME RESULTS ON SWITCHED SYSTEMS 2.1.2 . Properties

Convergence

The sequence (a k ) k≥1 defined by a k = ρ k (A, ∥.∥) 1/k converges and

ρ(A) = lim sup k→∞ a k = lim k→∞ a k = inf{a k |k ≥ 1}. (2.4)
The proof uses the Fekete's Lemma and can be found in [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF]. From now on, we can use a simple limit instead of the lim sup used in the definition of the JSR.

Scalar multiplication

Multiplying all the matrices of A by a real scalar α, also multiplies the JSR in the same way:

∀α ∈ R, ρ(αA) = |α|ρ(A), (2.5)
this is obtained easily from the relation ∥αA∥ = |α|∥A∥.

. Stability of switched systems and JSR

We consider a discrete-time switched system of the following form:

x(t + 1) = A θ(t) x(t), t ∈ N (2.6)
where x : N → R n is the trajectory and θ : N → I is the switching signal. I = {1, . . . , m}, with m ≥ 2, is the finite set of modes and A = {A i ∈ R n×n |i ∈ I} is a set of matrices. Let S(I) be the set of all arbitrary (non-constrained) switching signals taking values in I. Given an initial state x 0 ∈ R n , and a switching signal θ ∈ S(I), the trajectory defined by (2.6) with x(0) = x 0 is unique and denoted by x(., x 0 , θ). Before proceeding further, let us give some stability definitions.

Definition 2.1.1. The discrete-time switched system described by (2.6) is said to be globally uniformly stable (GUS) if the exists some C ≥ 0 such that for any initial condition x 0 ∈ R n and for any switching signal θ ∈ S(I), ∥x(t, x 0 , θ)∥ ≤ C∥x 0 ∥. This definition does not tell about the convergence of the trajectories, instead, it gives a uniform upper bound on the norm of the trajectories. The next definition is about the convergence of the trajectories to zero. Definition 2.1.2. The discrete-time switched system described by (2.6) is said to be globally attractive (GA) if for any initial condition x 0 ∈ R n and for any switching signal θ ∈ S(I), lim t→∞ ∥x(t, x 0 , θ)∥ = 0. Moreover, discrete-time switched system described by (2.6) is said to be the globally uniformly asymptotically stable GUAS if it is GA and GUS. It is worthwhile to note that if a linear discrete-time switched system is GA then it is GUAS [START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF].

We should stress on the relation between the joint spectral radius of a set of matrices and the stability of the associated switched dynamical system as detailed by the following theorem: Theorem 2.1.3. [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF] For any finite set of matrices A, the corresponding discretetime switched system with arbitrary switching is GUAS, if and only if ρ(A) < 1.

Consequently, this theorem shows in simple words that in order to check the stability of an arbitrary switched system one should verify that its JSR is strictly less than 1. However, the computation of the JSR is proven to be hard in the general case, but effective methods are proposed to approximate it. In fact, it is shown that unless P=NP, the joint spectral radius of a pair of matrices is not polynomial-time approximable. Moreover, given a finite set A of n × n matrices where their entries are rational then it is undecidable to determine if ρ(A) ≤ 1 (see [START_REF] John | The Lyapunov exponent and joint spectral radius of pairs of matrices are hard -when not impossible -to compute and to approximate[END_REF][START_REF] Gripenberg | Computing the joint spectral radius[END_REF][START_REF] Vincent | Computationally efficient approximations of the joint spectral radius[END_REF][START_REF] Parrilo | Approximation of the joint spectral radius using sum of squares[END_REF][START_REF] Vankeerberghen | JSR: A toolbox to compute the joint spectral radius[END_REF]).

Remark 2.1.4. For a GUS discrete-time switched system, the corresponding set of state matrices A, satisfies ρ(A) ≤ 1. However, the converse is not true in general.

Remark 2.1.5. A similar and more general theorem is given in the case of constrained switching signal where the constraints are described by a finite state automaton, see section 2.1.4.

Moreover, since the JSR plays a crucial role in the stability of a switched dynamical system and following the definition of the JSR, it is easy to build an inequality between the latter quantity and the trajectories of a dynamical system, as shown in the following theorem [17, Theorem 1]: Theorem 2.1.6. For all ρ > ρ(A), there exists C > 0 such that:

∀θ ∈ S(I), ∀x 0 ∈ R n , ∀t ∈ N, ∥x(t, x 0 , θ)∥ ≤ Cρ t ∥x 0 ∥.
(2.7)

Conversely, if there exists C ≥ 0 such that (2.7) holds then ρ ≥ ρ(A).

CHAPTER 2. SOME RESULTS ON SWITCHED SYSTEMS

Additionally, besides the JSR, there is another interesting notion to study and analyze the stability of a dynamical system, the Lyapunov function. A Lyapunov function is a positive definite function, which we will denote by V that is usually state-dependent and is non-increasing along the trajectories. Moreover, the deal is if one can find such a function V , we get that our system is GUS. However, usually the search for such functions is not always easy and challenging in some cases. Also, we should point out that this function may not only depend on the state variable x, additionally, it may depend on a second variable taking values in a finite set, for instance, it may depend on the set of modes I also. In the latter case we refer to the multiple Lyapunov functions which will be detailed later [START_REF] Branicky | Multiple lyapunov functions and other analysis tools for switched and hybrid systems[END_REF][START_REF] Daafouz | Stability analysis and control synthesis for switched systems: a switched lyapunov function approach[END_REF][START_REF] Bliman | Stability analysis of discrete-time switched systems through lyapunov functions with nonminimal state[END_REF]. Now let us restrain ourself to the case of the state-dependent Lyapunov function, and let us consider the function V : R n → R + . We say that V is a Lyapunov function if it satisfies the following conditions for some α, β > 0, for all x ∈ R n and every solution x(•) of (2.6):

α∥x∥ ≤ V (x) ≤ β∥x∥, V (x(t + 1)) ≤ V (x(t)), t ≥ 0
Now let us consider the class of quadratic Lyapunov function of the form V (x) =

√

x T P x where P ∈ R n×n is a positive definite matrix. In the context of discrete-time switched systems, the above conditions can be translated to the following:

α∥x∥ ≤ V (x) ≤ β∥x∥, (2.8)
V (A i x) ≤ V (x). ∀x ∈ R n , i ∈ I (2.9)
Now since V (x) = √ x T P x, we get a system of linear matrix inequalities (LMIs):

α 2 I n ≤ P ≤ β 2 I n ,
(2.10)

A T i P A i ≤ P, ∀i ∈ I. (2.11)
Therefore, we get a sufficient condition for stability based on an optimization problem which can be solved efficiently thanks to its convexity. These conditions are given by the following theorem without proof: Theorem 2.1.7. [START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF] If the LMIs (2.10) and (2.11) are feasible, then the corresponding discrete-time switched linear system is GUS. Conversely, if the discretetime switched linear system is GUS then there exists a (not necessarily quadratic) function V satisfying the inequalities (2.8) and (2.9).

Moreover, if we consider the set

A γ = { 1 γ A 1 , • • • , 1 γ A m } = 1
γ A for some positive scalar γ, if we prove that the discrete-time switched system described by (2.6) is GUS, then we get γ as an upper bound on ρ(A). In particular, in the case of quadratic Lyapunov function, if one can find a positive definite matrix P such that:

P > 0, A T i P A i ≤ γ 2 P, ∀i ∈ I.
Then ρ(A) ≤ γ. Also, the previous inequalities suggest to define ρ e (A), the ellipsoid norm approximation of the joint spectral radius of the set A [START_REF] Vincent D Blondel | On the accuracy of the ellipsoid norm approximation of the joint spectral radius[END_REF]:

ρ e (A) = inf ρ ≥ 0 ∃M > 0, M ⊤ = M, ∀A i ∈ A; A ⊤ i M A i ≤ ρ 2 M . (2.12)
This quantity characterizes the sets A such that the corresponding switched system admits a quadratic Lyapunov function and will be useful in Chapter 5.

. Constrained joint spectral radius

In the previous sections we dealt with the case of an arbitrary switching signal, however in some applications we can encounter some constraints on the switching signal. Usually these constraints can be described by a labeled graph or described by LTL formulas or belonging to some ω-regular language. In this section we focus on the case when the switching signal is generated by a labeled graph. A labeled graph, is a tuple G = (V, L, E) where V is a set of nodes, L is a set of labels, E ⊆ V × L × V is a set of edges or transitions. For an edge e = (v, l, v ′ ) ∈ E, the node v ∈ V is the origin, l ∈ L is the label, v ′ ∈ V is the end. A path in the labeled graph G is a set of consecutive edges (v 0 , l 1 , v 1 ), (v 1 , l 2 , v 2 ) • • • , where v i ∈ V for all i = 0, 1, • • • its label is the word w = l 1 l 2 • • • , in this case we say that w is accepted by G.

Remark 2.1.8. Throughout the thesis we will use the terms finite state automaton and labeled graph interchangeably.

Given a finite set of matrices

A = {A 1 , • • • , A m }
and a labeled graph G, we form a constrained system (A, G), where L = I = {1, • • • , m} i.e. the labels of G corresponds to the modes of the system. Thus the switching logic is constrained by the graph G in the sense that the switching signal must describe a path in the graph. Let us denote by Θ G the set of switching sequences θ such that θ(0)θ(1) • • • is accepted by G.

In the following example, taking I = {1, 2} we have 2 labeled graphs, the first one corresponds to arbitrary switching and the second one corresponds to the case of constrained switching where the repetition of the second mode is forbidden i.e. no -22-in the switching signal. Similar to the JSR, a notion of stability measure for such systems called the Constrained Joint Spectral Radius (CJSR) is defined as follows [START_REF] Dai | A Gel'fand-type spectral radius formula and stability of linear constrained switching systems[END_REF]. Given a constrained system (A, G), the CJSR of (A, G) denoted by ρ(A, G) is defined as follows:

ρ(A, G) = lim k→+∞ max    k i=1 A θ(i) 1 k : θ ∈ Θ G    .
(2.13)

This quantity can be seen as a generalization of the JSR for the context of constrained systems. In particular, if we consider G to be the automaton corresponding to arbitrary switching in Figure 2.1, then Equation (2.13) will coincide with the JSR equation (2.3). Moreover, Theorem 2.1.3 and equation (2.7) can be adapted to the case of the CJSR [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF].

Furthermore, the stability of such systems can be also studied by means of the multiple Lyapunov functions or the multinorms [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF].

. Shuffled switched systems

As already mentioned, families of constrained switching signals are not always described by finite state automaton. Shuffled switching signals represent an example of switching signals which cannot be characterized by such automata. The goal of this section is to provide a state of the art on the stability of shuffled systems. Firstly, a formal definition of the shuffled switching signal is introduced.

SHUFFLED SWITCHED SYSTEMS

Secondly, some stability definitions are given and lastly a characterization of stability using the Lyapunov functions is shown. All these definitions and results are given without proof from [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF].

. Shuffled switching signal

We start by giving a formal definition of the shuffling switching signal. We also present some notions and properties related to such signals.

Definition 2.2.1. A switching signal θ : N → I is shuffled if: ∀i ∈ I, ∀T ∈ N, ∃t ≥ T : θ(t) = i.
(2.14)

The sequence of shuffling instants (τ θ k ) k∈N is defined by τ θ 0 = 0 and for all k ∈ N:

τ θ k+1 = min t > τ θ k ∀i ∈ I, ∃s ∈ N : τ θ k ≤ s < t and θ(s) = i . (2.15)
The shuffling index is given by:

κ θ (t) = max{k ∈ N|τ θ k ≤ t}. (2.16)
The shuffling rate γ θ ∈ R + 0 is defined by

γ θ = lim inf t→+∞ κ θ (t) t .
(2.17)

Intuitively, between the instants τ θ k and τ θ k+1 -1, each mode in I is activated at least once. For a shuffled switching signal, the sequence of shuffling instants is well-defined, strictly increasing and thus goes to +∞. Similarly, the shuffling index is well-defined, non-decreasing and goes to +∞, it essentially counts the number of times the switching signal has shuffled between 0 and t. An illustration of these concepts is shown in Figure 2.2.

It is easy to remark that for all t ∈ N, 0 ≤ κ θ (t) ≤ t m . Then, it follows that the shuffling rate satisfies

γ θ ∈ [0, 1 m ].

. Shuffled stability analysis

We begin this section by introducing two crucial notions of stability in this context, then we introduce the shuffle Lyapunov function and we relate its existence with the stability of shuffled systems. Definition 2.2.2. Switched system (2.6) is said to be: CHAPTER 2. SOME RESULTS ON SWITCHED SYSTEMS

τ θ 0 τ θ 1 τ θ 2 t t θ(t) κ θ (t) τ θ 3 Figure 2.2:
A switching signal (with m = 2) and the associated shuffling instants and index. [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF] Globally shuffle attractive (GSA) if for all x 0 ∈ R n and for all shuffled switching signals θ:

lim t→∞ ∥x(t, x 0 , θ)∥ = 0. (2.

18)

Globally uniformly shuffle asymptotically stable (GUSAS) if there exists a KL function β such that for all x 0 ∈ R n , for all shuffled switching signals θ:

∥x(t, x 0 , θ)∥ ≤ β(∥x 0 ∥, κ θ (t)), ∀t ∈ R n . (2.19)
It is clear that if a system is GUSAS then it is GSA. Now let us give the definition of the shuffle Lyapunov function.

Definition 2.2.3. A function V : I × R n → R + 0 is called a shuffle Lyapunov function if there exists K ∞ functions α 1 , α 2 ,
and a K function λ with λ(r) < r for all r > 0, such that for all x ∈ R n , the following hold:

α 1 ∥x∥ ≤ V (i, x) ≤ α 2 ∥x∥, i ∈ I (2.20) V (i, A i ′ x) ≤ V (i, x), i, i ′ ∈ I, i ̸ = i ′ (2.21) V (i + 1, A i x) ≤ V (i, x), i ∈ I \ {m} (2.22) V (1, A m x) ≤ λ(V (m, x)). (2.23)
The shuffled Lyapunov function relates to the stability of such systems by the following theorem : Theorem 2.2.4. [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF] If there exists a shuffle Lyapunov function, then the switched system (2.6) is GUSAS. Conversely, if A consists of only invertible matrices and if the system is GSA, then there exists a Lyapunov function satisfying the above equations.

To give an intuition for the sufficiency part of the previous theorem, let us consider the automaton in Figure 2.3 and a switching sequence θ with 3 modes. The labels of the automaton correspond to the values taken by θ at each instant. It is clear that if the state 1 is visited infinitely often, then the switching signal is shuffled, that is all the 3 modes are activated infinitely often. Moreover, according to the inequalities (2.21), (2.22) and (2.23) the Lyapunov function V (x(t)) is non-increasing as time evolves and therefore the trajectories are bounded. Furthermore, since the state 1 is visited infinitely often, we get that (2.23) will be activated infinitely often, thus leading to the decrease of the trajectories to zero.

From the previous theorem, we deduce that the 2 defined notions of shuffled stability are equivalent when A consists of invertible matrices.

. Conclusion

In this section, a quantitative method for analyzing the stability of discretetime switched systems with arbitrary switching was shown, the joint spectral radius. Also, for systems with constrained switching, where the constraint is described by a finite state automaton, a similar approach was given: the constrained joint spectral radius. It was shown in Theorem 2.1.3 that the condition ρ(A) < 1

1 2 3 1 2 3 2, 3 1, 3 1, 2

CHAPTER 2. SOME RESULTS ON SWITCHED SYSTEMS

is a necessary and sufficient condition for stability. However, these methods fail to characterize the stability of shuffled switched systems. For that sake, another method is detailed in the previous subsection: the shuffle Lyapunov functions. Indeed, the existence of these functions guarantees the stability of the shuffled switched system. Yet, these functions do not allow us to estimate accurately the convergence rate of these systems. Thus it is important to define a joint spectral radius related to shuffled switched systems that allow us to quantify the rate of convergence of the switched system in a shuffling context. In the next chapter, we will define this notion, investigate its properties and develop algorithms for its approximation.

-Shuffled joint spectral radius

In this chapter, a new notion of joint spectral radius dedicated to shuffled switched systems is introduced. Intuitively, it measures how much the state of the system contracts each time the signal shuffles (i.e. each time all modes have been activated). Several of its properties are also established. Moreover, it is shown how it relates to stability properties of switched systems driven by shuffled switching signals (Theorem 3.2.1). In particular, it is shown that some switched systems that are unstable for arbitrary switching signals can be stabilized by using switching signals that shuffle sufficiently fast, the minimal shuffling rate being related to both the JSR and the SJSR (Corollary 3.3.1). Two approaches to compute approximations of the SJSR are also presented. The first approach is based on the JSR of a finite set of matrices and allows us to compute asymptotically tight lower and upper bounds. The second approach is based on Lyapunov functions and automata theoretic techniques and allows us to compute upper bounds. Finally, numerical examples are given to validate the approach.

This chapter represents the results of the following paper:

Georges Aazan, Antoine Girard, Luca Greco, and Paolo Mason. Stability of shuffled switched linear systems: A joint spectral radius approach. Automatica, 143:110434, 2022.

The organization of this chapter is as follows. In Section 3.1, the SJSR is introduced and several of its properties are established. Section 3.2 shows the relationship between the SJSR and stability properties of a switched system driven by shuffled switching signals. Section 3.3 shows some sufficient conditions for stabilization under shuffled switching. In Section 3.4, two approaches to compute approximations of the SJSR are presented. Finally, two numerical examples are used in Section 3.5 to illustrate the main results of the section.

. Definitions and properties

Before we give the definition of the shuffled joint spectral radius (SJSR), let us introduce some notations and notions. Let S(I) and S s (I) be the sets of arbitrary switching signals and of shuffled switching signals respectively. We will be using the same notations of the previous section (see Definition 2.

A θ,τ θ k ρ τ θ k 1/k   , (3.1)
where

A θ,t = t-1 i=0 A θ(i) = A θ(t-1) × • • • × A θ(0) .
In order to investigate the properties of the ρ-SJSR, let us analyze some properties of the function λ(A, •). We begin by showing a crucial observation that relates the new defined quantity with the JSR, in fact the ρ-SJSR of A can be seen as the JSR of an infinite but bounded set of matrices. Indeed, for ρ > ρ(A), let us consider the following set of matrices:

M ρ =    1 ρ N N k=1 A j k , j 1 , . . . , j N ∈ I, N ∈ N, ∀i ∈ I, ∃k, j k = i, and ∀k ̸ = N, j k ̸ = j N    .
Although that M ρ generally has an infinite number of elements, this set is bounded. In the following, we deal with the joint spectral radius of an infinite but bounded set of matrices. Although we have defined the JSR only for finite sets, the results still hold for the bounded case [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF]. The latter property is shown in the following Lemma. Lemma 3.1.2. For all ρ > ρ(A), M ρ is a bounded set of matrices.

Proof. Let ρ > ρ(A), then ρ( 1 ρ A) = ρ(A) ρ < 1. Thus, from [17, Theorem 1 (b)], we deduce that 1
ρ A is a left convergent product (following the terminology in [START_REF] Marc | Bounded semigroups of matrices[END_REF]). Since the elements of M ρ are products of matrices belonging to the set 1 ρ A, it follows from [17, Theorem 1 (a)] that M ρ is a bounded set of matrices.

Thanks to the boundedness of the set M ρ , its JSR is well defined. Furthermore, in any matrix of M ρ , all modes in I appear at least once with the last mode j N appearing only once. Consequently, the set M ρ matches with the set of all possible matrices 1

ρ τ θ 1 A θ,τ θ 1 for θ ∈ S s (I).
Now we are ready to introduce the following lemma that expresses our observation more formally.

Lemma 3.1.3. For all ρ > ρ(A), λ(A, ρ) = ρ(M ρ ).

DEFINITIONS AND PROPERTIES 21

Proof. Let ρ > ρ(A) and k ∈ N with k ≥ 1, observe that for every θ ∈ S s (I) the sequence (θ j ) j∈N of switching signals in S s (I) defined by θ j (t) = θ(t + τ θ j ) for t, j ∈ N is such that

A θ,τ θ k = k-1 j=0 A θ j ,τ θ j 1 and τ θ k = k-1 j=0 τ θ j 1 . (3.2)
On the other hand, given a sequence (θ j ) j∈N in S s (I) one can construct a switching signal θ ∈ S s (I) such that

τ θ i = i-1 j=0 τ θ j 1 for i ≥ 1 and θ(t) = θ i (t -τ θ i ) for τ θ i ≤ t < τ θ i+1 , so that (3.
2) holds true. Then, it follows that sup θ∈Ss(I)

A θ,τ θ k ρ τ θ k 1/k = sup θ 0 ,...,θ k-1 ∈Ss(I)    k-1 j=0 A θ j ,τ θ j 1 ρ τ θ 0 1 +•••+τ θ k-1 1    1/k = sup M 1 ,...,M k ∈Mρ k j=1 M j 1/k .
Then, taking the limit superior on both sides when k goes to infinity yields the expected result.

Following the previous Lemma 3.1.3, the ρ-SJSR inherits several properties of the JSR.

Proposition 3.1.4. For all ρ > ρ(A), λ(A, ρ) = lim k→+∞   sup θ∈Ss(I) A θ,τ θ k ρ τ θ k 1/k   . ( 3
ρ(A) < ρ 1 ≤ ρ 2 , λ(A, ρ 2 ) ≤ ρ 1 ρ 2 m λ(A, ρ 1 ). ( 3.4)
(ii) For all ρ > ρ(A), λ(A, ρ) = 0 and for all θ ∈ S s (I) A θ,t = 0, for all t ≥ τ θ n . Proof. Let ρ > ρ(A), similar to the proof of Lemma 3.1.2, applying [START_REF] Marc | Bounded semigroups of matrices[END_REF]Theorem 1] to the set of matrices 1 ρ A we get the existence of

C 1 ≥ 1 such that 0 ≤ A θ,T ρ T ≤ C 1 , ∀θ ∈ S(I), ∀T ∈ N. (3.5)
By letting T = τ θ k , raising to the power 1/k and taking the supremum over shuffled switching signals, we find

0 ≤ sup θ∈Ss(I) A θ,τ θ k ρ τ θ k 1/k ≤ C 1/k 1 .

Taking the limit of all terms yields

λ(A, ρ) ∈ [0, 1].
Let us assume that there exists ρ ′ > ρ(A) such that λ(A, ρ ′ ) = 0 and let us consider an arbitrary shuffled switching signal θ ∈ S s (I). Let us consider the sequence (θ j ) j∈N of switching signals in S s (I), defined as in the proof of Lemma 3.1.3. From Lemma 3.1.3, ρ(M ρ ′ ) = 0 and therefore the joint spectral radius of any finite subfamily of M ρ ′ is also zero. In particular, we get for the following subfamily of n elements:

ρ 1 ρ ′τ θ 0 1 A θ,τ θ 0 1 , . . . , 1
ρ ′τ θ n-1 1 A θ,τ θ n-1 1 = 0 .
By applying [42, Proposition 2.1] and using (3.2) we get A θ,τ θ n = 0. It follows that A θ,t = 0, for all t ≥ τ θ n , for all θ ∈ S s (I). Then, we get that λ(A, ρ) = 0 for all ρ > ρ(A). Now let us assume that for all ρ > ρ(A), λ(A, ρ) > 0. Let ρ(A) < ρ 1 ≤ ρ 2 . By recalling that τ θ k ≥ km, we have for all k ∈ N and for all θ ∈ S s (I)

A θ,τ θ k ρ τ θ k 2 = A θ,τ θ k ρ τ θ k 1 ρ 1 ρ 2 τ θ k ≤ A θ,τ θ k ρ τ θ k 1 ρ 1 ρ 2 km .
Raising to the power 1/k and taking the supremum over shuffled switching signals yields

sup θ∈Ss(I) A θ,τ θ k ρ τ θ k 2 1/k ≤ sup θ∈Ss(I) A θ,τ θ k ρ τ θ k 1 1/k ρ 1 ρ 2 m .
Now we take the limit of both terms and we get (3.4), which implies that ρ → λ(A, ρ) is decreasing. Then, let us assume that there exists

ρ 2 > ρ(A) such that λ(A, ρ 2 ) = 1. It follows from (3.4) that for all ρ 1 ∈ (ρ(A), ρ 2 ), λ(A, ρ 2 ) < λ(A, ρ 1 ), which contradicts the fact that λ(A, ρ 1 ) ∈ [0, 1]. Hence, λ(A, ρ) ∈ (0, 1) for all ρ > ρ(A).
Now, in order to get rid of the dependency of ρ in the ρ-SJSR, it is natural to introduce the following definition. Definition 3.1.6. The Shuffled Joint Spectral Radius (SJSR) of A is defined as

λ(A) = lim ρ→ρ(A) + λ(A, ρ). (3.6)
Since by Proposition 3.1.5, λ(A, •) is bounded and non-increasing in ρ, the right limit at ρ(A) in (3.6) exists and the SJSR is well-defined. We can now show some properties of the SJSR. Let us remark that while the JSR ρ(A) belongs to R + 0 , the SJSR λ(A) is always a value in [0, 1]. Intuitively, while the JSR provides an estimate of the contraction rate (when ρ(A) < 1) or of the expansion rate (when ρ(A) > 1) of the system state at each time step for arbitrary switching signals, the SJSR measures how much additional contraction of the state is obtained each time the signal shuffles. Theorem 3.2.1 in the next section provides theoretical ground to this interpretation.

In this section, we show how the SJSR relates to stability properties of switched linear systems with shuffled switching signals. From Proposition 3.1.5, we already know that if λ(A, ρ) = 0 for some ρ > ρ(A) then all trajectories of (2.6) will stay at 0 after n shuffling instants. So, we focus in this section on the case when λ(A, ρ) > 0 for all ρ > ρ(A). In particular, we show how the ρ-SJSR allows us to compute bounds on the shuffling rate ensuring stability. The next result clarifies the relationship between the ρ-SJSR and the behavior of the trajectories of (2.6).

Theorem 3.2.1. For all ρ > ρ(A), for all λ ∈ (λ(A, ρ), 1], there exists C ≥ 1 such that ∥x(t, x 0 , θ)∥ ≤Cρ t λ κ θ (t) ∥x 0 ∥, ∀θ ∈ S s (I), ∀x 0 ∈ R n , ∀t ∈ N.
(3.7)

Conversely, if there exists C ≥ 1, ρ ≥ 0 and λ ∈ [0, 1] such that (3.7) holds, then either ρ > ρ(A) and λ ≥ λ(A, ρ), or ρ = ρ(A) and λ ≥ λ(A).
Proof. We start by proving the direct result. Let ρ > ρ(A) and λ ∈ (λ(A, ρ), 1]. By definition of λ(A, ρ), there exists k 0 ≥ 1 such that sup θ∈Ss(I)

A θ,τ θ k ρ τ θ k 1/k ≤ λ, ∀k ≥ k 0 .
It follows that

A θ,τ θ k ≤ ρ τ θ k λ k , ∀θ ∈ S s (I), ∀k ≥ k 0 . (3.8)
Then, let C 1 ≥ 1 be such that (3.5) holds. In particular, for T = τ θ k and for shuffling switching signals, we obtain from (3.5) that

A θ,τ θ k ≤ C 1 ρ τ θ k , ∀θ ∈ S s (I), ∀k ∈ N. (3.9)
Then, let C 2 = C 1 λ -k 0 , it follows from (3.8) and (3.9) that

A θ,τ θ k ≤ C 2 ρ τ θ k λ k , ∀θ ∈ S s (I), ∀k ∈ N. (3.10) Let θ ∈ S s (I), t ∈ N, and k = κ θ (t), we have A θ,t = A θ ′ ,t-τ θ k A θ,τ θ k where θ ′ ∈ S s (I)
is given by θ ′ (s) = θ(τ θ k + s), for all s ∈ N. By (3.5), we get that

A θ ′ ,t-τ θ k ≤ C 1 ρ t-τ θ k . (3.11)

RELATION WITH DYNAMICAL SYSTEMS 25

Then, let C = C 1 C 2 , by (3.10) and (3.11), we get

A θ,t ≤ A θ ′ ,t-τ θ k A θ,τ θ k ≤ Cλ κ θ (t) ρ t .
Hence, (3.7) holds. We now prove the converse result. By definition of induced matrix norm, (3.7) is equivalent to the following:

∥A θ,t ∥ ≤ Cρ t λ κ θ (t) , ∀θ ∈ S s (I), ∀t ∈ N.
(3.12)

Since λ ∈ [0, 1] and κ θ (t) ∈ N we also have

∥A θ,t ∥ ≤ Cρ t , ∀θ ∈ S s (I), ∀t ∈ N.
Raising the previous terms to the power 1/t and taking the supremum over shuffling switching signals yields

sup θ∈Ss(I) ∥A θ,t ∥ 1/t ≤ C 1/t ρ, ∀t ∈ N.
Using the fact that for every θ ∈ S(I) and all t ∈ N there exists θ t ∈ S s (I) that coincides with θ up to time t, the equation above can be re-written as sup θ∈S(I)

∥A θ,t ∥ 1/t ≤ C 1/t ρ, ∀t ∈ N.

Taking the limit as t goes to infinity, one obtains that ρ(A) ≤ ρ. Recalling (3.12) and fixing t = τ θ k , we have

∥A θ,τ θ k ∥ ≤ Cρ τ θ k λ k , ∀θ ∈ S s (I), ∀k ∈ N which is equivalent to ∥A θ,τ θ k ∥ ρ τ θ k 1/k ≤ C 1/k λ, ∀θ ∈ S s (I), ∀k ∈ N. (3.13)
If ρ > ρ(A), taking the supremum over all shuffled switching signals and the limit as k goes to infinity yields λ(A, ρ) ≤ λ.

If ρ = ρ(A), then for all ρ ′ > ρ(A), (3.13) gives ∥A θ,τ θ k ∥ ρ ′τ θ k 1/k ≤ C 1/k λ, ∀θ ∈ S s (I), ∀k ∈ N.
Then, it follows that for all ρ ′ > ρ(A), λ(A, ρ ′ ) ≤ λ and therefore λ(A) ≤ λ.

CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS

. Stabilization and shuffling rate

In this section, we give sufficient conditions for shuffle stabilization based on the previous results. Theorem 3.2.1 provides a bound on the growth rate of the state and can be used to derive conditions for stabilization using shuffled switching signals with a minimal shuffling rate.

Corollary 3.3.1. Assume λ(A, ρ) > 0 for every ρ > ρ(A). Let θ ∈ S s (I), if there exists ρ > ρ(A) such that γ θ > -ln(ρ) ln(λ(A,ρ)) , then lim t→+∞ ∥x(t, x 0 , θ)∥ = 0, ∀x 0 ∈ R n . (3.14)
Proof. If λ(A, ρ) > 0 and γ θ > -ln(ρ) ln(λ(A,ρ)) , then there exists λ ∈ (λ(A, ρ), 1) such that γ θ > -ln(ρ) ln(λ) and ϵ > 0 such that ϵ < γ θ + ln(ρ) ln(λ) . Then, from the definition of shuffling rate, there exists t 0 ∈ N such that

κ θ (t) t > γ θ - ϵ 2 , ∀t ≥ t 0 .
From Theorem 3.2.1, there exists C ≥ 1 such that for all x 0 ∈ R n , for all t ≥ t 0 .

∥x(t, x 0 , θ)∥ ≤ Cρ t λ κ θ (t) ∥x 0 ∥ ≤ Cρ t λ (γ θ -ϵ 2 )t ∥x 0 ∥ ≤ Cρ t λ (- ln(ρ) ln(λ) + ϵ 2 )t ∥x 0 ∥ = Cλ ϵ 2 t ∥x 0 ∥, from which (3.14) follows.
A practical consequence of the previous corollary is that even if the switched system is unstable for arbitrary switching (i.e. if ρ(A) > 1), it can be stabilized by shuffling sufficiently fast. Note that since for all θ ∈ S s (I), the shuffling rate γ θ ≤ 1 m , it follows that stabilization by shuffling can only be done if there exists

ρ > ρ(A) such that -ln(λ(A,ρ)) ln(ρ) > m. Remark 3.3.2. As a consequence of Corollary 3.3.1, we have that if λ(A) ∈ (0, 1), γ θ > -ln(ρ(A))
ln(λ(A)) implies (3.14). However, we are unable to show that, in general, the function ρ → -ln(ρ) ln(λ(A,ρ)) is non-decreasing, hence replacing the assumption of Corollary 3.3.1 by γ θ > -ln(ρ(A)) ln(λ(A)) may increase the conservativeness of the result. Remark 3.3.3. In the case where the switching signal θ is generated by a Markov chain, an explicit expression for γ θ can be calculated, this is detailed in Appendix A.

. Computing bounds with Lyapunov techniques

Similar to the JSR, the exact computation of the ρ-SJSR appears in general out of reach, and an interesting problem is to look for theoretical and numerical methods allowing to estimate the ρ-SJSR. Such estimates would have an impact on the applicability of the stability results, Theorem 3.2.1 and Corollary 3.3.1. From Lemma 3.1.3, it follows that λ(A, ρ) could be approximated by computing bounds on ρ(M ρ ). However, off-the-shelf algorithms for computing approximations of the JSR only apply to finite sets of matrices [START_REF] Vankeerberghen | JSR: A toolbox to compute the joint spectral radius[END_REF]. A lower bound of λ(A, ρ) can still be computed by computing a lower bound of the JSR of a finite subfamily of M ρ . However, a similar approach does not allow to compute upper bounds. In the next subsection, we provide lower and upper bounds based on the computation of the joint spectral radius of a finite set of matrices. Methods to compute upper bounds for the ρ-SJSR based on Lyapunov techniques are then developed in Sections 3.4.2 and 3.4.3.

. Asymptotic estimate

In this section, we provide asymptotically tight bounds of λ(A, ρ) for a large enough ρ. We first recall the following classical result, which roughly speaking ensures, for any bounded set of matrices M, the existence of a matrix norm such that ρ(M) is approximated by the maximum norm of the matrices in M. Proposition 3.4.1. [17, Lemma 2] Let M be a bounded set of matrices. The following equality holds

ρ(M) = inf ∥•∥ max M ∈M ∥M ∥,
where the infimum is taken among all matrix norms induced from norms in R n .

When it exists, an induced norm

∥ • ∥ that satisfies ρ(M) = max M ∈M ∥M ∥ is called extremal for M.
We refer to [42, Theorem 2.2], and also to [START_REF] Barabanov | Lyapunov indicator of discrete inclusions. 1. 2. 3[END_REF] and [START_REF] Vs Kozyakin | Algebraic unsolvability of problem of absolute stability of desynchronized systems[END_REF], for sufficient conditions and for necessary and sufficient conditions for the existence of extremal norms. Let us consider the set N I of products of matrices where all modes in I appear exactly once:

N I = m k=1 A j k j 1 , . . . , j m ∈ I, ∀i ∈ I, ∃k ∈ {1, . . . , m}, j k = i .

CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS

The following proposition provides a lower bound for the ρ-SJSR.

Proposition 3.4.2. For all ρ > ρ(A)

λ(A, ρ) ≥ ρ(N I ) ρ m .
Proof. Let us remark that we have 1 ρ m N I ⊆ M ρ . Then, from the definition of the JSR, we get

ρ(M ρ ) ≥ ρ 1 ρ m N I = ρ(N I ) ρ m .
Lemma 3.1.3 then allows us to conclude.

It is natural to ask whether the lower bound provided in Proposition 3.4.2 can prove asymptotically tight. The following theorem provides an upper bound for the ρ-SJSR and answers to this question.

∥A θ,i ∥ * ≤ K∥A θ,i ∥ * * ≤ K Ri , ∀θ ∈ S(I), ∀i ∈ N.
Observe now that every element of Mρ \ N I takes the form 1

ρ τ θ 1 -m A θ,τ θ 1 for some θ ∈ S s (I) such that τ θ 1 > m. Setting R = max R, K K Rm+1 we have for every ρ ≥ R 1 ρ τ θ 1 -m A θ,τ θ 1 * ≤ 1 ρ τ θ 1 -m K Rτ θ 1 = K Rm R ρ τ θ 1 -m ≤ K Rm R R τ θ 1 -m ≤ K Rm+1 R ≤ K.
This proves that ∥M ∥ * ≤ K for every M ∈ Mρ \ N I , hence for every M ∈ Mρ , if ρ ≥ R. We deduce that

λ(A, ρ) = 1 ρ m ρ( Mρ ) ≤ 1 ρ m sup M ∈ Mρ ∥M ∥ * ≤ K ρ m ,
for ρ ≥ R, which proves (3.15). Setting K = ρ(N I ) + ϵ for an arbitrary ϵ > 0 we then get the existence of R ≥ ρ(A) such that, for all ρ ≥ R,

0 ≤ ρ m λ(A, ρ) -ρ(N I ) ≤ ϵ,
where the inequality on the left follows from Propositions 3.4.2. Letting ϵ tend to zero, this implies (3.16).

Finally, by taking ∥ • ∥ * extremal for N I in the argument above, we obtain that (3.15) holds true with K = ρ(N I ). Together with Proposition 3.4.2, this implies (3.17).

In the case where all the matrices A i are invertible, a practical criterion to estimate the lower bound R in Theorem 3.4.3 is given by the following lemma. Before stating the lemma, we define, for each i ∈ I, the set N i of products of N matrices in A with N < m, where each mode in I appears at most once and i appears exactly once:

N i = N k=1 A j k j 1 , . . . , j N ∈ I, N < m, ∀k ̸ = k ′ , j k ̸ = j k ′ ,
R = max i∈I,M ∈N i ∥M A i M -1 ∥ * , (3.18)

CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS

we have that R ≥ ρ(A) and (3.15) (and (3.17), if K = ρ(N I )) holds true for ρ ≥ R.

Proof. Following the proof of Theorem 3.4.3, it is enough to show that ∥A θ,τ θ

1 ∥ * ≤ KR τ θ 1 -m for every θ ∈ S s (I) such that τ θ 1 > m. The product of matrices A θ,τ θ 1 = A θ(τ θ 1 -1) • • • A θ(0)
is shuffling once, therefore all the modes appear at least once (with θ(τ θ 1 -1) appearing exactly once). The total number of repetitions in the product is given by n = τ θ 1 -m > 0. Suppose that the first repeated mode is θ(j 1 ). In order to remove A θ(j 1 ) , using the fact that all matrices A i are invertible, we multiply A θ,τ θ 1 on the right by

Q 1 = (A θ(j 1 -1) • • • A θ(0) ) -1 A -1 θ(j 1 ) (A θ(j 1 -1) • • • A θ(0) ). Then, A θ,τ θ 1 Q 1 = A θ (1) ,τ θ (1)
1

where the switching signal θ (1) is given by θ (1) (t) = θ(t)

until the instant j 1 -1, and with θ (1) (t) = θ(t + 1) afterwards. It is clear that

τ θ (1) 1 = τ θ 1 -1.
By repeating this process n times, we get a switching signal θ (n) without repetitions before its first shuffling instant (i.e. τ θ (n)

1 = τ θ 1 -n = m).

Then, we finally have

A θ,τ θ 1 n k=1 Q n+1-k = A θ (n) ,τ θ (n) 1 , with A θ (n) ,τ θ (n) 1 ∈ N I . It follows that A θ,τ θ 1 = A θ (n) ,τ θ (n) 1 n k=1 Q -1 k ,
where for all k = 1, . . . , n,

Q -1 k ∈ i∈I {M A i M -1 |M ∈ N i },
and therefore ∥Q -1 k ∥ * ≤ R, where R is given by (3.18). Moreover, since

A i ∈ N i , we have that R ≥ max i∈I ∥A i ∥ * , which implies by Proposition 3.4.1 that R ≥ ρ(A).
Finally, from submultiplicativity of the induced matrix norm, we get that for all θ ∈ S s (I)

∥A θ,τ θ 1 ∥ * ≤ ∥A θ (n) ,τ θ (n) 1 ∥ * n k=1 ∥Q -1 k ∥ * ≤ KR n ,
which yields the expected result since n = τ θ 1 -m.

We have seen with Theorem 3.4.3 and Lemma 3.4.4 that, under certain conditions, we can find tight bounds on the ρ-SJSR. In particular, if one can find a norm ∥ • ∥ * that is extremal for N I , (3.18) provides an R ≥ ρ(A) such that for all ρ ≥ R the exact value of ρ-SJSR is given by (3.17). For all ρ ∈ [ρ(A), R) we can still use the lower bound provided by Proposition 3.4.2, but we need an effective way to compute an upper bound. To address this problem, in the next section we present two Lyapunov-based methods.

Before that, we end this section by exhibiting a class of switched systems for which the value of the ρ-SJSR can be explicitly determined for all values of ρ > ρ(A). Let us consider a set of commuting matrices A = {A 1 , • • • , A m }, it is well known (see e.g. [START_REF] Vincent D Blondel | On the accuracy of the ellipsoid norm approximation of the joint spectral radius[END_REF]) that in that case the JSR is equal to the maximal value of the spectral radii of the matrices of A, that is ρ(A) = max(ρ(A 1 ), . . . ρ(A m )). Interestingly, in that case, we are also able to determine the expression of the ρ-SJSR: Proposition 3.4.5. For a finite set of commuting matrices

A = {A 1 , • • • , A m }, we have for all ρ > ρ(A), λ(A, ρ) = ρ(A 1 • • • A m ) ρ m .
Proof. Since the matrices commute, all matrices N I are equal to A 1 • • • A m . Then, Proposition 3.4.2 provides a lower bound on λ(A, ρ) with ρ(N

I ) = ρ(A 1 • • • A m ).
We need to show that it is also an upper bound. From Proposition 3.4.1 we know that, for all ρ > ρ(A), there exists a (submultiplicative) matrix norm ∥ • ∥ * such that ρ > max i∈I (∥A i ∥ * ). In the case of commuting matrices, the product A θ,τ θ k can be rearranged as follows

A θ,τ θ k = (A 1 • • • A m ) k A i 1 1 • • • A im m where mk + i 1 + • • • + i m = τ θ k . Whereby we have ∥A θ,τ θ k ∥ * ρ τ θ k ≤ ∥A 1 • • • A m ∥ k * ∥A 1 ∥ i 1 * • • • ∥A m ∥ im * ρ km ρ i 1 • • • ρ im .
Moreover, recalling that

∥A j ∥ * ρ < 1 for j = 1, . . . , m, we get ∥A θ,τ θ k ∥ * ρ τ θ k ≤ ∥A 1 • • • A m ∥ k * ρ km .

CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS

By raising the previous expression to the power 1 k , by taking the supremum over θ ∈ S s (I) and the limit for k going to infinity, we get

λ(A, ρ) ≤ ρ(A 1 • • • A m ) ρ m .
The rest details two methods for computing upper bounds on the JSR and the ρ-SJSR. Both approaches are based on Lyapunov functions and automata theoretic techniques. While the first approach is computationally more tractable, the second approach is shown to be tight.

The Lyapunov approach draws inspiration from [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF] but we will be considering different underlying automata which allow us to prove the tightness of our upper bound. Also, our Lyapunov conditions also resemble those of [START_REF] Kundu | On stability of discrete-time switched systems[END_REF], however, in that work, the relation of such Lyapunov functions to shuffled switching signals was not established.

. First method for computing bounds

Our first method is based on a Lyapunov function indexed by the set of modes I. It can be seen as an extension of Theorem 1 in [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF] in order to compute bounds on the JSR and the ρ-SJSR (in [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF], only a stability certificate is provided). Theorem 3.4.6. If there exist V : I × R n → R + 0 , α 1 , α 2 , ρ > 0 and λ ∈ [0, 1] such that the following inequalities hold true for every

x ∈ R n α 1 ∥x∥ 2 ≤ V (i, x) ≤ α 2 ∥x∥ 2 , i ∈ I (3.19) V (i, A i ′ x) ≤ ρ 2 V (i, x), i, i ′ ∈ I, i ̸ = i ′ (3.20) V (i + 1, A i x) ≤ ρ 2 V (i, x), i ∈ I \ {m} (3.21) V (1, A m x) ≤ ρ 2 λ 2m V (m, x), (3.22)
then the bound (3.7) holds.

Proof. The proof follows the main lines of that of Theorem 1 in [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF]. Let us consider an initial condition x 0 ∈ R n and a shuffled switching signal θ, let us denote x(•) = x(•, x 0 , θ). Let η : N → I be defined by η(0) = 1 and the following rules:

     if θ(t) ̸ = η(t), then η(t + 1) = η(t); if θ(t) = η(t) and η(t) ̸ = m, then η(t + 1) = η(t) + 1;
if θ(t) = η(t) and η(t) = m, then η(t + 1) = 1.

(3.23)

An equivalent description of the evolution of η can be given in terms of a finite state automaton, like the one shown in Figure 3.1 for m = 3. Inspecting the dynamics of η, one can easily see that η takes transitions from m to 1 an infinite number of times if and only if θ is a shuffled switching signal. Moreover, there is at least one such transition every m shuffling instants.

Let us consider W : N → R + 0 , defined by W (t) = V (η(t),x(t))

ρ 2t
, for all t ∈ N. It follows from (3.20), (3.21) and (3.22) that W (t + 1) ≤ W (t), thus W (t) is non-increasing. Proceeding as in the proof of Theorem 1 in [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF], we can show that

W (τ θ jm ) ≤ λ 2jm W (0), ∀j ∈ N. Let t ∈ [τ θ jm , τ θ (j+1)m ), then κ θ (t) ≤ (j + 1)m. From the monotonicity of W (t) we have W (t) ≤ W (τ θ jm ) ≤ λ 2κ θ (t)-2m W (0). From (3.19) we have W (0) ≤ α 2 ∥x 0 ∥ 2 and we get for all t ∈ N V (η(t), x(t)) ≤ α 2 ρ 2t λ 2κ θ (t)-2m ∥x 0 ∥ 2 . From (3.19) we also have, for all t ∈ N, ∥x(t)∥ 2 ≤ V (η(t),x(t)) α 1
. Whence, by taking

C = λ -m α 2
α 1 , we obtain the bound (3.7).

The previous result allows us to compute upper-bounds on the JSR and the ρ-SJSR. However, there is some conservativeness that is mostly due to the fact that the Lyapunov function is guaranteed to contract only every m shuffling instants. In the following subsection, we show an approach that makes it possible to compute a Lyapunov function that contracts at each shuffling instant. This also allows us to compute tight upper bounds on the JSR and the ρ-SJSR. Our second approach is also based on the use of a Lyapunov function and of an automaton. The main difference is that we use an automaton that visits a given state at each shuffling instant (instead of at most each m shuffling instants as in the previous section). In order to do that, we need to use a Lyapunov function indexed on the powerset of I. While this significantly increases the complexity of the approach, 2 I having exponentially more elements than I, this allows us to propose a method that provides tight bounds on the JSR and the ρ-SJSR. Proof. We first prove the direct part. Let us consider an initial condition x 0 ∈ R n and a shuffled switching signal θ, let us denote x(•) = x(•, x 0 , θ). Let η : N → 2 I \ {I} be defined by η(0) = ∅ and the following rules:

Theorem 3.4.7. If there exist V : (2 I \ {I}) × R n → R + 0 , α 1 , α 2 , ρ > 0 and λ ∈ [0, 1] such that the following inequalities hold true for every x ∈ R n α 1 ∥x∥ 2 ≤ V (J, x) ≤ α 2 ∥x∥ 2 , ∀J ⊊ I (3.24) V (J ∪ {i}, A i x) ≤ ρ 2 V (J, x), if J ∪ {i} ̸ = I (3.25) V (∅, A i x) ≤ ρ 2 λ 2 V (J, x), if J ∪ {i} = I (
if η(t) ∪ {θ(t)} ̸ = I, then η(t + 1) = η(t) ∪ {θ(t)}; if η(t) ∪ {θ(t)} = I, then η(t + 1) = ∅. (3.27)
An equivalent description of the evolution of η can be given in terms of a finite state automaton, like the one shown in Figure 3.2 for m = 3. It is straightforward to see from the dynamics of η that η(t) = ∅ if and only if t = τ θ k for some k ∈ N. Hence, the automaton state ∅ is visited at each shuffling instant. Now, let us consider W :

N → R + 0 , defined by W (t) = V (η(t),x(t)) ρ 2t
, for all t ∈ N. It follows from (3.25) and (3.26) that for all t ∈ N, W (t + 1) ≤ W (t), thus W (t) is non-increasing. Also since for all k ∈ N, we have η(

τ θ k ) = ∅, (3.26) gives W (τ θ k ) ≤ λ 2 W (τ θ k -1) for every k ∈ N, k ≥ 1.
The latter relation and the monotonicity of

W (t) implies that W (τ θ k ) ≤ λ 2 W (τ θ k-1 )
. Hence, by induction we conclude that

W (τ θ k ) ≤ λ 2k W (0), ∀k ∈ N. Let t ∈ [τ θ k , τ θ (k+1)
), then κ θ (t) = k, from the monotonicity of W (t) we have:

W (t) ≤ W (τ θ k ) ≤ λ 2κ θ (t) W (0)
. From this point on the proof is similar to the final part of that of Theorem 3.4.6. Therefore we finally obtain the bound (3.7).

We prove now the converse result. We first consider the case ρ = 1. For J ⊆ I with J ̸ = ∅, let M J consist of all finite products of N matrices in A, with N ∈ N, where each mode in J appears at least once, and the last mode j N belongs to J and appears exactly once:

M J =    N k=1 A j k , j 1 , . . . , j N ∈ I, N ∈ N, ∀i ∈ J, ∃k, j k = i, j N ∈ J and ∀k ̸ = N, j k ̸ = j N    .
In particular, M I is the set of all possible matrices A θ,τ 1 From [START_REF] Marc | Bounded semigroups of matrices[END_REF]Lemma 2] applied to the family of products of matrices in { 1 λ M | M ∈ M I }, it follows that there exists a norm ∥ • ∥ * in R n such that the corresponding induced matrix norm, also denoted by ∥ • ∥ * , satisfies sup

θ for θ ∈ S s (I). Since ρ = 1, it follows from (3.7) that for all k ∈ N ∥A θ,τ k θ ∥ ≤ Cλ k , ∀θ ∈ S s (I) , which is equivalent to k j=1 M j ≤ Cλ k , ∀M 1 , . . . , M k ∈ M I . ∅ {1} {2} {3} {1, 2} {2, 3} {1, 3} 2 1 2, 3 1, 3 1, 2 2
M ∈M I ∥M ∥ * ≤ λ.
Then, for all subsets J ⊊ I and x ∈ R n we define

V (J, x) = sup M ∈M I\J ∥M x∥ 2 * .
Let us first prove (3.24). For J ⊊ I, let M J be an arbitrary element of M I\J , then V (J, x) ≥ ∥M J x∥ 2 * . All matrices M J are invertible, ∥ • ∥ * is equivalent to ∥ • ∥, and 2 I \ {I} is a finite set, therefore there exists α 1 > 0 such that ∥M J x∥ 2 * ≥ α 1 ∥x∥ 2 , for all J ⊊ I, x ∈ R n . Also, it follows from (3.7) with ρ = 1 and λ ∈ [0, 1] that for all J ⊊ I, for all M ∈ M I\J , ∥M ∥ ≤ C. Then, ∥ • ∥ * being equivalent to ∥ • ∥, it follows that there exists α 2 > 0 such that V (J, x) ≤ α 2 ∥x∥ 2 , for all J ⊊ I, x ∈ R n .

To prove (3.25), we first notice that every product M A i with M ∈ M I\(J∪{i}) belongs to M I\J . Hence,

V (J ∪ {i}, A i x) = sup M ∈M I\(J∪{i}) ∥M A i x∥ 2 * ≤ sup M ′ ∈M I\J ∥M ′ x∥ 2 * = V (J, x).
In order to prove (3.26), we use the fact that if

J ⊊ I is such that J ∪ {i} = I then A i ∈ M I\J = M {i} . Consequently, V (∅, A i x) = sup M ∈M I ∥M A i x∥ 2 * ≤ λ 2 ∥A i x∥ 2 * ≤ λ 2 sup M ∈M I\J ∥M x∥ 2 * = V (J, x).
This concludes the proof in the case ρ = 1.

Let us consider now the general case ρ ̸ = 1. For the set of matrices 1 ρ A, the corresponding dynamics satisfies (3.7) with ρ = 1 and we can consider the function V defined above. It directly follows from the properties shown above and the fact that V is homogeneous of degree two that (3.

. Numerical examples

In this section, we give two numerical examples to validate our work. The first one is to validate the results of Section 3.4 by computing lower and upper bounds on the ρ-SJSR. The computation of the upper bounds is based on two methods. In the second example, we illustrate the results of Section 3.3 by computing a class of stabilizing shuffled switching signals. These signals stabilize well an unstable system.1

. Numerical example 1

Let us consider a switched system in R 3 with 2 modes, where A = {A 1 , A 2 } with: We first compute a lower bound for the ρ-SJSR using Proposition 3.4.2. Let us remark that N I = {A 1 A 2 , A 2 A 1 }. We use the JSR toolbox [START_REF] Vankeerberghen | JSR: A toolbox to compute the joint spectral radius[END_REF]

A 1 =   1 0 0 0 µ 1 cos(ϕ 1 ) -µ 1 sin(ϕ 1 ) 0 µ 1 sin(ϕ 1 ) µ 1 cos(ϕ 1 )   , A 2 =   µ 2 cos(ϕ 2 ) -µ 2 sin(ϕ 2 ) 0 µ 2 sin(ϕ 2 ) µ 2 cos(ϕ 2 ) 0 0 0 1   , (3.28
* = x ⊤ Qx, Q = Q ⊤ ≥ 0 with the associated induced matrix norm ∥M ∥ * = ∥Q 1/2 M Q -1/2
∥, the conditions above are equivalent to the following LMIs:

(A 1 A 2 ) ⊤ QA 1 A 2 ≤ ρ 2 Q, (A 2 A 1 ) ⊤ QA 2 A 1 ≤ ρ 2 Q.
Solving these LMIs yields

Q =   0
I n ≤Q i , i ∈ I A ⊤ i ′ Q i A i ′ ≤ρ 2 Q i , i, i ′ ∈ I, i ̸ = i ′ A ⊤ i Q i+1 A i ≤ρ 2 Q i , i ∈ I \ {m} A ⊤ m Q 1 A m ≤ρ 2 λ 2m Q m .
Similarly, searching for Lyapunov functions of the form V (J, x) = x ⊤ Q J x, J ⊊ I, the conditions of Theorem 3.4.7 translate to the following LMIs: Then, for each ρ ∈ Ω = {1, 1.05, • • • , 1.35}, we can find an upper bound λ(ρ) on λ(A, ρ) by searching (using a line search) for the smallest value of λ for which the LMIs above have a solution. Then, we can obtain an upper bound for the ρ-SJSR for all ρ ∈ (1, R) using (3.4):

I n ≤Q J , J ⊊ I A ⊤ i Q J∪{i} A i ≤ρ 2 Q J , if J ∪ {i} ̸ = I A ⊤ i Q 1 A i ≤ρ 2 λ 2 Q J , if J ∪ {i} = I.
∀ρ ∈ (1, R), λ(A, ρ) ≤ min ρ ′ ∈Ω,ρ ′ ≤ρ ρ ′ ρ m λ(ρ ′ ).
The resulting upper-bounds as well as the lower bound are shown in Figure 3.3. One can check that the upper-bound computed using Theorem 3.4.7 is always tighter than that provided by Theorem 3.4.6. However, let us remark that the former approach involves solving a set of m(m + 1) LMIs while the latter requires solving a set of (2 m -1)(m + 1) LMIs. For large values of m the latter approach is likely to be intractable.

. Numerical example 2

CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS

We provide a short case-study regarding an application of our tools to the design of networked controllers for synchronization of distributed oscillators. Let us consider m+1 identical components consisting of discrete-time oscillators whose dynamics is given by:

z i (t + 1) = Rz i (t) + u i (t), i = 1, . . . , m + 1 (3.29)
where

z i (t) ∈ R 2 , u i (t) ∈ R 2 and R = µ cos(ϕ) -µ sin(ϕ) µ sin(ϕ) µ cos(ϕ) with µ = 1.02
and ϕ = π 6 . The input u i (t) is used for synchronization purpose and is based on the available information at time t. The information is exchanged over a single hop communication network, which consists of m communication channels between components i and i + 1, i = 1, . . . , m. We assume that the network capacity is limited, in such a way that only one channel can be activated at a given time instant. Formally, the active channel is given by a switching signal θ : N → I = {1, . . . , m}. Then, the input value implementing the synchronization protocol is given as follows:

u 1 (t) = k(z 2 (t) -z 1 (t)), if θ(t) = 1 0, otherwise u i (t) =      k(z i-1 (t) -z i (t)), if θ(t) = i -1 k(z i+1 (t) -z i (t)), if θ(t) = i 0 otherwise for i = 2, . . . , m, u m+1 (t) = k(z m (t) -z m+1 (t)), if θ(t) = m 0 otherwise (3.30)
where k ∈ (0, 1) is a control gain. Denoting the vector of synchronization errors as x(t) = (x 1 (t) ⊤ , . . . , x m (t) ⊤ ) ⊤ with x i (t) = z i+1 (t) -z i (t), the error dynamics is described by a 2m-dimensional switched linear system of the form (2.6) with m modes. The expression of the matrices A i ∈ R 2m×2m , i = 1, . . . , m can be easily derived from (3.29)-(3.30). For m ≥ 2, it is clear that the synchronization cannot be achieved using arbitrary switching signals. Indeed, considering for instance the constant switching signal θ(t) = 1, for all t ∈ N, components 1 and 2 will synchronize but other agents that do not get the opportunity to exchange information cannot synchronize. Hence, we use shuffled switching signals. In our case study, we aim at providing answers to the following questions:

1. Co-design a control gain k and a minimal shuffling rate γ * so that all oscillators synchronize;

2. Determine the maximal number of oscillators that can be synchronized given the proposed network architecture and capacity.

We compute ρ(A) using the JSR toolbox. We then use Theorem 3.4.7 to compute an upper bound λ(ρ) on the ρ-SJSR by solving the associated LMIs presented in the previous subsection. Note that

γ * := inf ρ>ρ(A) - ln(ρ) ln(λ(ρ)) ≥ inf ρ>ρ(A)
ln(ρ) ln(λ(A, ρ)) .

In this example, we observe numerically that the infimum is reached for ρ = ρ(A) when γ * < 1 m (the case when the system is stabilizable, see Corollary 3.3.1). Else, the infimum is reached at infinity with γ * = 1 m . We computed γ * for several values of k ∈ (0, 1) and m + 1 ∈ {3, 4, 5} and we show the result in Figure 3.4. In this figure, the dashed lines correspond to the maximal achievable shuffling rate 1 m . From Corollary 3.3.1, we know that the switched system can be stabilized if we use shuffled switching signals θ ∈ S s (I) whose shuffling rate γ θ ∈ (γ * , 1 m ]. Hence, in order to stabilize the system, we should carefully select the control gain k such that the corresponding value of γ * < 1 m . This answers the first point of our case study. For instance, we can see that for a system composed of m + 1 = 3 oscillators, for a control gain k = 0.6 we get γ * = 0.08 and we can stabilize the system by imposing a shuffling rate γ θ ∈ (0.08, 0.5]. If we choose k = 0.88, then γ * = 1 m and we are not able to stabilize the system by shuffling.

We also verified that for m + 1 = 6 oscillators, γ * > 1 m for all control gain k ∈ (0, 1). Therefore, for 6 oscillators, there is no suitable choice of control gain k such that the system can be stabilized by shuffling. This answers the second point of our case study.

We now proceed with some illustrative numerical simulations. Let us consider a system composed of m + 1 = 3 oscillators with control gain k = 0.4, then from Figure 3.4, the corresponding lower bound on the shuffling rate is γ * = 0.06. Let us consider the initial synchronization error x(0) = (-1.5 -0.5 2 -1) ⊤ . We consider random switching signals generated by a discrete-time Markov chain with 2 states and the following transition matrix:

1 -p p p 1 -p where p ∈ (0, 1)
is the probability to switch at a given time instant. It is easy to see that such switching signals are shuffled almost surely. Moreover, the larger p the higher the shuffling rate of the switching signals. We first consider p = 1/10, Figure 3.5 shows the evolution of κ θ (t) t , the switching signal θ(t) and the synchronization errors x 1 (t), x 2 (t). It is interesting to note that κ θ (t) t > 0.06 and that the system stabilizes as expected. Next, we consider p = 1/70, the corresponding simulation results are shown in Figure 3.6. We can check on the figure that in this case κ θ (t) t < 0.06 and that the system does not stabilize, the shuffling being too slow.

. Conclusion

In this chapter, the ρ-SJSR and the SJSR were introduced, new notions of joint spectral radius for discrete-time switched linear systems driven by shuffled switching signals. Moreover, some of their properties were established. Also, their relation to stability properties of switched systems was detailed. A method to compute asymptotically tight lower and upper bounds of the ρ-SJSR was presented. This method relies on a JSR of a finite set of matrices. Furthermore, two approaches to compute upper-bounds of the ρ-SJSR were developed. These While the first approach is computationally more tractable, the second approach was shown to be tight. Numerical examples were also provided to show the effectiveness of the proposed numerical approximation methods. An application of the SJSR to the synchronization of unstable oscillators was also shown. Since the shuffled switching signal represents a particular ω-regular language, it is natural to ask the following question: can the above results be generalized to the case of an arbitrary ω-regular language driven switched system?

The next chapter discusses this question, moreover it details sufficient and necessary conditions for the stability of an arbitrary ω-regular language driven switched system.

-Switched systems driven by ω-regular language

In this chapter, we detail the stability of switched systems driven by an ωregular language generated by a given Büchi automaton. More precisely, we establish sufficient conditions for stability. For a particular class of systems we also show that these conditions are also necessary. This part can be seen as a generalization of [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF] from the particular case of shuffled switching signals to the general case of arbitrary ω-regular languages. Although the proof of the sufficient conditions is easily adapted from [START_REF] Girard | Lyapunov functions for shuffle asymptotic stability of discrete-time switched systems[END_REF], the proofs of the converse result require some novel techniques. =These techniques include the construction of a labeled graph based on accepting states of a non-deterministic Büchi automaton, also the lifting of results of [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF] for a construction of a Lyapunov function.

Furthermore, we introduce the ω-Regular Joint Spectral Radius (ω-RJSR). Intuitively, this quantity measures how much the system contracts each time some particular states on the Büchi automaton are visited. We also relate the ω-RJSR with the stability of switched systems driven by a given Büchi automaton (Theorem 4.3.7). Moreover, we show how this quantity can lead us to characterize a class of stabilizing switching signals (Corollary 4.3.8). We also present a Lyapunov-based method for computing upper bounds ω-RJSR. Finally, we present two numerical examples which validate our results. In fact, this part can be seen as a generalization of Chapter 3.

This chapter represents the results of the following paper and book chapter: The organization of the chapter is as follows. Section 4.1 introduces the Büchi automaton, the class of systems under consideration and the associated stability notions. In Section 4.2, we provide sufficient stability conditions given by the existence of a Lyapunov function. We also establish a converse Lyapunov result for a particular class of systems. An illustrative example is also shown in this section. The last section details the ω-RJSR and establishes several of its properties. It also shows a sufficient condition for stabilization under ω-regular language constraints. Moreover, a Lyapunov based method is shown to compute upper bounds on the ω-RJSR. Finally, a numerical example is given to illustrate the results of this section.

. ω-regular stability

. Büchi automaton

A non-deterministic Büchi automaton (NBA) is a tuple B = (Q, Σ, δ, Q 0 , F ) where Q is a finite set of states, Σ is the alphabet, δ : Q × Σ → 2 Q is a partial transition function, Q 0 is
the set of initial states and F ⊆ Q is the set of accepting states. A run associated with a finite or infinite word σ ∈ Σ + ∪ Σ ω is a sequence of states q 0 q 1 q 2 . . . such that q 0 ∈ Q 0 and q i+1 ∈ δ(q i , σ i ) for all i = 0, 1, . . . . Note that some words in σ ∈ Σ + ∪ Σ ω may not have associated runs since δ is a partial function. A run q 0 q 1 q 2 . . . associated with an infinite word σ ∈ Σ ω is said to be accepting if q i ∈ F for infinitely many indices i ∈ N. The language of B, denoted by Lang(B), is the set of all infinite words over the alphabet Σ which have an accepting run in B. We note that an NBA is called deterministic Büchi automaton (DBA) if |δ(q, i)| ≤ 1 for all q ∈ Q, i ∈ Σ and |Q 0 | = 1. Given q ′ , q ′′ ∈ Q and

σ 1 • • • σ n ∈ Σ * , we write q ′ σ 1 •••σn ----→ q ′′ if q ′′ is obtained as a concatenation of transitions from q ′ , namely q ′′ = δ(• • • δ(δ(q ′ , σ 1 ), σ 2 ), . . . , σ n ).
It is known that the Language of a Büchi automaton represents an example of an ω-regular language, moreover for any ω-regular language there exists a Büchi automaton recognizing that language [START_REF] Baier | Principles of model checking[END_REF]26].

An example of a Büchi automaton is shown in Figure 4.1. This automaton accepts infinite words over the alphabet Σ = {1, 2} that end with a sequence of 1's. Notice that this language cannot be characterized by a finite state automaton. A non-deterministic Büchi automaton B = {{a, b}, {1, 2}, δ, {a}, {b}} recognizing the ω-regular language (1 + 2) * 1 ω . Now given a DBA B, and an infinite word σ ∈ Lang(B), let us denote q 0 q 1 . . . the associated run in B and define the following quantities:

The sequence of accepting instants (τ σ k ) k∈N defined by τ σ 0 = 0, and for all k ∈ N,

τ σ k+1 = min {t > τ σ k |q t ∈ F }.
The accepting index κ σ : N → N given by

κ σ (t) = max{k ∈ N| τ σ k ≤ t}.
The accepting rate γ σ as

γ σ = lim inf t→+∞ κ σ (t) t .
Intuitively, τ σ k is the instant of the k-th visit of the run to the set F and the accepting index κ σ (t) counts the number of times the run has visited the set F up to time t. It is worth noting that since σ ∈ Lang(B), we have lim

t→∞ κ σ (t) = ∞.
The accepting rate γ σ characterizes the frequency of visits to the set F over all time. Notice that these defined quantities generalize the similar quantities defined to a shuffled switching signal in Definition 2.2.1.

In the next lemma, we establish a tight upper bound on the accepting rate of all switching sequences belonging to a language of a given DBA B.

Before introducing this result, let us define the notion of a cycle in B. A cycle is a sequence of states q 1 • • • q n such that for all i ̸ = j, q i ̸ = q j ; for all i = 1, • • • , n -1, there exists σ i ∈ Σ such that q i+1 = δ(q i , σ i ); and there exists σ n ∈ Σ such that q 1 = δ(q n , σ n ). We denote the set of cycles in B by C B . For a cycle c ∈ C B , we denote by F c the set of accepting states appearing in c. Formally, Proof. Let σ ∈ Lang(B), let q 0 q 1 . . . be the associated run, and let t ∈ N. The accepting index κ σ (t) is given by the number of occurrences of elements of F in the sequence r 0 = q 1 . . . q t . Since |r 0 | = t, if t ≤ |Q|, it is clear that κ σ (t) ≤ |Q| and (4.1) holds. If t > |Q|, then there exists at least one state appearing twice in r 0 . Let 1 ≤ i < j ≤ t be the indices of the first state appearing twice in r 0 . Then, there exists a cycle c 1 = q i . . . q j-1 ∈ C B . Moreover, the number of occurrences of elements of F in r 0 is given by the sum of the number of occurrences of elements of F in the cycle c 1 and in the sequence r 1 = q 1 . . . q i-1 q j . . . q t (or in the sequence r 1 = q j . . . q t if i = 1). By repeating this reasoning, we get that the number of occurrences of elements of F in r 0 is bounded by the sum of the number of occurrences of elements of F in a collection of cycles c 1 , . . γ σ ≤ M.

F c = {q i ∈ F : c = q 1 • • • q n }.
To show that this bound is tight, let us consider c ∈ C B such that |Fc| |c| = M . From Assumption 4.1.2, it follows that there exists a run of B of the form r = w.c ω . Let σ be an associated element of Σ ω . Then, it is easy to see that γ σ = M .

As an illustration, consider the DBA B shown in Figure 4.2. This DBA contains 6 cycles q 1 , q 2 , q 3 , q 0 q 1 , q 0 q 2 , q 0 q 3 . Then, the maximal accepting rate for infinite words σ ∈ Lang(B) is M = 1 2 . As explained in Section 1.1, Büchi automata play a crucial role in the description of the connectivity of consensus/synchronization of oscillators. Therefore, in the next sections we will shed light on the stability of systems driven by ω-regular language generated using a given Büchi automata.

4.1.2 . Stability notions for ω-regular language driven switched systems Let us consider a discrete-time switched linear system in which the switching sequences are infinite words accepted by a given NBA. Specifically, given a Büchi

q 0 q 1 q 2 q 3
Figure 4.2: An example of DBA whose language consists of infinite words that do not remain constant after some time. The accepting state is represented with a double circle.

automaton B = (Q, Σ, δ, Q 0 , F ) where the alphabet is the set Σ = I = {1, . . . , m}, given a finite set of matrices A = {A 1 , . . . , A m } with A i ∈ R n×n , i ∈ Σ, the discrete-time switched linear system with ω-regular switching sequences (A, B) is described by the trajectory equation (2.6) , i.e.

x(t + 1) = A θ(t) x(t), here we consider that θ ∈ Lang(B) where, by abuse of notation, we say that θ ∈ Lang(B) if the infinite word θ(0)θ(1) • • • ∈ Lang(B). We note that, given an initial condition x 0 ∈ R n , and a switching signal θ ∈ Lang(B), the trajectory with x(0) = x 0 is unique, denoted by x(., x 0 , θ) and given by ∀t ≥ 1 :

x(t, x 0 , θ) = t-1 i=0 A θ(i) x 0 , where t-1 i=0 A θ(i) = A θ(t-1) × • • • × A θ(0) .
Before we elaborate the sufficient conditions, let us introduce the following assumption: Assumption 4.1.2. All the states of the Büchi automaton B are reachable from at least one initial state and for any finite run q 0 q 1 q 2 . . . q k there exists an infinite sequence of states q k+1 q k+2 . . . such that q 0 q 1 q 2 . . . is an accepting run.

Note that there is no loss of generality to suppose that Assumption 4.1.2 holds true since it can be shown easily that for any NBA (resp. DBA), there exists an NBA (resp. DBA) with the same language and satisfying Assumption 4.1.2. Hence, in the rest of the work, Assumption 4.1.2 is always supposed to be satisfied.

We start by defining some stability notions. A,B) is globally uniformly stable (GUS) if there exists a scalar α ≥ 1 such that for all switching signals θ ∈ Lang(B) and for all initial conditions x 0 ∈ R n , we have

∥x(t, x 0 , θ)∥ ≤ α∥x 0 ∥, ∀t ∈ N.
Definition 4.1.5. The system (A, B), where B is a DBA, is globally uniformly exponentially stable (GUES) if there exist a scalar C ≥ 1 and a scalar 0 < λ < 1 such that for all switching signals θ ∈ Lang(B) and for all initial conditions x 0 ∈ R n , we have

∥x(t, x 0 , θ)∥ ≤ Cλ κ θ (t) ∥x 0 ∥, ∀t ∈ N.
It is clear that if the system (A, B) is GUES then it is GA and GUS, we note that this type of stability cannot be defined for an NBA since κ θ (t) is not defined for these automata.

We have seen in this section several notions of stability of switched linear systems with ω-regular switching sequences, some of them concern the general case of an NBA, and the rest concerns the DBA only. In the next sections, we will develop sufficient conditions for stability using a Lyapunov approach and we will give a converse result for a specific class of systems.

. Sufficient and necessary conditions for stability

In this section, for a system (A, B), we establish sufficient conditions for the notions of stability defined in the previous section. Moreover, we show that these conditions are also necessary when the state matrices are invertible.

. Sufficient conditions

Before establishing our conditions, let us give a definition of a Lyapunov function for a system (A, B). Definition 4.2.1. For the system (A, B), the function V : Q×R n → R + 0 , is called Lyapunov function if there exist scalars α 1 , α 2 > 0 and 0 < ρ < 1 such that for all x ∈ R n , the following hold:

α 1 ∥x∥ ≤ V (q, x) ≤ α 2 ∥x∥, q ∈ Q (4.2) V (q ′ , A i x) ≤ V (q, x), q ∈ Q, i ∈ Σ, q ′ ∈ δ(q, i) \ F (4.3) V (q ′ , A i x) ≤ ρV (q, x), q ∈ Q, i ∈ Σ, q ′ ∈ δ(q, i) ∩ F (4.4)
Theorem 4.2.2. If there exists a Lyapunov function for the system (A, B) then (A, B) is GA and GUS. If in addition B is a DBA then (A, B) is GUES.

Proof. Let us consider an initial condition x 0 ∈ R n and a switching signal θ ∈ Lang(B), let q 0 q 1 q 2 . . . be an accepting run associated with θ. Let t 0 = 0 and 0 < t 1 < t 2 < . . . be the time instants where q t i ∈ F , for all i ≥ 1. We denote x(.) = x(., x 0 , θ) and we define the function W : N → R + 0 by W (t) = V (q t , x(t)) for all t ∈ N. It follows from (4.3) and (4.4) that W (t + 1) ≤ W (t) for all t ∈ N. From the monotonicity of W , we get that ∀t ∈ N : W (t) ≤ W (0). Therefore, from (4.2) we conclude that

∀t ∈ N : ∥x(t)∥ ≤ α 2 α 1 ∥x 0 ∥,
and we get that the system (A, B) is GUS.

On the other hand, from (4.4), we get that

∀k ≥ 1 : W (t k ) ≤ ρW (t k -1).
From the monotonicity of W , we deduce that

∀k ≥ 1 : W (t k ) ≤ ρW (t k-1 ).
By induction on k, we get that

∀k ∈ N : W (t k ) ≤ ρ k W (0).
Since W is non-increasing and since W (t) ≥ 0 for all t ∈ N and 0 < ρ < 1, we get that lim t→∞ W (t) = 0.

CHAPTER 4. ω-REGULAR LANGUAGE

Therefore, from (4.2) we get that the system (A, B) is GA. Now if B is a DBA, the sequence (t k ) k∈N defined above coincides with the sequence of return instants (τ θ k ) k∈N . Therefore, we get that

∀k ∈ N : W (τ θ k ) ≤ ρ k W (0). Now let t ∈ N, and let k ∈ N such that t ∈ [τ θ k , τ θ k+1
), then the return index is κ θ (t) = k. We get from the monotonicity of W that W (t) ≤ ρ κ θ (t) W (0). Finally from (4.2), we get, for all t ∈ N,

x 0 ∈ R n that ∥x(t)∥ ≤ α 2 α 1 ρ κ θ (t) ∥x 0 ∥. (4.5) Hence (A, B) is GUES.
Let us remark that (4.5) provides an upper bound on the convergence rate of the state with respect to the number of visits to the accepting set F given by the return index κ θ (t). If we restrain to Lyapunov functions of the form V (q, x) =

x ⊤ P q x where, for every q ∈ Q, P q is a positive definite matrix, then the conditions in Definition 4.2.1 are equivalent to a set of LMIs. In that case, stability of the switched system (A, B) can be verified by solving a convex optimization problem.

. A converse result

In this section, we show that, if all matrices in A are invertible, then the existence of a Lyapunov function for (A, B) is not only sufficient but also necessary for the attractivity and uniform stability of the system. We introduce some quantities related to the NBA B. We define L qq f as the set of all words in Σ + corresponding to a run starting from q ∈ Q and reaching q f ∈ F without visiting any accepting state between q and q f . Formally

L qq f = σ 1 . . . σ k ∈ Σ + q i+1 ∈ δ(q i , σ i ) \ F, 1 ≤ i < k
where q 1 = q and q f ∈ δ(q k , σ k ) .

Now we define L × qq f as the set of all products of matrices in A associated with words in L qq f :

L × qq f = A σ k × • • • × A σ 1 σ 1 . . . σ k ∈ L qq f .
Given a word l ∈ L qq f the corresponding matrix in L × qq f is denoted M l . In order to establish necessary conditions, we apply a result obtained in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF] based on labeled graphs and constrained systems (Section 2.1.4). As a means to analyze the dynamics of the system (A, B), let us associate it to a constrained

L q 1 q 1 L q 2 q 2 L q 1 q 2 L q 2 q 1 q 1 q 2 q 3 L q 3 q 3 L q 1 q 3 L q 3 q 1 L q 3 q 2 L q 2 q 3 Figure 4.3:
The labeled graph G corresponding to an NBA B with 3 accepting states q 1 , q 2 and q 3 .

system (M F B , G), where M F B = q,p∈F
L × qp and the nodes of G are V = F , the labels

L = q,p∈F
L qp , and the set of edges is E = {(q, l, p) |q, p ∈ F, l ∈ L qp }.

Remark 4.2.3. In [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF], the set of labels L is assumed to be finite. In our case, this set can be infinite.

Figure 4.3 shows the labeled graph corresponding to an NBA B with three accepting states q 1 , q 2 and q 3 . In the figure, by an abuse of notation, for q i , q j ∈ F , the edge (q i , L q i q j , q j ), denotes the set of edges (q i , l, q j ) l ∈ L q i q j . Note that, unlike [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF], in our case the set of edges of the labeled graph is usually infinite. We consider the following stability notion. Definition 4.2.4. We say that the constrained system (M F B , G) is attractive if for all paths (q f 0 , l 1 , q f 1 ), (q f 1 , l 2 , q f 2 ), . . . we have

lim k→∞ ∥M l k • • • M l 1 ∥ = 0.
In the following, we will make use of the following assumption. The following lemma provides a uniform bound on the set of matrix products that correspond to transitions from any state q ∈ Q to an accepting state q f ∈ F .

54

CHAPTER 4. ω-REGULAR LANGUAGE Lemma 4.2.6. Under Assumption 4.2.5, if the system (A, B) is GUS, then the set L × qq f is either empty or bounded for all q ∈ Q, q f ∈ F .

Proof. Let q ∈ Q, q f ∈ F such that L qq f ̸ = ∅. Let l ∈ L qq f , by Assumption 4.1.2 we know that there exist a switching signal θ(0)θ(1) • • • ∈ Lang(B) and a corresponding run q 0 q 1 q 2 . . . such that q t ′ 0 = q and q t 0 = q f , for some t ′ 0 < t 0 and l = θ(t ′ 0 ) . . . θ(t 0 -1). Without loss of generality we may assume that q i ̸ = q j for every 0 ≤ i < j ≤ t ′ 0 since otherwise, if q i = q j , we can replace the switching signal θ with θ(0)θ(1) . . . θ(i -1)θ(j) . . . and consider the corresponding run q 0 q 1 q 2 . . . q i q j+1 . . . . Hence we may assume t ′ 0 ≤ |Q| -1. From the definition of global uniform stability we get that there exists α ≥ 1 such that

∥A θ(t 0 -1) • • • A θ(t ′ 0 ) A θ(t ′ 0 -1) • • • A θ(1) A θ(0) ∥ ≤ α Using the fact that, for A, B in R n×n with B invertible, one has ∥A∥ ≤ ∥AB∥∥B -1 ∥ and since M l = A θ(t 0 -1) • • • A θ(t ′ 0 )
, we obtain from the previous inequality

∥M l ∥ ≤ α∥(A θ(t ′ 0 -1) • • • A θ(1) A θ(0) ) -1 ∥ = α∥(A θ(0) ) -1 (A θ(1) ) -1 • • • (A θ(t ′ 0 -1) ) -1 ∥ ≤ α max A∈A ∥A -1 ∥ t ′ 0 ≤ α max 1, max A∈A ∥A -1 ∥ |Q|-1
.

We have thus obtained a uniform bound on the set of matrices L × qq f whenever L qq f ̸ = ∅.

We will analyse the attractivity of the constrained system (M F B , G) by making use of the concept of multinorm, defined below. Definition 4.2.7. (Definition 1 in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF]) A multinorm of the constrained system

(M F B , G), denoted by H, is a set of |F | norms in R n , that is H = {∥.∥ q , q ∈ F }. The value of the multinorm γ * (H) is defined as γ * (H) = inf γ > 0 ∥M x∥ p ≤ γ∥x∥ q , ∀x ∈ R n , ∀q, p ∈ F s.t. L qp ̸ = ∅, ∀M ∈ L × qp .
This definition coincides with Definition 1 in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF] except for the fact that here the matrix M takes values on a possibly infinite set. Theorem 4.2.8. Suppose that Assumption 4.2.5 holds true and that (A, B) is GUS. Then the constrained system (M F B , G) is attractive if and only if it admits a multinorm H with value γ * (H) < 1.

CHAPTER 4. ω-REGULAR LANGUAGE

Note that V is well defined thanks to Assumption 4.1.2. Let us prove that V is a Lyapunov function for (A, B), namely that V satisfies equations (4.2), (4.3) and (4.4) in Definition 4.2.1 for all x ∈ R n , for some positive constants α 1 , α 2 and ρ such that γ * (H) < ρ < 1.

Concerning (4.2), since the system is GUS and thanks to Assumption 4.2.5 we know from Lemma 4.2.6 that the set L × qq f is bounded for all q ∈ Q and q f ∈ F . Hence there exists B > 0 such that V (q, x) ≤ B max q f ∈F ∥x∥ q f . Furthermore, from the equivalence of norms in R n and since F is finite, we get that there exists a constant α 2 > 0 such that V (q, x) ≤ α 2 ∥x∥ for all q ∈ Q and x ∈ R n .

On the other hand, for q ∈ Q, there exists q f ∈ F such that L qq f ̸ = ∅. Taking M q ∈ L × qq f we get, from the equivalence of norms in R n and since F is finite, that there exists a scalar α > 0 such that for all x ∈ R n it holds

V (q, x) ≥ α∥M q x∥.
From Assumption 4.2.5, we then obtain

V (q, x) ≥ α ∥x∥ ∥M q -1 ∥ ≥ α min q∈Q 1 ∥M -1 q ∥ ∥x∥.
By taking α 1 = α min q∈Q 1 ∥Mq -1 ∥ we get that (4.2) holds true. We next show (4.3). Let q ∈ Q and q ′ ∈ δ(q, i) \ F for some i ∈ Σ. For every q f ∈ F such that L q ′ q f ̸ = ∅ and M ∈ L × q ′ q f we have that the product M A i is an element of the set L × qq f . In particular

{q f ∈ F | L q ′ q f ̸ = ∅} ⊆ {q f ∈ F | L qq f ̸ = ∅} and sup M ∈L × q ′ q f ∥M A i x∥ q f ≤ sup M ′ ∈L × qq f ∥M ′ x∥ q f , ∀x ∈ R n .
Then max

q f ∈F L q ′ q f ̸ =∅ sup M ∈L × q ′ q f ∥M A i x∥ q f ≤ max q f ∈F L q ′ q f ̸ =∅ sup M ′ ∈L × qq f ∥M ′ x∥ q f ≤ max q f ∈F Lqq f ̸ =∅ sup M ′ ∈L × qq f ∥M ′ x∥ q f Hence (4.3) is satisfied.
Finally, let us prove (4.4). Let q ∈ Q and q ′ ∈ δ(q, i) ∩ F for some i ∈ Σ. Let

q f ∈ F, M ∈ L × q ′ q f . Letting ρ such that γ * (H) < ρ < 1 we get that ∥M x∥ q f ≤ ρ∥x∥ q ′ for all x ∈ R n . Since A i ∈ L × qq ′ , then

CONDITIONS FOR STABILITY

57

∥M A i x∥ q f ≤ ρ∥A i x∥ q ′ ≤ ρ sup M ′ ∈L × qq ′ ∥M ′ x∥ q ′ ≤ ρ max q ′ f ∈F L qq ′ f ̸ =∅ sup M ′ ∈L × qq ′ f ∥M ′ x∥ q ′ f
Taking the supremum over M ∈ L × q ′ q f and then the maximum over all q f ∈ F such that L q ′ q f ̸ = ∅ on the left-hand side, we get that (4.4) is satisfied, concluding the proof of the theorem. Corollary 4.2.11. Under Assumption 4.2.5, let B be deterministic. Then, the (A, B) is GUES if and only if it is GA and GUS.

Proof. The fact that GUES implies GA and GUS follows directly from the definitions. Then, if (A, B) is GA and GUS. Then from Theorem 4.2.10, there exists a Lyapunov function. Theorem 4.2.2 gives that (A, B) is GUES.

. Numerical example

We consider a multi-agent system consisting of 3 discrete-time oscillators whose dynamics is given by:1 :

z i (t + 1) = Rz i (t) + u i (t), i = 1, 2, 3 (4.6)
where

z i (t) ∈ R 2 , u i (t) ∈ R 2 and R = cos(ϕ) -sin(ϕ) sin(ϕ) cos(ϕ) with ϕ = π 6 .
The input u i (t) is used for synchronization purpose and is based on the available information at time t. There exist 3 communication channels between agent 1 and agent 2 (channel 1), 2 and 3 (channel 2) and 1 and 3 (channel 3). At each instant, only one of these channels is active and the active channel is selected by form V (q, x) = x T P q x where P q is a positive definite symmetric matrix. The conditions in Theorem 4.2.2 translate into the following linear matrix inequalities:

I 4 ≤ P q , q ∈ Q A ⊤ i P q ′ A i ≤ P q , q ∈ Q, i ∈ Σ, q ′ ∈ δ(q, i) \ F A ⊤ i P q ′ A i ≤ ρ 2 P q q ∈ Q, i ∈ Σ, q ′ ∈ δ(q, i) ∩ F
By solving these 16 LMIs, we find for ρ = 0.96 :

P q 0 = 1.98I 2 0.98I 2 0.98I 2 1.98I 2 , P q 1 = 2.26I 2 0.99I 2 0.99I 2 1.98I 2 , P q 2 = 1.98I 2 0.99I 2 0.99I 2 2.26I 2 , P q 3 = 2.22I 2 1.22I 2 1.22I 2 2.22I 2 .
From Theorem 4.2.2, we get that the switched system (A, B) is GUES which means the oscillators synchronize well after sufficient time.

We now consider the following scenario: for the first 50 time units, the communication channel 1 is constantly active, then at t = 50 a switch occurs and for the next 50 time units the channel 2 is active, then at t = 100 another switch occurs and the communication channel 3 stays active for the next 50 time units. After t = 150, the switching signal randomly activates channel 1 and channel 2 with equal probability so that the accepting state q 0 is visited infinitely often. The simulation results are shown in Figure 4.4. It is interesting to remark that when the switching signal remains constant the synchronization error does not go to zero, however after t = 150, when q 0 is visited more frequently, the synchronization error starts to converge towards zero. As expected, the Lyapunov function V (q t , x(t)) is non-increasing and, as soon as the state q 0 is visited frequently enough, it starts approaching zero.

. Convergence rate characterization

In this section, we introduce a similar notion to the SJSR and we establish several of its properties. Before we introduce that quantity, let us begin by introducing some notions. In this section, we assume that the automaton B is a DBA. Given a set of matrices A = {A 1 , • • • , A m } and a Büchi automaton B = (Q, Σ, δ, Q 0 , F ). Let G B be the labeled graph obtained from B as following: The nodes of G B are V = Q, the labels L = Σ = {1, • • • , m}, and the set of edges is E = {(q, l, p) |q, p ∈ Q, l ∈ Σ, p = δ(q, l) }. Let ρ(A, G B ) be the CJSR of (A, G B ). By the CJSR of (A, B) we refer to the quantity ρ(A, B) = ρ(A, G B ). Let us denote by Θ B the set of switching sequences θ such that there exists a sequence of states

V(q t ,x(t)) p 0 p 1 . . . such that p t+1 = δ(p t , θ(t)) for all t ∈ N. Let us remark that all elements of Lang(B) belong to Θ B .

The following Lemma relates this notion to trajectories of (2.6).

Lemma 4.3.1. For all ρ > ρ(A, B), there exists a C ≥ 1 such that:

∥x(t, x 0 , θ)∥ ≤ Cρ t ∥x 0 ∥, ∀x 0 ∈ R n , θ ∈ Θ B , t ∈ N.
Proof. This is a direct consequence of [60, Theorem 1.1] after scaling the matrices in A by 1 ρ .

The latter inequality happens to be conservative in the case of switching sequences generated by a Büchi automaton B. Therefore, to better estimate the convergence rate of such systems, we introduce in the next section a new spectral

CONVERGENCE RATE CHARACTERIZATION

61

characteristic specific to switched linear systems driven by ω-regular switching sequences.

. The ω-RJSR

In this section, we introduce the ω-Regular Joint Spectral Radius and establish several of its properties. Definition 4.3.2. Let ρ > ρ(A, B), the ω-Regular Joint Spectral Radius relative to (A, B, ρ) (ρ-ω-RJSR for short) is defined as

λ(A, B, ρ) = lim sup k→+∞   sup θ∈Lang(B) A θ,τ θ k ρ τ θ k 1/k   . (4.7)
To better understand the characteristics of the ρ-ω-RJSR, we are going to analyze some properties of the function λ(A, B, •). Proof. This is straightforward from the equivalence of norms in a finite dimensional subspace.

(A, B) < ρ 1 ≤ ρ 2 , λ(A, B, ρ 2 ) ≤ ρ 1 ρ 2 1 M λ(A, B, ρ 1 ) (4.8)
where M is the same as in Lemma 4.1.1.

Proof. Let ρ > ρ(A, B), from Lemma 4.3.1, we get that there exists

C 1 ≥ 1 such that 0 ≤ A θ,t ρ t ≤ C 1 , ∀θ ∈ Θ B , ∀t ∈ N. (4.9)
Using the fact that Lang(B) ⊆ Θ B , we get that

0 ≤ A θ,t ρ t ≤ C 1 , ∀θ ∈ Lang(B), ∀t ∈ N. (4.10)
By considering t = τ θ k , raising to the power 1/k and taking the supremum over all switching signals in Lang(B), we find

0 ≤ sup θ∈Lang(B) A θ,τ θ k ρ τ θ k 1/k ≤ C 1/k 1 .

CHAPTER 4. ω-REGULAR LANGUAGE

Taking the lim sup of all terms yields λ(A, B, ρ) ∈ [0, 1]. Now, let us consider ρ(A, B) < ρ 1 ≤ ρ 2 . From (4.1), it follows that τ θ k ≥

k-|Q| M . Then, we have for all k ≥ 1 and for all θ ∈ Lang(B)

A θ,τ θ k ρ τ θ k 2 = A θ,τ θ k ρ τ θ k 1 ρ 1 ρ 2 τ θ k ≤ A θ,τ θ k ρ τ θ k 1 ρ 1 ρ 2 k-|Q| M .
Raising to the power 1/k and taking the supremum over all switching signals in

Lang(B) yields sup θ∈Lang(B) A θ,τ θ k ρ τ θ k 2 1/k ≤ sup θ∈Lang(B) A θ,τ θ k ρ τ θ k 1 1/k ρ 1 ρ 2 k-|Q| kM .
Now we take the lim sup of both terms and we get (4.8), which implies that ρ → λ(A, B, ρ) is non-increasing. Now, let us assume that there exists

ρ 2 > ρ(A, B) such that λ(A, B, ρ 2 ) = 1. It follows from (4.8) that for all ρ 1 ∈ (ρ(A, B), ρ 2 ), λ(A, B, ρ 2 ) < λ(A, Bρ 1 ), which contradicts the fact that λ(A, B, ρ 1 ) ∈ [0, 1]. Hence, λ(A, B, ρ) ∈ [0, 1) for all ρ > ρ(A, B).
In order to get rid of the dependence of ρ in the ρ-ω-RJSR, it is natural to introduce the following definition. Since by Proposition 4.3.4, λ(A, B, •) is bounded and non-increasing in ρ, the right limit at ρ(A, B) in (4.11) exists and the ω-RJSR is well-defined. We can now show some of its properties. Proposition 4.3.6. The ω-RJSR enjoys the following properties: (i) λ(A, B) belongs to [0, 1] and is independent of the choice of the norm; where the second equality comes from the property of the CJSR, ρ(KA, B) = |K|ρ(A, B), see e.g. [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF]. Furthermore, from (4.7), one can deduce that for all ρ > ρ(A, B), λ(KA, B, |K|ρ) = λ(A, B, ρ), therefore λ(KA, B) = λ(A, B).

(ii) For all K ∈ R, K ̸ = 0, we have λ(KA, B) = λ(A, B).
Let us remark that while the CJSR ρ(A, B) belongs to R + 0 , the ω-RJSR λ(A, B) is always in [0, 1]. Intuitively, while the CJSR provides an estimate of the contraction rate (when ρ(A, B) < 1) or of the expansion rate (when ρ(A, B) > 1) of the system state at each time step for constrained switching signals, the ω-RJSR measures how much additional contraction is obtained each time the set of accepting states F is visited. Theorem 4.3.7 in the next section provides theoretical ground to this interpretation.

. Stability and ω-RJSR

In this section, we show how the ρ-ω-RJSR relates to stability properties of constrained switched linear systems. In particular, we show how the ρ-ω-RJSR allows us to compute bounds on the accepting rate ensuring stability. The next result clarifies the relationship between the ρ-ω-RJSR and the behaviour of the trajectories of (2.6).

Theorem 4.3.7. For all ρ > ρ(A, B), for all λ ∈ (λ(A, B, ρ), 1], there exists

C ≥ 1 such that ∥x(t, x 0 , θ)∥ ≤ Cρ t λ κ θ (t) ∥x 0 ∥, ∀x 0 ∈ R n , θ ∈ Lang(B), t ∈ N. (4.12)
Conversely, if the matrices in A are invertible, if there exists C ≥ 1, ρ ≥ 0 and λ ∈ [0, 1] such that (4.12) holds, then either ρ > ρ(A, B) and λ ≥ λ(A, B, ρ), or ρ = ρ(A, B) and λ ≥ λ(A, B).

Proof. We start by proving the direct result. Let ρ > ρ(A, B) and λ ∈ (λ(A, B, ρ), 1]. By definition of λ(A, B, ρ), there exists k 0 ≥ 1 such that sup θ∈Lang(B)

A θ,τ θ k ρ τ θ k 1/k ≤ λ, ∀k ≥ k 0 .
It follows that

A θ,τ θ k ≤ ρ τ θ k λ k , ∀θ ∈ Lang(B), ∀k ≥ k 0 . (4.13)
Then, let C 1 ≥ 1 be such that (4.10) holds. In particular, for t = τ θ k and for θ ∈ Lang(B), we obtain from (4.10) that

A θ,τ θ k ≤ C 1 ρ τ θ k , ∀θ ∈ Lang(B), ∀k ∈ N. (4.14)
Then, let C 2 = C 1 λ -k 0 , then C 2 ≥ 1 and it follows from (4.13) and (4.14) that

A θ,τ θ k ≤ C 2 ρ τ θ k λ k , ∀θ ∈ Lang(B), ∀k ∈ N. (4.15) 64 CHAPTER 4. ω-REGULAR LANGUAGE Let θ ∈ Lang(B), t ∈ N, and k = κ θ (t), we have A θ,t = A θ ′ ,t-τ θ k A θ,τ θ k where θ ′ ∈ Θ B is given by θ ′ (s) = θ(τ θ k + s
), for all s ∈ N. By (4.9), we get that

A θ ′ ,t-τ θ k ≤ C 1 ρ t-τ θ k . (4.16)
Then, let C = C 1 C 2 , by (4.15) and (4.16) we get

A θ,t ≤ A θ ′ ,t-τ θ k A θ,τ θ k ≤ Cλ κ θ (t) ρ t .
Hence, (4.12) holds.

We now prove the converse result. By definition of induced matrix norm, (4.12) is equivalent to the following:

∥A θ,t ∥ ≤ Cρ t λ κ θ (t) , ∀θ ∈ Lang(B), ∀t ∈ N. (4.17)
Since λ ∈ [0, 1] and κ θ (t) ∈ N we also have

∥A θ,t ∥ ≤ Cρ t , ∀θ ∈ Lang(B), ∀t ∈ N. (4.18)
Now, let θ ∈ Θ B and t ∈ N. From Assumption 4.1.2, there exists θ ′ ∈ Lang(B) and t 0 ≤ |Q| such that θ(s) = θ ′ (t 0 + s), for all s = 0, . . . , t. Then, since all matrices in A are invertible we get

A θ,t = A θ ′ ,t+t 0 A -1 θ ′ ,t 0 . Let us denote D = max A∈A ∥A -1 ∥, then ∥A θ,t ∥ ≤ ∥A θ ′ ,t+t 0 ∥ ∥A -1 θ ′ ,t 0 ∥ ≤ ∥A θ ′ ,t+t 0 ∥ D t 0 .
From (4.18), we then get that

∥A θ,t ∥ ≤ Cρ t+t 0 D t 0 ≤ C ′ ρ t with C ′ = C max(1, ρD) |Q| . Hence, for all t ∈ N, sup θ∈Θ B A θ,t ≤ C ′ ρ t .
Raising both side of the inequality to the power 1 t and taking the limit one gets ρ(A, B) ≤ ρ. Considering (4.17) and fixing t = τ θ k , we have

∥A θ,τ θ k ∥ ≤ Cρ τ θ k λ k , ∀θ ∈ Lang(B), ∀k ∈ N which implies that ∥A θ,τ θ k ∥ ρ τ θ k 1/k ≤ C 1/k λ, ∀θ ∈ Lang(B), ∀k ≥ 1. (4.19)
If ρ > ρ(A, B), taking the supremum over all switching signals in Lang(B) and the lim sup as k goes to infinity yields λ(A, B, ρ) ≤ λ. If ρ = ρ(A, B), then for all ρ ′ > ρ(A, B), (4. [START_REF] Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF] gives

∥A θ,τ θ k ∥ ρ ′τ θ k 1/k ≤ C 1/k λ, ∀θ ∈ Lang(B), ∀k ≥ 1.
Then, it follows that for all ρ ′ > ρ(A, B), λ(A, B, ρ ′ ) ≤ λ and hence by taking the limit we get λ(A, B) ≤ λ.

The previous theorem provides a bound on the growth of the state and can be used to derive conditions for stabilization of system (2.6) using ω-regular switching sequences with a minimal accepting rate as shown in the following result.

Corollary 4.3.8. Let θ ∈ Lang(B), if there exists ρ > ρ(A, B) such that γ θ > -ln(ρ) ln(λ(A,B,ρ)) , then lim t→+∞ ∥x(t, x 0 , θ)∥ = 0, ∀x 0 ∈ R n . (4.20)
Proof. If γ θ > -ln(ρ) ln(λ(A,B,ρ)) , then there exists λ ∈ (λ(A, B, ρ), 1) such that γ θ > -ln(ρ) ln(λ) and ϵ > 0 such that ϵ < γ θ + ln(ρ) ln(λ) . Then, from the definition of accepting rate, there exists t 0 ∈ N such that

κ θ (t) t > γ θ - ϵ 2 , ∀t ≥ t 0 .
From Theorem 4.3.7, there exists C ≥ 1 such that for all x 0 ∈ R n , for all t ≥ t 0 .

∥x(t, x 0 , θ)∥ ≤ Cρ t λ κ θ (t) ∥x 0 ∥ ≤ Cρ t λ (γ θ -ϵ 2 )t ∥x 0 ∥ ≤ Cρ t λ (- ln(ρ) ln(λ) + ϵ 2 )t ∥x 0 ∥ = Cλ ϵ 2 t ∥x 0 ∥, from which (4.20) follows.
As a result of the previous corollary, even if the switched system is unstable for constrained switching (i.e. if ρ(A, B) > 1), it can still be stabilized by visiting the set F frequently enough. From Lemma 4.1.1 we know that the accepting rate always satisfies γ θ ≤ M . Consequently, stabilization in this scenario is only possible if there exists ρ > ρ(A, B) such that -ln(ρ) ln(λ(A,B,ρ)) < M . In this section, we present an approach for computing upper bounds of the ρ-ω-RJSR using a combination of Lyapunov and automata theoretic techniques. Our approach is mainly based on the following result: Theorem 4.3.9. If there exist V : Q × R n → R + 0 , α 1 , α 2 , ρ > 0 and λ ∈ [0, 1] such that the following inequalities hold true for every

x ∈ R n α 1 ∥x∥ ≤ V (q, x) ≤ α 2 ∥x∥, q ∈ Q (4.21) V (q ′ , A i x) ≤ ρV (q, x), q ∈ Q, i ∈ Σ, δ(q, i) = q ′ / ∈ F (4.22) V (q ′ , A i x) ≤ ρλV (q, x), q ∈ Q, i ∈ Σ, δ(q, i) = q ′ ∈ F (4.23)
then the bound (4.12) holds. Conversely, if the matrices in A are invertible, and the bound (4.12) holds for some ρ > 0, λ ∈ [0, 1] and C ≥ 1, then there exists a function V : Q × R n → R + 0 such that the inequalities (4.21), (4.22) and (4.23) are satisfied.

Proof. Let us consider an initial condition x 0 ∈ R n and a switching signal θ ∈ Lang(B), let q 0 q 1 q 2 . . . be the accepting run associated with θ. We denote x(•) = x(•, x 0 , θ) and we define the function W :

N → R + 0 by W (t) = V (qt,x(t))
ρ t for all t ∈ N. It follows from (4.22) and (4.23) that W (t + 1) ≤ W (t) for all t ∈ N. From (4.23), we get that ∀k ≥ 1, W (τ θ k ) ≤ λW (τ θ k -1). From the monotonicity of W , we deduce that

∀k ≥ 1, W (τ θ k ) ≤ λW (τ θ k-1 ).
By induction on k, we get that

∀k ∈ N, W (τ θ k ) ≤ λ k W (0). Now let t ∈ N, and let k ∈ N such that t ∈ [τ θ k , τ θ k+1
), then the accepting index is κ θ (t) = k. We get from the monotonicity of W that W (t) ≤ λ κ θ (t) W (0). Finally from (4.21), we get, for all t ∈ N,

x 0 ∈ R n that ∥x(t)∥ ≤ ρ t α 1 W (t) ≤ ρ t α 1 λ κ θ (t) W (0) ≤ α 2 α 1 ρ t λ κ θ (t) ∥x 0 ∥.
Hence, the bound (4.12) holds with C = α 2 α 1 . The proof of the converse result follows the same proof procedure as in [3,Theorem 3] with a slight modification, that is the scale of the matrices in A by ρ > ρ(A, B).

As a direct consequence of the previous result and Theorem 4.3.7 we have the following corollary. 4.23) can straightforwardly be translated into LMIs for which efficient solvers exist. However, the tightness of the conditions in Theorem 4.3.9 is lost when constraining the Lyapunov functions to be quadratic.

. Numerical Example

We consider a multi-agent system consisting of m discrete-time oscillators with identical dynamics given by:

z i (t + 1) = Rz i (t) + u i (t), i = 1, • • • , m
where z i (t) ∈ R 2 , u i (t) ∈ R 2 and R = µ cos(ϕ) -sin(ϕ) sin(ϕ) cos(ϕ) with ϕ = π 6 , µ = 1.02. The input u i (t) is used for synchronization purpose and is based on the available information at time t.

To exchange information, the agents are communicating over a network with ring topology. More precisely, there exist m communication channels in the network: one channel between agent i and agent i + 1, for i = 1, . . . , m -1, and one channel between agent m and agent 1. Hence, the vertices of the undirected communication graph are given by the agents of the network V = {1, . . . , m} and the set of edges are given by the communication channels E = {e 1 , . . . , e m } ⊆ V × V where:

e i = (i, i + 1) if i = 1, . . . m -1 (m, 1) if i = m
At each instant, only one of these channels is active and the active channel is selected by a switching signal θ : N → Σ = {1, • consider a switching signal with p = 0.98, The result of the simulation is shown in Figure 4.7. We can check that γ θ < 0.22 and that the system does not stabilize.

. Conclusion

In this chapter, we established some results concerning the stability of discretetime switched systems where the switching signal is generated by a Büchi automaton. We developed sufficient conditions for attractivity and uniform stability for this type of systems and also of uniform exponential stability when the considered Büchi automaton is deterministic, all based on Lyapunov arguments. Moreover, we proved that these conditions are also necessary for a subclass of such systems with invertible matrices.

In addition, we introduced the ρ-ω-RJSR, a special notion of joint spectral radius for discrete-time switched linear systems driven by infinite sequences generated by a given DBA. We have also shown its relation to stability properties of switched systems. We proposed a method based on Lyapunov functions and automata theoretic techniques to compute upper-bounds on this quantity. Finally, we illustrated our results with some applications based on oscillators.

In the next chapter we consider an application to observer design for switched systems. The approach is based on the results of this chapter. In this chapter, we consider the problem of designing asymptotic observers for discrete-time switched linear systems. For this class of systems, there exists a diversity of observability notions depending on whether the switching signal is known [START_REF] Sam Ge | Reachability and controllability of switched linear discrete-time systems[END_REF][START_REF] Babaali | Pathwise observability and controllability are decidable[END_REF][START_REF] Baştug | Reachability and observability reduction for linear switched systems with constrained switching[END_REF] or need to be estimated [START_REF] Babaali | Observability of switched linear systems[END_REF][START_REF] De Santis | Observability of discrete time linear switching systems[END_REF]. In our work, we assume that the switching signal is known. In that context, there have been several works for characterizing observable or reconstructible switching sequences [START_REF] Sam Ge | Reachability and controllability of switched linear discrete-time systems[END_REF][START_REF] Trenn | Observability and determinability characterizations for linear switched systems in discrete time[END_REF], i.e. finite switching sequences that make it possible to estimate the initial or the current state of the system, respectively. Relevant work also includes the characterization of observability for continuous-time switched systems with jumps at the switching instants [START_REF] Xie | Necessary and sufficient conditions for controllability and observability of switched impulsive control systems[END_REF][START_REF] Tanwani | Observability for switched linear systems: characterization and observer design[END_REF][START_REF] Tanwani | Observability implies observer design for switched linear systems[END_REF], which can be seen as a generalization of discrete-time switched systems.

The design of asymptotic observers itself has also been considered in several papers. Observers that are convergent for arbitrary switching sequences have been designed in [7,[START_REF] Daafouz | A poly-quadratic stability based approach for linear switched systems[END_REF] using mode dependent observer gains and quadratic or polyquadratic Lyapunov functions. Note that this design requires that the dynamics in each mode is observable since constant switching signals are allowed. The case where individual dynamics are unobservable but some observable (or reconstructible) switching sequences exist is also of interest. To be able to estimate the state of the system, it is necessary that the switching signal contains at least one reconstructible sequence. Actually, to be able to design observers that are robust to unmodelled disturbances or to measurement noises, it is necessary to consider switching signals containing an infinite number of reconstructible sequences.

The contributions of this chapter are multiple and can be summarized as follows. Firstly, we provide a formal characterization of the set of switching signals containing an infinite number of reconstructible sequences. More precisely, we show that this set coincides with the language of a DBA whose construction is presented in the sequel. We then consider the problem of designing an asymptotic observer. We propose a switched observer with an internal discrete state whose dynamics is given by the transition map of the DBA. Building on the results of Section 4, we then establish sufficient conditions to design the observer gains such that the resulting observer is convergent for all switching signals whose occurrence rate of resconstructible sequences is higher than a certain tunable parameter. In the case where all state matrices of the switched system are invertible, we present an explicit construction of suitable observer gains, showing that the proposed ob-server structure is universal in the sense that one can always find an observer of the proposed form. We also show an alternative design based on LMIs which are shown to always admit a feasible solution under the same invertibility assumption. We then show how to extend our approach to take into account additional constraints on the switching signals. Our theoretical contributions are illustrated using a simple example. To show the effectiveness of the proposed methodology, we consider a case study in which we design an observer for a multicellular converter [START_REF] Jérémy Van Gorp | Diagnostic et observation d'une classe de systèmes dynamiques hybrides. Application au convertisseur multicellulaire série. Theses[END_REF][START_REF] Van Gorp | Hybrid observer for the multicellular converter*[END_REF].

The most related works in the literature are the following. In [START_REF] Lee | Detectability and stabilizability of discrete-time switched linear systems[END_REF], a switched observer is presented where the observer gains at some instant t depends on the sequence of modes at time t -L, . . . , t. Similar to our construction, this can be seen as a switched observer with an internal discrete state though the discrete dynamics is different from that presented in this work. In [START_REF] Lee | Detectability and stabilizability of discrete-time switched linear systems[END_REF], the design of the observer gains is done by solving LMIs. However, contrarily to our approach, there is no clear characterization of the cases when the proposed design can be successful. Another approach can be to consider a switched linear system as a time-varying linear system and to apply associated observer design techniques, such as Kalman filters [START_REF] Zhang | On stability of the Kalman filter for discrete time output error systems[END_REF]. Alternatively, the design proposed in [START_REF] Tanwani | Observability for switched linear systems: characterization and observer design[END_REF] for observers of continuous-time switched linear systems with jumps at the switching instants can be adapted to discrete-time systems. The observers designed in [START_REF] Zhang | On stability of the Kalman filter for discrete time output error systems[END_REF] and [START_REF] Tanwani | Observability for switched linear systems: characterization and observer design[END_REF] can be shown to be convergent for switching signals containing an infinite number of reconstructible sequences. However, their gains have to be computed online. In comparison, the gains of our observer are computed offline, resulting in reduced requirements for its implementation.

This chapter represents the results of the following paper:

Georges Aazan, Antoine Girard, Luca Greco, and Paolo Mason. An Automata Theoretic Approach to Observer Design for Switched Linear Systems. Submitted to Automatica, 2023. This chapter is organized as follows. Section 5.1 presents the problem under consideration and introduces preliminary results on observability of switched systems and on DBAs. Section 5.2 gives a construction of a DBA generating switching signals containing an infinite number of reconstructible sequences. Section 5.3 presents the structure of the switched observers and the methods to design its gains. It also shows an illustration of a simple example while Section 5.4 deals with the application to a multicellular converter.

. Observability of discrete-time switched systems

Let us consider a discrete-time switched linear system described by the following equation:

x(t + 1) = A θ(t) x(t), y(t) = C θ(t) x(t) (5.1)
where x(t) ∈ R n is the state of the system, θ : N → I is the switching signal and I is the set of modes, I = {1, . . . , m}, the state matrices belong to the set A = {A 1 , . . . , A m } ⊆ R n×n . The output vector is y(t) ∈ R p and the output matrices are in the set C = {C 1 , . . . , C m } ⊆ R p×n . Our goal in this chapter is to propose a general procedure for designing asymptotic observers for system (5.1) capable of reconstructing the state x from the knowledge of the switching signal θ and of the output y.

By following [START_REF] Sun | Switched linear systems: control and design[END_REF], we recall a definition and a characterization of observability for the switched system (5.1). Definition 5.1.1. The switched system (5.1) is observable (resp., reconstructible), if there exist a switching signal θ and k ∈ N such that the knowledge of the output sequence y(0), . . . , y(k) is sufficient to determine the initial condition x 0 (resp., the state x(k)). We refer to the finite sequence of modes θ(0), . . . , θ(k) as an observable (resp., reconstructible) sequence.

We recall that an observable system is also reconstructible, while the opposite is true if all the matrices in A are invertible. We define the observability matrix corresponding to a sequence of modes i 1 , . . . , i j ∈ I, as

Ω(i 1 , . . . , i j ) = C ⊤ i 1 A ⊤ i 1 C ⊤ i 2 • • • A ⊤ i 1 • • • A ⊤ i j-1 C ⊤ i j ⊤ .
Necessary and sufficient conditions for observability and reconstructibility are recalled in the following theorem. rank Ω(i 1 , . . . , i j ) = n.

(5.

2)

It is reconstructible if and only if

ker Ω(i 1 , . . . , i j ) ⊆ ker(A

i 1 • • • A i j ). ( 5

.3)

As far as the design of asymptotic observers is concerned, it is sufficient to consider the notion of reconstructibility. However, let us remark that the conditions in (5.2) and (5.3) are equivalent if all matrices in A are invertible.

. Reconstructible sequences

In this section, we present a construction of a deterministic Büchi automaton whose language consists of switching signals that contain an infinite number of reconstructible sequences. Let us introduce the following notations:

Given a word w ∈ Σ * , we have that the length of w, denoted by |w| is n if w = σ 1 • • • σ n , or 0 if w = ϵ where ϵ is the empty word. For w ∈ Σ * , we say that w ′ is a prefix of w if it belongs to the set P(w) = {w ′ ∈ Σ * | ∃w ′′ ∈ Σ * , w = w ′ w ′′ }. Similarly, we say that w ′ is a suffix of w if it belongs to the set S(w) = {w ′ ∈ Σ * | ∃w ′′ ∈ Σ * , w = w ′′ w ′ }. We stress that, in the previous definitions, w ′ and w ′′ can be the empty word. Let S 1 , S 2 ⊆ Σ * , then the set S 1 S 2 is the set of words consisting of the concatenation of words of S 1 and S 2 , i.e. S 1 S 2 = {w = w 1 w 2 | w 1 ∈ S 1 , w 2 ∈ S 2 }. Let S ⊆ Σ * \ {ϵ}, then S ω is the set of words consisting of the concatenation of an infinite sequence of words of S, i.e.

S ω = {w 1 w 2 • • • | w i ∈ S, i = 1, . . .}.

. Construction of the automaton

Using Theorem 5.1.2, one can efficiently compute reconstructible sequences up to a specific length for a switched linear system given by (A, C) and described by equation (5.1). The set of reconstructible sequences of length j ≥ 1 is defined by

O j = σ 1 • • • σ j ∈ I * ker Ω(σ 1 , . . . , σ j ) ⊆ ker(A σ 1 • • • A σ j )
Moreover, the set of reconstructible sequences of length up to k ≥ 1 is given by

O [k] = j=1,...,k O j .
It is easy to see that if w is a reconstructible sequence, then any sequence containing w as a subsequence is also reconstructible. Therefore it is useful to define the following reduced set of reconstructible sequences:

O ′[k] = w ∈ O [k] ∄w 1 , w 2 ∈ I * , w ′ ∈ O [k] \ {w} s.t. w = w 1 w ′ w 2 .
Intuitively, O ′[k] consists of minimal reconstructible sequences, i.e. reconstructible sequences that do not contain reconstructible subsequences. It is easy to see that for any

k 1 ≤ k 2 , O ′[k 1 ] ⊆ O ′[k 2 ] . Let us consider k ≥ 1, such that O ′[k] ̸ = ∅.
Our goal is to generate words containing an infinite number of reconstructible sequences in O ′ [k] . To this aim, we provide Algorithm 1 which outputs a DBA B k = (Q, I, δ, q 0 , F ) generating

Q := Q ∪ {σ} 7: δ(ϵ, σ) := σ 8:
end if 9: end for 10: for σ ) ω . The main idea is to build an automaton that visits an accepting state each time a reconstructible sequence occurs. We note that in this automaton the states are words in I * , i.e. Q ⊆ I * .

1 • • • σ l ∈ O ′[k] , l ≥ 2 do 11: if l = 2
Q := Q ∪ {σ 1 • • • σ j } 16: δ(σ 1 • • • σ j-1 , σ j ) := σ 1 • • • σ j 17: end for 18: δ(σ 1 • • • σ l-1 , σ l ) := ϵ 19: end if 20: end for 21: W := {(w, σ) ∈ Q × I | (w, σ) / ∈ δ -1 (Q)} 22: for (w, σ) ∈ W do 23: if ∃w s ∈ S(w) s.t. w s σ ∈ O ′[k]
Algorithm 1 is comprised of three parts:

In the first part, from step 2 to step 9, we check if there are reconstructible sequences of length 1. If it is the case we create a self transition to the accepting state, otherwise we add a new state and we define a transition from the accepting state to the newly added state.

In the second part, from step 10 to step 20, we consider reconstructible sequences w in O ′[k] of length l ≥ 2. We add to the set Q all the prefixes of w, except w itself, and we define the corresponding transitions between consecutive prefixes. The last transition, which happens when the reconstructible sequence w has occurred, leads to the accepting state.

Finally, in the third part, from step 21 to step 28, we focus on the couples (w, σ) ∈ Q × I for which no transition is defined yet. In this case, if there exists a suffix w s of w such that w s σ ∈ O ′[k] , then we add a transition from w to the accepting state. Otherwise, we look for the longest suffix v of wσ such that v ∈ Q and we define a transition toward this state.

Example 5.2.1. Consider the switched linear system with two modes, i.e. I = {1, 2}, defined by the set of matrices

A = {A 1 , A 2 }, C = {C 1 , C 2 },
where Applying Algorithm 1, we obtain the DBA represented in Figure 5.2.1 where transitions are represented with arrows of different types depending on which phase of the algorithm they have been added.

A 1 = I 3 , A 2 = 1.5 ×   0 0 1 0 1 0 1 0 0   , C 1 = (1 0

. Language characterization

In this subsection, we prove that Lang(

B k ) = (I * O ′[k]
) ω . For that purpose, we make use of the following three lemmas. Lemma 5.2.2. Let B k be the Büchi automaton constructed using Algorithm 1 for some k ≥ 1, then B k is deterministic and any state of B k is reachable from any other state.

Proof. Algorithm 1 univocally builds the application δ for each pair of (w, σ) ∈ Q × I, hence the ensuing Büchi automaton is deterministic. Also, it is apparent from the couples of lines 6, 7 and 15, 16 that, whenever a new state is added to the set Q a chain of transitions from the accepting state to such a state is also created. As a consequence, all the states of B k are reachable from the accepting state. Furthermore, the last transition of any such chain, see steps 4, 12 and 18, brings the run back to the accepting state.

∈ O ′[k] , M ≤ λ 2 P w . Proof. Let w ∈ O ′[k] , w = σ 1 • • • σ l ,
then from (5.12)

P w =P σ 1 •••σ l =ρ 2l A -⊤ σ l • • • A -⊤ σ 1 M A -1 σ 1 • • • A -1 σ l + ρ 2l γλ 2 A -⊤ σ l • • • A -⊤ σ 1 C ⊤ σ 1 C σ 1 A -1 σ 1 • • • A -1 σ l + ρ 2(l-1) γλ 2 A -⊤ σ l • • • A -⊤ σ 2 C ⊤ σ 2 C σ 2 A -1 σ 2 • • • A -1 σ l + • • • + ρ 2 γλ 2 A -⊤ σ l C ⊤ σ l C σ l A -1 σ l .
Then, it follows that

P w ≥ ρ 2l γλ 2 A -⊤ σ l • • • A -⊤ σ 1 W ⊤ σ 1 •••σ l W σ 1 •••σ l A -1 σ 1 • • • A -1 σ l .
Then, from Lemma 5.3.4 and (5.10), we get

P w ≥ ρ 2l λ 2 A -⊤ σ l • • • A -⊤ σ 1 M A -1 σ 1 • • • A -1 σ l ≥ 1 λ 2 M.
Let us now define the matrices L (w,σ) ∈ R n×p , for all w ∈ I * , σ ∈ I as follows:

L (w,σ) = A σ P -1 w C ⊤ σ γλ 2 I p + C σ P -1 w C ⊤ σ -1
.

(5.13)

Then, the following fundamental property holds:

Lemma 5.3.8. For all w ∈ I * , σ ∈ I,

(A σ -L (w,σ) C σ ) ⊤ P wσ (A σ -L (w,σ) C σ ) ≤ ρ 2 P w .
Proof. From (5.12), we get that for all w ∈ I * , σ ∈ I,

1 ρ 2 A ⊤ σ P wσ A σ = P w + 1 γλ 2 C ⊤ σ C σ .
Then, it follows that

ρ 2 A -1 σ P -1 wσ A -⊤ σ = P w + 1 γλ 2 C ⊤ σ C σ -1 = P -1 w -P -1 w C ⊤ σ γλ 2 I p + C σ P -1 w C ⊤ σ -1 C σ P -1 w (5.14) = P -1 w -A -1 σ L (w,σ) C σ P -1 w (5.15)
Additionally, if S is itself generated by a DBA B, i.e. S = Lang(B), then we can use the following approach. We start by computing a DBA Bk such that Lang( Bk ) = Lang(B k ) ∩ S. This is always possible, following the approach described in [START_REF] Baier | Principles of model checking[END_REF]Lemma 4.59 and Theorem 4.56].

One can then adapt the approach described in Subsection 5.3.2 with the DBA Bk instead of B k . In that case, LMIs similar to (5.20) and (5.21) need to hold for all transitions to nonaccepting states and to accepting states, respectively. For the same values of ρ and λ, we also computed the observer gains using the explicit design presented in Subsection 5.3.1. For the chosen value of ρ and λ, we have ln(ρ) -ln(λ) = 0.18. We first consider a switching signal consisting of successions of a random reconstructible sequence in O ′[k] and of a random mode in I. Therefore, we have by construction that the accepting rate of this switching signal satisfies γ θ ≥ 0.25 > 0.18. Then, from Proposition 5.3.1, it follows that the observer asymptotically converges. For both types of observers, this is confirmed by the simulations shown in Figure 5.2. This figure shows the switching signal θ, the discrete state of the switched observer q given by the discrete dynamics in (5.4). The return instants (i.e. instants where q visits the accepting state ϵ) are indicated with red circles. We also show the evolution in logarithmic scale of the norm of the estimation error e for both types of gains. We can check that the observer converges faster with the explicit design than with the LMI-based design. Actually, the convergence rate of the observer designed using LMIs is quite close to the theoretical guarantees provided by Proposition 5.3.1, which essentially predicts a contraction of the estimation error by a factor λ between each return instants. Now we consider the case when the system is driven by a switching signal with low accepting rate. For this purpose, let us consider a periodic switching signal constructed as follows: between instants t = 0 and t = 30 mode 2 is activated, and between t = 31 and t = 40 mode 1 is activated and the rest is constructed using periodicity. The discrete state of the observer q(t) visits the accepting state twice over each period. Therefore, this switching signal satisfies γ θ = 0.05 < 0.18. Simulations for both types of observers are shown in Figure 5.3. One can check on these simulations that the observer diverges for both types of gains. This shows, as expected, that the occurrence of reconstructible sequences must be frequent enough in order to make the observer converge. -ln(λ) : top -switching signal θ; center -discrete state of the switched observer q, red circles indicate return instants; bottom -norm of the estimation error e in logarithmic scale for both type of gains.

CASE STUDY: THE MULTICELLULAR CONVERTER

. Case study: The multicellular converter

The field of power electronics has earned several insights in the last decades. A main branch of this field is that of energy conversion [START_REF] Erickson | Fundamentals of Power Electronics[END_REF]. It is known that the multicellular converter consists a vital example of this field. These circuits were introduced in the late 90s [START_REF] Meynard | French patent n 91, 09582 du 25 juillet 1991[END_REF], they involve several industrial applications [START_REF] Meynard | Multicell converters: basic concepts and industry applications[END_REF]. In this section we aim at the construction of a switched observer to estimate the voltage across the capacitors of a multicellular converter. The design is based on the construction of a Büchi automaton generating reconstructible sequences leading to the estimation.

Let us consider the circuit of the multicellular converter taken from [START_REF] Jérémy Van Gorp | Diagnostic et observation d'une classe de systèmes dynamiques hybrides. Application au convertisseur multicellulaire série. Theses[END_REF][START_REF] Van Gorp | Hybrid observer for the multicellular converter*[END_REF] and shown in Figure 5.4. This system is an example of switched dynamical systems due to several commutation cells in the circuit. The dynamics of this converter is described by the following equations:

E S n S j S 2 S 1 S n S j S 2 S 1 I L R V c n-1 V c j-1 V c 1 V s
İ = - R L I + E L S n - n-1 j=1 V c j L (S j+1 -S j ) Vc j = I c j (S j+1 -S j ), j = 1, . . . , n -1
where c j and V c j are the capacitance and the voltage of the j-th capacitor respectively, I is the current passing through the load consisting of the resistor R and the inductor L, E is the voltage of the source. S j ∈ {0, 1} is a binary signal corresponding to the j-th commutation cell. When S j = 1, the upper switch of the j-th cell is "on" and the lower switch is "off" and vice versa in the other case.

We consider the bijection between the set {0, 1} n and the set {1, . . . , 2 n } which maps the binary vector (S 1 , . . . , S n ) to θ = 1 + n-1 j=0 2 j S j+1 . Writing x = (V c 1 , . . . , V c n-1 , I) ⊤ ∈ R n , u = E, and assuming only y = I is measured, the system dynamics can be described by a continuous time switched system of the form: ẋ(t) = A θ(t) x(t) + B θ(t) u(t), y(t) = C θ(t) x(t) (5. Let us remark that the dynamics in all modes are unobservable. Hence, it is not possible to build an observer that is convergent for arbitrary switching signals. Additionally, the system is subject to the following constraint on the switching signal [START_REF] Jérémy Van Gorp | Diagnostic et observation d'une classe de systèmes dynamiques hybrides. Application au convertisseur multicellulaire série. Theses[END_REF][START_REF] Van Gorp | Hybrid observer for the multicellular converter*[END_REF]: only one commutation cell can be switched at a time. This constraint translates to some adjacency relations between modes described by the graph in Figure 5.5. When a mode change occurs in the switching signal θ, the new mode must be adjacent to the previous one. Our goal is to design an observer for this switched system with constrained switching. The approach presented in [START_REF] Jérémy Van Gorp | Diagnostic et observation d'une classe de systèmes dynamiques hybrides. Application au convertisseur multicellulaire série. Theses[END_REF][START_REF] Van Gorp | Hybrid observer for the multicellular converter*[END_REF] is similar to that of [START_REF] Tanwani | Observability for switched linear systems: characterization and observer design[END_REF] and requires computing the observer gains online.

As described in Subsection 5.3.3, we compute the set Õ′[k] of reconstructible sequences satisfying the switching constraints, which, for k = 3, contains 48 sequences. Then, we use Algorithm 1 to build the corresponding Büchi automaton B 3 . As (5.23) possesses a nonstrict common quadratic Lyapunov function (the energy of the system) and thanks to Remark 1, we can apply the explicit design of observer gains presented in Subsection 5.3.1 for ρ = 1 and λ = 0.1. Let us remark that switching sequences satisfying adjacency constraints can be generated using a DBA B (see e.g. [START_REF] Weiss | Automata based interfaces for control and scheduling[END_REF]). Then, as explained in Subsection 5.3.3, we can further compute the DBA B3 shown in Figure 5.6 and such that Lang( B3 ) = Lang(B 3 ) ∩ Lang(B). Then, we solve the corresponding LMIs (5.19), (5.20), (5.21) with ρ = 1 and λ = 0.1 to design observer gains.

Numerical simulations are shown in Figure 5.7. The figure shows the switching signal θ; the return instants (i.e. instants where q visits an accepting state) are indicated with red circles. We also show the evolution in logarithmic scale of the norm of the estimation error e for both designs. We can see again that the observer based on the explicit design converges faster than the one based on LMIs whose convergence rate is more consistent with the theoretical guarantees provided by Proposition 5.3.1.

We end this section by mentioning that in [START_REF] Jérémy Van Gorp | Diagnostic et observation d'une classe de systèmes dynamiques hybrides. Application au convertisseur multicellulaire série. Theses[END_REF][START_REF] Van Gorp | Hybrid observer for the multicellular converter*[END_REF], they consider a sampling period T = 1 ms. In that case, the state matrices of the sampled system are numerically close to singularity and thus Assumption 5.3.2 is not robustly satisfied. This results in the explicit design of Subsection 5.3.1 to be numerically ill-conditioned. In practice, due to numerical errors, the ensuing observer is divergent. However, it is important to remark that even in that case, the observer based on the LMI design still works smoothly.

. Conclusion

In this chapter, we presented an approach to design observers for discrete-time switched linear systems. Our approach combines automata theory, Lyapunov techniques and LMI-based design to synthesize switched observers. The most important feature of the proposed observer structure is that it is universal as we show that it is always possible to design observer gains that make this observer convergent. We have shown the effectiveness of our approach in a case study on multicellular converters.

-Conclusion and perspectives

Conclusion In this thesis, we have studied the stability of switched linear systems driven by ω-regular language. We first reviewed the definition and some properties of the joint spectral radius. Then we defined a special type of JSR specific to shuffled switched systems, the ρ-SJSR. This quantity intuitively measures how much the state of the system contracts each time the signal shuffles. We also showed how this notion relates to stability properties of the associated switched systems. Particularly, we showed that some switched systems that are unstable for arbitrary switching signals can be stabilized by using switching signals that shuffle sufficiently fast. The minimal shuffling rate required to stabilize the system is being related to ρ-SJSR. We then present several approaches to compute lower and upper bounds of the ρ-SJSR using tools such as the classical JSR, Lyapunov functions and finite state automata. Several tightness results of the bounds are established.

We also considered to the general case of an arbitrary ω-regular language and defined the ρ-ω-RJSR. Although its properties resemble well to those of the ρ-SJSR, their proofs require some new techniques and notions.

In addition, for ω-regular language driven systems, we provided sufficient and necessary conditions for stability based on a Büchi automaton. We showed a converse theorem for the sufficiency result when the dynamics are invertible.

Finally, we provided an application based on these results: the design of an asymptotic observer for switched systems. More precisely, these observers have an internal discrete state variable whose dynamics is given by the transition map of a Büchi automaton. This automaton is constructed based on computed reconstructible sequences. We then presented two approaches to design observer gains such that the observer is convergent for all switching signals belonging to a specific class. The first approach describes an explicit construction of the observer gains while the second one is based on linear matrix inequalities. For switched systems with invertible state matrices, we show that it is always possible to design an observer of the proposed form. Several numerical examples and a case study were given to illustrate our results.

Perspectives

The current work opens several research directions for the future. Firstly, even though the proposed Lyapunov conditions make it possible to compute tight 97 98 CHAPTER 6. CONCLUSION AND PERSPECTIVES upper bounds of the ρ-SJSR (Section 3.4.3) and the ρ-ω-RJSR (Section 4.3.3), their translation to LMIs may introduce some conservatism. It is then interesting to investigate how techniques similar to the path-complete graph Lyapunov functions [6] can be used in order to derive LMIs whose solution provides a tight upper bound of the ρ-SJSR. Moreover, it is shown in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF] that how some lifting techniques on the automaton can build arbitrary accurate approximation schemes for the CJSR. Therefore, one can wonder whether the same can be extended to the case of the ρ-SJSR and the ρ-ω-RJSR.

On the other hand, the development of numerical techniques to compute more complicated Lyapunov functions is necessary for cases where the simple linear matrix inequalities approach used in Section 4.2.1 proves unsuccessful. Therefore it would be of interest to use sum-of-squares Lyapunov functions in this case [START_REF] Parrilo | Approximation of the joint spectral radius using sum of squares[END_REF].

Furthermore, since the switching signal may not be always known in some practical applications, it is interesting to extend the results of Chapter 5 when the switching signal is partially known. In addition, it was shown that the DBA construction in Algorithm 1 depends on the length of reconstructible sequences k, therefore it would be of interest to study the complexity of the observer design with respect to k.

Finally, since observability and controllability are considered as dual problems. One could adapt the results of Chapter 5 to design, using a similar approach, switched controllers to stabilize discrete-time switched linear systems. We present a proof for completeness:

Proof. Given X 0 = i, we are now interested in counting the number of visits to state j over a period of time. Define the function I ij (t), t ≥ 1 to be 1 if X t = j given that X 0 = i, and 0 otherwise. The number of visits to state j, starting at state i, by time t is defined as:

N ij (t) = t k=1 I ij (k), t ≥ 1.
Let T (l) j , l ≥ 1, the time between the (l -1)th and l ′ th visit to state j, then from [57, Lemma 1.5.1] the non-negative random variables T Applying the previous theorem to the Markov chain of state space S ′ and transition matrix P ′ and assuming S = {∅ 1 , ∅ 2 } we get that N iS (t) = κ θ (t) and γ θ = j∈S π j , where π = P ′ π and π j is an element of the vector π corresponding to the state j.

Synthèse

Les systèmes commutés sont des systèmes dynamiques avec plusieurs modes de fonctionnement, chaque mode étant décrit par une équation différentielle (en temps continu) ou une équation de différence (en temps discret). À tout moment, le mode actif est déterminé par un signal de commutation. Les systèmes commutés sont très utiles en pratique pour décrire avec précision l'exécution d'algorithmes de contrôle sur des infrastructures informatiques distribuées et donc pour prendre en compte les contraintes liées à l'utilisation de ressources informatiques et de communication partagées. De plus, les systèmes commutés ont des propriétés inattendues (par exemple, un comportement instable peut résulter de la commutation entre des modes de fonctionnement stables) qui justifient le développement d'outils théoriques spécifiques pour leur étude. Les premiers travaux sur la stabilité des systèmes commutés ont porté sur la stabilité des signaux de commutation qui sont arbitraires ou qui satisfont une certaine condition de dwell-time (minimum ou moyen) (voir, par exemple, [1], [2], et les références citées). Plus récemment, plusieurs travaux ont examiné le problème de la démonstration de la stabilité pour des sous-ensembles de signaux de commutation. En général, de tels signaux de commutation sont supposés être générés par un automate fini et la stabilité est caractérisée soit en termes de rayon spectral joint contraint [3], [4], soit en utilisant des fonctions de Lyapunov [5], [6]. Cependant, il existe certains sous-ensembles de signaux de commutation qui ne peuvent pas être spécifiés à l'aide d'automates finis classiques. Les exemples sont les signaux de commutation contraints par des formules logiques temporelles linéaires (LTL), qui sont souvent utilisées pour spécifier des protocoles d'ordonnancement et de communication [7]. Une classe représentative de signaux qui peuvent être décrits par une formule LTL est celle des signaux de commutation mélangés (shuffled) : un signal de commutation est mélangé si et seulement si tous les modes sont activés infiniment souvent. Dans une étude préliminaire, la stabilité des systèmes commutés sous des signaux de commutation mélangés a été caractérisée au moyen de fonctions de Lyapunov [8]. Cette thèse vise à développer des outils théoriques et numériques pour analyser la stabilité des systèmes commutés sous des signaux de commutation mélangés et plus généralement sous des contraintes logiques temporelles linéaires. Nous nous appuierons sur les résultats préliminaires de [8] pour définir une notion de rayon spectral joint mélangé qui nous permettra de quantifier la vitesse de convergence du système commuté sous des signaux de commutation mélangés. Nous développerons des algorithmes numériques basés sur des inégalités matricielles linéaires (LMIs) et des techniques d'automates [5] pour calculer des approximations du rayon spectral joint mélangé. Dans la deuxième partie de la thèse, nous

1. 1 4 . 5

 145 The automaton at the left corresponds to arbitrary switching, the middle excludes the occurrence of -11-and in the last automaton the state "a" should be visited infinitely often. . . . . . . . . . . . 2.1 The automaton at the left corresponds to arbitrary switching and that of the right excludes the occurrence of -22-. . . . . . . . . . . 2.2 A switching signal (with m = 2) and the associated shuffling instants and index.[37] . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Automaton generating a shuffled switching signal θ in the case of 3 modes. Transition labels correspond to the value of θ. . . . . . . 3.1 Automaton describing the dynamics of η in (3.23) for m = 3. State labels correspond to the value of η, transition labels correspond to the value of θ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Automaton describing the dynamics of η in (3.27) for m = 3. State labels correspond to the value of η, transition labels correspond to the value of θ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Lower and upper bounds on the ρ-SJSR for (3.28). . . . . . . . . . 3.4 Minimal shuffling rate γ * as a function of the control gain k and of the number of oscillators m + 1. . . . . . . . . . . . . . . . . . . . . 3.5 Time evolution of the synchronization error x(t) and the switching signal θ(t) for a shuffling rate higher than γ * = 0.06. . . . . . . . . 3.6 Time evolution of the synchronization error x(t) and the switching signal θ(t) for a shuffling rate lower than γ * = 0.06. . . . . . . . . . 4.1 A non-deterministic Büchi automaton B = {{a, b}, {1, 2}, δ, {a}, {b}} recognizing the ω-regular language (1 + 2) * 1 ω . . . . . . . . . . . . . 4.2 An example of DBA whose language consists of infinite words that do not remain constant after some time. The accepting state is represented with a double circle. . . . . . . . . . . . . . . . . . . . 4.3 The labeled graph G corresponding to an NBA B with 3 accepting states q 1 , q 2 and q 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Time evolution of the synchronization error x(t) (top figures), switching signal θ(t) (bottom left), and the Lyapunov function V (q t , x(t)) (bottom right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minimal accepting rate γ * as a function of the control gain k and of the number of oscillators m. . . . . . . . . . . . . . . . . . . . . 4.6 Time evolution of the synchronization error x(t) and the switching signal θ(t) for an accepting rate higher than γ * = 0.22. . . . . . . . 4.7 Time evolution of the synchronization error x(t) and the switching signal θ(t) for an accepting rate smaller than γ * = 0.22. . . . . . . 5.1 The generated DBA B k corresponding to O ′[k] = {121, 122, 212, 221} for k = 3. The transitions built in part 1, 2 and 3 of Algorithm 1 are represented respectively by arrows with double head, single filled head and single empty head. . . . . . . . . . . . . . . . . . . 5.2 Simulations for the case γ θ > ln(ρ)

Figure 2 . 1 :

 21 Figure 2.1: The automaton at the left corresponds to arbitrary switching and that of the right excludes the occurrence of -22-.

Figure 2 . 3 :

 23 Figure 2.3: Automaton generating a shuffled switching signal θ in the case of 3 modes. Transition labels correspond to the value of θ.

20 CHAPTER 3 .

 203 2.1). Definition 3.1.1. Let ρ > ρ(A), we define the Shuffled Joint Spectral Radius SHUFFLED JOINT SPECTRAL RADIUS relative to (A, ρ) (ρ-SJSR for short) by the following λ(A, ρ) = lim sup k→+∞

. 3 )

 3 Moreover, the value of λ(A, ρ) either in(3.1) or in (3.3) is independent of the used matrix norm. Proof. The result is a direct consequence of Lemma 3.1.3 and of the properties of the JSR stated in [42, Lemma 1.2] and [42, Page 10]. Furthermore, λ(A, •) enjoys several properties given in the proposition below. Proposition 3.1.5. One of the following properties holds: CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS (i) The function ρ → λ(A, ρ) is decreasing, takes values in (0, 1) and, for all

Proposition 3 . 1 . 7 .

 317 The SJSR enjoys the following properties:(i) λ(A) belongs to [0, 1] and is independent of the choice of the norm;(ii) For all K ∈ R, K ̸ = 0, we have λ(KA) = λ(A). Proof. The first statement follows from (3.6) and by the properties of λ(A, •) proved in Propositions 3.1.4 and 3.1.5. Concerning the second item, let K ∈ R, K ̸ = 0, we have by (3.6) λ(KA) = lim ρ→ρ(KA) + λ(KA, ρ) = lim ρ→ρ(A) + λ(KA, |K|ρ) where the second equality comes from the property of the JSR, ρ(KA) = |K|ρ(A), see e.g. [42, Proposition 1.2]. Furthermore, from (3.1), one can deduce that for all ρ > ρ(A), λ(KA, |K|ρ) = λ(A, ρ), therefore λ(KA) = λ(A).

Theorem 3 . 4 . 3 .

 343 The following results hold true.(i) For all K > ρ(N I ), there exists R ≥ ρ(A) such that for all ρ ≥ R,λ(A, ρ) ≤ K ρ m . (3.15) (ii) We have the asymptotic estimate lim ρ→+∞ ρ m λ(A, ρ) = ρ(N I ). (3.16) (iii) If there exists a norm ∥ • ∥ * that is extremal for N I , then there exists R ≥ ρ(A) such that for all ρ ≥ R, λ(A, ρ) = ρ(N I ) ρ m . (3.17) Proof. Let us fix K > ρ(N I ). By Proposition 3.4.1 there exists an induced matrix norm ∥ • ∥ * such that ∥M ∥ * ≤ K for every M ∈ N I . Considering now the set Mρ = ρ m M ρ , we have N I ⊆ Mρ . We want to show that ∥M ∥ * ≤ K for every M ∈ Mρ \ N I , provided that ρ is large enough. For this purpose, we first take any R > ρ(A). Then, again by Proposition 3.4.1, there exists an induced matrix norm ∥ • ∥ * * such that ∥A∥ * * ≤ R for every A ∈ A. Taking K ≥ 1 such that ∥A∥ * ≤ K∥A∥ * * for every matrix A ∈ R n×n we obtain

  and ∃k, j k = i . Lemma 3.4.4. Assume all the matrices in A are invertible. Let K ≥ ρ(N I ) and let ∥ • ∥ * be an induced matrix norm such that ∥M ∥ * ≤ K for every M ∈ N I . Then, setting

Figure 3 . 1 :

 31 Figure 3.1: Automaton describing the dynamics of η in (3.23) for m = 3. State labels correspond to the value of η, transition labels correspond to the value of θ.

3 . 26 )

 326 then the bound (3.7) holds. Conversely, if the matrices A i are invertible, for all i ∈ I and the bound (3.7) holds for some ρ > 0, λ ∈ [0, 1] and C ≥ 1, then there exists a function V : (2 I \ {I}) × R n → R + 0 such that the inequalities (3.24), (3.25) and (3.26) are satisfied.

Figure 3 . 2 :

 32 Figure 3.2: Automaton describing the dynamics of η in (3.27) for m = 3. State labels correspond to the value of η, transition labels correspond to the value of θ.

  24)-(3.25)-(3.26) hold true. The proof is complete. As a direct consequence of the previous results and Theorem 3.2.1 we have the following corollary. Corollary 3.4.8. Let ρ > 0 and λ ∈ [0, 1] such that there exists a function V satisfying the conditions of Theorem 3.4.6 or Theorem 3.4.7, then either ρ > ρ(A) and λ ≥ λ(A, ρ), or ρ = ρ(A) and λ ≥ λ(A). Conversely, if the matrices A i are invertible, for all i ∈ I, then for all ρ > ρ(A), for all λ ∈ (λ(A, ρ), 1], there exists a function V satisfying the conditions of Theorem 3.4.7. Corollary 3.4.8 shows that upper-bounds of the JSR and of the ρ-SJSR can be found by computing Lyapunov functions satisfying the conditions in Theorems 3.4.6 and 3.4.7. Limiting the search to quadratic Lyapunov function, the conditions (3.19)-(3.20)-(3.21)-(3.22) or (3.24)-(3.25)-(3.26) can straightforwardly be translated to LMIs for which efficient solvers exist. However, the tightness of the conditions in Theorem 3.4.7 is lost when constraining the Lyapunov functions to be quadratic.

6 , ϕ 2 = π 3 .

 63 ) where the numerical values of the parameters are µ 1 = 0.9, µ 2 = 0.2, ϕ 1 = π Let us notice that ρ(A) = 1 with the Euclidean norm ∥ • ∥ being extremal for A.

  to compute tight bounds on ρ(N I ) and we obtain ρ(N I ) ∈ [ρ, ρ] where ρ = 0.7640321 and ρ = 0.7640322. It follows from Proposition 3.4.2, that ∀ρ > 1, λ(A, ρ) ≥ ρ ρ m . CHAPTER 3. SHUFFLED JOINT SPECTRAL RADIUS We now apply Theorem 3.4.3 and Lemma 3.4.4 to compute an upper bound on the ρ-SJSR. Considering K = ρ, we search for an induced matrix norm ∥ • ∥ * such that ∥A 1 A 2 ∥ * ≤ ρ and ∥A 2 A 1 ∥ * ≤ ρ. Limiting the search to a quadratic norm of the form ∥x∥

  .2755 0.0688 0.0257 0.0688 0.3660 0.2248 0.0257 0.2248 0.3585   . Then, we compute R according to (3.18) and we get R = max(∥A 1 ∥ * , ∥A 2 ∥ * ) = 1.3279. Then, from Lemma 3.4.4, we get that ∀ρ ≥ R, λ(A, ρ) ≤ ρ ρ m . Now, we use the Lyapunov techniques presented in Theorems 3.4.6 and 3.4.7 to compute upper-bounds of the ρ-SJSR for ρ ∈ (1, R). Searching for Lyapunov functions of the form V (i, x) = x ⊤ Q i x, i ∈ I the conditions of Theorem 3.4.6 translate to the following LMIs:

Figure 3 . 3 :

 33 Figure 3.3: Lower and upper bounds on the ρ-SJSR for (3.28).

Figure 3 . 4 :

 34 Figure 3.4: Minimal shuffling rate γ * as a function of the control gain k and of the number of oscillators m + 1.

Figure 3 . 5 :

 35 Figure 3.5: Time evolution of the synchronization error x(t) and the switching signal θ(t) for a shuffling rate higher than γ * = 0.06.

Figure 3 . 6 :

 36 Figure 3.6: Time evolution of the synchronization error x(t) and the switching signal θ(t) for a shuffling rate lower than γ * = 0.06.

  Figure 4.1:A non-deterministic Büchi automaton B = {{a, b}, {1, 2}, δ, {a}, {b}} recognizing the ω-regular language (1 + 2) * 1 ω .

48 CHAPTER 4 .

 484 ω-REGULAR LANGUAGE Lemma 4.1.1. Given a DBA B, let M = max c∈C B |Fc| |c| . Then, ∀σ ∈ Lang(B), ∀t ∈ N, κ σ (t) ≤ |Q| + M t.

  . , c k and in a sequence of states r k such that |r k | ≤ |Q|. The number of occurrences of elements of F in r k is bounded by |r k | ≤ |Q|. The total number of occurrences of elements of F in the cycles c 1 , . . . , c k is bounded by M (|c 1 | + • • • + |c k |) ≤ M t. Hence, it follows that (4.1) holds and we directly obtain that sup σ∈Lang(B)

Definition 4 . 1 . 3 .

 413 The system (A, B) is globally attractive (GA) if for all switching signals θ ∈ Lang(B) and for all initial conditions x 0 ∈ R n , we have lim t→∞ ∥x(t, x 0 , θ)∥ = 0. Definition 4.1.4. The system (

Assumption 4 . 2 . 5 .

 425 All the matrices in A are invertible.

Figure 4 . 4 :

 44 Figure 4.4: Time evolution of the synchronization error x(t) (top figures), switching signal θ(t) (bottom left), and the Lyapunov function V (q t , x(t)) (bottom right).

Proposition 4 . 3 . 3 .

 433 For all ρ > ρ(A, B), the value λ(A, B, ρ) does not change if we replace the induced matrix norm in (4.7) by any other matrix norm.

Proposition 4 . 3 . 4 .

 434 The function ρ → λ(A, B, ρ) is non-increasing, takes values in [0, 1) and, for all ρ

Definition 4 . 3 . 5 .

 435 The ω-Regular Joint Spectral Radius (ω-RJSR) of (A, B) is defined as λ(A, B) = lim ρ→ρ(A,B) + λ(A, B, ρ). (4.11)

Proof.

  The first statement follows from (4.11) and by the properties of λ(A, B, •) proved in Propositions 4.3.3 and 4.3.4. Concerning the second item, let K ∈ R, K ̸ = 0, we have by (4.11) λ(KA, B) = lim ρ→ρ(KA,B) + λ(KA, B, ρ) = lim ρ→ρ(A,B) + λ(KA, B, |K|ρ)

66 CHAPTER 4 .

 664 ω-REGULAR LANGUAGE 4.3.3 . Computing Upper bounds of the ρ-ω-RJSR

Corollary 4 . 3 . 10 .

 4310 Let us assume the matrices in A are invertible. Let ρ > 0 and λ ∈ [0, 1] such that there exists a function V satisfying the conditions of Theorem 4.3.9, then either ρ > ρ(A, B) and λ ≥ λ(A, B, ρ), or ρ = ρ(A, B) and λ ≥ λ(A, B). Conversely, for all ρ > ρ(A, B), for all λ ∈ (λ(A, B, ρ), 1], there exists a function V satisfying the conditions of Theorem 4.3.9. Corollary 4.3.10 shows that tight upper-bounds of the CJSR and of the ω-ρ-RJSR can be obtained by computing Lyapunov functions satisfying the conditions in Theorem 4.3.9. Limiting the search to quadratic Lyapunov functions, the conditions (4.21)-(4.22)-(

Figure 4 . 5 :

 45 Figure 4.5: Minimal accepting rate γ * as a function of the control gain k and of the number of oscillators m.

Figure 4 . 6 :

 46 Figure 4.6: Time evolution of the synchronization error x(t) and the switching signal θ(t) for an accepting rate higher than γ * = 0.22.

CHAPTER

Theorem 5 . 1 . 2 .

 512 [START_REF] Sun | Switched linear systems: control and design[END_REF] Theorems 4.32 & 4.33] A sequence of modes i 1 , . . . , i j ∈ I is observable if and only if

Algorithm 1 3 :

 13 Construction of DBA B k Inputs: alphabet I, reconstructible sequences O ′[k] Output: DBA B k such that Lang(B k ) = (I * O ′[k] ) ω 1: q 0 := ϵ, F := {ϵ}, Q := {ϵ} 2: for σ ∈ I do if σ ∈ O ′[k] then

  then

  for j ∈ {2, . . . , l -1} do 15:

  end for the language (I * O ′[k]

  For k = 3, we get that O ′[k] = {121, 122, 212, 221}.

Figure 5 . 1 :

 51 Figure 5.1: The generated DBA B k corresponding to O ′[k] = {121, 122, 212, 221} for k = 3. The transitions built in part 1, 2 and 3 of Algorithm 1 are represented respectively by arrows with double head, single filled head and single empty head.

Lemma 5 . 3 . 7 .

 537 For all w

5. 3 . 4 . 1 ⊤L ( 1 , 2 )L ( 2 , 1 )⊤L ( 2 , 2 ) 43 ⊤L ( 12 , 1 ) 11 ⊤L ( 12 , 2 ) 29 ⊤L ( 21 , 1 )

 341122122431211112229211 Numerical example Let us consider Example 5.2.1 again and let B k be the DBA constructed using Algorithm 1 for k = 3 as shown in Figure 5.2.1. Then, we solve the LMIs (5.19), (5.20), (5.21) for ρ = 1.5, λ = 0.1, to synthesize the following observer gains 1 : L (ϵ,1) = 1 -0.26 0.01 ⊤ , L (ϵ,2) = 0.82 0.68 -0.15 ⊤ L (1,1) = 1 6.12 -4.= 0.76 0.74 0.02 ⊤ = 1 -1.05 0.07 = 0.97 0.53 -0.= 1 -1.03 -0.= 0.14 1.36 -1.

Figure 5 . 2 :

 52 Figure 5.2: Simulations for the case γ θ > ln(ρ)-ln(λ) : top -switching signal θ; center -discrete state of the switched observer q, red circles indicate return instants; bottom -norm of the estimation error e in logarithmic scale for both type of gains.

Figure 5 . 3 :

 53 Figure 5.3: Simulations for the case γ θ < ln(ρ)-ln(λ) : top -switching signal θ; center -discrete state of the switched observer q, red circles indicate return instants; bottom -norm of the estimation error e in logarithmic scale for both type of gains.

Figure 5 . 4 :

 54 Figure 5.4: Multicellular converter with an inductive load.

23 )A 1 =

 231 For numerical experiments, we consider n = 3 commutations cell, with the following parameter values E = 1500 V, c 1 = c 2 = 40 µF, R = 10 Ω, L = 0.5 mH. For such numerical values, the state matrices are given by matrices are C i = (0 0 1), for all i = 1, . . . , 8. In the following, we consider a sampled version of (5.23) with a sampling period T = 0.3 ms.

Figure 5 . 5 :

 55 Figure 5.5: Adjacency relations between modes describing the constraints on the switching signal θ. When a mode change occurs in the switching signal θ, the new mode must be adjacent to the previous one.

2 , 3 , 5 1 , 2 , 4 , 6 1

 235246 , 3 , 4 , 7

Figure 5 . 6 :Figure 5 . 7 :

 5657 Figure 5.6: DBA B3 that generates switching sequences satisfying the adjacency constraints shown in Figure 5.5 and with an infinite number of reconstructible subsequences in Õ′[k] . Arrows with double head and labelled by σ lead to state σ, arrows with empty head and labelled by σ lead to accepting state ϵ σ .

Figure A. 2 :Figure A. 3 :

 23 Figure A.2: A finite state automaton representing the 2-state Markov chain. (p ij in red is the state transition probability.)

  j• • • , are inde-

  .2 A finite state automaton representing the 2-state Markov chain. (p ij in red is the state transition probability.) . . . . . . . . . . . . A.3 A finite state automaton corresponding to the reduced cartesian product of the two automata. . . . . . . . . . . . . . . . . . . . . .

	Notations
	R	the set of real numbers
	R + 0	the set of non-negative real numbers
	N	the set of non-negative integers
	I n	the n × n identity matrix
	∥.∥	arbitrary norm on R n and the associated induced ma-
		trix norm
	|.|	the cardinality of a finite set
	2 I	the powerset i.e. the set of subsets of I
	∅	the emptyset
	Σ

and with an infinite number of reconstructible subsequences in Õ′[k] . Arrows with double head and labelled by σ lead to state σ, arrows with empty head and labelled by σ lead to accepting state ϵ σ . . . . . . . . . . . . . . . . 5.7 Simulations for the multicellular converter: top -switching signal θ, red circles indicate return instants; bottom -norm of the estimation error e in logarithmic scale for both types of gains. . . . . . . . . A.1 A Büchi automaton generating all shuffled switching signals with 2 modes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A* the set of all finite words over the alphabet Σ Σ +

  • • , m}. More precisely, at time t ∈ N, the active channel is e θ(t) .

						CHAPTER 4. ω-REGULAR LANGUAGE
		0.6				stabilizability vs k
										m=3 oscillators
										m=4 oscillators
										m=5 oscillators
		0.5
		0.4
	-log( )/log( )	0.3
	Inf
		0.2
		0.1
		0
		0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
						k

  Time evolution of the synchronization error x(t) and the switching signal θ(t) for an accepting rate smaller than γ * = 0.22. switched systems

							4. ω-REGULAR LANGUAGE
		2.5
	(t)
		1.5
		100	200	300	400	500	600	700	800	900	1000
						t
		0.04
		0.03
	/t
	(t)	0.02
		0.01
		100	200	300	400	500	600	700	800	900	1000
						t
		500
	traj
		-500
		100	200	300	400	500	600	700	800	900	1000
						t
	Figure 4.7:

The Matlab scripts of these numerical examples are available at the following repository: https://github.com/georgesaazan/Shuffled-systems

The Matlab scripts of the numerical example and of the case study are available at the following repository: https://codeocean.com/capsule/7403312/tree/v1

The Matlab scripts of this numerical example are available at the following repository: https://github.com/georgesaazan/w-regular-oscillators

The Matlab scripts of the numerical example and of the case study are available at the following repository: https://github.com/georgesaazan/w-regular-observer

Acknowledgements

Proof. The result follows from Proposition 2.2 and Theorem 1.1 in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF], where these results are proven assuming that the number of labels going from a state to another is finite and that the graph G is strongly connected. The arguments of the proofs still apply in our case, although the set L × qp is bounded but not necessarily finite and we do not require G to be strongly connected. Now we relate the attractivity of (A, B) with that of (M F B , G) using the following lemma. Lemma 4.2.9. Under Assumption 4.2.5, if the switched system (A, B) is GA then the constrained system (M F B , G) is attractive.

Proof. Let (q f 0 , l 1 , q f 1 ), (q f 1 , l 2 , q f 2 ), . . . be a path in (M F B , G). By Assumption 4.1.2 there exist q 0 ∈ Q 0 , a switching sequence θ ∈ Lang(B) and a sequence of instants (t k ) k∈Z + with 0 < t 1 < t 2 . . . such that

By submultiplicativity we have

concluding the proof of the lemma.

We next provide a converse result to Theorem 4.2.2.

Theorem 4.2.10. Under Assumption 4.2.5, if the switched system (A, B) is GUS and GA, then it admits a Lyapunov function.

Proof. Under the assumptions of the theorem we get from Theorem 4.2.8 and Lemma 4.2.9 that, for the constrained system (M F B , G), there exists a multinorm H = {∥.∥ q f , q f ∈ F } with a value strictly less than 1, that is γ * (H) < 1.

Consider the function V : Q × R n → R + 0 defined as follows ∀q ∈ Q, x ∈ R n : V (q, x) = max

CHAPTER 4. ω-REGULAR LANGUAGE a switching signal θ : N → Σ = {1, 2, 3}. Then, the input value is given as follows:

where γ = 0.05 is a control gain. Denoting the vector of synchronization errors as x(t) = (x 1 (t) ⊤ , x 2 (t) ⊤ ) ⊤ with x i (t) = z i+1 (t) -z i (t), the error dynamics is described by a 4-dimensional switched linear system of the form:

where the 3 matrices describing the 3 modes of communication are given by:

As for the communication protocol, we impose a fairness constraint that the switching signal cannot keep activating the same communication channel:

Note that this property can be formulated as the following linear temporal logic formula:

This is equivalently described by a deterministic Büchi automaton, B, where the set of states is Q = {q 0 , q 1 , q 2 , q 3 }, the alphabet Σ = {1, 2, 3},

2 shows the corresponding Büchi automaton which describes the switching logic in this system. We want to show that the agents synchronize if the state q 0 in B is visited infinitely often. This can be done by studying the stability of (A = {A 1 , A 2 , A 3 }, B). We then look for a Lyapunov function of the CHAPTER 4. ω-REGULAR LANGUAGE Then, the input value is given as follows:

where k is a control gain. Denoting the vector of synchronisation errors as

, the error dynamics is described by a 2(m -1)-dimensional switched linear system of the form:

where the matrices A k for k = 1, . . . , m can be easily obtained from the multiagent dynamics and the input values given above. Similar to consensus problems [START_REF] Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF], we expect the stability of (4.24) to be related to the connectivity, for all t ∈ N, of the graph G t = (V, E t ) where E t = s≥t {e θ(s) }.

Let us consider the DBA B = (Q, Σ, δ, q init , F ) where the set of states is Q = 2 E \ E with 2 E the set of subsets of E; the alphabet is Σ = {1, . . . , m}; the initial state is q init = ∅ and the set of accepting states is F = {∅}. The transition function δ is given as follows

For m = 3 the automaton B corresponds to the DBA represented in Figure 4.2. For all switching signal θ ∈ Lang(B), we get by construction of B that for all k ∈ N, the graph G k = (V, E k ) is connected where

CONVERGENCE RATE CHARACTERIZATION 69

Then, it follows that θ ∈ Lang(B) if and only if G = (V, E t ) is connected for all t ∈ N. Moreover, by analyzing the cycles of B, we can check that the maximal achievable accepting rate established in Lemma 4.1.1 is given by M = 1 m-1 . Let us remark that for the DBA B defined above, any arbitrary switching signal belongs to Θ B . Hence, the CJSR of (A, B) coincides with the JSR of the set A. We can then compute ρ(A, B) using the JSR toolbox [START_REF] Vankeerberghen | JSR: A toolbox to compute the joint spectral radius[END_REF].

We then use Theorem 4.3.9 to compute an upper bound λ(ρ) on the ρ-ω-RJSR by solving the LMIs associated with (4.21)-(4.22)-(4.23). Note that

.

In this example, we observe numerically that the infimum is reached for ρ = ρ(A, B) if it satisfies γ * < M = 1 m-1 (in which case the system is stabilizable, see the discussion after Corollary 4.3.8), and at infinity otherwise, with γ * = 1 m-1 . We aim at finding the minimal accepting rate γ * required to stabilize the system with an arbitrary number of oscillators, therefore we computed γ * for several values of k ∈ (0, 1) and m ∈ {3, 4, 5} and we show the result in Figure 4.5. In this figure, the horizontal lines correspond to the maximal achievable accepting rate 1 m-1 . From Corollary 4.3.8, we know that the switched system can be stabilized if we use switching signals belonging to the language of B, whose accepting rate satisfies γ θ ∈ (γ * , 1 m-1 ]. Hence, in order to stabilize the system, we should carefully select the control gain k such that γ * < 1 m-1 . We also verified that for m = 6 oscillators, γ * > 1 m-1 for all control gain k ∈ (0, 1). Therefore, for 6 oscillators, there is no suitable choice of control gain k such that the system can be stabilized using switching signals with a sufficiently high accepting rate 2 .

We now proceed with some illustrative numerical simulations. Let us consider a system composed of m = 3 oscillators with control gain k = 0.1, then from Figure 4.5, the corresponding lower bound on the accepting rate is γ * = 0.22. Let us consider the initial synchronization error x(0) = (-1.5 -0.5 2 -1) ⊤ . We consider random switching signals generated by a discrete-time Markov chain with 3 states such that P(θ(t + 1) = j|θ(t) = j) = p, and P(θ

where p ∈ (0, 1) and i, j ∈ {1, 2, 3}, i ̸ = j, t ≥ 0. From the definition of the DBA B, it is easy to see that the smaller p, the higher the accepting rate.

We first consider p = 0.8. Figure 4.6 shows the switching signal θ(t), the evolution of κ θ (t) t , and the synchronization errors x 1 (t), x 2 (t). It is interesting to note that γ θ ≥ 0.23 > 0.22 and that the system stabilizes as expected. Then, we CHAPTER 5. OBSERVER DESIGN FOR SWITCHED SYSTEMS be as in Item (1). We write w = σ 1 • • • σ p and define w 0 = w ′ and, recursively for k = 1, . . . , p, w k = δ(w k-1 , σ k ). We then have

concluding the proof of Item (1).

Let us prove Item (2). Note that in steps 4, 12, 18 and 24 δ(w, σ) = ϵ and the conclusion of Item (2) holds. In steps 7 and 16 it is apparent that δ(w, σ) ̸ = ϵ. We now show that this is also the case for step 26. Note that, in this step,

For p = 1 the result follows from steps 4 and 24 of the algorithm. Let us then consider the case p ≥ 2. For k = 1, . . . , p, let us define w k such that w

In order to prove the claim, we proceed by induction on k. It follows from steps 7, 16 and 26 that either w 1 = wσ 1 , and thus the claim holds with w ′ 1 = w, or w 1 = arg max z∈Q∩S(wσ 1 )

|z|. In the latter case, since w 1 ̸ = ϵ by assumption, it follows that w 1 = w ′ 1 σ 1 for some w ′ 1 ∈ S(w). Hence the claim is proved for k = 1. Assume now that the claim holds true for some k ∈ {1, . . . , p -2}, hence we can write

Let us prove the claim for k + 1. It follows from steps 16 and 26 that either

|z|.

In the second case, since

), from which the claim follows for k + 1.

From the claim we have that

. By step 24 we then have w p = ϵ.

We can now state the main result of this subsection: Theorem 5.2.5. Let B k be the DBA constructed using Algorithm 1 for some

OBSERVER DESIGN 81

Proof. Note that (I * O ′[k] ) ω ⊆ I ω and B k is deterministic by Lemma 5.2.2, hence for any sequence in (I * O ′ [k] ) ω there exists a (unique) corresponding run in B k .

First, we show that (

Let us define some elements of the run in B k corresponding to the sequence w as w (0) = ϵ and, recursively,

w * i --→ ϵ. Now, in the infinite run corresponding to w, the state ϵ is visited at least once between each couple of states w (i-1) and w (i) . Therefore the accepting state is visited an infinite number of times in the run. This proves the first inclusion.

Let us focus on the inclusion (

Let us consider w i in the previous decomposition of w. We write w i = σ 1 • • • σ l for some l ≥ 1, and consider the word w ′ i such that ϵ

Let us remark that, since for any

, it follows from Theorem 5.2.5 that Lang(B k 1 ) ⊆ Lang(B k 2 ). Hence, considering longer reconstructible sequences produces a DBA accepting more switching signals.

. Observer design

In this section, we present an approach for designing asymptotic observers for system (5.1). The proposed design results in a switched observer where the switching is driven by the DBA B k presented in the previous section. We first introduce the structure of the observer and then propose two approaches for designing the gains of the observer. Let us consider the system (5.1) and let B k = (Q, I, δ, q 0 , F ) be the DBA constructed using Algorithm 1, for some k ≥ 1 such that O ′[k] ̸ = ∅. We consider the following switched observer where x(t) ∈ R n is the estimate of the state of (5.1) and q(t) ∈ Q is an internal discrete state: q(t + 1) = δ(q(t), θ(t)), q(0) = q 0 , x(t + 1) = A θ(t) x(t) + L (q(t),θ(t)) y(t) -C θ(t) x(t) .

(5.4)

Let us remark that the dynamics of q is given by the transition function δ of the DBA B k . The structure of the observer being given by (5.4), it remains to design CHAPTER 5. OBSERVER DESIGN FOR SWITCHED SYSTEMS the observer gains L (w,σ) , for all w ∈ Q and σ ∈ I.

Let e(t) = x(t)-x(t) be the estimation error of the observer, then the dynamics of e(t) is given by: e(t + 1) = (A θ(t) -L (q(t),θ(t)) C θ(t) )e(t).

We note that, given an initial condition e 0 ∈ R n , and a switching signal θ, the trajectory with e(0) = e 0 is unique and denoted by e(., e 0 , θ). In order to guarantee the convergence of the asymptotic observer, one needs to prove that e(t, e 0 , θ) goes to 0 as t tends to infinity. For this purpose, we will make use of the following Lyapunov-type result.

Proposition 5.3.1. Let us assume that there exist a function V : Q × R n → R + 0 , and scalars α 1 , α 2 , ρ > 0, and λ ∈ (0, 1), such that for all e ∈ R n , the following inequalities hold:

)

)

Then, there exists C ≥ 1 such that for all e 0 ∈ R n , and for all θ ∈ Lang(B k ):

∀t ∈ N, ∥e(t, e 0 , θ)∥ ≤ Cρ t λ κ θ,B k (t) ∥e 0 ∥.

(5.8)

Moreover, whenever γ θ > ln(ρ) -ln(λ) , we have lim t→∞ ∥e(t, e 0 , θ)∥ = 0.

(5.9)

Proof. The proof of (5.8) follows the same rationale as in [3, Theorem 1], with a slight modification that is the scaling of the set of state matrices by ρ > 0. The proof of (5.9) is as in [2, Corollary 1].

Equation (5.8) relates the convergence rate of the asymptotic observer to the return index κ θ,B k (t) associated with the DBA B k , which essentially counts the number of reconstructible sequences (i.e. elements of O ′ [k] ) that occur up to time t. Note that ρ may be greater than 1. In that case, in order to guarantee the convergence of the observer, one must consider switching signals where reconstructible sequences occur sufficiently often. This occurrence rate is measured by the accepting rate γ θ . If γ θ is sufficiently large, we get from (5.9) that the observer asymptotically converges. In general, the set of switching signals θ satisfying γ θ > ln(ρ)

-ln(λ) is not an ω-regular language anymore but belongs to the class of quantitative languages, studied in [START_REF] Chatterjee | Quantitative languages[END_REF].

. Explicit construction of gains

In this subsection, we present a particular design of the observer gains L (w,σ) , w ∈ Q and σ ∈ I, and of the associated Lyapunov function V . The proposed design requires the following property which is assumed to hold throughout the subsection:

Let us fix ρ > ρ e (A) where ρ e (A) is as in Equation (2.12) Then, by definition, there exists M ∈ R n×n symmetric positive definite such that

(5.10)

Let us also consider an arbitrary λ ∈ (0, 1).

Remark 5.3.3. The results presented in this section can be extended to the case ρ = ρ e (A) if there exists a symmetric positive definite matrix M such that (5.10) holds.

We start with a preliminary result:

Lemma 5.3.4. There exists γ > 0 such that for all reconstructible sequences

)Ω(σ 1 , . . . , σ l ). Proof. Since all matrices in A are invertible, any reconstructible sequence is also observable. Then, from Theorem 5.1.2, we get that for any

Then, the result follows directly from the fact that the set O ′[k] is finite.

In the following, we provide an explicit construction of observer gains L (w,σ) and of a Lyapunov function V under the form V (w, e) = e ⊤ P w e.

Let us associate a matrix P w ∈ R n×n with every word w ∈ I * , defined recursively as follows:

(5.11)

∀w ∈ I * , σ ∈ I.

CHAPTER 5. OBSERVER DESIGN FOR SWITCHED SYSTEMS

Let us prove several instrumental results related to properties of the matrices P w .

Lemma 5.3.5. For all w ∈ I * , P w > 0.

Proof. From (5.12), it follows that

Then, since P ϵ = M > 0 and A σ is invertible for all σ ∈ I by Assumption 5.3.2, it follows by induction that P w > 0 for all w ∈ I * .

Lemma 5.3.6. For all w ∈ I * , σ ∈ I, P w ≤ P σw .

Proof. From (5.12), we get that for all σ ∈ I,

From (5.10), we get that

Then, from (5.11) and the two previous inequalities, it follows that P ϵ ≤ P σ . Hence, the property holds for w = ϵ and hence for all words of length 0. Then, we proceed by induction. Let us assume that the property holds for all words of a certain length l ∈ N, and let us consider a word w of length l + 1. Then, there exists w l ∈ I * , |w l | = l and σ l+1 ∈ I such that w = w l σ l+1 . Then, from (5.12)

Since |w l | = l, we get by the induction assumption P σw l ≥ P w l and therefore

Then, from (5.12), we also get

Then, P σw ≥ P w . By induction, the property holds for all w ∈ I * .

OBSERVER DESIGN

where (5.14) is obtained by the Woodbury matrix identity and (5.15) is obtained by (5.13). Multiplying both sides by A σ on the left and by P w on the right, we obtain

Therefore,

(5.16)

Note that from (5.14), the following inequality holds:

which together with (5.16) gives:

We are now in position of stating the main result of this subsection:

Theorem 5.3.9. Let B k be the DBA constructed using Algorithm 1 for some k ≥ 1, let ρ > ρ e (A) and λ ∈ (0, 1). Under Assumption 5.3.2, for all w ∈ Q and σ ∈ I let the matrices P w and L (w,σ) be defined as in (5.11), (5.12) and (5.13).

Then, P w > 0, for all w ∈ Q, and

In particular, the function V (w, e) = e ⊤ P w e satisfies inequalities (5.5),(5.6) and (5.7).

Proof. The fact that P w > 0, for all w ∈ Q, follows from Lemma 5.3.5. Let us consider w ∈ Q, σ ∈ I, such that w ′ = δ(w, σ) ̸ = ϵ. Then, from Item (1) of Lemma 5.2.3, there exist w 1 , w 2 ∈ I * (possibly with w 1 = ϵ or w 2 = ϵ) such that w = w 1 w 2 and w ′ = w 2 σ. Then, from Lemma 5.3.6, P w ′ = P w 2 σ ≤ P w 1 w 2 σ = P wσ .

OBSERVER DESIGN 87

Then,

where the last inequality comes from Lemma 5.3.8. Now consider w ∈ Q, σ ∈ I, such that w ′ = δ(w, σ) = ϵ. Then, from Item (2) of Lemma 5.2.3, there exist w 1 , w 2 ∈ I * (possibly with w 1 = ϵ or w 2 = ϵ) such that w = w 1 w 2 and w 2 σ ∈ O ′ [k] . From Lemma 5.3.7 and Lemma 5.3.6, we get

Then,

where the last inequality comes from Lemma 5.3.8.

The fact that the function V satisfies inequalities (5.5),(

) is then a direct consequence of P w > 0, (5.17) and (5.18), respectively. Hence, in this section, we have shown that when all matrices in A are invertible, for all ρ > ρ e (A) and λ ∈ (0, 1) it is possible to design observer gains such that conditions of Proposition 5.3.1 are satisfied.

. Gains construction using LMIs solution

In this subsection, we present an alternative design of the observer gains based on solving a set of linear matrix inequalities. Proposition 5.3.10. Let B k be the DBA constructed using Algorithm 1 for some k ≥ 1, let ρ > 0 and λ ∈ (0, 1). Let us assume that there exist matrices P w ∈ R n×n , Y (w,σ) ∈ R n×p , for w ∈ Q, σ ∈ I, such that the following LMIs hold:

CHAPTER 5. OBSERVER DESIGN FOR SWITCHED SYSTEMS

Then, the function V (w, e) = e ⊤ P w e satisfies inequalities (5.5),(5.6) and (5.7) with observer gains

Moreover, under Assumption 5.3.2, LMIs (5.19), (5.20), (5.21) have a feasible solution for all ρ > ρ e (A) and λ ∈ (0, 1).

Proof. Considering L (w,σ) given by (5.22), we get by Schur complement that (5.20), (5.21) are equivalent to (5.17) and (5.18). This, together with (5.19) implies that the function V satisfies inequalities (5.5),(5.6) and (5.7). Conversely, under Assumption 5.3.2, for ρ > ρ e (A) and λ ∈ (0, 1), let the matrices P w and L (w,σ) be defined as in (5.11), (5.12) and (5.13). Then, let Y (w,σ) = P δ(w,σ) L (w,σ) . We get from Theorem 5.3.9 and using Schur complement that (5.19), (5.20), (5.21) are satisfied.

From Theorem 5.3.9 and Proposition 5.3.10, it appears that under Assumption 5.3.2, it is always possible to design gains for the switched observer (5.4), either using the explicit construction or by solving LMIs. In this sense, the proposed observer structure given by (5.4) is universal. Let us remark that the observer gains need not be computed online as opposed to approaches such as [START_REF] Tanwani | Observability for switched linear systems: characterization and observer design[END_REF] or based on Kalman filters [START_REF] Zhang | On stability of the Kalman filter for discrete time output error systems[END_REF], resulting in much simpler implementations in practice.

. Extension to switched systems with constrained switching

In this subsection, we briefly explain how our approach can be adapted when the switched system (5.1) is subject to switching constraints. Let us assume that switching signals θ ∈ S where S ⊆ I ω . We start by remarking that we can use the exact same approach as described in the previous subsections, since the conclusions of Proposition 5.3.1 hold for all θ ∈ S ∩ Lang(B k ). However, we can use the additional information provided by S to design observers with lower complexity or higher performance.

Firstly, due to switching constraints, not all reconstructible sequences may appear in the switching signals. We denote by S k the set of subsequences of length up to k of sequences in S. Formally, let

Then, it is sufficient to consider the set of reconstructible sequences given by Õ′

Then, we can design an observer using the same approach as before, simply building the automaton B k from the set of reconstructible sequences Õ′

A -Markov chains and shuffling rate

A natural way to represent a shuffled switching signal is to consider finite state Markov chains. A finite state Markov chain is a sequence of random variables (states) X 0 , X 1 , • • • taking values in a finite state S. These states satisfy the Markov property, i.e. the occurrence of a state at time t + 1 only depends on the state at time t. Let us denote by P its associated transition matrix, P is a stochastic matrix describing the probabilities of occurrence of the states. More precisely p ij , i, j ∈ S denoting the element of i'th row and j'th column in P is the probability to have a transition from state i to the state j, i.e. p ij = P(X k+1 = j|X k = i), k ≥ 0. Let us restrain to the case where every state can be reached from any state. Therefore, in this case, by taking S = I = {1, • • • , m} it is easy to see that we can generate a switching signal that is shuffled almost surely. Furthermore, we can establish a link between the shuffling rate and the parameters of the Markov chain. Moreover, we can prove also the averaged shuffling index converges as well, this is detailed below.

Let us consider a Markov chain with a transition matrix P , where the states are the set of indices I and let θ = X 0 , X 1 , • • • be a generated signal, thus, almost surely, θ is a shuffling switching signal, to relate κ θ (t) with the Markov chain it is important to have a tractability on this quantity, this is not possible with Markov chain as it is, therefore it is necessary to add some sort of 'memory' on the Markov chain without altering its properties. This is possible by considering the product of two automata, the first is a Büchi automaton generating all shuffled signals for a given number of modes m. The second is an m-state automaton corresponding to the Markov chain. The resulting automaton can be seen as a representation of a Markov chain. In the following, we restrain our self to the case of two modes (m = 2) and we detail a procedure on computing the shuffling rate in this case. Note that this procedure can be generalized to any m > 0, furthermore it can be extended easily to compute the accepting index of any ω-regular language whose elements are generated by a Markov chain. Intuitively, each time the state ∅ 1 or the state ∅ 2 is visited we know that the switching signal has shuffled once. Therefore we will rely on this Markov chain to compute the shuffling rate of the switching signal. This is detailed in the following lines. Now let us consider a discrete-time Markov chain, the state-space is S and the transition matrix is P . Let us assume that there exists a row vector π satisfying πP = π, where all the elements of π are strictly positive and their sum is 1. Let N ij (t) denote the number of visits to state j ∈ S in t transition steps given that X 0 = i ∈ S, t ≥ 1. We aim to find if the limit lim

The left-hand side is the time of the first visit to j after t -1. Hence T (1)

≤ T

(1)

By the strong law of large numbers P T

(1)

and, since there are no absorption states (the Markov chain is irreducible and finite)

So, letting t → ∞ in (A), we get

→ m j as t → ∞ = 1 which implies

Finally, since the Markov chain is finite and irreducible, then from in [57, Theorem 1.7.7], we have 1 m j = π j , where π j is the j'th element of the limiting distribution vector π verifying πP = π and

Now if we consider j to belong to a particular set of states S, starting from X 0 = i the number of visits to states in S up to time t is given by N iS (t) =