On Interaction, Efficiency, and Reversibility
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 JanDisplayed time zone: London change
09:00 - 10:30 | |||
09:00 45mKeynote | On Interaction, Efficiency, and Reversibility GALOP Ugo Dal Lago University of Bologna & INRIA Sophia Antipolis | ||
09:45 22mTalk | 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 22mTalk | 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 |