Dans la première partie, on propose un système de type pour le lambda-calcul, dans le style du calcul des séquents, nomme « Soft Type Assignment » (STA) qui est inspiré par la logique linéaire « soft ». STA a la propriété de réduction du sujet et est correct et complète pour les calculs en temps polynomial. Par la suite on propose un déduction naturelle, STA_N. Ce système est simple mais il a le désavantage que les variables dans le sujet peuvent être explicitement renommées. Pour résoudre ce problème, on propose le système STA_M, où les contextes sont des multi-ensembles, donc les règles pour renommer les variables peuvent être interdit. L’inférence de type pour STA_M ne semble pas décidable. On propose un algorithme qui pour chaque lambda-terme rend l’ensemble de contraintes que doivent être satisfait pour que le terme soit type. Pi est correct et complet. Ensuite on étend le lambda-calcul par des constantes booléennes et on propose le système STA_B. La particularité de STA_B est que la règle du conditionnel utilise les contextes de façon additive. Chaque programme de STA_B peut être exécuté, par une machine abstraite, en espace polynomial. De plus le système est aussi complet pour PSPACE. Dans la deuxième partie, on propose une restriction de PCF, nommée SlPCF. Ce langage est équipé avec une sémantique opérationnelle qui mélange l’appelle par nom et l’appelle par valeur et peut être interprèté en mode standard dans les espaces cohérents linéaires. SlPCF est complet pour les fonctions récursives, mais il n’est pas complet et donc il n’est pas fully abstract pour les espaces cohérents linéaires / In the first part, we propose, inspired by Soft Linear Logic, a type assignment system for lambda-calculus in sequent calculus style, named Soft Type Assignment (STA). STA enjoys the subject reduction property. and is correct and complete for polynomial time computations. Then, we propose a natural deduction named STA_N. While simple, STA_N has the disadvantage of allowing the explicit renaming of variables in the subject. To overcome to this problem, we propose another natural deduction system, named STA_M, where contexts are multisets, hence rules renaming variables can be avoided. The type inference for STA_M seems in general undecidable. We propose an algorithm Pi returning, for every lambda-term, a set of constraints that need to be satisfied in order to type the term. Pi is correct and complete. We extend the lambda-calculus by basic boolean constants and we propose the system STA_B. The peculiarity of STA_B is that the conditional rule treats the contexts in an additive way. Every STA_B program can be executed, through an abstract machine, in polynomial space. Moreover, STA_B is also complete for PSPACE. In the second part we propose a restriction of PCF, named SlPCF. The language is naturally equipped with an operational semantics mixing call-by-name and call-by-value parameter passing and it can be interpreted in linear coherence space in a standard way. SlPCF is recursive complete, but it is not complete, and thus not fully abstract, with respect to linear coherence spaces

Le but de cette thèse est de trouver des modèles de haut niveau dans lesquelles l'auto-modification s'exprime facilement. Une donnée est lisible et modifiable, alors qu'un programme est exécutable. On décrit une machine abstraite où cette dualité est structurellement mise en valeur. D'une part une zone de programmes contient tous les registres exécutables, et d'autre part une zone de données contient les registres lisibles et exécutables. L'auto-modification est permise par le passage d'un registre d'une zone à l'autre. Dans ce cadre, on donne une abstraction de l'exécution de la machine qui extrait seulement les informations d'auto-modification. Logiquement, on essaye de trouver une correspondance de Curry-Howard entre un langage avec auto-modification et un système logique. Dans ce but on construit une extension de lambda-calcul avec termes gelés, c'est à dire des termes qui ne peuvent se réduire. Ces termes sont alors considérés comme des données, et les autres sont les programmes. Notre langage a les propriétés usuelles du lambda-calcul (confluence). D'autre part, on donne un système de types dans lequel un sous ensemble des termes du langage peuvent s'exprimer. Ce système est inspiré de la Logique Linéaire, sans gestion des ressources. On prouve que ce système de types a de bonnes propriétés, comme celle de la réduction du sujet. Finalement, on étend le système avec les continuations et la double négation, dans un style à la Krivine / The goal of my Ph.D. is to finds high level models in which self-modification can be expressed. What is readable and changeable is a data, and a program is executable. We propose an abstract machine where this duality is structurally emphasized. On one hand the program zone beholds registers which can be executed, and on the other hand data zone contains readable and changeable registers. Self-modification is enabled by passing a data register into program zone, or a program register into data zone. In this case, we give an abstraction of executions which only extracts information about self-modifications: execution is cut into paths without self-modification. For the logical part, we tried to find a Curry-Howard correspondence between a language with self-modifications and logical world. For that we built an extension of lambda-calculus with frozen terms, noted <t>, that is, terms which cannot reduce. This terms are considered as data. Other terms are programs. We first prove that this language as expected properties like confluence. On the other hand, we found a type system where a subset of terms of this language can be expressed. Our type system is inspired by Linear Logic, without resources management. We prove that this system has good properties like subject reduction. We finally have extended the system with continuation and double negation. This extension can be expressed in a krivine style, using a machine inspired by krivine machine

