
   
WORKSHOPS
Workshops will take place on the premises of Reykjavik University (Ofanleiti 2) in the
two weekends before and after the ICALP'08 week
Preconference: 6 July 2008.
Postconference: 1213 July 2008.
NEWS DATED 5 JULY 2008: The location of
the workshops Foundations of Information Management in Networks (July 6),
Second International workshop on Mobility, Algorithms and Graph theory In dynamic
NEtworks (IMAGINE 2008) (July 12) and
Classical Logic and Computation (July 13) has changed. These workshops will be
held in room 304.

ALGOSENSORS 2008 
International Workshop on Algorithmic Aspects of Wireless Sensor
Networks
(July 12, Room 231a)
Wireless adhoc 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 adhoc 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 faulttolerant
realizations of such very large, highlydynamic, complex,
nonconventional 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:
Sándor P. Fekete

Classical
Logic and Computation (July 13, Room 304)
Classical Logic and Computation will cover all work intending to
propose a programming language inspired by classical logic, and a
semantics for it. The seminal work in this area is the typing of
continuations provided by Griffin in '80. Classical Logic and
Computation will focus on (but not be limited to)
 types for lambda calculus with continuations,
 design of programming languages inspired by classical logic,
 witness extraction from classical proofs,
 constructive semantic for classical logic (e.g. game semantic),
 case studies (for any of the previous points)
Contact:
Steffen van Bakel

FOCLASA'08 (July 13, Room 235)
A number of
hot research topics are currently sharing the common problem of
combining concurrent, distributed, mobile and heterogenous components,
trying to harness the intrinsic complexity of the resulting systems.
These include coordination, peertopeer systems, grid computing, Web
services, multiagent systems, and componentbased systems.
Coordination languages and software architectures are recognised as
fundamental approaches to tackle this issue, improving software
productivity, enhancing maintainability, advocating modularity,
promoting reusability, and leading to systems more tractable and more
amenable to verification and global analysis.
The goal of the FOCLASA workshop is to put together researchers and
practitioners of the aforementioned fields, to share and identify
common problems, and to devise general solutions in the contexts of
coordination languages and software architectures.
Contact:
Carlos Canal,
Pascal Poizat and
Marjan Sirjani

Foundations
of Information Management in Networks (July 6, Room 304)
Network information management is a growing area of research at the
attention of several computer science communities: Algorithms, Formal
Methods, Information systems, Machine Learning and Data mining,
Networks and Distributed Systems. The reason of this interest is
given by the recent emergence of information systems distributed
across the network, pervasive systems, physical mobile and virtual
networks of users. These systems are often selforganized,
interconnected, highly dynamic, expand up to include the users as
source of content and intelligence, ask for a unifying view of data,
services and users.
Query, search and retrieval of structured and unstructured information
in such systems has already prompted a large body of research at the
intersection between databases, information retrieval and
networks. Examples are peertopeer systems, distributed hash tables,
distributed information retrieval, filtering and integration of
information, representation, query processing and compression of
structured data. Computing aggregate information and statistics in
these systems require novel sampling, hashing and streaming techniques
that operate with limited storage and computational resources and/or
by looking only at a suitable subset of the data. In pervasive systems
and networks of sensing entities, local statistics often need to be
computed at several vantage points in the network with even more
severe restrictions.
These network systems are open and thus prone to manipulation of
malicious individuals and collectives. Mechanisms that protect the
system against manipulation using incentives, reward and penalties are
a wide subject of study as well as the equilibria they induce. On the
other hand, the devise of trust and reputation mechanisms that cannot
be manipulated by users and coalitions of users are also an important
field of investigation. We also observe a growing role of the players
in performing fundamental tasks of the network. Users provide tags,
annotation, feedback in terms of preferences and opinions. Modelling
user behaviour and learning about user profiles from logs and past
behavior is therefore becoming crucial in several applications.
Most of these systems are interconnected in nature. They give rise to
dynamic networks of complex structure, with the structure tightly
related to the functions. Mining the structure of these large scale
dynamic networks, detecting regularities, anomalies and associations
between entities play a major role in several applications as for
instance ranking, trust management , indexing, navigation and
classification of entities.
These challenges ask for a more solid asset of the theoretical
foundations of information management in networks. A number of
position papers and recent results will be presented by key
researchers in the area that will be invited to this workshop. Several
of these subjects are already of interest of the ICALP community, all
tracks. However, we believe that a more focussed and thorough
presentation of the main challenges of these areas will make an
original contribution to the conference.
A partial list of the topics of interest of the workshop includes:
 Localization and distribution of information in networks.
 Overlay networks and distributed hash tables.
 Trust and reputation in social networks.
 Selfishness and market mechanisms in networks.
 Mining, ranking, clustering and retrieval of networked information.
 Models of dynamic and mobile networks.
 Security of networks of low capability devices.
 Integration and filtering of heterogeneous information.
 Distributed databases.
 Streaming and Sampling algorithms for information aggregation in networks.
 Formal methods for network information management.
