Cette thèse est consacrée à l’étude d’expansions de certaines structures algébriques et leur place dans la classification modèle-théorique des structures, initiée par Shelah. La première partie aborde de manière abstraite l’expansion d’une théorie par un prédicat aléatoire –ou générique– pour une sous-structure modèle d’un réduit de la théorie. Nous éla- borons un critère pour l’existence d’une telle expansion, qui est vérifié pour certaines théories de structures algébriques. En particulier, nous montrons l’existence de sous-groupes additifs génériques pour certaines théories de corps, ainsi que de sous-groupes multiplicatifs génériques pour les corps algébriquement clos en toute caractéristique. Nous étudions aussi la conservation de diverses notions de néostabilité, en particulier nous montrons que cette expansion préserve la propriété NSOP 1 , mais en général ne préserve pas la simplicité. Nous produisons par cette construction de nouveaux exemples de structures NSOP 1 non simples, et faisons une étude toute particulière de l’une d’entre elles : l’expansion d’un corps algébriquement clos de caractéristique positive par un sous-groupe additif générique. La deuxième partie étudie les expansions du groupe des entiers par des valuations p-adiques. Nous montrons l’élimination des quantificateurs dans un langage naturel et calculons le dp-rang d’une telle expansion : il est égal au nombre de valuations considérées. L’expansion du groupe des entiers par une seule valuation p-adique est donc une nouvelle expansion dp-minimale du groupe des entiers. Enfin, nous montrons que cette dernière n’admet pas de structures intermédiaires : tout ensemble définissable dans l’expansion est soit définissable dans le groupe des entiers, soit capable de “reconstruire” la valuation en utilisant seulement la structure additive / This thesis is concerned with the expansions of some algebraic structures and their fit in Shelah’s classification landscape. The first part deals with the expansion of a theory by a random –or generic– predicate for a substructure model of a reduct of the theory. We describe a setup allowing such an expansion to exist, which is suitable for several algebraic structures. In particular, we obtain the existence of additive generic subgroups of some theories of fields and multiplicative generic subgroups of algebraically closed fields in all characteristic. We also study the preservation of certain neostability notions, for instance, the NSOP 1 property is preserved but the simplicity is not in general. Thus, this construction produces new examples of NSOP 1 not simple theories, and we study in depth a particular example: the expansion of an algebraically closed field of positive characteristic by a generic additive subgroup. The second part studies expansions of the groups of integers by p-adic valuations. We prove quantifier elimination in a natural language and compute the dp-rank of these expansions: it equals the number of distinct p-adic valuations considered. Thus, the expansion of the integers by one p-adic valuation is a new dp-minimal expansion of the group of integers. Finally, we prove that the latter expansion does not admit intermediate structures: any definable set in the expansion is either definable in the group structure or is able to "reconstruct" the valuation using only the group operation

No description available.

