Affordable Access

Quantitative Game Semantics for Linear Logic

Authors
  • Dal Lago, Ugo
  • Laurent, Olivier
Publication Date
Sep 15, 2008
Source
Hal-Diderot
Keywords
Language
English
License
Unknown
External links

Abstract

We present a game-based semantic framework into which the time complexity of any MELL proof can be read out of its interpretation. This gives a compositional view of the geometry of interaction framework introduced by the first author. In our model the time measure is given by means of slots, as introduced by Ghica in a recent paper. The cost associated to a strategy is polynomially related to the normalization time of the interpreted proof, in the style of a complexity-theoretical full abstraction result.

Report this publication

Statistics

Seen <100 times