| Scientific Question:
| How can qualitative methods in
| programming languages solve quantitative
| problems in algorithms and complexity?
Scientific Approach: | Proven Results Published in 1996: 1. Types facilitate algorithm |1. O(n+m+logn) time O(n) space algorithm design by modeling complex data |to solve DFA minimization, where n and m structures. |are the number of DFA states and 2. Rule Induction used in algorithm |transitions respectively. Design and Analysis. |2. O(r) time O(s) space algorithm to turn 3. Program well typedness is used |regular expressions with r symbols and to guarantee speedup from expected |s alphabet symbols into compressed NFA's. to worst case time |3. Runtime of complete linear time 4. Formal Semantic Specification of |fragment of Willard's RCS query language type-directed high level batch |improved from linear expected to linear read method is used to develop |worst case time on a pointer RAM. an efficient read algorithm that |4. Linear time algorithm to convert unifies input complexity with |input in string form into efficient algorithmic complexity on a pointer |data structures for a variable list with RAM. |any signature from our type system.
Click here to see vugraphs of ONR funded achievement.