Les principaux sujets d'intérêt de cette thèse concerneront deux notions de la complexité d'un mot infini : la complexité abélienne et la complexité de permutation. La complexité abélienne a été étudiée durant les dernières décennies. La complexité de permutation est, elle, une forme de complexité des mots relativement nouvelle qui associe à chaque mot apériodique de manière naturelle une permutation infinie. Nous nous pencherons sur deux sujets dans le domaine de la complexité abélienne. Dans un premier temps, nous nous intéresserons à une notion abélienne de la maximal pattern complexity définie par T. Kamae. Deuxièmement, nous analyserons une limite supérieure de cette complexité pour les mots C-équilibré. Dans le domaine de la complexité de permutation des mots apériodiques binaires, nous établissons une formule pour la complexité de permutation du mot de Thue-Morse, conjecturée par Makarov, en étudiant la combinatoire des sous-permutations sous l'action du morphisme de Thue-Morse. Par la suite, nous donnons une méthode générale pour calculer la complexité de permutation de l'image de certains mots sous l'application du morphisme du doublement des lettres. Finalement, nous déterminons la complexité de permutation de l'image du mot de Thue-Morse et d'un mot Sturmien sous l'application du morphisme du doublement des lettres. / The main topics of interest in this thesis will be two types of complexity, abelian complexity and permutation complexity. Abelian complexity has been investigated over the past decades. Permutation complexity is a relatively new type of word complexity which investigates lexicographical ordering of shifts of an aperiodic word. We will investigate two topics in the area of abelian complexity. Firstly we will consider an abelian variation of maximal pattern complexity. Secondly we consider an upper bound for words with the C-balance property. In the area of permutation complexity, we compute the permutation complexity function for a number of words. A formula for the complexity of Thue-Morse word is established by studying patterns in subpermutations and the action of the Thue-Morse morphism on the subpermutations. We then give a method to calculate the complexity of the image of certain words under the doubling map. The permutation complexity function of the image of the Thue-Morse word under the doubling map and the image of a Sturmian word under the doubling map are established.

La thèse s'intéresse au problème de l'analyse syntaxique pour les langages de programmation. Si ce sujet a déjà été traité à maintes reprises, et bien que des outils performants pour la génération d'analyseurs syntaxiques existent et soient largement employés, l'implémentation de la partie frontale d'un compilateur reste encore extrêmement complexe.<br /><br />Ainsi, si le texte d'un programme informatique se doit de n'avoir qu'une seule interprétation possible, l'analyse des langages de programmation, fondée sur une grammaire algébrique, est, pour sa part, le plus souvent non déterministe, voire ambiguë. Confrontés aux insuffisances des analyseurs déterministes traditionnels, les développeurs de parties frontales se sont tournés massivement vers des techniques d'analyse générale, à même d'explorer des choix non déterministes, mais aussi au prix de la garantie d'avoir bien traité toutes les ambiguïtés grammaticales. Une difficulté majeure dans l'implémentation d'un compilateur réside alors dans l'identification (non décidable en général) et le traitement de ces ambiguïtés.<br /><br />Les techniques décrites dans la thèse s'articulent autour d'approximations des grammaires à deux fins. L'une est la génération d'a\-na\-ly\-seurs syntaxiques non canoniques, qui sont moins sensibles aux dif\-fi\-cultés grammaticales, en particulier parce qu'ils peuvent exploiter un langage algébrique non fini en guise de contexte droit pour résoudre un choix non déterministe. Ces analyseurs rétablissent la garantie de non ambiguïté de la grammaire, et en sus assurent un traitement en temps linéaire du texte à analyser. L'autre est la détection d'ambiguïté en tant que telle, avec l'assurance qu'une grammaire acceptée est bien non ambiguë quel que soit le degré d'approximation employé.

