Proefschrift--Eindhoven. / "Stellingen": [6] p. inserted. Summary in Dutch. Bibliography: p. 77-78.

La notion de théorie s'est séparée de la notion de logique à la fin des années 1920, lorsque Hilbert et Ackermann ont distingué les règles de déduction, indépendantes de l'ob jet du discours, des axiomes qui lui sont spécifiques. S'est alors posée la question de caractériser les théories, définies donc comme des ensembles d'axiomes, que l'on peut utiliser pour formaliser une partie du raisonnement mathématique. Un premier critère est la cohérence de cette théorie : le fait qu'on ne puisse pas démontrer toutes les propositions de cette théorie. Cependant il est progressivement apparu que la cohérence n'était pas une propriété suffisante. Le fait que les démonstrations constructives vérifient les propriétés de la dijonction ou du témoin, ou la complétude de certaines méthodes de démonstration automatique ne découlent pas de la seule cohérence d'une théorie. Mais toutes trois sont par contre conséquentes d'une même propriété : la normalisation des démonstrations. En 1930, le théorème de complétude de Gödel montra que le critére de cohérence pouvait être vu sous différents angles. En plus de la définition précédente interne à la théorie de la démonstration, on peut également définir de manière algébrique la cohérence d'une théorie comme le fait qu'elle possède un modèle. L'équivalence entre ces deux définitions constitue un outil fondamental, qui a permis notamment la démonstration de la cohérence de nombreuses théories : la théorie des ensembles avec la négation de l'axiome du choix par Fraenkel et Mostovski, la théorie des ensembles avec l'axiome du choix et l'hypothèse du continue par Gödel, la théorie des ensembles avec la négation de l'hypothèse du continu par Cohen, . . . A l'inverse, la normalisation des démonstrations semblait ne pouvoir se définir que de manière interne à la théorie de la démonstration. Certains critères inspirés de la théorie des modèles étaient certes parfois utilisés pour démontrer la propriété de normalisation des démonstrations de certaines théories, mais la nécéssité de ces critéres n'avait pas été établie. Nous proposons dans cette thèse un critère algébrique à la fois nécessaire et suffisant pour la normalisation des démonstrations. Nous montrons ainsi que la propriété de normalisation des démonstrations peut également se définir comme un critère algébrique, à l'instar de la propriété de cohérence. Nous avons pour cela défini une nouvelle notion d'algèbre de valeurs de vérités (TVA) appelée algèbres de vérité dépendant du langage (LDTVA). La notion de TVA permet d'exhiber l'algèbre de valeurs de vérité des candidats de réductibilité définis par Girard en 1970. L'existence d'un modèle à valeurs dans cette algèbre définit un critère algébrique suffisant pour la propriété de normalisation des démonstrations. Puis nous avons défini un raffinement de la notion de candidats de réductibilité comme une de ces LDTVAs et avons montré que l'existence d'un modèle à valeurs dans cette algèbre définit un critère algébrique toujours suffisant mais également nécessaire pour la propriété de normalisation des démonstrations. Ce critère est défini pour les cadres logiques de la déduction minimale et du λΠ-calcul modulo. Et nous exhibons finalement la puissance du λΠ-calcul modulo en montrant que tous les systèmes de types purs fonctionnels peuvent être simulés dans ce cadre logique.

Cette thèse est constituée de deux parties indépendantes, étudiant deux aspects de la théorie des (φ,Γ)-modules en caractéristique p. La première partie porte sur l'étude de la réduction modulo p des représentations cristallines irréductibles de dimension deux. Nous donnons, pour des poids k ≤ p², un calcul explicite de la réduction de V(k,a) pour a dans un disque fermé centré en zéro, généralisant ainsi des résultats déjà connus pour k ≤ 2p. En particulier, nous calculons le plus grand rayon possible pour ce disque, et montrons que dans certains cas, la réduction qui est constante à l'intérieur du disque change sur son bord. Dans la seconde partie, nous nous intéressons aux représentations d'un sous-groupe de Borel de GL[indice]2(Q[indice]p) sur un corps de caractéristique p, et en particulier à celles qui sont lisses, irréductibles et admettent un caractère central. Une méthode pour construire de telles représentations à partir de (φ,Γ)-modules irréductibles a été décrite par Colmez dans sa construction de la correspondance de Langlands p-adique. Après avoir donné un cadre un peu plus général dans lequel la construction de Colmez fonctionne encore, nous classifions les représentations irréductibles du Borel, prouvant que la construction précédente permet d'obtenir toutes les représentations de dimension infinie. Lorsque le corps des coefficients est fini, ou algébriquement clos, nous disposons d'une interprétation galoisienne des (φ,Γ)-modules irréductibles, et la classification précédente permet alors d'obtenir une correspondance entre ces représentations du Borel et des représentations galoisiennes modulaires.

