Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

Structures linéaires dans les ensembles à faible densité

Réalisé en cotutelle avec l'Université Paris-Diderot.

Concept de non-violence chez le théologien processuel David Ray Griffin entre la guerre du Vietnam et celle d'Iraq (1968-2008)

La non-violence fait référence à une idéologie et un ensemble de pratiques qui ont pour caractéristique commune de rejeter la violence sous toutes ses formes dans l’actualisation quotidienne. La non-violence est cependant devenue également un outil auquel certains recourrent dans des objectifs qui ne servent pas nécessairement le bien commun. En d’autres termes, la non-violence n’est pas systématiquement un outil de paix. Elle est un moyen d’obtenir ce que l’on veut, sans recourir à la violence. Cette thèse propose une vision de la non-violence au service du bien commun. Elle puise dans l’historicité de grands événements et acteurs qui ont utilisé la non-violence pour libérer une collectivité de formes d’oppression qui amenuisaient la dignité humaine. Elle fait référence à des auteurs et acteurs qui ont influencé le théologien processuel David Ray Griffin dans sa propre démarche d’enseignement et de recherche théologiques sur une quarantaine d’années, soient de la guerre du Vietnam à celle d’Iraq. Les dates survolées vont de 1968 à 2008. Une première démarche entreprise par la recherche est de comprendre le plus précisément possible quelles sont les avenues les plus récentes concernant la non-violence et d’explorer ses influences sur la vie et la carrière du théologien processuel États-Unien David Ray Griffin. En second lieu, une rétrospective historique des événements marquants aux États-Unis permet de cerner le contexte au sein duquel Griffin a évolué et comment son discours a laissé transparaître ces influences historiques, sociales et académiques. Une analyse plus centrée sur la politique extérieure des États-Unis en matière d’économie et de militarisme aiguille vers l’identification de signes que Griffin qualifie lui-même d’anti-théologiques, ce qui l’incite à élaborer une vision paradigmatique globalisante, équilibrée selon lui, où les ressources planétaires sont redistribuées dans un souci d’équité et de justice. Pour ce faire, un tribunal international, une religion globale, à l’image de ce que propose la pensée processuelle whiteheadienne-hartshornienne sont proposés. Griffin en brosse les grands traits dans un discours où l’exhortation s’assortit d’une méthodologie et d’une pédagogie éprouvés depuis 40 ans. Une grille d’analyse des textes griffiniens est par la suite élaborée, structurant les différentes composantes fondamentales de sa pensée. Un modèle d’intégration des valeurs de la non-violence est dégagé des lectures, applicable à d’autres disciplines. Appuyé sur une tradition authentique d’auteurs non-violents, David Ray Griffin présente les caractéristiques d’un homme de paix, duquel les idéaux débordent le cadre national pour rejoindre le planétaire, dans une visée résolument sotériologique. Cette visée devient urgente alors que les événements des attentats terroristes du World Trade Center du 11 septembre 2001 font dire à Griffin que non seulement les États-Unis sont engagés dans une démarche impérialiste démoniaque, mais qu’ils contribuent de manière accélérée à la destruction de la planète. Il faut absolument, croit-il, renverser le courant et devenir, pour le monde, un leader de la réparation des écosystèmes, des économies et des sociétés. S’adjoignant des auteurs d’autres disciplines, et toujours dans un cadre processuel, Griffin entreprend le long périple pédagogique qu’est celui de convaincre le plus grand nombre d’individus possible que le temps est venu d’agir.

On some Density Theorems in Number Theory and Group Theory

Gowers, dans son article sur les matrices quasi-aléatoires, étudie la question, posée par Babai et Sos, de l'existence d'une constante $c>0$ telle que tout groupe fini possède un sous-ensemble sans produit de taille supérieure ou égale a $c|G|$. En prouvant que, pour tout nombre premier $p$ assez grand, le groupe $PSL_2(\mathbb{F}_p)$ (d'ordre noté $n$) ne posséde aucun sous-ensemble sans produit de taille $c n^{8/9}$, il y répond par la négative. Nous allons considérer le probléme dans le cas des groupes compacts finis, et plus particuliérement des groupes profinis $SL_k(\mathbb{Z}_p)$ et $Sp_{2k}(\mathbb{Z}_p)$. La premiére partie de cette thése est dédiée à l'obtention de bornes inférieures et supérieures exponentielles pour la mesure suprémale des ensembles sans produit. La preuve nécessite d'établir préalablement une borne inférieure sur la dimension des représentations non-triviales des groupes finis $SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ et $Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Notre théoréme prolonge le travail de Landazuri et Seitz, qui considérent le degré minimal des représentations pour les groupes de Chevalley sur les corps finis, tout en offrant une preuve plus simple que la leur. La seconde partie de la thése à trait à la théorie algébrique des nombres. Un polynome monogéne $f$ est un polynome unitaire irréductible à coefficients entiers qui endengre un corps de nombres monogéne. Pour un nombre premier $q$ donné, nous allons montrer, en utilisant le théoréme de densité de Tchebotariov, que la densité des nombres premiers $p$ tels que $t^q -p$ soit monogéne est supérieure ou égale à $(q-1)/q$. Nous allons également démontrer que, quand $q=3$, la densité des nombres premiers $p$ tels que $\mathbb{Q}(\sqrt[3]{p})$ soit non monogéne est supérieure ou égale à $1/9$.