Hi Ali:

Here are some thoughts.

-- Karl

Develop a complexity theory for adaptive software, both for upper
and lower bounds.
The Longpr{\'e} Conjecture is relevant in this context:
For a ``natural'' adaptive algorithm, the time complexities
of the algorithms obtained by instantiating the adaptive algorithm
on compatible data structures, are of the same order of magnitude.

What are sufficient conditions for the ``natural''
property used above? Prove the conjecture or give a counterexample.
Can the upper-bound analysis be done for a ``minimal'' compatible
data structure and then be generalized to all other data structures,
using Longpr{\'e}'s Conjecture?

--------
Since the conjecture was formulated, the following results have been 
obtained:

- more general model for AP, might be easier to analyze
- journal paper by Jens Palsberg on type inference of class graphs

----------

Of practical interest is the question how to optimize an adaptive program
by selecting a suitable class graph. This question becomes more interesting
if the implementation of the class graph involves computation,
i.e., if not each get method is O(1). Each such computation could
itself be implemented adaptively.

The optimization problem of interest is as follows:
Given an adaptive program with a class graph G and
complexity T(n), find a class graph G' where each edge e
has a complexity function c(e) so that for G' the
complexity T'(n) <= T(n) for sufficiently large n.

Example:

Find B-object with name n:
from A to B
  find B such that B.n = n1
Requires that basic operations, such as Find, Insert,
Delete, are written at a high level
of abstraction. Is missing in current Demeter/Java.

A = List(B).
B = <n> Ident.

A = HashTable(B).
B = <n> Ident.