En se fondant sur les travaux de Trimble et al., puis Hughes, on donne une notion de théorie symétrique monoïdale close (smc) et une construction explicite de la catégorie smc engendrée, formant ainsi une adjonction entre théories et catégories. On étudie les exemples du lambda-calcul pur linéaire, du lambda-calcul pur standard, puis des bigraphes de Milner. À chaque fois on donne une théorie smc et on compare la catégorie smc engendrée avec la présentation standard. Entre autres, dans les trois cas, on montre une équivalence entre les deux sur les termes clos. / From the work of Trimble et al. and Hughes, we define a notion of symmetric monoidal closed (smc) theory and give an explicit construction of the smc category generated by it. This construction yields a monadic adjunction between smc theories and smc categories. We study in our algebraic framework different models of programming languages: the linear λ-calculus, the pure λ-calculus and Milner's bigraphs. For each model, we give a smc theory and compare the generated smc category with the standard presentation. We show that, in each case, there is an equivalence on closed terms.

Le lambda calcul avec constructeurs (de Arbiser, Miquel et Rios) est une extension du lambda calcul avec un mécanisme de filtrage. Le filtrage à la ML y est décomposé en deux étapes: une analyse de cas sur des constantes (telle l'instruction «case» de Pascal), et une commutation de l'application avec la construction de filtrage. Cette règle de commutation entre deux constructions de natures différentes induit une géométrie de calcul surprenante, a priori incompatible avec les intuitions habituelles de typage. Cependant il a été montré que ce calcul est confluent, et vérifie la propriété de séparation (à la Böhm). Cette thèse propose un système de types du polymorphique pour ce calcul, et décrit ensuite un modèle de réalisabilité, qui adapte les candidats de réductibilité de Girard au lambda calcul avec constructeurs. La normalisation forte du calcul typé et l'absence d'erreur de filtrage lors de l'évaluation en découlent immédiatement. Nous nous intéressons ensuite à la sémantique du lambda calcul avec constructeurs non typé. Une notion générique de modèle catégorique pour ce calcul est définie, puis un modèle particulier (le modèle syntaxique dans la catégorie des PERs) est construit. Nous en déduisons un résultat de complétude. Enfin, nous proposons une traduction CPS du lambda calcul avec constructeurs dans le lambda calcul simplement typé avec paires. Le lambda calcul avec constructeurs peut ainsi être simulé dans un calcul bien connu, et cette traduction nous permet aussi de transformer tout modèle par continuation en modèle du lambda calcul avec constructeurs. Une équation catégorique caractéristique de ces modèles apparait alors, qui permet de construire des modèles non syntaxiques (dans les domaines) de Scott du lambda calcul avec constructeurs. / The lambda calculus with constructors was introduced by Arbiser, Miquel and Rios in the early 2000's as an extension of lambda calculus with pattern matching features. It decomposes the pattern matching à la ML into a case-analysis on constant constructors (in the spirit of the case instruction in Pascal), and a commutation rule between case construction and application. This commutation rule between two different kinds of constructions designs a surprising computational behaviour, a priori} not compatible with usual typing intuitions. However the whole calculus was proved confluent, and it enjoys the separation property (a version of Böhm's lemma).In this thesis we propose a polymorphic type system for this calculus, and we develop a realisability model, based on Girard's reducibility candidates. This leads to a strong normalisation result for the typed calculus, and guaranties that the type system prevents match failure. Next we focus on semantics for the untyped calculus. We first define a generic notion of models for the lambda calculus with constructors in Cartesian closed categories. We then establish the syntactic model in the category of PERs, and deduce a completeness result from it.Finally, we consider a translation of the lambda calculus with constructors into the pure lambda lambda calculus relying on continuation passing style techniques. This enables the simulation of the lambda calculus with constructors by a well known calculus, and provides a transformation of every continuation model into a model of the lambda calculus with constructors. Thereby a categorical equation characteristic of these models appears, which enables the construction of non syntactic models in Scott's domains.

La complexité implicite (ICC) vise à donner des caractérisations de classes de complexité dans des langages de programmation ou des logiques, sans faire référence à des bornes sur les ressources (temps, espace mémoire). Dans cette thèse, nous étudions l’approche de la logique linéaire à la complexité implicite. L’objectif est de donner des caractérisations de classes de complexité, à travers des variantes du lambda-calcul qui sont typables dans de tels systèmes. En particulier, nous considérons à la fois une perspective monovalente et une perspective polyvalente par rapport à l’ICC. Dans le premier cas, le but est de caractériser une hiérarchie de classes de complexité à travers un lambda-calcul élémentaire typé dans la logique linéaire élémentaire (ELL), où la complexité ne dépend que de l’interface d’un programme, c’est à dire son type. La deuxième approche rend compte à la fois des fonctions calculables en temps polynomial et de la normalisation forte, à travers des termes du lambda-calcul pur qui sont typés dans un système inspiré par la logique linéaire Soft (SLL); en particulier, par rapport à l’approche logique ordinaire, ici nous abandonnons la modalité “!” en faveur de l’emploi des types stratifiés, vus comme un raffinement des types intersection non associatifs, afin d’améliorer la typabilité et, en conséquence, l’expressivité. Enfin, nous explorons l’utilisation des types intersection, privés de certaines de leurs propriétés, vers une direction plus quantitative que l’approche qualitative habituelle, afin d’obtenir une borne sur le calcul de lambda-termes purs, en obtenant en plus une caractérisation de la normalisation forte. / In this thesis we explore the linear logic approach to implicit computational complexity, through the design of type assignment systems based on light linear logic, or heavily inspired by them, with the purpose of giving a characterization of one or more complexity classes, through variants of lambda-calculi which are typable in such systems. In particular, we consider both a monovalent and a polyvalent perspective with respect to ICC. In the first one the aim is to characterize a hierarchy of complexity classes through an elementary lambda-calculus typed in Elementary Linear Logic (ELL), where the complexity depends only on the interface of a term, namely its type. The second approach gives an account of both the functions computable in polynomial time and of strong normalization, through terms of pure lambda-calculus which are typed in a system inspired by Soft Linear Logic (SLL); in particular, with respect to the usual logical take, in the latter we give up the “!” modality in favor of employing stratified types as a refinement of non-associative intersection types, in order to improve typability and, as a consequence, expressivity.Finally we explore the use of intersection types, deprived of some of their usual properties, towards a more quantitative approach rather than the usual qualitative one, namely in order to compute a bound on the computation of pure lambda-terms, obtaining in addition a characterization of strong normalization.

A Matemática Intervalar se assenta em dois conceitos fundamentais, a propriedade da inclusão-monotonicidade de sua aritmética e uma topologia de Hausdorff definida no conjunto dos intervalos. A propriedade da inclusão-monotonicidade tem se revelado uma ferramenta útil na elaboração de algoritmos intervalares, enquanto a topologia de Hausdorff não consegue refletir as características lógicas daquela propriedade, comprometendo, desse modo, a construção de uma lógica cujo modelo seria a estrutura intervalar munida dessa topologia. Essa lógica seria necessária para fundamentação da matemática intervalar como uma teoria de algorítmos da análise real. Neste trabalho se mostra que o insucesso na construção dessa fundamentação se deve a incompatibilidade entre a propriedade da inclusão-monotonicidade e a topologia de Hausdorff. A partir dessa constatação se descarta essa topologia e define-se uma outra topologia - a topologia de Scott - que é compatível com essa propriedade, no sentido de que todo resultado obtido usando-se a lógica, isto é, a propriedade da inclusão-monotonicidade, obtém-se também usando-se a ferramenta topológica e reciprocamente. A teoria resultante da substituição da topologia de Hausdorff pela topologia de Scott tem duas características fundamentais. A Análise Funcional Intervalar resultante possui a maioria das propriedades interessantes da Análise Real, suprimindo, assim, as deficiências da Análise Intervalar anterior. A elaboração da propriedade da inclusão-monotoniciadade permite construir uma lógica geométrica e uma teoria lambda cujo modelo é essa nova matemática intervalar. Além disso, a partir dessa lógica e da teoria lambda se elabora uma teoria construtiva, como a teoria dos tipos de Martin-Löf, que permite se raciocinar com programas dessa matemática. Isso significa a possibilidade de se fazer correção automática de programas da matemática intervalar. Essa nova abordagem da matemática intervalar é desenvolvida pressupondo, apenas, o conceito de número racional, além, é claro, da linguagem da teoria dos conjuntos. Desse modo é construído o sistema intervalar de um modo análogo ao sistema real. Para isso é generalizado o conceito de corte de Dedekind, resultando dessa construção um sistema ordenado denominado de quasi-corpo, em contraste com o números reais cujo sistema é algébrico, o corpo dos números reais. Assim, no sistema intervalar a ordem é um conceito intrínseco ao sistema, diferentemente do sistema de números reais cuja a ordem não faz parte da álgebra do sistema. A lógica dessa nova matemática intervalar é uma lógica categórica. Isto significa que todo resultado obtido para domínios básicos se aplica para o produto cartesiano, união disjunta, o espaço de funções, etc., desses domínios. Isto simplifica consideravelmente a teoria. Um exemplo dessa simplificação é a definição de derivada nessa nova matemática intervalar, conceito ainda não bem definido na teoria intervalar clássica. / The Interval Mathematics is based on two fundamental concepts, the inclusion-monotonicity of its arithmetics and a Hausdorff topology defined on the interval set. The property of inclusion-monotonicity has risen as an useful tool for elaboration of interval algorithms. In contrast, because the Hausdorff topology does not reflect the logical features of that property, the interval mathematics did not, permit the elaboration of a logic whose model is this interval mathematics with that topology. This logic should be necessary to the foundation of the interval mathematics as a Real Analysis Theory of Algorithms. This thesis shows that the theory of algorithms refered above was not possible because of the incompatibility between the property of inclusion-monotonicity and the Hausdorff topology. By knowing the shortcoming of this topology, the next step is to set it aside and to define a new topology - the Scott topology - compatible with the refered property in the sense that every result, obtained via the logic is also obtainable via the topology and vice-versa. After changing the topology the resulting theory has two basic features. The Interval Functional Analysis has got the most, interesting properties belonging to Real Analysis, supressing the shortcomings of previous interval analysis. The elaboration of the inclusion-monotonicity property allows one to construct a geometric logic and a lambda theory whose model is this new interval mathematics. From this logic and from the lambda theory a constructive theory is then elaborated, similar to Martin-Löf type theory, being possible then to reason about programs of this new interval mathematics. This means the possibility of automatically checking the correctness of programs of interval mathematics. This new approach assumes only the concept, of rational numbers beyond, of course, the set theory language. It is constructed an interval system similar to the real system. A general notion of the concept of Dedekind cut was necessary to reach that. The resulting construction is an ordered system which will be called quasi-field, in opposition to the real numbers system which is algebraic. Thus, in the interval system the order is an intrinsic concept, unlike the real numbers sistems whose order does not belong to the algebraic system. The logic of this new interval mathematics is a categorical logic. This means that, every result got for basic domains applies also to cartesian product, disjoint union, function spaces, etc., of these domains. This simplifies considerably the new theory. An example of this simplication is given by the definition of derivative, a concept not, derived by the classical interval theory.

Le lambda-calcul est un formalisation de la notion de calcul. Dans cette thèse nous nous intéresserons à certaines variantes non déterministes, et nous nous pencherons plus particulièrement sur le cas probabiliste.L'étude du lambda-calcul probabiliste n'est pas nouvelle, mais les travaux précédents considéraient le comportement probabiliste comme un effet de bord. Notre objectif est de présenter ce calcul d'une manière plus équationnelle, en intégrant le comportement probabiliste à la réduction.Tout d'abord nous définissons une sémantique opérationnelle déterministe et contextuelle pour le lambda-calcul probabiliste en appel par nom. Afin de traduire la signification de la somme nous définissons une équivalence syntaxique dans notre calcul, dont nous démontrons qu'il ne déforme pas la réduction: considérer une réduction modulo équivalence revient à considérer simplement le résultat du calcul modulo équivalence. Nous prouvons également un résultat de standardisation.Dans ce cadre nous définissons une notion de théorie équationnelle pour le lambda-calcul probabiliste. Nous étendons certaines notions usuelles, et en particulier celle de bon sens. Cette dernière se formalise facilement dans un cadre déterministe mais est bien plus complexe dans le cas probabiliste.Pour finir nous prouvons une correspondance entre l'équivalence observationnelle, l'égalité des arbres de Böhm et la théorie cohérente sensée maximale. Nous définissons une notion d'arbres de Böhm probabilistes dont nous prouvons qu'elle forme un modèle. Nous démontrons ensuite un résultat de séparabilité disant que deux termes avec des arbres de Böhm distincts ne sont pas observationnellement équivalents. / The lambda-calculus is a way to formalize the notion of computation. In this thesis we will be interested in some of these variants introducing non deterministim, and we will focus mostly on a probabilistic calculus.The probabilistic lambda-calculus has been studied for some time, but the probabilistic behaviour has always been treated as a side effect. Our purpose is to give a more equational representation of this calculus, by handling the probabilities inside the reduction rather than as a side effect.To begin with we give a deterministic and contextual operational semantics for the call-by-name probabilistic lambda-calculus. To express the probabilistic behaviour of the sum we introduce a syntactic equivalence in our calculus, and we show it has little consequence on the calculus: reducing modulo equivalence amount to reducing and then looking at the result modulo equivalence. We also prove a standardization theorem.Then using this operational semantics we define a notion of equational theories for the probabilistic lambda-calculus. We extend some usual notions to this setting, and in particular the sensibility of a theory. This notion is quite simple in a deterministic setting but becomes more complicated when we have a probabilistic computation.Finally we prove a generalization of the equality between the observational equivalence, the Böhm tree equality and the maximal coherent sensible lambda-theory. We give a notion of probabilistic Böhm trees, and prove that this forms a model of the probabilistic lambda-calculus. Then we prove a separability result stating that two terms with different Böhm trees are separable, i.e. are not observationally equivalent.

Les grammaires catégorielles abstraites (ou λ-grammaires) sont un formalisme basé sur le λ-calcul simplement typé. Elles peuvent être vues comme des grammaires générant de tels termes, et ont été introduites afin de modéliser l’interface entre la syntaxe et la sémantique du langage naturel, réunissant deux idées fondamentales : la distinction entre tectogrammaire (c.a.d. structure profonde d’un énoncé) et phénogrammaire (c.a.d représentation de la surface d’un énoncé) de la langue, ex- primé par Curry ; et une modélisation algébrique du principe de compositionnalité afin de rendre compte de la sémantique des phrases, due à Montague. Un des avantages principaux de ce formalisme est que l’analyse d’une grammaires catégorielle abstraite permet de résoudre aussi bien le problème de l’analyse de texte, que celui de la génération de texte. Des algorithmes d’analyse efficaces ont été découverts pour les grammaires catégorielles abstraites de termes linéaires et quasi-linéaires, alors que le problème de l’analyse est non-élémentaire dans sa forme la plus générale. Nous proposons d’étudier des classes de termes pour lesquels l’analyse grammaticale reste solvable en temps polynomial. Ces résultats s’appuient principalement sur deux théorèmes de typage : le théorème de cohérence, spécifiant qu’un λ-terme donné est l’unique habitant d’un certain typage ; et le théorème d’expansion du sujet, spécifiant que deux termes β-équivalents habitent les même typages. Afin de mener cette étude à bien, nous utiliserons une représentation abstraite des notions de λ-termes et de typages, sous forme de jeux. En particulier, nous nous appuierons grandement sur cette notion afin de démontrer le théorème de cohérence pour de nouvelles familles de λ-termes et de typages. Grâce à ces résultats, nous montrerons qu’il est possible de construire de manière directe, un reconnaisseur dans le langage Datalog, pour des grammaires catégorielles abstraites de -termes quasi-affines. / Abstract categorial grammars (or, equivalently, lambda-grammars) is formalism based on the simply-typed lambda-calculus. These grammars can be described as grammars of such terms and were introduced in order to bring a model of the syntax-semantics interface in natural language, based on two main ideas: the distinction between the tectogrammatical (i.e. the deep structure of an utterance) and phenogrammatical (i.e. the interpretation of this structure) levels in natural languages, which was expressed by Curry; and an algebraic modeling of the principle of compositionality in order to give account of the semantics of a sentence. an idea formalized by Montague. One of the main advantages of abstract categorial grammars is that both the problems of natural language parsing and generation can be tackled under the same problem: parsing abstract categorial grammars. Efficient algorithms were discovered for abstract categorial grammars of linear and almost linear lambda-terms, while it is known the recognition problem is decidable but non-elementary in general. This work focuses on the study of classes of terms for which parsing can still be solved in polynomial time. The results we give are mainly based on two theorems: the coherence theorem which specifies that a given lambda-term in the desired class must be the unique inhabitant of one of its typing; and the subject expansion theorem, which states that two beta-equivalent terms of the desired class must inhabit the same typings. In order to lead the study, we use an alternative representation of both simply-typed lambda-terms and their typings as games. In particular, we will use this representation in order to prove the coherence theorems for new classes of lambda-terms. Thanks to these results, we will show it is possible to build in a direct way, recognizers for grammars of almost affine lambda-terms as Datalog programs.

No description available.

Cette thèse concerne la combinaison du lambda-calcul et de la réécriture, dont nous étudions principalement deux propriétés : la confluence et la normalisation forte. Nous commençons par étudier sous quelles conditions la combinaison d'une relation de réécriture conditionnelle confluente au lambda-calcul donne une relation de réécriture confluente. Ensuite nous nous intéressons aux preuves de normalisation forte de lambda-calculs typés utilisant la technique de réductibilité. Notre contribution la plus importante est une comparaison de diverses variantes de cette technique, utilisant comme outil de comparaison la manière dont ces variantes s'étendent à la réécriture et dont elles prennent en compte les types unions et les types existentiels implicites. Enfin, nous présentons un critère, basé sur un système de types contraints, pour la normalisation forte de la réécriture conditionnelle combinée au lambda-calcul. Notre approche étend des critères de terminaison existants qui utilisent des annotations de taille. C'est à notre connaissance le premier critère de terminaison pour la réécriture conditionnelle avec membres droits d'ordre supérieur qui prenne en compte, dans l'argument de terminaison, de l'information issue de la satisfaction des conditions des règles de réécriture / This thesis is about the combination of lambda-calculus with rewriting. We mainly study two properties: confluence and strong normalization. We begin by studying under which conditions the combination of a confluent conditional rewrite relation to the lambda-calculus leads to a confluent relation. Next, we study strong normalization proofs of typed lambda-calculi that use the reducibility technique. Our main contribution is a comparison of variants of this technique, with respect to how they extend to rewriting and how they handle union and implicit existential types. Finally, we present a termination criterion for the combination of conditional rewriting and lambda-calculus based on a constrained type system. Our approach, which extends known criteria that use sized types, is to our knowledge the first termination criterion for conditional rewriting with higher-order right-hand sides that takes into account in the termination argument some information generated by the satisfaction of the conditions of the rewrite rules

Cette thèse porte sur l’adaptation de la réalisabilité et la paramétricité au cas des types dépendants dans le cadre des Systèmes de Types Purs. Nous décrivons une méthode systématique pour construire une logique à partir d’un langage de programmation, tous deux décrits comme des systèmes de types purs. Cette logique fournit des formules pour exprimer des propriétés des programmes et elle offre un cadre formel adéquat pour développer une théorie de la réalisabilité au sein de laquelle les réalisateurs des formules sont exactement les programmes du langage de départ. Notre cadre permet alors de considérer les théorèmes de représentation pour le système T de Gödel et le système F de Girard comme deux instances d'un théorème plus général.Puis, nous expliquons comment les relations logiques de la théorie de la paramétricité peuvent s'exprimer en terme de réalisabilité, ce qui montre que la logique engendrée fournit un cadre adéquat pour développer une théorie de la paramétricité du langage de départ. Pour finir, nous montrons comment cette théorie de la paramétricité peut-être adaptée au système sous-jacent à l'assistant de preuve Coq et nous donnons un exemple d'application original de la paramétricité à la formalisation des mathématiques. / This thesis focuses on the adaptation of realizability and parametricity to dependent types in the framework of Pure Type Systems. We describe a systematic method to build a logic from a programming language, both described as pure type systems. This logic provides formulas to express properties of programs and offers a formal framework that allows us to develop a theory of realizability in which realizers of formulas are exactly programs of the starting programming language. In our framework, the standard representation theorems of Gödel's system T and Girard's system F may be seen as two instances of a more general theorem. Then, we explain how the so-called « logical relations » of parametricity theory may be expressed in terms of realizability, which shows that the generated logic provides an adequate framework for developping a general theory of parametricity. Finally, we show how this parametricity theory can be adapted to the underlying type system of the proof assistant Coq and we give an original example of application of parametricity theory to the formalization of mathematics.