An overview of lambda-calculus optimal reductions and of their implementation

We want to focus on the main ideas behind lambda-calculus optimal reductions and sharing graph reductions. For the amount and the complexity of the results that we want to analyze, there will be no time for a lot of details. The main aim is at justifying why optimal reductions and sharing graphs are milestones in the quest for understanding the computational complexity of beta-reduction, and in which sense Asperti-Mairson result on the relations between families and actual reduction complexity in the typed lambda-calculus opens new and interesting problems in the field.

LS Home page or Talks in 1998/99