Cette thèse étudie les structures dont la théorie au second ordremonadique est décidable, et en particulier la hiérarchie à pile. Onpeut définir celle-ci comme la hiérarchie pour $n$ des graphesd'automates à piles imbriquées $n$ fois ; une définition externe, partransformations de graphes, est également disponible. Nous nousintéressons à l'exemple des ordinaux. Nous montrons que les ordinauxplus petits que $epsilon_0$ sont dans la hiérarchie, ainsi que des graphesporteurs de plus d'information, que l'on appelle "graphecouvrants''. Nous montrons ensuite l'inverse : tous les ordinaux de lahiérarchie sont plus petits que $epsilon_0$. Ce résultat utilise le fait queles ordres d'un niveau sont en fait isomorphes aux structures desfeuilles des arbres déterministes dans l'ordre lexicographique, aumême niveau. Plus généralement, nous obtenons une caractérisation desordres linéaires dispersés dans la hiérarchie. Dans un troisièmetemps, nous resserons l'intérêt aux ordres de type $omega$ --- les mots infinis --- pour montrer que les mots du niveau 2 sont les motsmorphiques, ce qui nous amène à une nouvelle extension au niveau 3 / This thesis studies the structures with decidable monadic second-ordertheory, and in particular the pushdown hierarchy. The latter can bedefined as the family for $n$ of pushdown graphs with $n$ timesimbricated stacks ; another definition is by graph transformations. Westudy the example of ordinals. We show that ordinals smaller that $epsilon_0$are in the hierarchy, along with graphs called "covering graphs'', which carry more data than ordinals. We show then the converse : allordinals of the hierarchy are smaller than $epsilon_0$. This result uses thefact that linear orders of a level are actually isomorphic to thestructure of leaves of deterministic trees by lexicographic ordering, at the same level. More generally, we obtain a characterisation ofscattered linear orders in the hierarchy. We finally focus on the caseof orders of type $omega$ --- infinite words --- and show that morphicwords are exactly words of the second level of the hierarchy. Thisleads us to a new definition of words for level 3

On s'est interesse dans ce travail a l'etude de deux equations cinetiques. La premiere est une equation cinetique quantique homogene decrivant l'effet Compton. Ce phenomene se produit lorsque les photons entrent en collision avec les electrons. Le noyau dans l'integrale de collision presente une forte singularite en l'energie nulle. Un resultat d'existence locale en temps d'une solution entropique au probleme de Cauchy est obtenu pour de petites valeurs initiales. La deuxieme est une equation de Vlasov couplee avec l'equation de Poisson. Le systeme de Vlasov-Poisson modelise les interactions entre plasma et satellite. Plus precisement, on s'interesse au phenomene de charge electrostatique d'un satellite en orbite geostationnaire. Les particules, essentiellement des ions et des electrons, sont décrites suivant une approche cinétique. On considère le cas où la dynamique des ions et des électrons obéit à une équation de Vlasov et où le potentiel est donné par l'équation de Poisson. Le but est d'etudier ce probleme dans un cadre 3D dans tout l'espace. Une methode particulaire pour la resolution de l'equation de Vlasov est couplee a une methode d'elements finis et infinis pour la partie Poisson.

Cette thèse traite du problème de la vérification de systèmes ayant un nombre infini d'états. Ces systèmes peuvent être décrits par plusieurs formalismes tels que des algèbres de processus ou des automates finis munis de structures de données non-bornées (automates à pile, réseaux de Petri ou systèmes à files). Dans une première partie de la thèse nous nous intéressons à la caractérisation de classes de systèmes infinis et de propriétés pour lesquels le problème de vérification est décidable. Nous considérons d'abord la complexité de la vérification du mu-calcul linéaire pour les réseaux de Petri. Ensuite, nous définissons des logiques temporelles qui permettent d'exprimer des propriétés non-régulières comportant des contraintes linéaires sur le nombre d'occurrences d'événements. Ces logiques sont plus expressives que les logiques utilisées dans le domaine. Nous montrons en particulier que le problème de la vérification d'une logique qui est plus expressive que le mu-calcul linéaire est décidable pour des classes de systèmes infinis telles que les automates à pile et les réseaux de Petri. Une deuxième partie de la thèse est consacrée aux systèmes communicant par files d'attente, dont le problème de vérification est en général indécidable. Nous appliquons le principe de l'analyse symbolique à ces systèmes. Nous proposons des structures finies qui permettent de représenter et de manipuler des ensembles infinis de configurations de tels systèmes. Ces structures permettent de calculer l'effet exact d'une exécution répétée de tout circuit dans le graphe de transitions du système. Ainsi, chaque circuit peut être considéré comme une nouvelle "transition" du système. Nous utilisons ce résultat pour accélérer le calcul de l'ensemble des configurations atteignables d'un système afin d'augmenter les chances de terminaison de ce calcul.

