Littérature scientifique sur le sujet « Complexité Borélienne de relations d'équivalence »

Cette thèse s'inscrit dans le cadre de la dynamique topologique, branche des systèmes dynamiques s'intéressant aux comportements qualitatifs asymptotiques de transformations continues provenant d'une action de groupe ou de semigroupe sur un espace métrique usuellement compact. Par exemple, une question classique pourrait être de savoir si tel système dynamique admet des points récurrents, c'est à dire des points qui vont revenir arbitrairement proche de leur point de départ infiniment souvent sous la dynamique. Souvent, de par leur caractère qualitatif et asymptotique, ces propriétés ne dépendent pas précisément du système mais plutôt des orbites des points, i.e des positions qu'il vont atteindre. D'où la notion d'équivalence orbitale au coeur de cette thèse, qui consiste à considérer que, après identification des espaces sous-jacents, deux systèmes dont tous les points auraient les mêmes orbites seraient "qualitativement les mêmes". Au cours des années 90, Giordano Putnam et Skau ont réussi à établir grâce à des outils d'algèbre homologique une classification à équivalence orbitale près des systèmes dynamiques minimaux provenant d'actions de \Z sur l'espace de Cantor en termes à la fois de groupes pleins et de mesures invariantes. Ce résultat montre en particulier qu'il existe une infinité non-dénombrable de tels systèmes différents à équivalence orbitale près, ce qui contraste assez fortement avec le cadre de la théorie ergodique, domaine très proche s'intéressant aux systèmes dynamiques mesurés, dans lequel la combinaison de deux célèbres résultats, l'un dû à Ornstein et Weiss et l'autre à Dye montre qu'il n'y a à équivalence orbitale près qu'une seule action de groupe moyennable sur un espace de probabilité standard. Ma principale contribution à travers le présent manuscrit consiste à apporter un éclairage et des preuves dynamiques élémentaires aux classifications obtenues par Giordano, Putnam et Skau (celle sur l'équivalence orbitale susmentionnée ainsi qu'une autre traitant d'une variation nommée équivalence orbitale forte), tant afin de les comprendre sous une autre perspective que pour tenter de les étendre à d'autres contextes. Chemin faisant, je démontrerai également un résultat de complexité Borélienne, à savoir que la relation d'isomorphisme de groupes dénombrables, localement finis et simples et une relation universelle provenant d'une action Borélienne de S_\infty, et nous améliorerons un résultat de Krieger sur la conjugaison des groupes amples
This thesis takes place in the context of topological dynamics, a branch of dynamical systems concerned with the asymptotic qualitative behavior of continuous transformations arising from a group or semigroup action on a usually compact metric space. For example, a classic question might be whether a dynamical system admits recurrent points, i.e. points that will return arbitrarily close to their starting point infinitely often under the dynamics. Often, because of their qualitative and asymptotic nature, these properties do not depend precisely on the system but rather on the orbits of the points, i.e. the positions they will reach. Hence the notion of orbit equivalence at the heart of this thesis, which consists in considering that, after identification of the underlying spaces, two systems whose points all have the same orbits would be "qualitatively the same". In the 1990s, Giordano Putnam and Skau used homological algebra to establish a classification up to orbit equivalence of minimal dynamical systems arising from Z-actions on a Cantor space in terms of both full groups and invariant measures. This result shows in particular that there are non-countably many such different systems up to orbit equivalence, which contrasts quite strongly with the framework of ergodic theory, a very close field concerned with measured dynamical systems, in which the combination of two famous results, one due to Ornstein and Weiss and the other to Dye, shows that there is only one amenable group action on a standard probability space up to orbit equivalence. My main contribution in the present manuscript is to bring an elementary perpective and dynamical proofs to the classifications obtained by Giordano, Putnam and Skau (the one on orbital equivalence mentioned above as well as another one dealing with a variation called strong orbital equivalence), both in order to understand them from another perspective and to try to extend them to other contexts. Along the way, I will also prove a result of Borelian complexity, namely that the isomorphism relation of countable, locally finite and simple groups and a universal relation arising from a Borelian action of S_\infty, and improve a result of Krieger about the conjugation of ample groups

Le problème de la combinaison des services, autrement appelé problème de la composition, constitue le foyer d'une intense activité de recherche. Composer les services entre eux, c'est entrelacer leurs séquences d'actions, de manière à obtenir des séquences qui satisfassent les exigences des clients. Le problème de la composition de services est difficile à résoudre en général. Dans cette thèse nous considérons des services qui peuvent à la fois exécuter des actions de communications ainsi que des actions internes. De plus, des conditions peuvent être exigées et des effets peuvent être appliqués sur les transitions. Formellement, les services sont représentés par des automates communicants conditionnels. Nous définissons, pour ce modèle, le problème de la composition et nous étudions sa décidabilité pour différentes relations d'équivalence et de préordre à savoir : l'inclusion de traces, l'équivalence de traces, la simulation et la bisimulation. Suite aux résultats de décidabilité obtenus, nous proposons trois variantes pour le modèle initial. Pour chacune d'elles, nous définissions le problème de la composition et nous étudions sa complexité pour les relations citées ci-dessus.

