Developments
in Implicit Computational Complexity : DICE
Series
of workshops
DICE
is a thematic workshop in the field of Implicit Computational
Complexity and related topics, where researchers can meet and
discuss their most recent results. It takes place annually as part of
ETAPS.
Upcoming event
DICE-FOPARA 2019 was the last edition of DICE, but a new workshop will be organised as part of FSCD 2020 in Paris:
SCOT : Semantic and formal approaches to COmplexiTy.
The rest of this page contains archive information about DICE.
Scope and Topic
The area of Implicit Computational Complexity (ICC) has grown from several
proposals for using logic and formal methods to provide languages for
complexity-bounded computation (e.g. PTIME, LOGSPACE computation). Its aim is
to study computational complexity without reference to external measuring
conditions or particular machine models, but only in terms of 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 one hand to the study of complexity
classes, and on the other hand to static program analysis.
Steering Committee
Martin Hofmann (LMU Munich) has been a member of the Steering Committee until his tragic disappearance in 2018.
The DICE 2018 workshop and the special volume for DICE 2014 and 2015
have been dedicated to his memory.
Past events
- DICE-FOPARA 2019 Prague, Czech Republic.
- DICE 2018 , Thessaloniki, Greece.
- DICE-FOPARA 2017 Uppsala,
Sweden. Proceedings in EPTCS 248
.
- DICE 2016
Eindhoven, Netherlands.
- DICE 2015
London, Great-Britain, colocated with FOPARA 2015 .
- DICE 2014 Grenoble,
France.
- DICE 2013 Rome,
Italy.
- DICE 2012 Tallinn,
Estonia.
- DICE 2011 Saarbrucken,
Germany. Proceedings in EPTCS 75
.
- DICE 2010 Paphos,
Cyprus. Proceedings in EPTCS 23
.
Special issues of journals
- Special issue of Information and Computation, following DICE
2014 & 2015, edited by Marco Gaboardi and Ulrich Schöpp. In press, available online.
- Special issue of Information and Computation, vol. 248 p. 1-226 (June 2016), following DICE
2013, edited by S. Ronchi Della Rocca.
- Special issue of Theoretical Computer Science,
Volume 58 (June 2015) , following DICE
2012, edited by U. Dal Lago and G. Bonfante.
- Special Section of
Information and Computation, vol. 241, April 2015 , following DICE
2011, edited by
J.-Y. Marion.
Starting from the 2014 edition, journal special issues are biannual, collecting every odd year some extended versions of
contributions of the previous two years.