Interaction Graphs: Exponentials
In two previous papers [Sei12b, Sei12a], we exposed a combinatorial approach to the program of Geometry of Interaction, a program initiated by Jean-Yves Girard [Gir89b]. The strength of our approach lies in the fact that we interpret proofs by simpler structures — graphs — than Girard’s constructions, while generalizing the latter since they can be recovered as special cases of our setting. This third paper tackles the complex issue of defining exponential connectives in this framework. In order to succeed in this, we consider a generalization of graphs named graphings, which is in some way a geometric realization of a graph. We explain how we can then define a GoI for Elementary Linear Logic (ELL), a sub-system of linear logic where representable functions are exactly the functions computable in elementary time. This construction is moreover parametrized by the choice of a map, giving rise to a whole family of models.