NP search problems and reductions among them Renáta Ševčíková In the thesis we study the class of Total NP search problems. More attention is devoted to study the subclasses of Total NP search problems and reductions among them. We combine some known methods: the search trees and their relation to re- ductions, the Nullstellensatz refutation and the degree lower bound based on design to show that two classes of relativized NP search problems based on Mod-p counting principle and Mod-q counting principle, where p and q are different primes, are not reducible to each other. This thesis is finished by a new separation result for p = 2 and q = 3.

Nous présentons une méthode originale de recherche de preuve par récurrence utilisant la surréduction. Elle a la particularité d'être fondée sur la déduction modulo et d'utiliser la surréduction pour sélectionner à la fois les variables de récurrence et les schémas d'instanciation. Elle donne également la possibilité de traduire directement toute dérivation effectuée avec succès en une preuve dans le calcul des séquents modulo. La correction et la complétude réfutationnelle de la méthode sont démontrées en théorie de la preuve. Nous étendons ensuite cette première approche aux théories de réécriture équationnelles constituées d'un système de réécriture R et d'un ensemble E d'égalités. A partir du moment où le système de réécriture équationnel (R,E) possède de bonnes propriétés de terminaison et de complétude suffisante, et si on suppose également que E préserve les constructeurs, la surréduction au niveau des positions les plus profondes où apparaît un symbole défini s'effectue uniquement à l'aide d'unificateurs qui sont également des substitutions constructeurs. Ceci est particulièrement intéressant dans le cas des théories associatives, ou associatives commutatives, pour lesquelles notre système de recherche de preuve a été raffiné.

[pt] O presente trabalho apresenta uma reflexão sobre a relação entre arquitetura e fotografia no contexto das revistas especializadas ao longo do período de modernização acelerada que se deu no Brasil a partir da década de 1950. Com o amparo de uma investigação sobre o histórico da fotografia de arquitetura e da consolidação do modelo de revista ilustrada moderna, foi realizada uma breve análise gráfica da revista Módulo em seu primeiro período de circulação (1955-1965), com o objetivo de verificar na publicação elementos identificados na pesquisa e discutir a importância da memória gráfica na historiografia da arquitetura moderna brasileira. / [en] This work presents an examination on the relationship between architecture and photography concerning the specialized magazines through the rapid process of modernization that took place in Brazil from the 1950s. Supported by an investigation on the history of architectural photography and the development of the modern illustrated magazine standard, we conduct a brief graphical analysis of the first circulation phase of Módulo magazine (1955-1965), aiming to relate some of the publication aspects to the research made and ratify the importance of graphic memory to the Brazilian modern architecture historiography.

Dans ce travail nous étudions les propriétés arithmétiques et statistiques d'une nouvelle classe de fonctions de comptage des chiffres appelées fonctions digitales restreintes. Nous présentons tout d'abord les principales propriétés des suites engendrées par une substitution ou un $q$-automate ainsi que la suite célèbre de Thue-Morse et ses généralisations, puis nous comparons ces notions avec celle de fonction digitale restreinte.Nous étudions ensuite les sommes d'exponentielles associées à ces fonctions digitales restreintes ainsi que leur application d'une part à l'étude de la répartition modulo 1 des fonctions digitales restreintes et d'autre part à l'étude des propriétés statistiques des suites arithmétiques définies par des fonctions digitales restreintes.Dans la dernière partie de ce travail on étudie la représentation géométrique de ces sommes d'exponentielle à la lumière des travaux antérieurs de Dekking et Mendès-France ce qui nous conduit à énoncer plusieurs problèmes ouverts. / In this work we study the arithmetic and statistic properties of a new class of digital counting functions called restricted digital functions. We first present the main properties of sequences generated by a substitution or a $q$-automate followed by presenting the famous Thue-Morse sequence and its generalizations, then we compare these notions with the one of the restricted digital function.We then study the exponential sums associated with these restricted digital function and their implementation on the one hand to the study of uniform distribution modulo 1 of these restricted digital functions and on the other, to the study of the statistical properties of the arithmetic sequences defined by restricted digital functions.In the last part of this work we study the geometric representation of these exponential sums in the light of previous works of Dekking and Mendès-France which leads us to announce several open problems.

