Self-adjusting computation
Robert W. Harper · Logic in Computer Science · 2004
A static algorithm is one that computes the result of a query about the output for a single, fixed input. For example, a static sorting algorithm is one that takes as input a set of keys, and permits queries about the relative order of these keys according to some ordering relation. A dynamic, or incremental, algorithm is one that permits queries about the output to be interleaved with operations that incrementally modify the input. For example, a dynamic sorting algorithm is one that would permit insertion or deletion of keys to be interleaved with queries about their relative ordering. It is often easier to find a static algorithm than a dynamic algorithm for a given problem. There is a large and growing literature on dynamic algorithms for a broad range of problems. Self-adjusting computation is a method for deriving a dynamic algorithm for a problem by dynamizing a static algorithm for it. We have studied three main techniques for dynamization: 1. adaptivity 2. selective memoization 3. adaptive memoization.