| Scientific Question:
| How can programming language concepts
| lead to algorithmic results?
Scientific Approach: | Proven Results Published in 1995:
|
1. Type/subtype system abstracts |1.Theta(mn + n**2) time Ready Simulation
sequential RAM model of computation,|algorithm; improves Omega(mn**6) solution
and makes a high level set theoretic|2. Two new space/time improved algorithms
language computationally transparent|for DFA minimization
|3. Over a dozen algorithms that solve
2. Language abstraction captures |Programming Language Problems improved
complexity and replaces counting |from Omega(f) hash operations to O(f) in
arguments by a more syntactic and |the worst case
algebraic worst case and amortized |
algorithmic analysis |(New and Unpublished)
|
|4. Linear expected time fragment of
|Willard's RCS Database Query Language
|improved to linear worst case time
Click here to see vugraphs of ONR funded achievement.