[TYPES/announce] Workshop on ICC

Pierre Boudes pierre.boudes at lipn.univ-paris13.fr
Thu Nov 15 11:47:09 EST 2007


Call for participation and talk proposals


           *************************************************
           * Workshop on Implicit Computational Complexity *
           * --------------------------------------------- *
           *              February 11-12, 2008             *
           *              Villetaneuse (Paris)             *
           *  http://lipn.fr/~mogbil/workshopNOCOST.html   *
           *                                               *
           * LIPN, Université Paris 13 & CNRS              *
           * Workshop supported by the ANR project NOCoST  *
           *************************************************


**Important Dates**
Talk proposals:           December 21, 2007
Registration (no fees):   January 21, 2008


**Invited Speakers**
* Simona Ronchi Della Rocca, Università di Torino
* others TBA

**Implicit Computational Complexity**
Implicit  Computational  Complexity  (ICC)  has emerged  from  various
propositions  to use logic  and formal  methods like  types, rewriting
systems,     interpretations...     to    provide     languages    for
complexity-bounded  computation,  in  particular for  polynomial  time
computing.

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 programming  or logical disciplines
that  imply  complexity  properties.   Several  approaches  have  been
explored for  that purpose, like restrictions  on primitive recursion,
lambda  calculus, types,  linear logic,  rewriting systems  ....  They
originally mostly  came from the functional  programming paradigm, but
imperative programming is now also addressed.

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  criteria  usable  for  the  static
verification of  programs complexity.   In particular the  latter goal
requires  characterizations  which  are  flexible enough  to  validate
commonly used algorithms.

**Purpose and scope of the meeting**
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):
* characterizations of various complexity classes,
* logical systems for ICC,
* semantic and interpretation-based methods for complexity,
* types for controlling complexity,
* linear logic,
* semantics of complexity-bounded computation,
* function algebras, subrecursion.

**Location and access**
The  workshop will take  place on  the campus  of Villetaneuse  of the
University of Paris  13, in the north suburd of  Paris (approx. 25 min
for Gare du Nord see http://lipn.fr/planfac/?lang=uk ).


**Previous related meetings**

* ICC Workshop, Marseille, February 2006
http://lipn.fr/~baillot/GEOCAL06/ICCworkshop.html

* ICC and Logic meeting, Villetaneuse, September 2004
http://lipn.fr/~baillot/workshopGEOCAL/complexite.html

**Registration  (no fees)**
http://lipn.fr/~mogbil/workshopNOCOST.html
Inline  registration will  open very  soon. Lunches  on the  campus of
Villetaneuse are included at no fees. If you have any trouble with the
web form simply drop us an email.

**Talk proposal**

If you intend  to give a talk, just send us  by email the informations
at the end of this message  December 21. We will notify the acceptance
and communicate the list of talks on January 2008.

**About the  Workshop**
This  workshop is  supported  by  the project  NOCoST  "New Tools  for
Computational  Complexity:  Semantics  and  Types", funded  by  Agence
Nationale de la Recherche (ANR)
http://www-lipn.univ-paris13.fr/nocost/

The organizers,

Pierre Boudes <Pierre.Boudes at lipn.univ-paris13.fr>,
Virgile Mogbil <Virgile.Mogbil at lipn.univ-paris13.fr>,
Paulin Jacobé de Naurois <Paulin.Jacobedenaurois at lipn.univ-paris13.fr>


Talk proposal: send it to Paulin.Jacobedenaurois at lipn.univ-paris13.fr
---8<-----------------------------------------------------------------
First name:
Last name:
Institution:
Title:
Short abstract:
----------------------------------------------------------------------




More information about the Types-announce mailing list