Les travaux présentés dans cette thèse sont lies aux problèmes de vérification de l'atteignabilité et de la terminaison de programmes qui manipulent des données entières non-bornées. On décrit une nouvelle méthode de vérification basée sur une technique d'accélération de boucle, qui calcule, de manière exacte, la clôture transitive d'une relation arithmétique. D'abord, on introduit un algorithme d'accélération de boucle qui peut calculer, en quelques secondes, des clôtures transitives pour des relations de l'ordre d'une centaine de variables. Ensuite, on présente une méthode d'analyse de l'atteignabilité, qui manipule des relations entre les variables entières d'un programme, et applique l'accélération pour le calcul des relations entrée-sortie des procédures, de façon modulaire. Une approche alternative pour l'analyse de l'atteignabilité, présentée également dans cette thèse, intègre l'accélération avec l'abstraction par prédicats, afin de traiter le problème de divergence de cette dernière. Ces deux méthodes ont été évaluées de manière pratique, sur un nombre important d'exemples, qui étaient, jusqu'a présent, hors de la portée des outils d'analyse existants. Dernièrement, on a étudié le problème de la terminaison pour certaines classes de boucles de programme, et on a montré la décidabilité pour les relations étudiées. Pour ces classes de relations arithmétiques, on présente un algorithme qui s'exécute en temps au plus polynomial, et qui calcule l'ensemble d'états qui peuvent générer une exécution infinie. Ensuite on a intégré cet algorithme dans une méthode d'analyse de la terminaison pour des programmes qui manipulent des données entières. / This work presents novel methods for verification of reachability and termination properties of programs that manipulate unbounded integer data. Most of these methods are based on acceleration techniques which compute transitive closures of program loops. We first present an algorithm that accelerates several classes of integer relations and show that the new method performs up to four orders of magnitude better than the previous ones. On the theoretical side, our framework provides a common solution to the acceleration problem by proving that the considered classes of relations are periodic. Subsequently, we introduce a semi-algorithmic reachability analysis technique that tracks relations between variables of integer programs and applies the proposed acceleration algorithm to compute summaries of procedures in a modular way. Next, we present an alternative approach to reachability analysis that integrates predicate abstraction with our acceleration techniques to increase the likelihood of convergence of the algorithm. We evaluate these algorithms and show that they can handle a number of complex integer programs where previous approaches failed. Finally, we study the termination problem for several classes of program loops and show that it is decidable. Moreover, for some of these classes, we design a polynomial time algorithm that computes the exact set of program configurations from which non-terminating runs exist. We further integrate this algorithm into a semi-algorithmic method that analyzes termination of integer programs, and show that the resulting technique can verify termination properties of several non-trivial integer programs. / Tato pr´ace pˇredstavuje nov´e metody pro verifikaci program°u pracuj´ıc´ıch s neomezen´ymiceloˇc´ıslen´ymi promˇenn´ymi, konkr´etnˇe metody pro anal´yzu dosaˇzitelnosti a koneˇcnosti.Vˇetˇsina tˇechto metod je zaloˇzena na akceleraˇcn´ıch technik´ach, kter´e poˇc´ıtaj´ı tranzitivn´ıuz´avˇery cykl°u programu.V pr´aci je nejprve pˇredstaven algoritmus pro akceleraci nˇekolika tˇr´ıd celoˇc´ıseln´ychrelac´ı. Tento algoritmus je aˇz o ˇctyˇri ˇr´ady rychlejˇs´ı neˇz existuj´ıc´ı techniky. Z teoretick´ehohlediska pr´ace dokazuje, ˇze uvaˇzovan´e tˇr´ıdy relac´ı jsou periodick´e a poskytuje tud´ıˇzjednotn´e ˇreˇsen´ı prol´emu akcelerace.Pr´ace d´ale pˇredstavuje semi-algoritmus pro anal´yzu dosaˇzitelnosti celoˇc´ıseln´ych program°u, kter´y sleduje relace mezi promˇenn´ymi programu a aplikuje akceleraˇcn´ı technikyza ´uˇcelem modul´arn´ıho v´ypoˇctu souhrn°u procedur. D´ale je v pr´aci navrˇzen alternativn´ıalgoritmus pro anal´yzu dosaˇzitelnosti, kter´y integruje predik´atovou abstrakci s accelerac´ıs c´ılem zv´yˇsit pravdˇepodobnost konvergence v´ypoˇctu. Proveden´e experimenty ukazuj´ı, ˇzeoba algoritmy lze ´uspˇeˇsnˇe aplikovat k verifikaci program°u, na kter´ych pˇredchoz´ı metodyselh´avaly.Pr´ace se rovnˇeˇz zab´yv´a probl´emem koneˇcnosti bˇehu program°u a dokazuje, ˇze tentoprobl´em je rozhodnuteln´y pro nˇekolik tˇr´ıd celoˇc´ıseln´ych relac´ı. Pro nˇekter´e z tˇechto tˇr´ıdrelac´ı je v pr´aci navrˇzen algoritmus, kter´y v polynomi´aln´ım ˇcase vypoˇc´ıt´a mnoˇzinu vˇsechkonfigurac´ı programu, z nichˇz existuje nekoneˇcn´y bˇeh. Tento algoritmus je integrov´ando metody, kter´a analyzuje koneˇcnost bˇeh°u celoˇc´ıseln´ych program°u. Efektivnost t´etometody je demonstrov´ana na nˇekolika netrivi´aln´ıch celoˇc´ıseln´ych programech.