Contact:
Stefano Leonardi
and Friedhelm
Meyer auf der Heide

From Biology To Concurrency and back 2008 (FBTC 2008) (July 12, Room 235)
In computational theory, several formal approaches make use of biology as
inspiration for the development of problem solving techniques. Most of them are
taken from complex, inherently concurrent, systems. Some examples of "biological
inspired computing", with their biological counterpart, are:
 artificial immune systems vs. immune system
 cellular automata vs. life
 genetic algorithms vs. evolution
 membrane computing vs. intramembrane molecular processes in the living cell
 neural networks vs. the brain
 swarm intelligence, emergent behaviour vs. ant colonies, bee hives, bird
flocking, animal herding, fish schooling etc.
On the other hand, concurrency has itself begun to inspire an emerging research
area in Biology. Regev and Shapiro indicated in 2002 the CellsasComputation
metaphor as the "muchneeded abstraction for biomolecular systems". Computers
and biomolecular systems both start from a small set of elementary components
from which, layer by layer, more complex entities are constructed with evermore
sophisticated functions. In computational systems biology, the abstractions,
tools and methods used to specify and study concurrent and distributed systems
can therefore be naturally adopted to model and better understand the complex
biomolecular systems. Recently, in order to achieve more realistic models and
simulations, various process calculi have been actually inspired by biomolecular processes.
In the workshop we intend to explore this "crossfertilization" between
computational sciences and biology, with the focus posed on concurrent
formalisms and related models of alive systems.
Contact:
Nicola Cannata, Emanuela Merelli and
Irek Ulidowski

