Invited Paper: Self-Adjusting Computation (at LICS 2004)

Authors: Robert Harper

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.

BibTeX

  @InProceedings{Harper-SelfAdjustingComput,
    author = 	 {Robert Harper},
    title = 	 {Self-Adjusting Computation},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004)},
    year =	 {2004},
    month =	 {July}, 
    pages =      {254--255},
    location =   {Turku, Finland}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}
  }