[TYPES] CFP: Workshop on Implicit Computational Complexity (Geocal'06)

Patrick Baillot patrick.baillot at lipn.univ-paris13.fr
Fri Oct 7 03:42:23 EDT 2005

          -------    Call for participation      ---------

                          Workshop on
          Implicit Computational Complexity
                  as part of  GEOCAL'06


        Marseille, France, february 13th to 17th 2006.


   Implicit Computational Complexity (ICC) has emerged from various propositions
 to use logic and formal methods like types, rewriting systems... to provide
languages for complexity-bounded computation, in particular for polynomial time
   It aims at studying the computational complexity of programs without refering
to a particular machine model and explicit bounds on time or memory, but instead
by relying on  logical or computational principles that entail complexity
properties. Several approaches have been explored for that purpose, like linear
logic, restrictions on primitive recursion, rewriting systems, types and
lambda-calculus... They often rely on the functional programming paradigm.
    Two objectives of ICC are:
- on the one hand to find natural implicit logical characterizations of
functions of various complexity classes,
- on the other hand to design systems suitable for static verification of
programs complexity.
In particular the latter goal requires characterizations  which are general
enough to include commonly used algorithms.

   This meeting will be preceded by a course on "Complexity and Logic" (6->10/2)
 organized as part of the GEOCAL'06 winter school and especially targeted at PhD
students, with lectures by P.Baillot, M.Hofmann and J.-Y. Marion. Some
(limited) funding is possible for students attending the school and/or the

 The  workshop is intended to be a forum for researchers interested in
ICC to discuss recent developments and open issues. It will be open to
contributions on various aspects of ICC including (but not exclusively):
- logical systems for implicit computational complexity,
- linear logic,
- semantics of complexity-bounded computation,
- rewriting and termination orderings,
- types for controlling complexity,
- extensions from functional approach to ICC to imperative or concurrent
setting; applications to automated verification...

 Propositions of contributions consist in a title and a short abstract (see the
web page for preregistration).
After the workshop a call-for-paper for a special issue of a journal might be
considered (either for the GEOCAL'06 session, or for the workshop itself), with
standard refering procedure.

* Invited Speakers :

- Martin Hofmann, LMU Munich.
- Kazushige Terui, NII Tokyo.

 others TBA.

* About the Geometry of Computation session (GEOCAL'06):

This session intends to gather researchers interested in various topics of
theoretical computer science. It will consist of a series of events: 4 winter
school lectures during the first 2 weeks followed by 9 thematic workshops. A
detailed description including a provisional programme and the preregistration
form are available on the Geocal06 home page.

* Important dates:
-  10/30/2005:          deadline for preregistration and abstract subsmissions,
-  2/6/2006-> 2/10/2006: lecture on Logic and Complexity, Geocal'06 Winter
- 2/13/2006-> 2/17/2006: workshop.

* Organizers:
 Patrick Baillot, Univ. Paris 13/CNRS, patrick.baillot at lipn.univ-paris13.fr
 Jean-Yves Marion, LORIA Nancy,        jean-yves.marion at loria.fr


More information about the Types-list mailing list