[Prev][Next][Index][Thread]

Report on the DIMACS Workshop on Comp. Complexity & Prog. Languages


A report on the 

   DIMACS Workshop on Computational Complexity and Programming Languages 

is available through: 

   http://dimacs.rutgers.edu/Workshops/Programming/index.html

The workshop, which took place 25-26 July 1996, had the goal of
bringing together researchers in computational complexity and in
programming languages to discuss common problems and the interplay
between the two areas.  The report consists of a brief overview of
the workshop and abstracts of all of the talks.  The talks were the
following.


INVITED TALKS

 * Computability and complexity from a programming perspective,
   Neil D. Jones, DIKU, University of Copenhagen 

 * Semantically-based cost-models and provably efficient
   implementations, 
   Guy Blelloch, School of Computer Science, Carnegie Mellon University  

 * Lazy functional programming languages and persistent amortized
   data structures, 
   Chris Okasaki, School of Computer Science, Carnegie Mellon University  

 * Complexity and optimal reduction, 
   Harry Mairson, Department of Computer Science, Brandeis University 

 * Polynomial time type-2 computation, 
   Bruce M. Kapron, Department of Computer Science,  University of
   Victoria  

 * Feasibility in higher types, 
   Daniel Leivant, Computer Science Department, Indiana University  

 * Berry and Curien's intensional legacy, 
   Denis Dancanet, School of Computer Science, Carnegie Mellon University 

 * Intensional semantics, abstract interpretation and complexity
   estimates, 
   Eugenio Moggi,  Dipartimento di Informatica, University of Genova  

 * Intensional semantics and complexity, 
   Samson Abramsky, Department of Computer Science, Edinburgh University 

CONTRIBUTED TALKS 

 * A feasible type-3 functional that fails to be basic feasible,
   James S. Royer, School of Computer and Information Science,
   Syracuse University  

 * Computational models based on explicit substitution with an
   address oracle using parallel reduction, 
   Kristoffer H. Rose, BRICS, University of Aarhus  
  
 * Characterizing computation models with a constant factor time
   hierarchy, 
   Eva Rose, DIKU, University of Copenhagen 

 * A category-theoretic proof that PV_\omega = PTIME, 
   Martin Hofmann, Fachbereich Mathematik, Technische Hochschule Darmstadt 

 * Half tiers and linear space (and time), 
   James Otto 

 * Explicit process locations and functional parallel programming,
   Gaetan Hains, LIFO, Universite d'Orleans