First Interaction and
Concurrency Experience (ICE'08): Synchronous and Asynchronous
Interactions in Concurrent Distributed Systems (July 6, Room 231b)
The workshop intends to attract researchers interested in models,
verification, tools, and programming primitives concerning
theoretical and applied aspects of interactions and the
synchronization mechanisms used among actors of concurrent or
distributed systems.
Synchronisation mechanisms are one of the key aspects in concurrency
and they are becoming enormously relevant in modern distributed
systems. Theoretical models, design and verification of interaction
protocols and programming practice must take synchronisations into
account for specifying, implementing and reasoning on systems where
computations are spread across possibly many actors that interact
within a precise interaction framework.
At a low level of abstraction, systems can be classified according
to a wide spectrum, ranging between the two extremes of (completely)
synchronous or asynchronous interactions. In fact, such a
classification can be given according to the assumptions made on,
e.g., the number of participants or the time interactions need to be
effected. Significantly, the behaviour of such systems can be
investigated using different assumptions that yield different
expressiveness or complexity results.
Several recent theoretical results shed light on the
interrelations between synchronous and asynchronous interaction
mechanisms (e.g., expressiveness results for distributed algorithms,
relations among observational semantics of (a)synchronous
models). Interaction mechanisms have also been studied in relation to
other features of systems such as mobility (e.g., name passing process
calculi, graphbased models). Recent models of distributed systems
(e.g., Service Oriented or Overlay Computing, multiagent systems)
pose further challenging problems. For instance, overlay computing
envisages systems as abstract computations among loosely coupled
partners relying on heterogeneous communication infrastructures which
typically exploit different interaction mechanisms. In this context,
several interaction mechanisms based on different underlying concepts
have been proposed (e.g., sessions, data driven coordination,
probabilistic/timed models). Interestingly, recent lines of research
have (re)considered synchronisation mechanisms proposed in the past
(for instance, the CCS or CSPlike synchronisation and weaker
variants of them) as coordination mechanisms that can suitably
represent interactions of distributed systems at different levels of
abstraction. For instance, abstract interactions can be suitably
modelled using CSPlike synchronisation and then mapped, at a lower
level, to CCSlike ones that correspond more closely to e.g., the
synchronisation in TCP/IP protocols.
Additionally, recent models of computations (e.g., those inspired by
other disciplines like biology or chemistry) utilise novel kinds of
interactions that typically interlace with other important
characteristics of systems (e.g., spatial or environmental
conditions).
Finally, synchronisation aspects of interactions also
affect the implementation and verification of systems. Theoretical
results can indeed suggest new techniques and methods for
implementing systems and the efficient verification of their
properties. Examples of this include the recent works proposing type
systems or algorithms based on checking behavioural equivalences of
systems whose specification exploits a different interaction mechanism
with respect to the implementation.
Contact:
Filippo Bonchi

Matching Under Preferences  Algorithms and Complexity
(July 6, Room 201)
Many practical situations
give rise to largescale matching problems involving sets of
participants  for example pupils and schools, schoolleavers and
universities, applicants and positions  where some or all of the
participants express preferences over the others. A large class of
matching problems that involve preferences is the class of stable
matching problems.
Such problems involve a set of agents, each of
whom ranks a subset of the other agents in order of preference. The
task is to find a stable matching, i.e., a set of pairs of acceptable
agents such that no two agents could improve their assignment by
becoming matched to each other. Since their introduction by Gale and
Shapley in 1962, stable matching problems (and the classical stable
marriage problem in particular) have attracted the attention of many
researchers in the area of the design and analysis of algorithms (one
of the major topics of ICALP Track A) as well as in other fields, such
as discrete mathematics, game theory and economics. Important
developments prior to the 1990s include the fundamental GaleShapley
algorithm, algorithms for manytoone hospitalsresidents problems
[Gale et al. 62], and algorithms for nonbipartite stable roommates
problems [Irving 85], as well as the identification, analyses and
exploitation of lattice and poset structures underlying stable
matchings [Knuth 76, Gusfield 87, Irving et al. 87, Feder 89]. The
monograph of [Gusfield and Irving, 89], is a comprehensive source for
aspects of these problems studied during that period.
Stable matching
problems have important practical applications; the most famous
example is the NRMP (National Resident Matching Program) in the US,
for which GaleShapley type algorithms have been used for more than 50
years. Similar applications, to medical and other domains, also exist
in Canada, Scotland, Japan, and many other countries . A variety of
new problems arising from such applications, such as consideration of
couples, have also been studied.
Since the mid1990s, the trend has
been towards extensions and variants of the basic problem in several
different directions. These have included different notions of
stability for the case that preference lists may include ties [Irving
94, Irving et al. STACS'03, Kavitha et al. STACS'04], manytomany
versions [Bansal et al. ICALP'03, Malhotra ESA'04], gametheoretic
analyses [Cechlárová et al. 04, Huang, ESA'06, STACS'07], dynamic
systems and equilibrium analyses [Abraham et al. SWAT'06], and
approximation algorithms for hard variants of stable matching [Iwama
et al. ICALP'99, SWAT'04, SODA'07, WADS'07, Halldórsson et al. ESA'03,
Irving and Manlove COCOON'07]. In addition, new research into matching
problems where preferences are expressed on only side has been
productive, including studies of socalled rankmaximal matchings
[Irving et al. SODA'04] and popular matchings [Abraham et
al. SODA'05, Mestre ICALP'06, Manlove et al. ESA'06]. Thus
developments in the field in the last few years have been impressive
and the time seems to be right for researchers to come together.
This
workshop will mainly focus on these new developments, with keywords
"matching" and "preference". We are interested in not only
ongoing developments as above but also in future directions for the
research community, e.g., towards more gametheoretic and financial
aspects of the problems. We also hope that this meeting will provide
an ideal opportunity to bring together researchers from the computer
science and economics communities, whose efforts in this field
hitherto have tended to follow different paths.
Contact:
Kazuo Iwama

Mathematically Structured Functional Programming 2008
(July 6, Room 235)
The workshop on Mathematically Structured Functional Programming is
devoted to the derivation of functionality from structure. It is a
celebration of the direct impact of Theoretical Computer Science on
programs as we write them today. Modern programming languages, and
in particular functional languages, support the direct expression of
mathematical structures, equipping programmers with tools of
remarkable power and abstraction. Monadic programming in Haskell is
the paradigmatic example, but there are many more mathematical
insights manifest in programs and in programming language design:
Freydcategories in reactive programming, symbolic differentiation
yielding context structures, and comonadic presentations of
dataflow, to name but three. This workshop is a forum for
researchers who seek to reflect mathematical phenomena in data and
control.
Contact:
Venanzio Capretta and
Conor McBride

Second International
workshop on Mobility, Algorithms and Graph theory In
dynamic NEtworks (IMAGINE 2008) (July 12, Room 304)
IMAGINE is a workshop whose speakers and members of the
program/steering committee are junior researchers (Master and
Ph.D. students or doctors who have defended their PhD for no more than
approximately 2 years) and whose areas of interest mainly concern
dynamic networks, from both the applied and the theoretical points of
view.
On one hand, mobile computing and communication devices will have
an enormous impact on our lifestyle over the next several
decades. Wireless connectivity with mobility support is an important
enabling technology for pervasive computing and communications. The
emergence of multihop wireless networks raises a number of
interesting, and difficult theoretical and algorithmic issues and will
play a key role in the development and progress of these emerging
paradigms. On the other hand, modern systems are often large scale
networks consisting of a very large number of nodes, characterized by
an inherent instability since every entity is mobile and dependent of
each other. Thus, studying dynamic networks (e.g., wireless ad hoc and
sensor networks, large scale systems) implies studying mobility,
algorithms and graph theory in order to provide reliable,
faulttolerant and generic theoretical models. Indeed, since systems'
sizes are more and more important, when a fault locally occurs, the
system has to recover without impacting every entity of the network.
To improve such models, researchers in the field of wireless networks
need to understand many tools like graph theory, graph decompositions,
stochastic geometry, mobility models derived from social graphs area,
selfstabilization mechanisms, etc.
Conversely, researchers working in the field of graph theory, and
more generally in fields in the scope of track A of ICALP, have
developed several tools, like efficient distributed algorithms and
useful graph decompositions or embeddings, for which dynamic and
wireless networks offer a wide field of applications. Unfortunately,
nowadays, most of researchers studying that fields work independently
of what is done in other research areas.
Dynamic networks as
well as graph theory need the meeting of different communities from
research areas susceptible to bring new tools to be
improved. Therefore, IMAGINE wants to gather junior researchers in
order to promote a multidisciplinary approach in the field of dynamic
networks. For this purpose, this workshop wants to promote surveys
done by junior researchers about their own works.
Contact:
David Ilcinkas,
Nathalie Mitton and
Nicolas Nisse

Second
Training School on Algorithmic Aspects of Dynamic Networks (DYNAMO
2008) (July 46, Room 101)
This Training School is organized by the COST Action 295
on Dynamic Communication Networks: Foundations and Algorithms (DYNAMO).
The Action is motivated by the need to supply a convincing theoretical
framework for the analysis and control of all modern large networks. It
aims at providing foundations, models, algorithms, and general tools
for dynamic networks that include decentralised and evolving computing
entities, characterised by their inherently dynamic nature.
The Training School is open to the entire scientific community, and PhD
students from institutions adhering to COST Action 295 will receive
special supports. It will focus on three aspects of the design and
analysis of dynamic networks, and propose three Comprehensive Lectures
on Game Theory, Online Algorithms, and PeertoPeer Systems,
respectively. A set of Introductory Lectures will complement a panorama
on recent advances in Dynamic Networks.
Contact:
Pierre Fraigniaud

Structural
Operational Semantics 2008 (July 6, Room 231a)
Structural operational
semantics (SOS) provides a framework for giving operational semantics
to programming and specification languages. A growing number of
programming languages from commercial and academic spheres have been
given usable semantic descriptions by means of structural operational
semantics. Because of its intuitive appeal and flexibility, structural
operational semantics has found considerable application in the study
of the semantics of concurrent processes. Moreover, it is becoming a
viable alternative to denotational semantics in the static analysis of
programs, and in proving compiler correctness.
Recently, structural operational semantics has been successfully
applied as a formal tool to establish results that hold for classes of
process description languages. This has allowed for the generalisation
of wellknown results in the field of process algebra, and for the
development of a metatheory for process calculi based on the
realization that many of the results in this field only depend upon
general semantic properties of language constructs.
This workshop aims at being a forum for researchers, students and
practitioners interested in new developments, and directions for
future investigation, in the field of structural operational
semantics. One of the specific goals of the workshop is to establish
synergies between the concurrency and programming language communities
working on the theory and practice of SOS. Moreover, it aims at
widening the knowledge of SOS among postgraduate students and young
researchers worldwide.
Contact:
Matthew
Hennessy and Bartek
Klin
