Symmetric dialogue games in the proof theory of linear logic - Archive ouverte HAL Access content directly
Theses Year : 2009

Symmetric dialogue games in the proof theory of linear logic

Olivier Delande
  • Function : Author

Abstract

This thesis develops an original approach to the interactive interpretation of the proof theory of linear logic. In contrast with the player/opponent dichotomy commonly associated with game semantics for logic, we propose a model in which the two players have symmetric roles. More precisely, we shift from a situation in which a player aims at proving a goal while the other one aims at refuting it to a situation in which the players aim at proving opposite goals. In the tradition of computation-as-proof-search, each step of the interaction is seen as a step in two orthogonal sequent calculus proof searches. To some extent, this work contributes to formalising the connections between proof search and proof normalisation. We first present a simple symmetric game for the additive fragment of linear logic, as a first introduction to dual proof search. We then introduce a much more involved symmetric game accounting for the multiplicative and additive fragment of linear logic. In order to get a full completeness result, we then develop a third, highly concurrent, symmetric game. Finally, we investigate a few extensions of our model.
Cette thèse développe une approche originale de l'interprétation interactive de la théorie de la démonstration en logique linéaire. À l'inverse du cadre joueur/opposant communément associé aux sémantiques des jeux pour la logique, nous proposons un modèle dans lequel les deux joueurs ont des rôles symétriques. Plus précisément, nous passons d'une situation dans laquelle un joueur tente de démontrer un énoncé tandis que l'autre tente de le réfuter à une situation dans laquelle les deux joueurs tentent de démontrer des énoncés contraires. Dans la tradition du calcul vu comme comme recherche de démonstrations, chaque étape de l'interaction est vue comme une étape de deux recherches de démonstrations orthogonales en calcul des séquents. Ce travail contribue dans une certaine mesure à formaliser les liens entre la recherche de démonstrations et la normalisation de démonstrations. Nous présentons d'abord un jeu symétrique simple pour le fragment additif de la logique linéaire, en guise d'introduction à la recherche duale de démonstrations. Nous passons ensuite à un jeu symétrique bien plus complexe pour le fragment additif et multiplicatif de la logique linéaire. Afin d'obtenir un résultat de pleine complétude, nous développons ensuite un troisième jeu à la fois symétrique et concurrent. Enfin, nous étudions quelques extensions de notre modèle.
Fichier principal
Vignette du fichier
These_Olivier_Delande.pdf (773.18 Ko) Télécharger le fichier

Dates and versions

pastel-00006196 , version 1 (30-06-2010)

Identifiers

  • HAL Id : pastel-00006196 , version 1

Cite

Olivier Delande. Symmetric dialogue games in the proof theory of linear logic. Computer Science [cs]. Ecole Polytechnique X, 2009. English. ⟨NNT : ⟩. ⟨pastel-00006196⟩
294 View
206 Download

Share

Gmail Facebook Twitter LinkedIn More