Dans une première partie de cette thèse, nous donnons des minorations universelles ne dépendant que de la dimension – explicites, de trois invariants globaux des quotients des espaces hyperboliques quaternioniques : leur rayon maximal, leur volume, ainsi que leur caractéristique d’Euler. Nous donnons également une majoration de leur constante de Margulis, montrant que celle-ci décroit au moins comme une puissance négative de la dimension. Dans une seconde partie, nous étudions un réseau remarquable des isométries du plan hyperbolique quaternionique, le groupe modulaire d’Hurwitz. Nous montrons en particulier qu’il est engendré par quatres éléments, et construisons un domaine fondamental pour le sous-groupe des isométries de ce réseau qui stabilisent un point à l’infini. / In the first part of this thesis, we derive explicit universal – that is, depending only on the dimension – lower bounds on three global invariants of quaternionic hyperbolic sapces : their maximal radius, their volume, and their Euler caracteristic. We also exhibit an upper bound on their Margulis constant, showing that this last quantity decreases at least like a negative power of the dimension. In the second part, we study a specific lattice of isometries of the quaternionic hyperbolic plane : the Hurwitz modular group. In particular, we show that this group is generated by four elements, and we construct a fundamental domain for the subgroup of isometries of this lattice stabilising a point on the boundary of the quaternionic hyperbolic plane.

No description available.

Cette thèse d'algèbre commutative porte principalement sur la théorie de la profondeur. Nous nous efforçons d'en fournir une approche épurée d'hypothèse noethérienne dans l'espoir d'échapper aux idéaux premiers et ceci afin de manier des objets élémentaires et explicites. Parmi ces objets, figurent les complexes algébriques de Koszul et de Cech dont nous étudions les propriétés cohomologiques grâce à des résultats simples portant sur la cohomologie du totalisé d'un bicomplexe. Dans le cadre de la cohomologie de Cech, nous avons établi la longue suite exacte de Mayer-Vietoris avec un traitement reposant uniquement sur le maniement des éléments. Une autre notion importante est celle de dimension de Krull. Sa caractérisation en termes de monoïdes bords permet de montrer de manière expéditive le théorème d'annulation de Grothendieck en cohomologie de Cech. Nous fournissons également un algorithme permettant de compléter un polynôme homogène en un h.s.o.p.. La profondeur est intimement liée à la théorie des résolutions libres/projectives finies, en témoigne le théorème de Ferrand-Vasconcelos dont nous rapportons une généralisation due à Jouanolou. Par ailleurs, nous revenons sur des résultats faisant intervenir la profondeur des idéaux caractéristiques d'une résolution libre finie. Nous revisitons, dans un cas particulier, une construction due à Tate permettant d'expliciter une résolution projective totalement effective de l'idéal d'un point lisse d'une hypersurface. Enfin, nous abordons la théorie de la régularité en dimension 1 via l'étude des idéaux inversibles et fournissons un algorithme implémenté en Magma calculant l'anneau des entiers d'un corps de nombres. / This Commutative Algebra thesis focuses mainly on the depth theory. We try to provide an approach without noetherian hypothesis in order to escape prime ideals and to handle only basic and explicit concepts. We study the algebraic complexes of Koszul and Cech and their cohomological properties by using simple results on the cohomology of the totalization of a bicomplex. In the Cech cohomology context we established the long exact sequence of Mayer-Vietoris only with a treatment based on the elements. Another important concept is that of Krull dimension. Its characterization in terms of monoids allows us to show expeditiously the vanishing Grothendieck theorem in Cech cohomology.We also provide an algorithm to complete a omogeneous polynomial in a h.s.o.p.. The depth is closely related to the theory of finite free/projective resolutions. We report a generalization of the Ferrand-Vasconcelos theorem due to Jouanolou. In addition, we review some results involving the depth of the ideals of expected ranks in a finite free resolution.We revisit, in a particular case, a construction due to Tate. This allows us to give an effective projective resolution of the ideal of a point of a smooth hypersurface. Finally, we discuss the regularity theory in dimension 1 by studying invertible ideals and provide an algorithm implemented in Magma computing the ring of integers of a number field.