POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom
Sun 14 Jan 2024 09:00 - 09:45 at Lovelace Room - Session 1 Chair(s): Pierre Clairambault

We give an overview of some results we obtained in the last three years about the so-called Interaction Abstract Machine (IAM in the following) and its efficiency in time and space. More specifically, we are interested in checking whether any invariance result in the style of Slot and van Emde Boas is possible for the IAM. Unfortunately, the answer is going to be negative. Still, while the time inefficiency of the IAM is expected, its space inefficiency could be seen as surprising, given, e.g., the well-known results of Schöpp and coauthors on the characterization of logarithmic space computable functions through a construction very closely related to the IAM. We conclude the talk by giving some observations about the IAM’s reversibility properties, which can be seen as partially justifying the results above.

Sun 14 Jan

Displayed time zone: London change

09:00 - 10:30
Session 1GALOP at Lovelace Room
Chair(s): Pierre Clairambault CNRS & LIS, Aix-Marseille Université
09:00
45m
Keynote
On Interaction, Efficiency, and Reversibility
GALOP
Ugo Dal Lago University of Bologna & INRIA Sophia Antipolis
09:45
22m
Talk
Normal Form Bisimulations by Value
GALOP
Beniamino Accattoli Inria & Ecole Polytechnique, Adrienne Lancelot Inria, LIX Ecole Polytechnique, IRIF Université Paris Cité, Claudia Faggian Université de Paris & CNRS
10:08
22m
Talk
Fully Abstract Normal Form Bisimulation for Call-by-Value PCF
GALOP
Nikos Tzevelekos Queen Mary University of London, Vasileios Koutavas Trinity College Dublin, Yu-Yang Lin Queen Mary University of London