Dans le dernier siècle, nombreux sciences ont enrichi leur syntaxe pour pouvoir modeler des interactions. Entre eux on peut compter l'informatique, la physique quantique, et aussi la biologie et l’économie : toutes ces sciences sont des exemples de domaines qui ont besoin d'une syntaxe et d'une sémantique soit pour la concurrence que pour la séquentialité.Les diagrammes des cordes sont bien adapté à cet effet. Dans leur syntaxe on peut retrouver deux compositions : une composition parallèle et une composition séquentielle, qui peuvent interagir à travers une loi d'interchange. Si on considère cette loi comme une égalité, les diagrammes de cordes sont une syntaxe pour les catégories monoidales strictes, avec une représentation graphique plus intuitive que les formules algébriques traditionnelles.Dans cette thèse, on étude cette syntaxe de dimension 2 et sa sémantique. On considéré la réécriture des diagrammes et on donne des applications de cet méthode :- une preuve détaillée du théorème de cohérence de MacLanes pour les catégories monoidales symétriques basée sur un système de réécriture convergent donnée en arXiv:1606.01722;;- une interprétation des dérivations de preuves avec les diagrammes de preuve pour le fragment MELL de la logique linéaire, qui capture l’équivalence de preuves. On peut vérifier la séquentialité en temps linéaire, c'est à dire vérifier si un diagramme corresponds à une preuve. Cette interprétation est une extension de celle pour le fragment MLL donnée en arXiv:1606.09016 en donnant aussi un résultat de élimination du coupure. / In the last century, several sciences enriched their syntax in order to model interactions.Not only computer science and quantum physics, but also biology and economicsare examples of fields requiring syntax and semantics for concurrency as wellas for sequentiality.String diagrams are suitable for that purpose. In that syntax, we have two compositions:the parallel one and the sequential one, which may interact by the interchangerule. If we consider this rule as an equality, string diagrams are a syntax for strictmonoidal categories, with a more intuitive graphical representation than traditionalalgebraic formulas.In this thesis, we study this 2-dimensional syntax and its semantics. We considerdiagram rewriting and we give two applications of those methods:• a detailed proof of Mac Lane’s coherence theorem for symmetric monoidal categoriesbased on convergent diagram rewriting, which is given in arXiv:1606.01722;• an interpretation of proof derivations by string diagrams for the MELL fragmentof linear logic, which captures proof equivalence. We get a linear sequentializabilitytest to verify if a diagram corresponds to a proof . This interpretationextends the one for the MLL fragment given in arXiv:1606.09016,providing also a cut-elimination result.

