Programs: Improvements, Complexity, and Meanings

Dagstuhl Seminar on
Programs: Improvements, Complexity, and Meanings

Schloß Dagstuhl
Wadern, Germany, June 8-12, 1998.


Topic: The interface between Programming Languages and Complexity Theory.

Much interest has been shown in recent results relating speed of imperative LISP to pure LISP (Pippenger), "pointers versus addresses" (Ben-Amram and Galil), and a proof that "constant time factors do matter" (Jones), but the field is far from well-developed. This workshop will bring together three communities:
Our goal is fruitful interactions, leading to formulation and perhaps solving new questions that are both of theoretical interest and of practical relevance.

A model question: Are functional or logic programs necessarily less efficient than equivalent imperative programs? Such questions need to be made more precise in order to be answered; and solution can be tricky indeed.

A model answer by Nick Pippenger (POPL 1996): "Pure LISP" is provably less efficient, by a logarithic time factor, than "impure LISP" with list-modifying assignments, when applied to solve a problem involving a series of online permutations.

Some relevant topics:
Emphases, nature of the meeting:

Participants should be open to bridge-building, and are encouraged to bring draft papers for discussion (a preliminary proceedings will be printed). It will not be one long conference with hours of lecture-style presentations. Rather, there will be a mixture of session types, perhaps including

Meeting plan, titles and abstracts: (evolving)
The organizers:
Related workshops by the organizers:

Bibliography (under construction!) of books and papers relevant to the workshop.




To the Dagstuhl Homepage