Comment jouer la logique linéaire?

pages

Français

Documents

Écrit par
André Hirschowitz Michel Hirschowitz Tom Hirschowitz

Publié par
Vewyer

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

Français

Ebook

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Vewyer

Nombre de lectures

Langue

Français

Comment jouer la
logique lineaire?
Hirschowitz
Introduction
Les positions
Comment jouer la logique lineaire?
Les coups
Les parties
Les strategies
1Andre HirschowitzLes exponentielles
2MichelwitzConclusions
3Tom Hirschowitz
1 2 3CNRS, UNS CEA - LIST CNRS, Universite de Savoie
Paris
1/12/2008Comment jouer la
logique lineaire? Le probleme
Hirschowitz
Introduction
Les positions
Les coups
Les parties
Les strategies Trouver une de nition de la verite independante des preuves
Les exponentielles
via les jeux (de la semantique) en esperant l’eliminationConclusions
des coupures et la consistance gratuites ...
en logique lineaire en esperant un tiers-exclu gratuit...Comment jouer la
logique lineaire? Les niveaux
Hirschowitz
Introduction
Les positions
Les coups
Les parties
Les strategies
1 pour MALL
Les exponentielles
2 + exponentiellesConclusions
3 + quanti cateurs du premier ordre
4 + choix? + tiers-exclu?Comment jouer la
logique lineaire? Travaux connexes
Hirschowitz
Introduction
Les positions
Les coups
Modeles de la logique lineaire
Les parties
Les strategies Abramsky-Jagadeesan-Malacaria, Hyland-Ong, Nickau.
Les exponentielles
Abramsky-Mellies, Mellies.
Conclusions
Girard.
Delande-Miller.
Mellies-Mimram.
L’incontournable standard: "Full completeness".Comment jouer la
logique lineaire? Les resultats
Hirschowitz
Introduction
Les positions
Un jeu graphique (ou topologique, les positions sont des
Les coups
graphes etiquetes),
Les parties
avec un coup Cut (et Mix si on veut) ...

Voir

Publié par

Vewyer

Nombre de lectures

Langue

Français

Commentjouerlalgoqieuil´naeri?ersHiowchzIitronttcudLnoiopseitisescoonsLespaupsLLssetrei´tgetsarexessLieientnepocnoCsellsnoisul

2CEA - LIST3srevinU,SRNCievoSade´eit

Paris 1/12/2008

Commentjouerlalogiqueline´aire?

1CNRS, UNS

Andre´Hirschowitz1 Michel Hirschowitz2 Tom Hirschowitz3

Le probleme `

vialesjeux(delase´mantique)e´rantl’´elimination n espe des coupures et la consistance gratuites ... enlogiquelin´eaireenesp´erantuntiers-exclugratuit...

Trouveruned´eﬁnitiondela´tee´irvedsespraenutvependnd´ei

igolalree´nileuqCooutjenmmdocunIrteLpsitno?HirairewitzschoLeestrssspLetiarcseLspuotisosnoisConclusentielleeLespxnotae´igsesnoi

omCortntcudwohcIztitisisLonnLiopoeslrlagoqiemtnojeuire?Hirsuelin´eaulisoCcnnosponeesexllesntieartsseLsLseige´tsLupcoesiertpaes

1 2 3

pour MALL + exponentielles + quantiﬁcateurs du premier ordre

+ choix? + tiers-exclu?

niveaux

Les

scoupsLestionsLessetsar´taptreiLspoexntneieegessLulcnnoislleioCse

Mode`lesdelalogiquelin´eaire

Abramsky-Jagadeesan-Malacaria, Hyland-Ong, Nickau. Abramsky-Mellie`s,Melli`es. Girard. Delande-Miller. Mellies-Mimram.

Travaux connexes

L’incontournable standard: ”Full completeness”.

nLesposiroductiowotiIztn?eiHsrhcn´liireaogalueiqojtnlreuCemmo

dortnIztiwohcsri?Hreai´einelqugipsraspeLcsuosneLitiosposonLeuctiuorealoloCmmnejtLeesxpseenoneltiseitsseLtartige´elCsnolcsuoisn

Mode`leincomplet!

Les resultats ´

Un jeugraphique(outopologique, les positions sont des graphes´etiquet´es), avec un coupCut(etMixsi on veut). Lesstrat´egiesgagnantesconstituentunmod`elecorrect etcoh´erent, Avece´liminationdescoupurespourlefragmentMALL. Lescoupssontdesmorphismesdansunecate´gorieG. L’´eliminationdescoupuresde´couled’unsyst`emede factorisation dans G.

mais aujourd’hui Priorite´auxexponentielles

Sans toucher au jeu. Enchangeantlanotiondestrate´gie Pourunenotiondestrate´giepluslocale(innocente?)

(Onpeutrecouvrerlavainecomple´tude)

hcwotiIzri?eiHsruelin´earlalogiqtnemeuojmoCsoneitnsellcnoCisuliesLt´egponeesextreiseaptsarLssesLontisisLupcoestcudortnopseLnoi

CommeHie?chrsn´liireagolaeuqiojtnlreusLestionposinLestcoiorudIztnwotiessLieegt´rastesLseitrapseLspuoc

Conclusions

poexntnellieCoesulcnnoiss

Les parties

Les positions

Les exponentielles

Lesstrate´gies

Les coups

Introduction

⊥⊥=A.

A,B,C, . . .∈ F::=1|A⊗B|A⊕B|0 | ⊥ |A`B|A&B| >.

Onaladualite´deDeMorgan(verticale):A

Ce sont les formules de MALL avec constantes et sans atomes

Les formules

oisulcnosnenonxpsesCleeltirttaeLssseeLe´igpsLescoutiessparCommuqigolalreuojtnescir?Hreai´einelcuitrtdoztnIohiwnsLeitiosposonLe

•

Il faut identiﬁer

•

⊥

avec

Aus´equent`A1, . . . ,Anpqounetd´lee:grapchoer´reetsi A1• • . An•

Les sequents sont des graphes ´

pxnoeLesigsetae´clussConelleentispuocseLsnoitisotrssLeestiarspLesnoiaire?HirschowitznIrtdocuitnoeLpsCoenmmoutjalreigolleuqe´ni

ionLductsitiespohcwoiHsrtnortiIzessLiertegt´rastocseLsnoapseLspuiqogliueean´e?irmoCtnemeuojlalr

devient

Γ.•.Δ

•

.Δ

•

Γ.

Lar`egle:

Γ`A A`Δ Γ`Δ

Notre coupcut:

La coupure

nepoientsLieexesisulsnosellcnoC

Les hypersequents ´

Chaque coup cut ou⊗uedn.xuqe´etnesscanseu D’o`udesconﬁgurationsdes´equentsappele´essntuehqe´srepy; unhypers´equent,c’est ungraphedirig´e,acyclique de´core´pardesformules.