京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第18771号 / 理博第4029号 / 新制||理||1580(附属図書館) / 31722 / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 長谷川 真人, 教授 玉川 安騎男, 准教授 照井 一成 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

Dans cette thèse nous rappelons la notion de L-algèbre, qui a pour objet d'être un modèle algébrique des types d'homotopie. L'objectif principal de cette thèse est la description d'une structure de E-infini-coalgèbre sur l'élément principal d'une L-algèbre. Ceci peut être vu comme une généralisation de la structure de E-infini-coalgèbre sur le complexe des chaînes d'un ensemble simplicial, telle que décrite par Smith dans Iterating the cobar construction, 1994. Nous construisons une E-infini-opérade, notée K, utilisée pour construire la E-infini-coalgèbre sur l'élément principal d'une L-algèbre. Cette structure de E-infini-coalgèbre montre que la L-algèbre canoniquement associée à un ensemble simplicial contient au moins autant d'information homotopique que la E-infini-coalgèbre couramment associée à un ensemble simplicial / In this thesis we recall the notion of L-algebra. L-algebras are intended as algebraic models for homotopy types. L-algebras were introduced by Alain Prouté in several talks since the eighties. The principal objective of this thesis is the description of an E-infinity-coalgebra structure on the main element of an L-algebra. This can be seen as a generalization of the E-infinity-coalgebra structure on the chain complex associated to a simplicial set given by Smith in Iterating the cobar construction, 1994. We construct an E-inifity-operad, denoted K, used to construct the E-inifity-coalgebra on the main element of a L-algebra. This E-inifity-coalgebra structure shows that the canonical L-algebra associated to a simplicial set contains at least as much homotopy information as the E-inifity-coalgebras usually associated to simplicial sets.

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.