Le but de ce travail est de proposer un système formel pour prouver que l'ensemble des succès d'un programme logique est inclus dans l'ensemble correspondant d'un autre programme. Cela permet de prouver que deux programmes logiques, un qui représente la spécification et un représentant l'implantation sont équivalents. Le langage logique considéré est CLPforall qui est le langage le langage de programmation logique avec contraintes (CLP) auquel est ajouté le quantificateur universel. Nous présentons les sémantiques des succès finis et infinis et montrons qu'elles sont données par le plus petit et le plus grand point fixe du même opérateur. Un système de preuve pour l'inclusion des succès finis est présenté. Le système utilise pour les opérateurs et les quantificateurs logiques les mêmes règles que la logique du premier ordre. Pour raisonner sur les prédicats récursifs le système contient une règle d'induction. Nous prouvons la correction du système sous certains conditions. Un système analogue pour l'inclusion des succès infinis est présenté. La règle d'induction est remplacée par une règle de coinduction. La correction est démontrée sous conditions analogues. Les deux systèmes sont équivalents sous certains conditions. Une implantation a été réalisée sous la forme d'assistant de preuve écrit en Prolog. Le programme a environ 4000 lignes et contient des procédures simples mais efficaces de recherche de preuves. Nous présentons des exemples de preuves réalises avec ce programme parmi lesquels la preuve de correction de quicksort.

Cette thèse est consacrée à l'étude mathématique des propriétés de stabilité de systèmes quantiques infinis, décrits par des modèles non linéaires. Dans les chapitres 1 et 2, on étudie l'instabilité du vide relativiste menant au phénomène de création de paires électron-positron. Dans le chapitre 3, on considère la dynamique de ce même vide relativiste couplé à un champ scalaire. Les chapitres 4 et 5 sont consacrés au caractère dispersif de la dynamique non linéaire de Hartree pour des perturbations de la mer de Fermi, et en particulier à sa stabilité orbitale et asymptotique. Enfin, le chapitre 6 introduit une notion générale d'entropie relative entre deux états comportant une infinité de particules. / This thesis is devoted to the mathematical study of stability properties of infinite quantum systems described by nonlinear models. In chapters 1 and 2, we study the instability of the relativistic vacuum leading to the phenomenon of electron-positron pair production. In chapter 3, we consider the dynamics of this same relativistic vacuum coupled to a scalar field. Chapters 4 and 5 are devoted to the dispersive behaviour of the nonlinear Hartree dynamics for perturbations of the Fermi sea, and in particular to its orbital and asymptotic stability. Finally, chapter 6 introduces a general notion of relative entropy between states having infinitely many particles.

