47 citations · 105 across the 13 of their papers we have counts for
3 papers · 1 filter
An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus
Patrick Baillot, Marco Pedicini
This paper brings together two lines of research: implicit characterization of complexity classes by Linear Logic (LL) on the one hand, and computation over an arbitrary ring in th…
On Quasi-Interpretations, Blind Abstractions and Implicit Complexity
Patrick Baillot, Ugo Dal Lago, Jean-Yves Moyen
Quasi-interpretations are a technique to guarantee complexity bounds on first-order functional programs: with termination orderings they give in particular a sufficient condition f…
Verification of Ptime reducibility for system F terms via Dual Light Affine Logic
Vincent Atassi, Patrick Baillot, Kazushige Terui
In a previous work we introduced Dual Light Affine Logic (DLAL) ([BaillotTerui04]) as a variant of Light Linear Logic suitable for guaranteeing complexity properties on lambda-calc…