International Workshop on

Developments in Implicit Computational complExity
(DICE 2010)

March 27-28, 2010, Paphos, Cyprus, as part of ETAPS 2010

Important dates:
Deadline for full paper submission: December 21, 2009 (extended)
Deadline for short presentation (extended abstract) submission: January 28, 2010 (extended)
Notification for full papers: January 27, 2010
Final version due: February 8, 2010
Notification for short presentations: February 5, 2010
Workshop: March 27-28, 2010

Invited speakers:
Amir Ben-Amram (Tel-Aviv)
Simone Martini (Bologna)

Program Committee:
Patrick Baillot (CNRS-ENS Lyon) (Chair)
Ugo Dal Lago (University of Bologna)
Martin Hofmann (LMU Munich)
Lars Kristiansen (University of Oslo)
Daniel Leivant (Indiana University)
Jean-Yves Marion (Nancy University)
Virgile Mogbil (University Paris 13)
Simona Ronchi Della Rocca (University of Torino)
Olha Shkaravska (Radboud University, Nijmegen)
Kazushige Terui (University of Kyoto)
Lorenzo Tortora de Falco (University Roma Tre)

Workshop programme (pdf)

The proceedings have appeared as volume 23 of EPTCS, 2010.

The area of Implicit Computational Complexity (ICC) has grown out from several proposals to use logic and formal methods to provide languages for complexity-bounded computation (e.g. Ptime, Logspace computation). It aims at studying computational complexity without referring to external measuring conditions or a particular machine model, but only by considering language restrictions or logical/computational principles implying complexity properties.
This workshop focuses on ICC methods related to programs (rather than descriptive methods). In this approach one relates complexity classes to restrictions on programming paradigms (functional programs, lambda calculi, rewriting systems), such as ramified recurrence, weak polymorphic types, linear logic and linear types, and interpretative measures. The two main objectives of this area are:
  • to find natural implicit characterizations of various complexity classes of functions, thereby illuminating their nature and importance;
  • to design methods suitable for static verification of program complexity.

  • Therefore ICC is related on the one hand to the study of complexity classes, and on the other hand to static program analysis.
    The workshop will be open to contributions on various aspects of ICC including (but not exclusively):
  • types for controlling complexity,
  • logical systems for implicit computational complexity,
  • linear logic,
  • semantics of complexity-bounded computation,
  • rewriting and termination orderings,
  • interpretation-based methods for implicit complexity,
  • application of implicit complexity to other programming paradigms (e.g. imperative or object-oriented languages).
  • Recent meetings on this topic have been held with success in Paris in 2008 ( WICC'08 ), in Marseille in 2006 ( GEOCAL'06 workshop on Implicit computational complexity ), and Paris in 2004 (ICC and logic meeting ), which motivated the organization of an international event at ETAPS 2010 .

    The workshop proceedings will be published in the new EPTCS series (Electronic Proceedings in Theoretical Computer Science).
    There will be two categories of submissions:
  • Full papers (that will appear in the electronic proceedings): up to 15 pages (including bibliography).
  • Extended abstracts for short presentations (that will not be included in the electronic proceedings): up to 3 pages;

  • Authors must indicate if their submission belongs to the second category (by mentioning "(Extended Abstract)" in the title).
    Papers must be submitted electronically, as pdf files, in the EPTCS format, at the following URL:
    Submissions of the first category (full papers) should not have been published before or submitted simultaneously to another conference or journal. This restriction does not hold for the second category (extended abstracts). These latter submissions will be an opportunity to present work in progress or to get a feedback from the audience on a work already published elsewhere. Submissions of papers authored by PC members are allowed.
    If the number and the quality of submissions justifies it, the publication of a special issue of a journal devoted to the workshop will be considered.

    A limited number of student grants will be available for some PhD or Master students presenting a paper at the workshop, so as to cover their local expenses and registration. Students who have not yet defended their PhD or have defended it after September 2009 are eligible. To apply for a grant, send by January 4, 2010 (extended) a mail to , with subject line 'DICE 2010 student grant application' , containing: (i) a short recommendation letter by your PhD/Master advisor, (ii) a scan of your university student card justifying your status.

    The workshop is partially supported by: Ecole Normale Supérieure de Lyon and ANR project COMPLICE (Implicit Computational Complexity, Concurrency and Extraction), ANR-08-BLANC-0211-01.