Cette these est composee de deux parties independantes ayant pour point commun l’utilisation intensive de la theorie des ∞-categories. Dans la premiere, on s’interesse aux liens entre deux approches differentes de la formalisation de la physique des particules : les algebres vertex et les algebres a factorisation a la Costello. On montre en particulier que dans le cas des theories dites topologiques, elles sont equivalentes. Plus precisement, on montre que les∞-categories de fibres vectoriels factorisant non-unitaires sur une variete algebrique complexe lisse X est equivalente a l’∞-categorie des EM-algebres non-unitaires et de dimension finie, ou M est la variete topologique associee a X. Dans la seconde, avec Mathieu Anel, nous etudions la caracterisation de l’exponentiabilite dans l’∞-categorie des ∞-topos. Nous montrons que les ∞-topos exponentiables sont ceux dont l’∞-categorie de faisceaux est continue. Une consequence notable est que l’∞-categorie des faisceaux en spectres sur un ∞-topos exponentiable est un objet dualisable de l’∞-categorie des ∞-categories cocompletes stables munie de son produit tensoriel. Ce chapitre contient aussi une construction des ∞-coends a partir de la theorie du produit tensoriel d’∞- categories cocompletes, ainsi qu’une description des ∞-categories de faisceaux sur un ∞-topos exponentiable en termes de faisceaux de Leray. / This thesis is made of two independent parts, both relying heavily on the theory of ∞-categories. In the first chapter, we approach two different ways to formalize modern particle physics, through the theory of vertex algebras and the theory of factorisation algebras a la Costello. We show in particular that in the case of ‘topological field theories’, they are equivalent. More precisely, we show that the ∞-category of non-unital factorization vector bundles on a smooth complex variety X is equivalent to the ∞-category of non-unital finite dimensional EM-algebras where M is the topological manifold associated to X. In the second one, with Mathieu Anel, we study a characterization of exponentiable objects of the∞-category of∞-toposes.We show that an ∞-topos is exponentiable if and only if its ∞-category of sheaves of spaces is continuous. An important consequence is the fact that the ∞-category of sheaves of spectra on an exponentiable ∞-topos is a dualisable object of the ∞-category of cocontinuous stable ∞-categories endowed with its usual tensor product. This chapter also includes a ix construction of∞-coends from the theory of tensor products of cocomplete∞- categories, together with a description of∞-categories of sheaves on exponentiable ∞-toposes in terms of Leray sheaves.

Pour des applications depositionnement, les moteurs piézoélectriquesprésentent aujourd’hui une alternativeintéressante aux moteurs électromagnétiquesclassiques en raison de leur forte précision del’ordre de quelques nanomètres ainsi que de leurfaible niveau de bruit électromagnétique. Dansce contexte, les travaux de cette thèse portent surla modélisation, la conception, et l’implantationen temps réel de contrôleurs en position pour desmoteurs piézoélectriques. L’objectif est deproposer un système de contrôle en positionrobuste pour des applications robotiques avecun cahier des charges prédéfini. Trois moteurspiézoélectriques avec des principes defonctionnement différents (USR60, PAD7220,N-310.13) ont été choisis. Leurs modèlesélectromécaniques ont été développés afin devalider leurs principes de fonctionnement etd’analyser leurs comportements dynamiquesface à des perturbations (variation de couple decharge, de température, etc…). Ensuite, cesmodèles sont utilisés pour simuler et valider lesperformances des algorithmes de contrôle enboucle fermée notamment en termes deprécision, de robustesse et de stabilité. Desbancs de test expérimentaux ont été mis enœuvre pour les trois moteurs, et des modèlesréduits reliant les positions des moteurs auxsignaux de commande correspondants ont étéidentifiés expérimentalement. Deux contrôleursde position de type H-infini (H∞) et RST sontensuite synthétisés et simulés. Ces contrôleurssont implantés en temps réel sur les bancs detests expérimentaux via un système dSPACE.Les performances de chaque moteur associé à sacommande sont évaluées. Une étudecomparative entre les résultats expérimentauxde ces deux contrôleurs et ceux d’un contrôleurPID classique est aussi présentée. / The Piezoelectric motors present aninteresting alternative to electromagneticsmotors for precise positioning systems. This ismainly due to their high accuracy in thenanometer scale, and to their very lowelectromagnetic noise levels. In this context, thework presented in this thesis deals with themodeling, design, and real time implementationof position controllers for piezoelectric motors.The objective is to propose robust closed loopposition controller of piezoelectric motors forrobotic applications. Based on the applicationspecification requirements, three motors withdifferent topologies (USR60, PAD7220, N-310.10) are selected. Their electro mechanicmodels are developed in order to validate theiroperating principle and to analyze theirdynamics.These models are also used to simulate thecontroller algorithms in closed loop.Experimental platforms based on the threemotors are designed, and the reduced modelslinking the motor positions to the correspondingcontrol signals are experimentally identified.Afterwards, two position controllers of type Hinfinity(H∞) and RST are synthesized andsimulated. These controllers are implemented inreal time via the experimental platformsequipped by dSPACE boards. The performancesof each motor in closed loop associated to theposition controllers are evaluated using theexperimental results. Comparative studybetween the experimental results of twoproposed controllers and conventional PIDcontroller is also presented.Université Paris-

