TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 9418

Incremental Computation and Dynamic Algorithms

( 02. May – 06. May, 1994 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/9418

Organisatoren
  • J. van Leeuwen
  • K. Mehlhorn
  • T. Reps



Summary

The purpose of the Seminar was to bring two research communities together that have common interests, but that (to date) have had relatively limited contact:

  1. theoretical computer scientists who work in the area of "dynamic algorithms" and
  2. programming language/ systems researchers who work in the area of "incremental computing".

The goal of the Seminar was to stimulate an intellectual cross-fertilization between the two groups. For example, theoreticians were exposed to the concerns that arise when making use of incremental processing in practical systems; the systems people were exposed to new algorithms and analysis techniques developed by theoreticians.

For both groups, an important goal is to find efficient algorithms that make use of the solution to one problem instance to find the solution to a "nearby" problem instance. In the dynamic algorithms community, several avenues of approach have been followed:

  1. the design of dynamic combinatorial algorithms ('update algorithms' especially in the context of network problems),
  2. on-line algorithms and competitive analysis,
  3. parametric algorithms and sisitivity analysis, and
  4. the design of on-the-fly, adaptive, and self-stabilizing algorithms in the context of distributed computing

From the programming languages/ systems perspective, the motivations for work on incremental computation and dynamic algorithms include concerns such as:

  1. ecient techniques for dealing with "incremental changes" in order to speed up the response times of interactive systems,
  2. the creation of languages and systems that provide support for incremental computation, and
  3. the design of environments involving cooperating tools. (In such environments, it is paramount that the tools communicate information about changes to each other, which raises the possibility for the processing of changes by individual tools to be performed incrementally.)

The Seminar provided the opportunity to present the state-of-the-art in the relevant fields at a high level and to let the two research communities benefit from each other's insights. We are grateful to all participants of the Seminar for engaging in the endeavor with us and for making the meeting so successful. We thank Han La Poutré for organisational assistance. We hope that through the Seminar lasting bonds have been created between the two fields.


Teilnehmer
  • J. van Leeuwen
  • K. Mehlhorn
  • T. Reps