In this thesis, we consider three fundamental problems of transducers theory. The containment problem asks, given two transducers,whether the relation defined by the first is included into the relation defined by the second. The equivalence problem asks, given two transducers,whether they define the same relation. Finally, the sequential uniformisation problem,corresponding to the synthesis problem in the setting of transducers,asks, given a transducer, whether it is possible to deterministically pick an output correspondingto each input of its domain. These three decision problems are undecidable in general. As a first step, we consider different manners of recovering the decidability of the three problems considered.First, we characterise a family of classes of transducers, called controlled by effective languages, for which the containment and equivalence problems are decidable. Second, we add structural constraints to the problems considered: for instance, instead of only asking that two transducers define the same relation, we require that this relation is defined by both transducers in a similar way. This `similarity' is formalised through the notion of delay,used to measure the difference between the output production of two transducers. This allows us to introduce stronger decidable versions of our three decision problems, which we use to prove the decidability of the original problems in the setting of finite-valued transducers. In the second part, we study extensions of the automaton model,together with the adaptation of the sequential uniformisation problems to these new settings.Weighted automata are automata which,along each transition, output a weight in Z. Then, whereas a transducer preserves all the output mapped to a given input, weighted automata only preserve the maximal weight. In this setting, the sequential uniformisation problem turns into the determinisation problem: given a weighted automaton, is it possible to deterministically pick the maximal output mapped to each input? The decidability of this problem is open.The notion of delay allows us to devise a complete semi-algorithm deciding it. Finally, we consider two-way transducers, that are allowed to move back and forth over the input tape. These transducers enjoy good properties with respect to the sequential uniformisation problem: every transducer admits a sequential two-way uniformiser. We strengthen this result by showing that every transducer admits a reversible two-way uniformiser, i.e. a uniformiser that is both sequential and cosequential (backward sequential). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this thesis, we are concerned with multi-player games played on finite graphs. They are games in which the players interact trying to fulfil their own objectives which are not necessarily antagonistic to the others’. More particularly, we are interested in the study of dynamics which model the behaviour of the players when they repeatedly update their strategy in order to achieve a better outcome. A dynamics terminates when these updates converge to a state in which the players have no incentive to further update their respective strategies. We define several dynamics characterised by the type of updates made by the players.There are two types of contributions in this thesis. The first one is to draw a general framework to reason about the termination of dynamics in order to show its applicability to particular problems. In this abstract framework, we present several meta-theorems that make the links between games and dynamics explicit. For example, we introduce a notion of game minor that allows to induce simulations between the associated dynamics. The second type of contribution is the application of dynamics to a particular context, characterised by three parameters: the arena of the game, the conditions over the dynamics, and the payoff functions of the players. The first arena we deal with are sequential games (or games played on trees). Among other results, we prove that the acyclicity of the preferences is a necessary and sufficient condition to ensure the termination of dynamics that respect the Subgame Improvement Property (i.e. every update has to improve the payoff in the subgame of the change).Another studied arena is the so called One-player Games. We model BGP (Border Gateway Protocol, which is a standard interdomain routing protocol) into dynamics on graphs. We firstly revisit some classical results of network theory in our context, then we identify a theoretical and relevant framework regarding to the termination of the dynamics. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse a pour but d'illustrer et de faire avancer l'état des connaissances sur certaines problématiques liées à l'utilisation de la cryptographie résistante à un adversaire muni d'un ordinateur quantique. L'intérêt suscité par le développement d'algorithmes dit "post-quantiques" a pris une ampleur majeure dans les dernières années suite aux progrès techniques de l'informatique quantique et la décision du NIST (National Institute of Standards and Technology) d'organiser un projet de standardisation. En particulier, nous nous intéressons aux algorithmes basant leur sécurité sur la difficulté de résoudre certains problèmes liés a un object mathématique appelé emph{réseau euclidien}. Ce type de cryptographie ayant déjà été étudiée de manière soutenue en théorie, une partie la communauté scientifique s'est maintenant tournée vers les aspects pratiques. Nous présentons dans la thèse trois sujets majeurs relatifs à ces aspects pratiques, chacun discuté dans un chapitre soutenu par une publication scientifique. Le premier sujet est celui des implémentations efficaces. L'utilisation de la cryptographie dans la société moderne implique de programmer du matériel informatique sécurisant des données. Trouver la manière la plus efficace d'implémenter les fonctions mathématiques décrites dans les spécifications de l'algorithme n'est pas toujours simple. Dans le chapitre correspondant à ce premier sujet, nous allons présenter un papier établissant la façon la plus rapide connue actuellement d'implémenter certains algorithmes participant au projet du NIST. Le deuxième sujet est celui des attaques par canaux auxiliaires. Une fois l'algorithme implémenté, son utilisation dans le monde physique donne une surface d'attaque étendue à l'adversaire. Certaines techniques sont connues pour mitiger les nouvelles attaques pouvant survenir. Dans ce chapitre, nous étudierons l'application d'une technique appelée emph{masquage} qui a été appliquée à un algorithme de signature post-quantique, lui aussi candidat au projet du NIST. Finalement, le dernier chapitre de contributions s'intéresse à la possibilité de fusionner deux algorithmes afin de créer un outil spécialisé plus efficace que l'utilisation des deux algorithmes de base. Cette technique de fusion était déjà connue par le passé mais n'avait été beaucoup étudiée dans le cadre de la cryptographie post-quantique. Ce dernier aspect est donc légèrement plus orienté design que purement pratique, mais la possibilité de fusionner à moindre coup des fonctionnalités permet d'avoir un gain concret lors de l'utilisation. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui ont été établies concernant les langages, notamment le célèbre théorème de Schützenberger-McNaughton-Papert. Dans le cadre des fonctions rationnelles sur les mots finis, nous obtenons une caractérisation à la Myhill-Nerode en termes de congruences d'indice fini. Cette caractérisation nous permet d'obtenir un résultat de transfert, à partir d'équivalences logique-algèbre pour les langages vers des équivalences pour les transductions. En particulier nous montrons comment décider si une fonction rationnelle est définissable en logique du premier ordre. Sur les mots infinis, nous pouvons également décider la définissabilité en logique du premier ordre, mais avec des résultats moins généraux.Les fonctions rationnelles sur les mots infinis sont plus difficiles à caractériser et nous obtenons un résultat plus faible: étant donné un transducteur nous montrons comment calculer un transducteur canonique, c'est-à-dire indépendant du transducteur initial, réalisant la même fonction.Cependant cette machine canonique nous permet tout de même de décider si une fonction est définissable en logique du premier ordre.Dans la seconde partie nous introduisons une logique pour les transductions et nous résolvons le problème de synthèse régulière: étant donnée une formule de la logique, peut-on obtenir un transducteur bidirectionnel déterministe satisfaisant la formule ?Dans la seconde partie nous considérons un problème de synthèse: étant donné une relation (spécification) peut-on obtenir une fonction (un programme) qui est inclus dans (qui satisfait) la relation. Les fonctions réalisées par des transducteurs bidirectionnels déterministes sont caractérisés par plusieurs modèles différents, y compris par les transducteurs MSO, et ont ainsi été nommées transductions régulières.Nous introduisons une logique expressive pour les transduction et nous résolvons le problème de synthèse régulière pour cette logique.Plus précisément nous fournissons un algorithme qui produit toujours une fonction régulière satisfaisant une spécification donnée en entrée.Nous exposons également un lien intéressant entre les transductions et les mots avec données.Par conséquent nous obtenons une logique expressive pour les mots avec données, pour laquelle le problème de satisfiabilité est décidable. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this work, we focus on two kinds of problems involving the proximity of geometric objects. The first part revolves around intersection detection problems. In this setting, we are given two (or more) geometric objects and we are allowed to preprocess them. Then, the objects are translated and rotated within a geometric space, and we need to efficiently test if they intersect in these new positions. We develop representations of convex polytopes in any (constant) dimension that allow us to perform this intersection test in logarithmic time.In the second part of this work, we turn our attention to facility location problems. In this setting, we are given a set of sites in a geometric space and we want to place a facility at a specific place in such a way that the distance between the facility and its farthest site is minimized. We study first the constrained version of the problem, in which the facility can only be place within a given geometric domain. We then study the facility location problem under the geodesic metric. In this setting, we consider a different way to measure distances: Given a simple polygon, we say that the distance between two points is the length of the shortest path that connects them while staying within the given polygon. In both cases, we present algorithms to find the optimal location of the facility.In the process of solving facility location problems, we rely heavily on geometric structures called Voronoi diagrams. These structures summarize the proximity information of a set of ``simple'' geometric objects in the plane and encode it as a decomposition of the plane into interior disjoint regions whose boundaries define a plane graph. We study the problem of constructing Voronoi diagrams incrementally by analyzing the number of edge insertions and deletions needed to maintain its combinatorial structure as new sites are added. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Nous étudions le problème de la synthèse automatique de programmes dans des architectures multi-composants tels qu'elles respectent les spécifications par construction. Le principal objectif de cette thèse est de développer des procédures pour résoudre le problème de synthèse qui peut conduire à des implémentations efficaces. Chaque composant a une observation partielle sur l'état global du système multi-composants. Le problème est alors de fournir des protocoles basés sur les observations tel que les composants synthétisés assurent les spécifications pour tout le comportement de leur environnement.L'environnement peut être antagoniste, ou peut avoir ses propres objectifs et se comporter de façon rationnelle. Nous étudions d'abord le problème de synthèse lorsque l'environnement est présumé antagoniste. Pour ce contexte, nous proposons une procédure "Safraless" pour la synthèse d'un composant partiellement informé et un environnement omniscient à partir de spécifications KLTL+. Elle est implémentée dans l'outil Acacia-K. Ensuite, nous étudions le problème de synthèse lorsque les composants de l'environnement ont leurs propres objectifs et sont rationnels. Pour le cadre plus simple de l'information parfaite, nous fournissons des complexités serrées pour des objectifs oméga-réguliers particuliers. Pour le cas de l'information imparfaite, nous prouvons que le problème de la synthèse rationnelle est indécidable en général, mais nous regagnons la décidabilité si on demande à synthétiser un composant avec observation partielle contre un environnement multi-composante, omniscient et rationnel. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

This thesis presents methods for minimizing the computational effort of problem solving. Rather than looking at a particular algorithm, we consider the issue of computational complexity at a higher level, and propose techniques that, given a set of candidate algorithms, of unknown performance, learn to use these algorithms while solving a sequence of problem instances, with the aim of solving all instances in a minimum time. An analogous meta-level approach to problem solving has been adopted in many different fields, with different aims and terminology. A widely accepted term to describe it is algorithm selection. Algorithm portfolios represent a more general framework, in which computation time is allocated to a set of algorithms running on one or more processors.Automating algorithm selection is an old dream of the AI community, which has been brought closer to reality in the last decade. Most available selection techniques are based on a model of algorithm performance, assumed to be available, or learned during a separate offline training sequence, which is often prohibitively expensive. The model is used to perform a static allocation of resources, with no feedback from the actual execution of the algorithms. There is a trade-off between the performance of model-based selection, and the cost of learning the model. In this thesis, we formulate this trade-off as a bandit problem.We propose GambleTA, a fully dynamic and online algorithm portfolio selection technique, with no separate training phase: all candidate algorithms are run in parallel, while a model incrementally learns their runtime distributions. A redundant set of time allocators uses the partially trained model to optimize machine time shares for the algorithms, in order to minimize runtime. A bandit problem solver picks the allocator to use on each instance, gradually increasing the impact of the best time allocators as the model improves. A similar approach is adopted for learning restart strategies online (GambleR). In both cases, the runtime distributions are modeled using survival analysis techniques; unsuccessful runs are correctly considered as censored runtime observations, allowing to save further computation time.The methods proposed are validated with several experiments, mostly based on data from solver competitions, displaying a robust performance in a variety of settings, and showing that rough performance models already allow to allocate resources efficiently, reducing the risk of wasting computation time. / Permanent URL: http://doc.rero.ch/record/20245 / info:eu-repo/semantics/nonPublished

A few methodological contributions to the PROMETHEE method, essentially based on 3 articles:-FlowSort parameters elicitation based on categorization examples;-PROMETHEE is Not Quadratic: An O (qnlog (n)) Algorithm;-Lexicographic constrained multicriteria ordered clustering. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Les codes identifiants dans les graphes modélisent des systèmes de détection et de localisation à distance de pannes multiples dans les réseaux. Nous abordons dans une première partie différents problèmes de nature algorithmique ou structurelle concernant plusieurs variations autour de ces codes ; en particulier, nous obtenons de nombreux résultats quant à la structure des graphes sans jumeaux. Ces questions nous amènent dans une deuxième partie à considérer une notion de puissance de graphe, que nous étudions plus avant. Nous obtenons en particulier des résultats de type extrémal et nous consacrons l'étude des racines carrées de graphes.

Cette thèse présente différents aperçus de problèmes de mathématiques discrètes en lien avec la théorie des graphes. Elle s'intéresse en particulier à la coloration de graphes, i.e. l'assignation de couleurs aux sommets (ou arêtes) d'un graphes sous certaines contraintes locales, notamment l'exclusion de motifs. Pour différents types de coloration (choisissabilité des sommets, des arêtes, coloration acyclique ou linéaire, ...), un état de l'art est présenté, accompagné de résultats d'existence sur les graphes planaires ou leurs sous-classes, ayant pour but de minimiser le nombre de couleurs nécessaires pour un degré maximum ou un degré moyen maximum (Mad) donnés. Cette thèse traite également de décompositions induites de graphes, et démontre qu'il existe pour tout graphe $H$ une suite infinie de graphes denses dont les arêtes peuvent être partitionnées en copies induites de $H$. Cette preuve requiert le formalisme des hypergraphes, pour lesquels un autre résultat de décomposition est démontré, i.e. une décomposition optimale de l'hypergraphe complet 3-régulier en hypergraphes $\alpha$-acycliques. La troisième parti porte sur des questions algorithmiques. Elles consistent en problèmes d'optimisation ou d'existence, motivés par le routage d'information dans les réseaux, analysés par le formalisme classique de complexité algorithmique, ou traitent de la recherche de sous-graphes dans le formalisme de la complexité paramétrée. Dans une quatrième partie sont considérés des problèmes de comptage issus de la chimie, suivis de la présentation de Programmes Linéaires Entiers utilisés dans le logiciel de mathématiques Sage.