Le sujet de cette thèse se divise en trois parties: les deux premières traitent chacune d'une extension du modèle utilisé en théorie des automates, tandis que la dernière aborde une partie plus concrète qui consiste à générer des automates avec des propriétés particulières. Tout d'abord, nous donnons une extension du concept d'automate universel, défini sur les mots finis, aux omega-langages. Pour cela, nous avons défini une forme normale pour tenir compte de la spécificité du mode d'acceptation des automates de Büchi qui nous permettent de reconnaître les omega-langages. Ensuite nous avons défini deux types d'omega-factorisations, "classiques" et "pures", qui sont des extensions du concept de factorisation d'un langage, ce qui nous a permis de définir l'automate universel d'un omega-langage. Nous avons prouvé que ce dernier dispose bien des différentes propriétés attendues: il est le plus petit automate de Büchi reconnaissant l'omega-langage et qui possède la propriété d'universalité (moyennant la forme normale). Nous présentons également une méthode pour calculer efficacement les omega-factorisations maximales d'un langage à partir d'un automate prophétique reconnaissant le dit langage. Dans la seconde partie, nous traitons le cas des automates bidirectionnels à multiplicité dans un semi-anneau. Dans un premier temps, nous donnons une version légérement différente de la construction permettant de passer d'un automate bidirectionnel à multiplicité à un automate unidirectionnel à multiplicité et nous prouvons qu'elle préserve la non-ambiguïté mais pas le déterminisme. Nous montrons, également à l'aide d'une construction, que les automates bidirectionnels à multiplicité non-ambigus sont équivalents aux automates unidirectionnels à multiplicité déterministes. Dans un second temps, nous nous concentrons sur les semi-anneaux tropicaux (ou min-+). Nous montrons que sur N-min-+, les automates bidirectionnels sont équivalents aux automates unidirectionnels. Nous montrons également que sur Z-min-+, les automates bidirectionnels n'ont pas toujours un comportement défini et que cette propriété est décidable tandis qu'il n'est pas décidable s'il existe un mot pour lequel le comportement est défini. Dans la dernière partie, nous proposons un algorithme de génération aléatoire d'automate acycliques, accessibles et déterministes ainsi que d'automates acycliques minimaux avec une distribution qui est quasiment uniforme, tout cela à l'aide de chaîne de Markov. Nous prouvons l'exactitude de chacun de ces deux algorithmes et nous expliquons comment adapter en tenant compte de contraintes sur l'ensemble des états finals / The subject of this thesis is decided into three parts: two of them are about extensions of the classical model in automata theory, whereas the third one is about a more concrete aspect which consists in randomly generate automata with specific properties. We first give an extension of the universal automaton on finite words to infinite words. To achieve this, we define a normal form in order to take account of the specific acceptance mode of Büchi automata which recognize omega-langages. Then we define two kinds of omega-factorizations, a "regular" one and the "pure" kind, which are both extensions of the classical concept of factorization of a language. This let us define the universal automaton of an omega-language. We prove that it has all the required properties: it is the smallest Buchi automaton, in normal form, that recognizes the omega-language and which has the universal property. We also give an effective way to compute the "regular" omega-factorizations of a language using a prophetic automaton recognizing the language. In the second part, we deal with two-way automata weighted over a semi ring. First, we give a slightly different version of the computation of a weighted one-way automaton from a weighted two-way automaton and we prove that it preserves the non-ambiguity but not the determinism. We prove that non-ambiguous weighted two-way automata are equivalent to deterministic weighted one-way automata. In a later part, we focus on tropical semi rings (or min-+). We prove that two-way automata on N-min-+ are equivalent to one-way automata on N-min-+. We also prove that the behavior of two-way automata on Z-min-+ are not always defined and that this property is decidable whereas it is undecidable whether or not there exists a word on which the behavior is defined. In the last section, we propose an algorithm in order to randomly generate acyclic, accessible and determinist automata and minimal acyclic automata with an almost uniform distribution using Morkov chains. We prove the reliability of both algorithms and we explain how to adapt them in order to fit with constraints on the set of final states