ICALP 2011, the 38th edition of the International Colloquium on Automata,
Languages and Programming, was held in Z¨urich, Switzerland, during July
4–8, 2011. ICALP is a series of annual conferences of the European Association
for Theoretical Computer Science (EATCS) which first took place in 1972. This
year, the ICALP program consisted of three tracks: the established Track A
(focusing on Algorithms, Complexity and Games) and Track B (focusing on
Logic, Semantics, Automata and Theory of Programming), and a Track C focusing
on Foundations of Networked Computation: Models, Algorithms and
Information Management.
In response to the call for papers, the Program Committee received 398 submissions:
243 for Track A (three of which were later withdrawn), 103 for Track B
and 52 for Track C. Out of these, 114 papers were selected for inclusion in the
scientific program: 68 papers for Track A, 29 for Track B, and 17 for Track C.
The selection was made by the Program Committees based on originality, quality,
and relevance to theoretical computer science. The quality of the manuscripts
was very high indeed, and many deserving papers could not be selected.
The EATCS sponsored both a best paper and a best student paper (all authors
are students) award for each of the three tracks, to be selected by the
Program Committees. The best paper awards were given to Malte Beecken, Johannes
Mittmann, and Nitin Saxena for their paper “Algebraic Independence
and Blackbox Identity Testing” (Track A), to Olivier Carton, Thomas Colcombet,
and Gabriele Puppis for their paper “Regular Languages of Words Over
Countable Linear Orderings” (Track B), and to Martin Hoefer for his paper “Local
Matching Dynamics in Social Networks” (Track C). The best student paper
awards were given to Shi Li for his paper “A 1.488-Approximation Algorithm
for the Uncapacitated Facility Location Problem” (Track A), to Martin Delacourt
for his paper “Rice’s Theorem for mu-Limit Sets of Cellular Automata”
(Track B), and to Shiri Chechik for her paper “Fault-Tolerant Compact Routing
Schemes for General Graphs” (Track C).
ICALP 2011 consisted of five invited lectures and the contributed papers.
This volume of the proceedings contains all contributed papers from Track A,
except for the two papers that received one of the best paper awards. These
two papers are contained in a companion volume, together with all contributed
papers from Track B and Track C, and the papers by four of the invited speakers:
Rajeev Alur (University of Pennsylvania, USA), Thore Husfeldt (IT University of
Copenhagen, Denmark), Catuscia Palamidessi (INRIA Saclay and LIX, France),
and Ronen Shaltiel (University of Haifa, Israel). The program had an additional
invited lecture by ´Eva Tardos (Cornell University, USA), which does not appear
in the proceedings.
