Cette thèse s'inscrit dans l'étude de familles de graphes infinis de présentation finie, de leurs propriétés structurelles, ainsi que des comparaisons entre ces familles. Étant donné un alphabet fini Σ, un graphe infini étiqueté par Σ peut être caractérisé par un ensemble fini de relations binaires (Ra )a∈Σ sur un domaine dénombrable V quelconque. De multiples caractérisations finies de tels ensembles de relations existent, soit de façon explicite grâce à des systèmes de réécriture ou à divers formalismes de la théorie des automates, soit de façon implicite. Après un survol des principaux résultats existants, nous nous intéressons plus particulièrement à trois problèmes. Dans un premier temps, nous définissons trois familles de systèmes de réécriture de termes dont nous démontrons que la rela- tion de dérivation peut être représentée de façon finie. De ces résultats découlent plusieurs questions sur les familles de graphes infinis correspondantes. Dans un se- cond temps, nous étudions deux familles de graphes dont les ensembles de traces forment la famille des langages contextuels, à savoir les graphes rationnels et les graphes linéairement bornés. Nous nous intéressons en particulier au cas des langages contextuels déterministes, ainsi qu'à la comparaison structurelle de ces deux familles. Enfin, d'un point de vue plus proche du domaine de la vérifica- tion, nous proposons un algorithme de calcul des prédécesseurs pour une famille d'automates à pile d'ordre supérieur.

Cette thèse s'inscrit dans l'étude des graphes infinis de présentation finie. Nous nous intéressons à la fois à leurs propriétés logiques et aux langages qui leur sont associés. Nous nous concentrons sur l'étude des graphes infinis associés aux automates à pile d'ordre supérieur. Notre première contribution est la définition d'une notion de rationalité pour les piles d'ordre supérieur. Nous montrons que cette notion partage de nombreuses propriétés de la rationalité sur les mots : clôture par complémentaire, accepteurs déterministes et complets, et caractérisation en logique du second ordre monadique. Nous établissons un lien étroit entre les automates à pile d'ordre supérieur et les ensembles rationnels de piles d'ordre supérieur. Notre seconde contribution est l'étude structurelle des graphes associés à ces automates. Nous en donnons différentes caractérisations qui montrent la robustesse de ces familles de graphes infinis.

Cette thèse a pour cadre la spécification et la vérification de systèmes informatiques distribués, concurrents ou réactifs au moyen de graphes infinis associés à des spécifications de Thue et à certaines machines. Nous montrons que la classe des graphes des spécifications de Thue est fermée par produit synchronisé. Nous établissons aussi ce fait pour la classe des graphes des machines de Turing et pour certaines de ses sous-classes. Nous nous intéressons également à la conservation par produit synchronisé de la décidabilité de la théorie du premier ordre de graphes infinis. Nous montrons que le produit synchronisé de graphes de machines à pile restreint à sa partie accessible depuis un sommet donné à une théorie du premier ordre qui n'est pas décidable. Cependant, le produit synchronisé de graphes sans racine distinguée et dont la théorie du premier oordre est décidable a une théorie du premier ordre qui est décidable. Enfin nous mettons en évidence des liens qui unissent les graphes des machines de Turing à ceux des spécifications de Thue.

Les jeux à deux joueurs sur des graphes finis ou infinis permettent de modéliser de nombreux problèmes liés à la vérification des systèmes. Le système spécifié dépend de la nature du graphe de jeu considéré tandis que la propriété à vérifier est décrite par la condition de gain. Le premier joueur, Eve, représente un programme qui évolue dans un environnement hostile représenté par le second joueur, Adam. Dans ce formalisme, Eve possède une stratégie gagnante si et seulement si le programme peut être contrôlé de sorte à satisfaire la propriété spécifiée par la condition de gain. On souhaite alors décider si Eve possède une stratégie gagnante et si oui la déterminer, afin de synthétiser ensuite un contrôleur. <br /><br />Dans cette thèse, les graphes de jeu considérés sont des graphes de processus à pile qui offrent une représentation finie simple de systèmes infinis relativement complexes. Sur de tels graphes, on peut considérer des conditions de gain classiques (accessibilité, Büchi ou parité) mais aussi des conditions plus spécifiques au modèle comme celles portant sur le bornage de la pile. On peut également combiner ces dernières entre elles. <br /><br />Une première contribution a été de fournir une représentation des ensembles de positions gagnantes pour les jeux de parité ainsi qu'une nouvelle présentation des résultats connus pour ces derniers. On a alors pu étendre de façon naturelle les techniques de preuves à d'autres conditions de gain, notamment à celles portant sur le bornage de la pile. <br /><br />Une autre contribution a été la description d'une famille de conditions de gain de complexité borélienne arbitraire finie pour lesquelles les jeux (sur des graphes finis ou sur des graphes de processus à pile) restent décidables. <br /><br />L'étude des jeux sur les graphes de BPA et sur les graphes de processus à compteur a permis de proposer des techniques propres à ces modèles qui fournissent alors des bornes de complexité meilleures que celles obtenues dans le cas général des graphes de processus à pile. <br /><br />Enfin, une dernière contribution a été de proposer une solution pour les jeux sur des graphes de processus à pile munis de conditions combinant des conditions régulières et des conditions sur la hauteur de pile et pour des conditions décrites par des automates à pile avec visibilité.

Cette thèse porte sur des propriétés d'approximation généralisant la moyennabilité pour les groupes localement compacts. Ces propriétés sont définies à partir des multiplicateurs de certaines algèbres associés aux groupes. La première partie est consacrée à l'étude de la propriété p-AP, qui est une extension de la AP de Haagerup et Kraus au cadre des opérateurs sur les espaces Lp. Le résultat principal dit que les groupes de Lie simples de rang supérieur et de centre fini ne satisfont p-AP pour aucun p entre 1 et l'infini. La deuxième partie se concentre sur les multiplicateurs de Schur radiaux sur les graphes. L'étude de ces objets est motivée par les liens avec les actions de groupes discrets et la moyennabilité faible. Les trois résultats principaux donnent des conditions nécessaires et suffisantes pour qu'une fonction sur les nombres naturels définisse un multiplicateur radial sur des différentes classes de graphes généralisant les arbres. Plus précisément, les classes de graphes étudiées sont les produits d'arbres, les produits de graphes hyperboliques et les complexes cubiques CAT(0) de dimension finie. / This thesis focusses on some approximation properties which generalise amenability for locally compact groups. These properties are defined by means of multipliers of certain algebras associated to the groups. The first part is devoted to the study of the p-AP, which is an extension of the AP of Haagerup and Kraus to the context of operators on Lp spaces. The main result asserts that simple Lie groups of higher rank and finite centre do not satisfy p-AP for any p between 1 and infinity. The second part concentrates on radial Schur multipliers on graphs. The study of these objects is motivated by some connections with actions of discrete groups and weak amenability. The three main results give necessary and sufficient conditions for a function of the natural numbers to define a radial multiplier on different classes of graphs generalising trees. More precisely, the classes of graphs considered here are products of trees, products hyperbolic graphs and finite dimensional CAT(0) cube complexes.