La Méthode B est une méthode formelle de spécification et de développement de logiciels critiques largement utilisée dans l'industrie ferroviaire. Elle permet le développement de programmes dit corrects par construction, grâce à une procédure de raffinements successifs d'une spécification abstraite jusqu'à une implantation déterministe du programme. La correction des étapes de raffinement est garantie par la vérification de la correction de formules mathématiques appelées obligations de preuve et exprimées dans la théorie des ensembles de la Méthode B. Les projets industriels utilisant la Méthode B génèrent généralement des milliers d'obligation de preuve. La faisabilité et la rapidité du développement dépendent donc fortement d'outils automatiques pour prouver ces formules mathématiques. Un outil logiciel, appelé Atelier B, spécialement développé pour aider au développement de projet avec la Méthode B, aide les utilisateurs a se décharger des obligations de preuve, automatiquement ou interactivement. Améliorer la vérification automatique des obligations de preuve est donc une tache importante. La solution que nous proposons est d'utiliser Zenon, un outils de déduction automatique pour la logique du premier ordre et qui implémente la méthode des tableaux. La particularité de Zenon est de générer des certificats de preuve, des preuves écrites dans un certain format et qui permettent leur vérification automatique par un outil tiers. La théorie des ensembles de la Méthode B est une théorie des ensembles en logique du premier ordre qui fait appel à des schémas d'axiomes polymorphes. Pour améliorer la preuve automatique avec celle-ci, nous avons étendu l'algorithme de recherche de preuve de Zenon au polymorphisme et à la déduction modulo théorie. Ce nouvel outil, qui constitue le cœur de notre contribution, est appelé Zenon Modulo. L'extension de Zenon au polymorphisme nous a permis de traiter, efficacement et sans encodage, les problèmes utilisant en même temps plusieurs types, par exemple les booléens et les entiers, et des axiomes génériques, tels ceux de la théorie des ensembles de B. La déduction modulo théorie est une extension de la logique du premier ordre à la réécriture des termes et des propositions. Cette méthode est parfaitement adaptée à la recherche de preuve dans les théories axiomatiques puisqu'elle permet de transformer des axiomes en règles de réécriture. Par ce moyen, nous passons d'une recherche de preuve dans des axiomes à du calcul, réduisant ainsi l'explosion combinatoire de la recherche de preuve en présence d'axiomes et compressant la taille des preuves en ne gardant que les étapes intéressantes. La certification des preuves de Zenon Modulo, une autre originalité de nos travaux, est faite à l'aide de Dedukti, un vérificateur universel de preuve qui permet de certifier les preuves provenant de nombreux outils différents, et basé sur la déduction modulo théorie. Ce travail fait parti d'un projet plus large appelé BWare, qui réunit des organismes de recherche académique et des industriels autour de la démonstration automatique d'obligations de preuve dans l'Atelier B. Les partenaires industriels ont fournit à BWare un ensemble d'obligation de preuve venant de vrais projets industriels utilisant la Méthode B, nous permettant ainsi de tester notre outil Zenon Modulo.Les résultats expérimentaux obtenus sur cet ensemble de référence sont particulièrement convaincant puisque Zenon Modulo prouve plus d'obligation de preuve que les outils de déduction automatique de référence au premier ordre. De plus, tous les certificats de preuve produits par Zenon Modulo ont été validés par Dedukti, nous permettant ainsi d'être très confiant dans la correction de notre travail. / The B Method is a formal method heavily used in the railway industry to specify and develop safety-critical software. It allows the development of correct-by-construction programs, thanks to a refinement process from an abstract specification to a deterministic implementation of the program. The soundness of the refinement steps depends on the validity of logical formulas called proof obligations, expressed in a specific typed set theory. Typical industrial projects using the B Method generate thousands of proof obligations, thereby relying on automated tools to discharge as many as possible proof obligations. A specific tool, called Atelier B, designed to implement the B Method and provided with a theorem prover, helps users verify the validity of proof obligations, automatically or interactively. Improving the automated verification of proof obligations is a crucial task for the speed and ease of development. The solution developed in our work is to use Zenon, a first-orderlogic automated theorem prover based on the tableaux method. The particular feature of Zenon is to generate proof certificates, i.e. proof objects that can be verified by external tools. The B Method is based on first-order logic and a specific typed set theory. To improve automated theorem proving in this theory, we extend the proof-search algorithm of Zenon to polymorphism and deduction modulo theory, leading to a new tool called Zenon Modulo which is the main contribution of our work. The extension to polymorphism allows us to deal with problems combining several sorts, like booleans and integers, and generic axioms, like B set theory axioms, without relying on encodings. Deduction modulo theory is an extension of first-order logic with rewriting both on terms and propositions. It is well suited for proof search in axiomatic theories, as it turns axioms into rewrite rules. This way, we turn proof search among axioms into computations, avoiding unnecessary combinatorial explosion, and reducing the size of proofs by recording only their meaningful steps. To certify Zenon Modulo proofs, we choose to rely on Dedukti, a proof-checker used as a universal backend to verify proofs coming from different theorem provers,and based on deduction modulo theory. This work is part of a larger project called BWare, which gathers academic entities and industrial companies around automated theorem proving for the B Method. These industrial partners provide to BWare a large benchmark of proof obligations coming from real industrial projects using the B Method and allowing us to test our tool Zenon Modulo. The experimental results obtained on this benchmark are particularly conclusive since Zenon Modulo proves more proof obligations than state-of-the-art first-order provers. In addition, all the proof certificates produced by Zenon Modulo on this benchmark are well checked by Dedukti, increasing our confidence in the soundness of our work.

