Affordable Access

Quantitative Game Semantics for Linear Logic

Authors
Publication Date
Source
Hal-Diderot
Keywords
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.

Statistics

Seen <100 times