FULLY PERSISTENT LISTS WITH CATENATION

This paper considers the problem of representing stacks with catenatio n so that any stack, old or new, is available for access or update ope rations. This problem arises in the implementation of list-based and f unctional programming languages. A solution is proposed requiring cons tant time and space for each stack operation except catenation, which requires O(log log k) time and space. Here k is the number of stack op erations done before the catenation. All the resource bounds are amort ized over the sequence of operations.