[pt] O objetivo desta dissertação é construir um tableaux linear intuicionista a partir de um cálculo de sequentes relevante clássico. Os passos principais dessa construção são: i) tradução das regras do cálculo dos sequentes relevante clássico para regras de tableaux (capítulo 3), usando a estratégia apresentada por D Agostino et al. em Tableau Methods for Substructural Logic. ii) construção de um tableaux linear clássico através da linearização do tableaux clássico relevante (capítulo 4). iii) apresentar um tableau intuicionista ao estilo Fitting, em que são adicionados rótulos T s e F s às fórmulas (capítulo 5). / [en] The main goal of this master tesis is intuitionistic linear tableaux from a relevant sequent calculus. The central steps are: i) Apply D Agostino et al. strategy to translate classical relevant sequent calculus rules to tableaux rules for classical relevant logic (Chapter 3). ii) Use Meyer et al. strategy to linearize the classical relevant tableaux (Chapter 4). iii) Build a new intuicionistic linear tableaux with Fitting labels.

Notre propos est la conception assistée par ordinateur des scénarios comprenant des contenus multimédia qui interagissent avec les actions extérieures, notamment celles de l’interprète (e.g., spectacles vivants, installations muséales interactives et jeux vidéo). Le contenu multimédia est structuré dans un ordre spatial et temporel selon les exigences de l’auteur. Par conséquent, la complexité potentiellement élevée de ces scénarios nécessite des langages de spécification adéquats pour leur complète description et vérification.Partitions Interactives est un formalisme qui a été proposé comme un modèle pour la composition et l’exécution des scénarios multimédias interactifs. En outre, un séquenceur inter-médias, appelé ISCORE,a été élaboré à partir de la sémantique Petri net proposée par ce formalisme. Au cours des dernières années, I-SCORE a été utilisé avec succès pour la composition et l’exécution des spectacles et des expositions interactives. Néanmoins, ces applications et les applications émergentes telles queles jeux vidéo et les installations muséales interactives, de plus en plus exigent deux caractéristiques que la version stable actuelle de I-SCORE ainsi que son modèle sous-jacent ne supportent pas : (1)des structures de contrôle flexibles comme des conditionnelles et des boucles ; et (2) des mécanismes pour la vérification automatique de scénarios.Dans cette thèse, nous présentons deux modèles formels pour la composition et la vérification automatique de scénarios interactifs multimédia avec des choix interactifs, i.e., des scénarios où l’interprète ou le système peut prendre des décisions au sujet de leur état d’exécution avec un certain degré de liberté définie par le compositeur.Dans notre première approche, nous définissons un nouveau langage de programmation appelé REACTIVEIS dont les programmes sont définis comme des arbres représentant l’aspect hiérarchique des scénarios interactifs et dont les noeuds contiennent les conditions nécessaires pour démarrer et arrêter les objets temporels (TOS). En outre, nous définissons une sémantique opérationnelle basé sur des arbres marqués, contenant dans leurs noeuds, les informations sur le début et la fin de chaque TO. Nous définissons également une interprétation déclarative de REACTIVEIS comme formules de la logique linéaire intuitionniste avec sous exponentiels (SELL). Nous montrons que cette interprétation est adéquate : les dérivations dans la logique correspondent à des traces du programme et vice-versa.Dans notre deuxième approche, nous présentons un système basé sur des Automates Temporisés.Dans le système proposé, nous modélisons des scénarios interactifs comme un réseau d’automates temporisés et les étendons avec des points interactifs gardés par des conditions, permettant ainsi la spécification de comportements avec branchements. Par ailleurs, nous profitons des outils matures et efficaces pour simuler et vérifier automatiquement des scénarios modélisés comme des automates temporisés. Dans notre système, les scénarios peuvent être synthétisés dans un matériel reconfigurable afin de fournir une faible latence et l’exécution en temps réel.Dans cette thèse, nous explorons également une nouvelle façon de définir et mettre en oeuvre des scénarios interactifs, visant à un modèle plus dynamique en utilisant le langage réactif REACTIVEML.Enfin, nous présentons une extension des scénarios interactifs utilisant des réseaux de Petri colorés(CPN) qui vise à traiter des données complexes, en particulier, les données statiques et dynamiques de flux audio. / Interactive multimedia deals with the computer-based design of scenarios consisting of multimediacontent that interacts with external actions and those of the performer (e.g., multimedialive-performance arts, interactive museum installations, and video games). The multimedia content is structured in a spatial and temporal order according to the author’s requirements. Therefore, thepotentially high complexity of these scenarios requires adequate specification languages for theircomplete description and verification.Interactive scores is a formalism which has been proposed as a model for composing and performing interactive multimedia scenarios. In addition, an inter-media sequencer, called I-SCORE, hasbeen developed following the Petri Net semantics proposed by this formalism. During the last years,I-SCORE has been used successfully for the composition and performance of live performances and interactive exhibitions. Nevertheless, these applications and emergent applications such as videogames and interactive museum installations, increasingly demand two features that the current stable version of I-SCORE as well as its underlying model do not support: (1) flexible control structures such as conditionals and loops; and (2) mechanisms for the automatic verification of scenarios.In this dissertation we present two formal models for composition and automatic verification of multimedia interactive scenarios with interactive choices, i.e., scenarios where the performer or thesystem can take decisions about their execution state with a certain degree of freedom defined bythe composer.In our first approach, we define a novel programming language called REACTIVEIS. This language extends the full capacity of temporal organization of interactive scenarios by allowing the composerto use a defined logical system for the specification of the starting and stopping conditions of temporal objects (TOs). REACTIVEIS programs are formally defined as tree-like structures representing the hierarchical aspect of interactive scenarios and whose nodes contain the conditions needed to startand stop the TOs. Moreover, we define an operational semantics based on labeled trees, containing in their nodes, the information about the start and stop times of each TO.We show that this operational semantics offers an intuitive yet precise description of the behavior of interactive scenarios.We also endowed REACTIVEIS with a declarative interpretation as formulas in Intuitionistic LinearLogic with Subexponentials (SELL). We shall show that such interpretation is adequate: derivations in the logic correspond to traces of the program and vice-versa. Hence, we can use all the meta-theory of Intuitionistic Linear Logic (ILL) to reason about interactive scenarios and develop tools for theverification and analysis of interactive scenarios.In our second approach, we present a Timed Automata (TA) based framework. In the proposed framework, we model interactive scenarios as a network of timed automata and extend them with interactive points (IPs) guarded by conditions, thus allowing for the specification of branching behaviors.Moreover, we take advantage of the mature and efficient tools for TA to simulate and automatically verify scenarios. In our framework, scenarios can be synthesized into a reconfigurable hardware in order to provide a low-latency and real-time execution by taking advantage of the physical parallelism,low-latency, and high-reliability of these devices. Furthermore, we implemented a tool to systematically construct bottom-up TA models from the composition environment of I-SCORE. Doing that, we provide a friendly and specialized environment for composing and automatic verification of interactive scenarios. Finally, we present an extension of interactive scenarios using Colored Petri Nets (CPNs) thataims to handle complex data, in particular, dynamic and static data audio streams. [...]

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.

No description available.

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.

In this thesis I study several deductive systems for linear logic, its fragments, and some noncommutative extensions. All systems will be designed within the calculus of structures, which is a proof theoretical formalism for specifying logical systems, in the tradition of Hilbert's formalism, natural deduction, and the sequent calculus. Systems in the calculus of structures are based on two simple principles: deep inference and top-down symmetry. Together they have remarkable consequences for the properties of the logical systems. For example, for linear logic it is possible to design a deductive system, in which all rules are local. In particular, the contraction rule is reduced to an atomic version, and there is no global promotion rule. I will also show an extension of multiplicative exponential linear logic by a noncommutative, self-dual connective which is not representable in the sequent calculus. All systems enjoy the cut elimination property. Moreover, this can be proved independently from the sequent calculus via techniques that are based on the new top-down symmetry. Furthermore, for all systems, I will present several decomposition theorems which constitute a new type of normal form for derivations.