The Workshop in Implicit Computational Complexity

in Programming Language Design and Methodology

Program

September 26, 1998

Welcome

9:00 - 9:10

Proof Theory and Functional Programming

9:10-9:50Bellantoni Abstract
Using Recent Results in Functional Programming to Define a New Feasible Arithmetic

9:55-10:30Leivant Abstract
Ramified Intrinsic Theories: A Proof Theoretic Framework for Computational Complexity

First Order Ramification

10:45-11:15 Marion Abstract
Rewriting System and Computational Complexity

11:20 - 11:40 CaporasoAbstract (PostScript file)
Predicativity, Complexity and the Classification Problem

Higher Order Ramification

11:45 -12:05PezzoliAbstract
On the Computational Complexity of Type Two Functionals

Lunch


Extensions

1:45 - 2:25JonesAbstract
Some Complexity Results Interesting from a Programming Viewpoint

2:35-3:05 Clote Abstract (PostScript file)
Some Reflections on a Boolean Circuit Generation Language, and on an Application in Computational Biology

Higher Order Ramification

3:25-3:55Hofmann Abstract
Linear Types and Non-Size-Increasing Polynomial Time Computation

4:00- 4:30NigglAbstract
Characterising Polytime Through Higher Type Recursion

4:40-5:10 Royer Abstract
Type-Theoretic Characterizations of the Basic Feasible Functionals

Implementation

5:20-6:00 Constable/Benzinger Abstract
Automated Reasoning about Computational Complexity

Joan Lockwood, Department of Computer Science, Cornell University, Ithaca, NY. Mail to: joan@cs.cornell.edu