Abstract
How efficient can a persistent data structure be? Does it necessarily cost more than a transient structure ? The final lecture will attempt to answer these questions, first by reviewing the best known implementations of persistent arrays, purely functional or not, and then by studying the lower bounds on the efficiency of the computational models " pure LISP " and " impure LISP " established by Ben-Amram , Galil, and Pippenger.