Relational type-checking of connected proof-structures

International audienceIt is possible to define a typing system for Multiplicative Exponential Linear Logic (MELL): in such a system, typing judgments are of the form ⊢ R : x : Γ, where R is a MELL proof-structure, Γ is the list of types of the conclusions of R, and x an element of the relational interpretation of Γ, meaning that x is an element of the relational interpretation of R (of type Γ).As relational semantics can be used to infer execution properties of the proof-structure, these judgment can be considered as forms of quantitative typing.We provide an abstract machine that decides, if R satisfies a geometric condition, whether the judgment ⊢ R : x : Γ is valid. Also, the machine halts in bilinear time in the sizes of R and x