Ca' Foscari logo ICALP 2006
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 week:

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.

    Contact: Sotiris Nikoletseas

  • 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.

    Contact: Tom Schrijvers

  • 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 for it. 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 X-calculus. 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.

    Contact: 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.

    Contact: Ian Mackie

  • 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.

    Contact: Véronique Cortier

  • 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.

    Contact: Osamu Watanabe

  • 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.

    Contact: 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 this area.

    Contact: Maribel Fernandez

  • 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.

    Contact: Giovanni Di Crescenzo