Cette thèse traite de la theorie de la preuve pour les logiques a points fixes, telles que le μ-calcul, lalogique lineaire a points fixes, etc. ces logiques sont souvent munies de systèmes de preuves finitairesavec des règles d’induction à la Park. Il existe néanmoins d’autres sytèmes de preuves pour leslogiques à points fixes, qui reposent sur la notion de preuve infinitaire, mais qui sont beaucoupmoins developpés dans la litterature. L’objectif de cette thèse est de pallier à cette lacune dansl’état de l’art, en developpant la théorie de la preuve infnitaire pour les logiques a points fixes,avec deux domaines d’application en vue: les langages de programmation avec types de données(co)inductifs et la vérification des systèmes réactifs.Cette thèse contient trois partie. Dans la première, on rappelle les deux principales approchespour obtenir des systèmes de preuves pour les logiques à points fixes: les systèmes finitaires avecrègle explicite d’induction et les systèmes finitaires, puis on montre comment les deux approchesse relient. Dans la deuxième partie, on argumente que les preuves infinitaires ont effectivement unréel statut preuve-theorique, en montrant que la logique lineaire additive multiplicative avec pointsfixes admet les propriétés d’élimination des coupures et de focalisation. Dans la troisième partie,on utilise nos developpements sur les preuves infinitaires pour monter de manière constructive lacomplétude du μ-calcul lineaire relativement à l’axiomatisation de Kozen. / The subject of this thesis is the proof theory of logics with fixed points, such as the μ-calculus,linear-logic with fixed points, etc. These logics are usually equipped with finitary deductive systemsthat rely on Park’s rules for induction. other proof systems for these logics exist, which relyon infinitary proofs, but they are much less developped. This thesis contributes to reduce thisdeficiency by developing the infinitary proof-theory of logics with fixed points, with two domainsof application in mind: programming languages with (co)inductive data types and verification ofreactive systems.This thesis contains three parts. In the first part, we recall the two main approaches to theproof theory for logics with fixed points: the finitary and the infinitary one, then we show theirrelationships. In the second part, we argue that infinitary proofs have a true proof-theoreticalstatus by showing that the multiplicative additive linear-logic with fixed points admits focalizationand cut-elimination. In the third part, we apply our proof-theoretical investigations to obtain aconstructive proof of completeness for the linear-time μ-calculus w.r.t. Kozen’s axiomatization.

Dans cette thèse on s'intéresse aux formes de "circularité" qui apparaissent dans la théorie de la preuve de la logique du second ordre et de son contrepartie constructive, le Système F.Ces "circularités", ou "cercles vicieux" (Poincaré 1900), sont analysées sur la base d'une distinction entre deux points de vue distincts et irréductible (à cause des théorèmes d'incomplétude): le premier ("le pourquoi", Girard 1989) concerne la cohérence et l'Hauptsatz et demande des méthodes infinitaires (i.e. non élémentaires) de preuve. Le deuxième ("le comment", Girard 1989) concerne le contenu computationnel et combinatoire des preuves, donné par la correspondance entre preuves et programmes, et ne demande que de méthodes élémentaires de preuve.Dans la première partie de la thèse, dévouée au "pourquoi", les arguments philosophiques traditionnels sur les "cercles vicieux" sont confrontés avec la perspective qui émerge de la démonstration de l' Hauptsatz pour la logique de second ordre (obtenue par Girard avec la technique des candidats de réductibilité).Dans la deuxième partie de la thèse, dévouée au "comment", deux approches combinatoires aux cercles vicieux sont proposés: la première se basant sur la théorie du polymorphisme paramétrique, la deuxième sur l'analyse géométrique du typage qui vient de la théorie de l'unification. / In this dissertation several issues concerning the proof-theory of second order logic and its constructive counterpart (System F, Girard 1971) are addressed. The leitmotiv of the investigations here presented is the apparent "circularity'' or "impredicativity'' of second order proofs. This circularity is reflected in System F by the possibility to type functions applied to themselves, in contrast with Russell's idea that typing should rather forbid such ``vicious circles'' (Poincare 1906). A fundamental methodological distinction between two irreducible (because of incompleteness) approaches in proof theory constitutes the background of this work: on the one hand, "why-proof theory'' ("le pourquoi'', Girard 1989) addresses coherence and the Hauptsatz and requires non-elementary ("infinitary'') techniques; on the other hand, "how-proof theory'' ("le comment'', Girard 1989) addresses the combinatorial and computational content of proofs, given by the correspondence between proofs and programs, and is developed on the basis of elementary ("finitary'') techniques. }In the first part of the thesis, dedicated to "why-proof theory'', the traditional philosophical arguments on "vicious circles'' are confronted with the perspective arising from the proof of the Hauptsatz for second order logic (first obtained in Girard 1971 with the technique of reducibility candidates).In the second part of the thesis, dedicated to "how-proof theory'', two combinatorial approaches to "vicious circles'' are presented, with some technical results: the first one based on the theory of parametric polymorphism, the second one on the geometrical analysis of typing coming from unification theory.

Cette recherche vise à établir les propriétés fondamentales d'un système formel aux preuves circulaires introduit par Santocanale, auquel on a rajouté la règle de coupure. On démontre, dans un premier temps, qu'il y a une pleine correspondance entre les preuves circulaires et les flèches issues des catégories dites µ-bicomplètes. Ces flèches sont celles que l'on peut définir purement à partir des outils suivants: les produits et coproduits finis, les algèbres initiales et les coalgèbres finales. Dans la catégorie des ensembles, les preuves circulaires dénotent donc les fonctions qu'on peut définir en utilisant les produits cartésiens finis, les unions disjointes finies, l'induction et la coinduction. On décrit également une procédure d'élimination des coupures qui produit, à partir d'une preuve circulaire finie, une preuve sans cycles et sans coupures, mais possiblement infinie. On démontre que l'élimination des coupures fournit une sémantique opérationnelle aux preuves circulaires, c'est-à-dire qu'elle permet de calculer les fonctions dénotées par celles-ci, par le moyen d'une sorte d'automate avec mémoire. Enfin, on s'intéresse au problème de la puissance expressive de cet éliminateur de coupures, c'est-à-dire à la question de caractériser la classe des expressions qu'il peut calculer. On démontre, par une simulation, que l'éliminateur des coupures est strictement plus expressif que les automates à pile d'ordre supérieur. / This research aims at establishing the fundamental properties of a formal system with circular proofs introduced by Santocanale, to which we added the cut rule. We first show that there is a full correspondence between circular proofs and arrows from the so-called µ-bicomplete categories. These arrows are those that can be defined purely from the following tools: finite products and coproducts, initial algebras and final coalgebras. In the category of sets, circular proofs denote functions that one can define by using finite cartesian products, finite disjoint unions, induction and coinduction. We also describe a cut-elimination procedure that produces, from a given finite circular proof, a proof without cycles and cuts, but which may be infinite. We prove that cut-elimination gives an operational semantics to circular proofs, which is to say that they allow to compute the functions denoted by them, by using a sort of automaton with memory. Finally, we are interested in finding the expressive power of that cut-eliminating automaton. In other words, we want to characterize the class of functions that it can compute. We show, through a simulation, that the cut-eliminating automaton is strictly more expressive than higher-order pushdown automata.