Cette thèse s'intéresse à l'usage des formalismes d'inférence profonde comme fondement des interprétations calculatoires des systèmes de preuve, en suivant les deux approches principales: celle des preuves comme programmes et celle de la recherche de preuve comme calcul. La première contribution est le développement d'une famille de systèmes de preuve pour la logique intuitionniste dans le calcul des structures et dans les séquents imbriqués. pour lesquels des procédures de normalisation internes sont fournies. L'une de ces procédures est alors interprétée en termes calculatoires, comme un raffinement de la correspondance de Curry-Howard permettant d'introduire une forme de partage ainsi que des opérateurs de communication dans un lambda-calcul avec substitution explicite. Du coté de la recherche de preuve, la notion de preuve focalisée en logique linéaire est transférée du calcul des séquents au calcul des structures, où elle induit une forme incrémentale de focalisation, dotée d'une preuve de complétude très simple. Enfin, une autre interprétation de la recherche de preuve est donnée par l'encodage de la réduction d'un lambda-calcul avec substitution explicite dans les règles d'inférence d'un sous-système de la logique intuitionniste dans le calcul des structures.

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.

La complexité implicite est la caractérisation de classes de complexité par des restrictions syntaxiques sur des modèles de calcul. Plusieurs sous-systèmes de la logique linéaire caractérisant le temps polynomial ont été définis: ces systèmes sont corrects (les termes normalisent en temps polynomial) et complets (il est possible de simuler une machine de Turing pendant un nombre polynomial d'étapes). Un des buts sur le long terme est de donner statiquement des bornes de complexité. C’est pourquoi nous cherchons les caractérisations du temps polynomial les plus expressives possible. Notre principal outil est la sémantique des contextes: des jetons voyagent à travers le réseau selon certaines règles. Les chemins définis par ces jetons représentent la réduction du réseau. Contrairement aux travaux précédents, nous ne définissons pas directement des sous-systèmes de la logique linéaire. Nous définissons d'abord des relations -> sur les sous-termes des réseaux de preuves tel que: B -> C ssi ”le nombre de copies de B dépend du nombre de copies de C”. L’acyclicité de -> borne le nombre de copies de chaque sous-terme, donc la complexité du terme. Ensuite nous définissons des sous-systèmes de la logique linéaire assurant l’acyclicité de ->. Nous étudions aussi des caractérisations du temps élémentaire et primitif récursif. Dans le but d’adapter nos sous-systèmes de la logique linéaire à des langages plus riches, nous adaptons la sémantique des contextes aux réseaux d’interaction, utilisés comme langage cible pour de petits langage de programmation. Nous utilisons cette sémantique des contexte pour définir une sémantique dénotationnelle sur les réseaux d’interactions. / Implicit computational complexity is the characterization of complexity classes by syntactic restrictions on computation models. Several subsystems of linear logic characterizing polynomial time have been defined : these systems are sound (terms normalize in polynomial time) and complete (it is possible to simulate a Turing machine during a polynomial number of steps). One of the long term goals is to statically prove complexity bounds. This is why we are looking for the most expressive characterizations possible. Our main tool is context semantics : tokens travel across proof-nets (programs of linear logic) according to some rules. The paths defined by these tokens represent the reduction of the proof-net.Contrary to previous works, we do not directly define subsystems of linear logic. We first define relations -> on subterms of proof-nets such that: B -> C means \the number of copies of B depends on the number of copies of C". The acyclicity of -> allows us to bound the number of copies of any subterm, this bounds the complexity of the term. Then, we define subsystems of linear logic guaranteeing the acyclicity of ->. We also study characterizations of elementary time and primitive recursive time. In orderto adapt our linear logic subsystems to richer languages, we adapt the context semantics to interaction nets, used as a target language for small programming languages. We use this context semantics to define a denotational semantics on interaction nets.

L'objectif de cette thèse est de fournir un modèle, une méthode et un outil d'aide à la réalisation de scénarios interactifs. Cette solution répond au problème de l'opposition entre la maîtrise du déroulement d'un jeu vidéo et son niveau d'interactivité. En d'autres termes, notre but est d'aider à réaliser des jeux vidéo dont l'évolution satisfait les intentions des auteurs tout en autorisant un déroulement influencé par les choix du joueur (exprimés aux travers de ses actions). Pour cela, notre proposition permet à l'utilisateur de produire un modèle de scénario de jeu de bonne qualité qui est : (a) riche - le scénario fournit suffisamment d'options pertinentes aux personnages joueur/non-joueur de sorte que le joueur puisse déterminer le déroulement du jeu et sente toujours que le discours créé est intéressant, (b) valide - tous les discours possibles dans le scénario sont cohérents et répondent aux effets désirés par les auteurs, (c) opérationnel - la représentation du scénario est exécutable. Ce scénario est ensuite employé comme l'entrée d'un système de pilotage de narration interactive assurant le contrôle de la gestion du déroulement du jeu. Par conséquent, l'évolution des jeux, qui sont dirigés par un tel système de pilotage, garantit que l'exécution du jeu respecte les souhaits des auteurs, et en même temps, autorise la liberté des actions du joueur. Pour répondre au problème exposé ci-dessus, nous appuyons notre solution sur un modèle mathématique calculable (la logique linéaire) qui offre des mécanismes de déductions rigoureux et automatiques.Nous avons fait un tour d'horizon des approches existantes concernant le pilotage de narration interactive et la validation de scénario. Ceci nous permet d'identifier les principes nécessaires à notre solution, tels que les éléments d'architecture d'un système de pilotage ; la construction,la représentation, l'exécution de scénarios narratifs ; les propriétés de narration importantes ; l'évolution de référence des paramètres dramatiques ; la structuration de discours ; la stratégie pour la validation d'un scénario ; les informations qualitatives et statistiques nécessaires... Nos contributions portent (1) sur la définition d'un ensemble de propriétés de narration spécifiant la qualité des scénarios de jeu ; (2) sur la proposition de modèles, algorithmes et outils pour écrire des modèles de scénario respectant ces propriétés. Nous validons nos résultats par la réalisation de deux exemples. Le premier est un extrait d'un jeu éducatif expliquant comment appliquer notre outil en vue de produire un modèle de scénario de jeu valide, qui est exprimé par un séquent de logique linéaire dont la représentation est conforme à un métamodèle du calcul des séquents. Pour le second exemple, nous décrivons le processus de production complet d'un jeu vidéo réel basé sur l'histoire " Le Petit Chaperon rouge ", mettant en oeuvre un prototype de système de pilotage que nous avons proposé, ce qui permet de dérouler le jeu selon le scénario valide produit, donc son évolution satisfait les intentions des auteurs, et en même temps, dépend des actions du joueur.

L'objectif de cette thèse est de fournir un modèle, une méthode et un outil d'aide à la réalisation de scénarios interactifs. Cette solution répond au problème de l'opposition entre la maîtrise du déroulement d'un jeu vidéo et son niveau d'interactivité. En d'autres termes, notre but est d'aider à réaliser des jeux vidéo dont l'évolution satisfait les intentions des auteurs tout en autorisant un déroulement influencé par les choix du joueur (exprimés aux travers de ses actions). Pour cela, notre proposition permet à l'utilisateur de produire un modèle de scénario de jeu de bonne qualité qui est : (a) riche - le scénario fournit suffisamment d'options pertinentes aux personnages joueur/non-joueur de sorte que le joueur puisse déterminer le déroulement du jeu et sente toujours que le discours créé est intéressant, (b) valide - tous les discours possibles dans le scénario sont cohérents et répondent aux effets désirés par les auteurs, (c) opérationnel - la représentation du scénario est exécutable. Ce scénario est ensuite employé comme l'entrée d'un système de pilotage de narration interactive assurant le contrôle de la gestion du déroulement du jeu. Par conséquent, l'évolution des jeux, qui sont dirigés par un tel système de pilotage, garantit que l'exécution du jeu respecte les souhaits des auteurs, et en même temps, autorise la liberté des actions du joueur. Pour répondre au problème exposé ci-dessus, nous appuyons notre solution sur un modèle mathématique calculable (la logique linéaire) qui offre des mécanismes de déductions rigoureux et automatiques.Nous avons fait un tour d'horizon des approches existantes concernant le pilotage de narration interactive et la validation de scénario. Ceci nous permet d'identifier les principes nécessaires à notre solution, tels que les éléments d'architecture d'un système de pilotage ; la construction,la représentation, l'exécution de scénarios narratifs ; les propriétés de narration importantes ; l'évolution de référence des paramètres dramatiques ; la structuration de discours ; la stratégie pour la validation d'un scénario ; les informations qualitatives et statistiques nécessaires... Nos contributions portent (1) sur la définition d'un ensemble de propriétés de narration spécifiant la qualité des scénarios de jeu ; (2) sur la proposition de modèles, algorithmes et outils pour écrire des modèles de scénario respectant ces propriétés. Nous validons nos résultats par la réalisation de deux exemples. Le premier est un extrait d'un jeu éducatif expliquant comment appliquer notre outil en vue de produire un modèle de scénario de jeu valide, qui est exprimé par un séquent de logique linéaire dont la représentation est conforme à un métamodèle du calcul des séquents. Pour le second exemple, nous décrivons le processus de production complet d'un jeu vidéo réel basé sur l'histoire " Le Petit Chaperon rouge ", mettant en oeuvre un prototype de système de pilotage que nous avons proposé, ce qui permet de dérouler le jeu selon le scénario valide produit, donc son évolution satisfait les intentions des auteurs, et en même temps, dépend des actions du joueur.

Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisissant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions — qui semblent à première vue si différentes — sont des conséquences d'une même identité géométrique. / This work is a study of the geometry of interaction in the hyperfinite factor introduced by Jean-Yves Girard, and of its relations with ancient constructions. We start by showing how to obtain purely geometrical adjunctions as an identity between sets of cycles appearing between graphs. It is then possible, by chosing a function that measures those cycles, to obtain a numerical adjunction. We then show how to construct, on the basis of such a numerical adjunction, a geometry of interaction for multiplicative additive linear logic where proofs are interpreted as graphs. We also explain how to define from this construction a denotational semantics for MALL, and a notion of truth. We extend this setting in order to deal with exponential connectives and show a full soundness result for a variant of elementary linear logic (ELL). Since the constructions on graphs we define are parametrized by a function that measures cycles, we then focus our study to two particular cases. The first case turns out to be a combinatorial version of GoI5, and we thus obtain a geometrical caracterisation of its orthogonality which is based on Fuglede-Kadison determinant. The second particular case we study will giveus a refined version of older constructions of geometry of interaction, where orthogonality is based on nilpotency. This allows us to show how these two versions of GoI, which seem quite different, are related and understand that the respective adjunctions are both consequences of a unique geometrical property. In the last part, we study the notion of subjective truth.

Une bonne partie des résultats contenus dans ce travail portent sur les réseaux de démonstration de la logique linéaire ainsi que sur la sémantique des espaces cohérents. Ces résultats concernent plus particulièrement les variantes non commutatives de la logique linéaire que ce soit à la Lambek-Abrusci ou dans le calcul ordonné de l'auteur. Ils sont ensuite appliqués à la syntaxe du langage naturel, modélisée bien évidemment par les grammaires catégorielles, les TAGS, mais aussi par les grammaires minimalistes de Stabler que l'on peut aussi simuler en logique linéaire. Pour tous ces systèmes grammaticaux, le calcul de représentations sémantiques est explicité.

Thèse par articles. / La présente thèse fait état des avancées en logique déontique et propose des outils formels pertinents à l'analyse de la validité des inférences légales. D'emblée, la logique vise l'abstraction de différentes structures. Lorsqu'appliquée en argumentation, la logique permet de déterminer les conditions de validité des inférences, fournissant ainsi un critère afin de distinguer entre les bons et les mauvais raisonnements. Comme le montre la multitude de paradoxes en logique déontique, la modélisation des inférences normatives fait cependant face à divers problèmes. D'un point de vue historique, ces difficultés ont donné lieu à différents courants au sein de la littérature, dont les plus importants à ce jour sont ceux qui traitent de l'action et ceux qui visent la modélisation des obligations conditionnelles. La présente thèse de doctorat, qui a été rédigée par articles, vise le développement d'outils formels pertinents à l'analyse du discours juridique. En première partie, nous proposons une revue de la littérature complémentaire à ce qui a été entamé dans Peterson (2011). La seconde partie comprend la contribution théorique proposée. Dans un premier temps, il s'agit d'introduire une logique déontique alternative au système standard. Sans prétendre aller au-delà de ses limites, le système standard de logique déontique possède plusieurs lacunes. La première contribution de cette thèse est d'offrir un système comparable répondant au différentes objections pouvant être formulées contre ce dernier. Cela fait l'objet de deux articles, dont le premier introduit le formalisme nécessaire et le second vulgarise les résultats et les adapte aux fins de l'étude des raisonnements normatifs. En second lieu, les différents problèmes auxquels la logique déontique fait face sont abordés selon la perspective de la théorie des catégories. En analysant la syntaxe des différents systèmes à l'aide des catégories monoïdales, il est possible de lier certains de ces problèmes avec des propriétés structurelles spécifiques des logiques utilisées. Ainsi, une lecture catégorique de la logique déontique permet de motiver l'introduction d'une nouvelle approche syntaxique, définie dans le cadre des catégories monoïdales, de façon à pallier les problèmes relatifs à la modélisation des inférences normatives. En plus de proposer une analyse des différentes logiques de l'action selon la théorie des catégories, la présente thèse étudie les problèmes relatifs aux inférences normatives conditionnelles et propose un système déductif typé. / The present thesis develops formal tools relevant to the analysis of legal discourse. When applied to legal reasoning, logic can be used to model the structure of legal inferences and, as such, it provides a criterion to discriminate between good and bad reasonings. But using logic to model normative reasoning comes with some problems, as shown by the various paradoxes one finds within the literature. From a historical point of view, these paradoxes lead to the introduction of different approaches, such as the ones that emphasize the notion of action and those that try to model conditional normative reasoning. In the first part of this thesis, we provide a review of the literature, which is complementary to the one we did in Peterson (2011). The second part of the thesis concerns our theoretical contribution. First, we propose a monadic deontic logic as an alternative to the standard system, answering many objections that can be made against it. This system is then adapted to model unconditional normative inferences and test their validity. Second, we propose to look at deontic logic from the proof-theoretical perspective of category theory. We begin by proposing a categorical analysis of action logics and then we show that many problems that arise when trying to model conditional normative reasoning come from the structural properties of the logic we use. As such, we show that modeling normative reasoning within the framework of monoidal categories enables us to answer many objections in favour of dyadic and non-monotonic foundations for deontic logic. Finally, we propose a proper typed deontic system to model legal inferences.

Le but de cette thèse est d'étudier la somme et le zéro dans deux principaux cadres : les isomorphismes de types et la normalisation de lambda-termes. Les isomorphismes de type avaient déjà été étudiés dans le cadre du lambda-calcul simplement typé avec paires surjectives mais sans somme. Pour aborder le cas avec somme et zéro, j'ai commencé par restreindre l'étude au cas des isomorphismes linéaires, dans le cadre de la logique linéaire, ce qui a conduit à une caractérisation remarquablement simple de ces isomorphismes, obtenue grâce à une méthode syntaxique sur les réseaux de preuve. Le cadre plus général de la logique intuitionniste correspond au problème ouvert de la caractérisation des isomorphismes dans les catégories bi-cartésiennes fermées. J'ai pu apporter une contribution à cette étude en montrant qu'il n'y a pas d'axiomatisation finie de ces isomorphismes. Pour cela, j'ai tiré partie de travaux en théorie des nombres portant sur un problème énoncé par Alfred Tarski et connu sous le nom du « problème des égalités du lycée ». Pendant tout ce travail sur les isomorphismes de types, s'est posé le problème de trouver une forme canonique pour représenter les lambda-termes, que ce soit dans le but de nier l'existence d'un isomorphisme par une étude de cas sur la forme du terme, ou pour vérifier leur existence dans le cas des fonctions très complexes que j'étais amené à manipuler. Cette réflexion a abouti à poser une définition « extensionnelle » de forme normale pour le lambda-calcul avec somme et zéro, obtenue par des méthodes catégoriques grâce aux relations logiques de Grothendieck, apportant ainsi une nouvelle avancée dans l'étude de la question réputée difficile de la normalisation de ce lambda-calcul. Enfin je montrerai comment il est possible d'obtenir une version « intentionnelle » de ce résultat en utilisant la normalisation par évaluation. J'ai pu ainsi donner une adaptation de la technique d' évaluation partielle dirigée par les types pour qu'elle produise un résultat dans cette forme normale, ce qui en réduit considérablement la taille et diminue aussi beaucoup le temps de normalisation dans le cas des isomorphismes de types considérés auparavant.

Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.