Computing with sequents and diagrams in classical logic - calculi *X, dX and ©X

This Ph.D. thesis addresses the problem of giving computational interpretation to proofs in classical logic. As such, it presents three calculi reflecting different approaches in the study of this area. The thesis consists of three parts. The first part introduces the *X calculus, whose terms represent proofs in the classical sequent calculus, and whose reduction rules capture most of the features of cut-elimination in sequent calculus. This calculus introduces terms which enable explicit implementation of erasure and duplication and to the best of our knowledge it is the first such calculus for classical logic. The second part studies the possibility to represent classical computation diagrammatically. We present the dX calculus, the diagrammatic calculus for classical logic, whose diagrams originate from *X-terms. The principal difference lies in the fact that dX has a higher level of abstraction, capturing the essence of sequent calculus proofs, as well as the essence of classical cut-elimination. The third part relates the first two. It presents the ©X calculus, a one-dimensional counterpart of the diagrammatic calculus. We start from *X, where we explicitly identify terms which should be considered the same. These are the terms that code sequent proofs which are equivalent up to permutations of independent inference rules. They also have the same diagrammatic representation. Such identification induces the congruence relation on terms. The reduction relation is defined modulo congruence rules, and reduction rules correspond to those of dX calculus.Cette thèse de doctorat étudie l'interprétation calculatoire des preuves de la logique classique. Elle présente trois calculs reflétant trois approches différentes de la question. Cette thèse est donc composée de trois parties. La première partie introduit le *X calcul, dont les termes représentent des preuves dans le calcul des séquents classique. Les règles de réduction du *X calcul capture la plupart des caractéristiques de l'élimination des coupures du calcul des séquents. Ce calcul introduit des termes permettant uneimplémentation implicite de l'effacement et de la duplication. Pour autant que nous sachions, c'est le premier tel calcul pour la logique classique. La deuxième partie étudie la possibilité de représenter les calculs classiques au moyen de diagrammes. Nous présentons le dX calcul, qui est le calcul diagrammatique de la logique classique, et dont les diagrammes sont issus des*X-termes. La différence principale réside dans le fait que dX fonctionne à un niveau supérieur d'abstraction. Il capture l'essence des preuves du calcul des séquents ainsi que l'essence de l'élimination classique des coupures. La troisième partie relie les deux premières. Elle présente le $copy;X calcul qui est une version unidimensionnelle du calcul par diagramme. Nous commencons par le *X, où nous identifions explicitement les termes qui doivent l'être. Ceux-cisont les termes qui encodent les preuves des séquents qui sont équivalentes modulo permutation de règles d'inférence indépendantes. Ces termes ont également la même représentation par diagramme. Une telle identification induit une relation de congruence sur les termes. La relation de réduction est définie modulo la congruence, et les règles de réduction correspondent à celle du dX calcul