Visit Reykjavik ICALP 2008
35th International Colloquium on
Automata, Languages and Programming

July 6 - 13, 2008
Reykjavik - Iceland


Workshops will take place on the premises of Reykjavik University (Ofanleiti 2) in the two weekends before and after the ICALP'08 week

Pre-conference: 6 July 2008.
Post-conference: 12-13 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 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: 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, peer-to-peer systems, grid computing, Web services, multi-agent systems, and component-based 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 self-organized, 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 peer-to-peer 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:

    1. Localization and distribution of information in networks.
    2. Overlay networks and distributed hash tables.
    3. Trust and reputation in social networks.
    4. Selfishness and market mechanisms in networks.
    5. Mining, ranking, clustering and retrieval of networked information.
    6. Models of dynamic and mobile networks.
    7. Security of networks of low capability devices.
    8. Integration and filtering of heterogeneous information.
    9. Distributed databases.
    10. Streaming and Sampling algorithms for information aggregation in networks.
    11. 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. intra-membrane 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 Cells-as-Computation metaphor as the "much-needed 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 bio-molecular processes.
    In the workshop we intend to explore this "cross-fertilization" 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, graph-based models). Recent models of distributed systems (e.g., Service Oriented or Overlay Computing, multi-agent 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 CSP-like 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 CSP-like synchronisation and then mapped, at a lower level, to CCS-like 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 large-scale matching problems involving sets of participants - for example pupils and schools, school-leavers 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 Gale-Shapley algorithm, algorithms for many-to-one hospitals-residents problems [Gale et al. 62], and algorithms for non-bipartite 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 Gale-Shapley 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 mid-1990s, 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], many-to-many versions [Bansal et al. ICALP'03, Malhotra ESA'04], game-theoretic 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 so-called rank-maximal 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 on-going developments as above but also in future directions for the research community, e.g., towards more game-theoretic 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: Freyd-categories 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

  • Quantum Physics and Logic/Developments in Computational Models (July 12 and 13, Room 201)

    This joint event combines two established workshops:

    • The International Workshop on Quantum Programming Languages has as a goal to bring together researchers working on mathematical foundations and programming languages for quantum computing. In the last few years, there has been a growing interest in logical tools, languages, and semantical methods for analyzing quantum computation. These foundational approaches complement the more mainstream research in quantum computation which emphasizes algorithms and complexity theory.
    • Developments in Computational Models. Several new models of computation have emerged in the last few years, and many developments of traditional computational models have been proposed with the aim of taking into account the new demands of computer systems users and the new capabilities of computation engines. A new computational model, or a new feature in a traditional one, usually is reflected in a new family of programming languages, and new paradigms of software development. 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.

    Contact: Ian Mackie

  • 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 multi-hop 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, fault-tolerant 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, self-stabilization 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 4-6, 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 Peer-to-Peer 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 well-known results in the field of process algebra, and for the development of a meta-theory 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