Le problème de la combinaison des services, autrement appelé problème de la composition, constitue le foyer d'une intense activité de recherche. Composer les services entre eux, c'est entrelacer leurs séquences d'actions, de manière à obtenir des séquences qui satisfassent les exigences des clients. Le problème de la composition de services est difficile à résoudre en général. Dans cette thèse nous considérons des services qui peuvent à la fois exécuter des actions de communications ainsi que des actions internes. De plus, des conditions peuvent être exigées et des effets peuvent être appliqués sur les transitions. Formellement, les services sont représentés par des automates communicants conditionnels. Nous définissons, pour ce modèle, le problème de la composition et nous étudions sa décidabilité pour différentes relations d'équivalence et de préordre à savoir : l'inclusion de traces, l'équivalence de traces, la simulation et la bisimulation. Suite aux résultats de décidabilité obtenus, nous proposons trois variantes pour le modèle initial. Pour chacune d'elles, nous définissions le problème de la composition et nous étudions sa complexité pour les relations citées ci-dessus
The problem of combining services, also called the services composition problem, constitutes the centre of intense research activity. To compose services consists of merging their action sequences in order to obtain new sequences that satisfy the client requirements. This problem is in general difficult to solve. In this thesis, we consider services that are able to perform two kinds of actions: communication actions and internal actions. Moreover, services are able to verify conditions before an action execution and to change the value of variables after an action execution. Formally, services are represented by conditional communicating automata. We define for this model the services composition problem and we study its decidability for the following preorder and equivalence relations: traces inclusion, trace equivalence, simulation and bisimulation. Further to the decidability results obtained we propose three variants of the initial model. For each variant we define the composition problem and we study its complexity regarding the relations cited above

Cette thèse porte sur l’analyse des protocoles cryptographiques. Ce sont des suites d’instructions permettant d’interagir à distance avec un interlocuteur tout en protégeant le contenu sensible de la communication d’une potentielle tierce partie malveillante. Des cas classiques où la confidentialité et l’intégrité de la communication sont critiques sont, parmi d’autres, les paiements et services de santé en ligne, ou le vote électronique. Nous étudions les notions de sécurité définies techniquement par des équivalences observationnelles (ce qui inclut, entre autres, la confidentialité, l’anonymat ou la non-traçabilité). Nous avons conçu un programme, DeepSec, qui, à partir de la description d’un protocole pour un nombre fixé de participants, vérifie de manière entièrement automatisée si le protocole offre une garantie de sécurité donnée de ce type. Nous démontrons ensuite la capacité de cet outil à analyser des scenarios d’attaques complexes à travers plusieurs exemples. Dans un deuxième temps, nous présentons une technique d’optimisation reposant sur l’exploitation de symétries dans les preuves de sécurité. Typiquement, les participants ayant des rôles similaires dans le protocole ont souvent les mêmes instructions à suivre, ce qui induit des tâches redondantes lors de l’analyse. Sur plusieurs exemples, l’utilisation de cette technique d’optimisation a permis de réduire le temps d’analyse de DeepSec de plusieurs ordres de magnitude. Enfin, nous avons également étudié l’aspect théorique du problème afin de déterminer dans quelle mesure l’algorithme de DeepSec pouvait être amélioré (peut-on rendre l’outil plus rapide ?) ou rendu plus expressif (peut-on rendre l’outil capable d’analyser plus de protocoles, i.e., nous débarrasser de certaines de ses limitations ?). Nous avons pour cela fait une analyse de complexité calculatoire complète de l’algorithme de DeepSec, et l’avons intégré à une revue détaillée de l’état de l’art des résultats de complexité dans des contextes similaires. Cette revue minutieuse nous a permis de mettre au jour des variations subtiles dans la formalisation du problème à travers la littérature — parfois ayant un impact sur sa complexité. Nous y incluons de nouveaux résultats et améliorons certains ce ceux passés en revue, offrant une compréhension plus claire du problème
This thesis studies the analysis of cryptographic protocols. They are sequences of instructions permitting to interact with a recipient remotely while protecting the sensitive content of the communication from a potential malicious third party. Classical cases where the confidentiality and the integrity of the communication are critical are, among others, online payments and medical-service booking, or electronic voting. We study notions of security defined technically by observational equivalences (which includes among others confidentiality, anonymity or non-traceability). We designed a program, DeepSec, which, from the description of a protocol for a fixed number of participants, verifies in a fully-automated way whether the protocol offers a security guarantee of this type. We demonstrate the ability of this tool to analyse complex attack scenarios through several examples. After that, we present an optimization technique exploiting symmetries in security proofs. Typically, participants with similar roles in the protocol often have similar instructions to follow, inducing redundant work during the analysis. On several examples, using this technique allowed to reduce the analysis time of DeepSec by several orders of magnitude. Finally, we also studied the theoretical aspect the problem in order to determine to which extent DeepSec’s algorithm could be improved (can we make the tool faster?) or made more expressive (can we get rid of some of the limitations of the tool?). For that we carried out a complete analysis of the computational complexity of DeepSec’s algorithm, and integrated it to a detailed survey of the state of the art regarding complexity results in similar contexts. This meticulous survey allowed us to expose subtle variations in how the problem is formalised across the literature—sometimes impacting its complexity. We also include new results and improve some of the surveyed ones, resulting in a clearer understanding of the problem