Topology studies the geometric properties of spaces that are preserved by continuous deformations. Manifolds are the main examples of topological spaces, with the local properties of Euclidean space in an arbitrary dimension n. They are the higher dimensional analogs of curves and surfaces. For example a circle is a one-dimensional manifold. Balloons and doughnuts are examples of two-dimensional manifolds. A balloon cannot be deformed continuously into a doughnut, so we see that there are essential topological differences between them. An "invariant" of a topological space is a number or an algebraic structure such that topologically equivalent spaces have the same invariant. For example the essential topological difference between the balloon and the doughnut is calculated by the "Euler characteristic", which is 2 for a balloon and 0 for a doughnut. In this thesis I investigate the relation between three different but related invariants of manifolds with dimension divisible by 4: the signature, the Brown-Kervaire invariant and the Arf invariant. The signature invariant takes values in the set (...;-3;-2;-1; 0; 1; 2; 3; ...) of integers. In this thesis we focus on the signature invariant modulo 8, that is its remainder after division by 8. The Brown-Kervaire invariant takes values in the set (0; 1; 2; 3; 4; 5; 6; 7). The Arf invariant takes values in the set (0; 1). The main result of the thesis uses the Brown-Kervaire invariant to prove that for a manifold with signature divisible by 4, the divisibility by 8 is decided by the Arf invariant. The thesis is entirely concerned with pure mathematics. However it is possible that it may have applications in mathematical physics, where the signature modulo 8 plays a significant role.

Neste trabalho determinamos o módulo elástico de filmes finos metálicos nanoestruturados. Os metais estudados, platina, ouro e paládio foram depositados utilizando a técnica de Metal Plasma Immersion Ion Implantation and Deposition. Um novo método foi utilizado para as medidas de módulo elástico, no qual cantiléveres de microscopia de força atômica são uniformemente recobertos com os filmes finos metálicos. Medidas das frequências de ressonância dos cantiléveres foram realizadas antes e depois dos recobrimentos com os filmes. Usando a teoria de vibração de barras, determinamos os valores dos módulos elásticos desses filmes. Obtivemos valores que estão entre 7 e 12% menores do que os respectivos módulos elásticos dos metais na forma de bulk. Um modelo simples em conta o caráter nanoestruturado dos materiais. Caracterizações complementares foram realizadas como : microscopia de tunelamento, difração de raios X e RBS (Rutherfor Backscattering Spectrometry). / In this work we have determined the elastic moduli of nanostructured metallic thin films. The analyzed metals, platinum, gold and palladium, have been deposited using the technique Metal Plasma Immersion Ion Implantation and Deposition. A new method was adopted to determine the elastic moduli, where cantilevers of atomic force microscopy were uniformly coated with thin films. The resonance frequencies of the cantilevers have been measured before and after the films coating. The elastic moduli were finally obtained using the vibration beam theory. The determined elastic constants are smaller than the respective bulk moduli: about 12% for Pt and Au and about 7% for Pd. A simple model is proposed to explain the softening of the elastic moduli taking into account the nanostructured character of the films. Additional characterizations have been done like: scanning tunneling microscopy, X-ray diffraction and RBS (Rutherford Backscattering Spectrometry).