[TYPES/announce] DICE 2012 - Call for Presentations

Ugo Dal Lago dallago at cs.unibo.it
Wed Feb 15 03:16:45 EST 2012

DICE 2012
3rd Workshop on Developments in Implicit Complexity
Tallinn (Estonia), March 31st and April 1st, 2012

(Affiliated with ETAPS 2012)



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. polytime or
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 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
• to find natural implicit characterizations of various complexity
classes of functions, thereby illuminating their nature and
• to design methods suitable for static verification of program

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,
• programming languages for complexity-bounded computation,
• certification of complexity properties of programs,
• application of implicit complexity to other programming paradigms
(e.g. imperative or object-oriented languages).

The first two DICE workshops were held in 2010 in Cyprus and in 2011
in Germany, both as part of ETAPS conferences. Before that, several
meetings on this topic had already been held with success in Paris
(WICC 2008), and Marseille (GEOCAL 2006 workshop on Implicit
computational complexity).


Extended abstracts for presentations of up to 3 pages.

The following deadlines are strict:

• Submission (extended abstracts): February 18th, 2012;
• Notification (extended abstracts): February 28th, 2012.

Abstracts must be submitted electronically, as pdf files, at the
following page:


• Guillaume Bonfante (Nancy)
• Ugo Dal Lago (Bologna, chair)
• Marco Gaboardi (Bologna and UPenn)
• Nao Hirokawa (JAIST)
• Martin Hofmann (Munchen)
• Olivier Laurent (ENS Lyon)
• Jean-Yves Moyen (Paris Nord)
• Isabel Oitavem (Lisboa)
• German Puebla (Madrid)
• Simona Ronchi Della Rocca (Torino)

More information about the Types-announce mailing list