33rd International Colloquium on
Automata, Languages and Programming
July 9 - 16, 2006
S. Servolo, Venice - Italy
Workshops will take place in the two weekends before and after the ICALP'06
Pre-conference: 9 July 2006.
Post-conference: 15-16 July 2006.
ALGOSENSORS 2006 - International Workshop on
Algorithmic Aspects of Wireless Sensor Networks
(July 15, Room 1E)
Wireless ad-hoc sensor networks have recently become a very active research subject due to their potential of providing diverse services to numerous important applications, including remote monitoring and tracking of environmental applications and low maintenance ambient intelligence in everyday life. The effective and efficient realization of such large scale, complex ad-hoc networking environments requires intensive, coordinated technical research and development efforts, especially in power aware, scalable, wireless distributed protocols, due to the unusual application requirements and the severe resource constraints of the sensor devices.
On the other hand, a solid foundational background seems necessary for sensor networks to achieve their full potential. It is a challenge for abstract modelling, algorithmic design and analysis to achieve efficient and fault-tolerant realizations of such very large, highly-dynamic, complex, non-conventional networks. Features including the huge number of sensor devices in the network, the severe power, computational and memory limitations, their dense, random deployment and frequent failures, pose new interesting design, analysis and implementation challenges.
CHR 2006 - Third Workshop on Constraint Handling Rules
(July 9, Room R2)
The Constraint Handling Rules (CHR) language has become a major declarative
specification and implementation language for constraint-based algorithms
and applications. Algorithms are often specified using inference rules,
rewrite rules, sequents, proof rules or logical axioms that can be directly
written in CHR. Based on first order predicate logic, this clean semantics
of CHR facilitates non-trivial program analysis and transformation.
The CHR workshop calls for full papers and short papers describing ongoing work, on all aspects of CHR, including topics such as: semantics, algorithms, constraint solvers, expressivity and complexity, program analysis, implementations and optimization, program transformation and generation, language extensions, retractable constraints, programming pearls, programming environments, applications, critical assessment, comparisons with related approaches.
CL&C 2006 - Classical Logic and Computation
(July 15, Room R2)
CL&C'06 is the first of a new conference series on "Classical
Logic and Computation". It intends to cover all work aiming to propose
a programming language inspired by classical logic, and a semantics
The fact that classical mathematical proofs of simply existential
statements can be read as programs was established by Godel and
Kreisel some 50 years ago. But the possibility of programming using a
style inspired by Classical Logic (much as functional programming is
inspired by Intuitionistic Logic) was taken seriously only after the
seminal work of Griffin about typing continuations.
There are today two main lines of research.
The first studies some (version of lambda) calculus adapted to
represent classical logic, like the symmetric mu-calculs, or the
The second studies semantics for programs inspired by classical
proofs, like game semantic or learning algorithms. These two
directions are often independent. This workshop aims to start a
fruitful exchange of ideas in the field.
Steffen van Bakel
DCM 2006 - 2nd International Workshop on Developments in Computational Models
(July 16, Room R2)
The aim of this workshop is to bring together researchers who are
currently developing new computational models or new features for
traditional computational models, in order to foster their
interaction, to provide a forum for presenting new ideas and work in
progress, and to enable newcomers to learn about current activities in
this area. Topics of interest include all abstract models of
computation and their applications to the development of programming
languages and systems. This includes (but is not limited to):
Functional calculi: lambda-calculus, rho-calculus, term and graph
rewriting; Object calculi; Interaction-based systems: interaction
nets, games; Concurrent models: process calculi, action graphs;
Calculi expressing locality, mobility, and active data; Quantum
computational models; Biological or chemical models of computation.
FCC 2006 - Formal and Computational Cryptography
(July 9, Room 9A)
Cryptographic protocols are small distributed programs that add
security services, like confidentiality or authentication, to
network communication. Since the 1980s, two approaches have been
developed for analyzing security protocols. One of the approaches
relies on a computational model that considers issues of complexity
and probability. The other approach relies on a symbolic model of
protocol executions in which cryptographic primitives are black boxes.
The workshop focuses on the relation between the symbolic (Dolev-Yao)
model and the computational (complexity-theoretic) model. Recent
results have shown that in some cases the symbolic analysis is sound
with respect to the computational model. A more direct approach which
is also investigated considers symbolic proofs in the computational
model. The workshop seeks results in these areas.
iETA 2006 - Improving Exponential-Time Algorithms: Strategies and Limitations
(July 16, Room 1E)
Recently several attemps have been made for improving exponential time
algorithms for some of the hard problems, most typically NP-hard problems,
such as 3SAT, SAT, Coloring, etc. The purpose of this workshop is to
provide a forum for exchanging various idea for improvements, for obtaining
an unified and/or systematic view of those improvements, and for discussing
their limitations. We focus on the worst-case complexity of such algorithms.
Although experiments on average-case performance is out of the scope, we
will also welcome reports on implimentation techniques of exponential-time
algorithms on real computer systems, e.g., supercomputers.
MeCBIC 2006 - Membrane Computing and Biologically Inspired Process Calculi
(July 9, Room 9B)
Biological membranes play a fundamental role in the complex reactions taking place in living cells. The importance of this role has been considered in two different types of formalisms recently introduced.
Membrane systems were introduced as a class of distributed parallel computing devices of a biochemical type. The emphasis is mainly on the computational properties of the model, and it makes use of automata, languages, and complexity theoretic tools.
In the process algebra research community, the notions of membranes and compartments have been explicitely represented in a family of calculi, such as Brane Calculi and BioAmbients. The emphasis is mainly on the fidelity to the biological reality, and the main interest is in the systems biology area.
A cross fertilization of the two research areas has recently started. The workshop aim is to bring together researchers working in membrane computing and in biologically inspired process calculi, to present recent research works and to discuss new ideas.
Nadia Busi and Claudio Zandron
SecReT 2006 - 1st Int. Workshop on Security and Rewriting Techniques
(July 15, Room 9A)
With the increasing use of digital communication, network-based
applications and mobile code, software, system and data security are
key issues affecting everybody, from individuals to industry and
governments. Recently, rewriting techniques have been fruitfully used
for performing validations on policy specifications and analysis of
cryptographic protocols, to mention just a few. The theory of
rewriting can provide a formal basis for the study of a broad range of
security issues, ranging from the specification, implementation, and
validation of access control policies, to the analysis of logs and the
development of tools for intrusion detection. In this context, the
aim of this workshop is to bring together researchers who are
currently working in the area of rewriting and security experts, in
order to foster their interaction and develop future collaborations in
this area, to provide a forum for presenting new ideas and work in
progress, and to enable newcomers to learn about current activities in
WCAN 2006 - 2nd Workshop on Cryptography for Ad Hoc Networks
(July 16, Room 9A)
Wireless ad hoc networks are today receiving much attention for militar, commercial and civilian applications, thus becoming a challenging area in security research. The security research community has mainly focused on securing routing and is only recently widening its scope of analysis. The cryptography research community has mainly focused on abstract models of networks like the Internet; however, cryptographic protocols for the Internet face serious challenges to be adapted to the ad-hoc, partial-connectivity, mobile, resource-constrained and infrastructureless nature of ad-hoc networks. The aim of this workshop is to help bridging this gap, towards a comprehensive investigation of security and cryptographic tools, analysis and modeling methodologies applicable to ad hoc networks, (including cellular, wireless, sensor, etc. networks) by bringing together the cryptography, network security, and wireless networking research communities.
Giovanni Di Crescenzo