Background:
The theory of programming languages is one of the most technically sophisticated theoretical areas in computing, and, for all its abstractness, it has been reasonably successful in having its insights applied in practice. Most successes in programming language theory have been in studying the input/output behavior of programs, procedures, etc. The successes in studying other aspects of the behavior of programs (e.g., their time and space complexity) have been extremely limited-especially in regard to more advanced programming constructs. For example, while ML is a wonderful language in which to state algorithms, there is no adequate theoretical support for the complexity analysis of ML programs and modules. This is in part due to the fact that ML includes features such as higher-type procedures for which there is only a rudimentary theory of their computational complexity. For another example, program specifications can be very detailed and formal when it comes to laying out requirements for module interfaces and such, but in the matter of stating performance specifications (e.g., time complexity requirements) one has to resort to loose informal narratives. This is weak engineering, but it is the result of weak scientific support -- there is currently no precise way to talk about the computational complexity of a module or an ``object.''
There has been scattered work in the past few years in extending the theories of programming languages and computational complexity to deal with these problems. However, there is little synergy between the various pockets of researchers working on these problems. The groups come from very different communities, speak different technical languages, and have quite different perspectives on the core phenomena.
Workshop Goals:
The aim of the workshop is to bring together researchers in computational complexity and in programming languages to start a discussion between the various parties, explain each other's concerns to one another, define problem areas, and possibly start some collaborations.
The planned format consists of a series of invited talks on the 25th on a broad range of topics, concluding in the afternoon with a pannel discussion. The morning of the 26th will be general discussion of problem areas, general goals, and particular problems of interest. In addition we hope to schedule an evening rump session on the 25th for participants to report on technical results.
Next: Call for Participation
Workshop Index
DIMACS Homepage