A semantic study of higher-order model-checking

Charles Grellois
LIS, LIRICA team, Aix-Marseille Université

Date(s) : 19/02/2015   iCal
11 h 00 min - 12 h 00 min

Using higher-order recusion schemes, one can model the computation flow of functional programs, and produce trees abstracting their set of executions. The higher-order model-checking problem is concerned with the verification of a logical property — typically expressed in monadic second-order logic — over this tree. A key feature of this logic being that it allows to express finitary as well as infinitary properties.
Ong proved the decidability of this problem in 2006 using game semantics. Since then, other semantic approaches lead to alternate proofs, each of them bringing a new semantic insight to the problem. One of them, by Kobayashi and Ong, made use of intersection types.
In this talk, I will explain how Paul-André Melliès and I could obtain a new proof of this result at the light of linear logic and of its semantics. It notably relies on a connection between intersection types and the exponential modality and its interpretation in models of linear logic, but also on an extension of the latter to the infinitary framework required by this higher-order model-checking problem.


Retour en haut 

Secured By miniOrange