Self-adjusting computation

Author

Harper, Robert

Author_Institution

Dept. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA

fYear

2004

fDate

13-17 July 2004

Firstpage

254

Lastpage

255

Abstract

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.

Keywords

algorithm theory; adaptive memoization; dynamic sorting algorithm; fixed input; incremental algorithm; ordering relation; selective memoization; self-adaptive computation; self-adjusting computation; static sorting algorithm; Adaptive control; Computer science; Data structures; Heuristic algorithms; Kinetic theory; Logic; Programmable control; Sorting;

fLanguage

English

Publisher

ieee

Conference_Titel

Logic in Computer Science, 2004. Proceedings of the 19th Annual IEEE Symposium on

ISSN

1043-6871

Print_ISBN

0-7695-2192-4

Type

conf

DOI

10.1109/LICS.2004.1319619

Filename

1319619