CALL FOR PAPERS

           ACM Transactions on Computational Logic (TOCL)

       Special Issue on Implicit Computational Complexity (ICC)


Following the success of the GEOCAL workshop on ICC, there will
be a special issue of the ACM Transactions on Computational Logic
(TOCL), see <http://www.acm.org/pubs/tocl/>
Submissions for this special issue are hereby solicited to  participants
of the workshop, but also to other contributors.

The workshop was held on February 13-17 2006 in Marseille (France)
as part of the Geometry of Computation 2006 meeting (series of  
lectures and
workshops) organized by the GEOCAL project.
More information can be found at

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.
It aims at studying the computational complexity of programs without
referring 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...
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 program complexity. In particular the latter goal
requires characterizations, which are general enough to include
commonly used algorithms.

Submissions consist in either
(i)  Sending  to patrick.baillot'at'lipn.univ-paris13.fr the file in
pdf or ps format, with "ICC ToCL issue submission" in the subject line.
(ii) by posting the paper first at the Computing Research Repository
(CoRR) and subsequently sending the archive identifier by email to
to  patrick.baillot'at'lipn.univ-paris13.fr (see Submission via CoRR
for the benefits of this form of submission :

All submissions will be acknowledged. Submitted papers must be
original and not submitted for publication. Submissions will be
refereed according to the usual very high standards of TOCL.

Deadline for submissions : 31 August 2006
Notification : 30 November  2006
Final manuscrits : 1st March 2007

Patrick Baillot, Université Paris 13, LIPN,
email : patrick.baillot 'at' lipn.univ-paris13.fr
Jean-Yves Marion, Ecole des Mines de Nancy, LORIA-INPL,
email : Jean-Yves.Marion 'at' loria.fr
Simona Ronchi della Rocca,  Università di Torino,
email :  ronchi'at'di.unito.it