Automata, Languages and Programming

1. Front Matter

   PDF

2. Invited Lectures

   1. Nondeterministic Streaming String Transducers

      • Rajeev Alur, Jyotirmoy V. Deshmukh

      Pages 1-20

   2. An Introduction to Randomness Extractors

      • Ronen Shaltiel

      Pages 21-41

   3. Invitation to Algorithmic Uses of Inclusion–Exclusion

      • Thore Husfeldt

      Pages 42-59

   4. On the Relation between Differential Privacy and Quantitative Information Flow

      • Mário S. Alvim, Miguel E. Andrés, Konstantinos Chatzikokolakis, Catuscia Palamidessi

      Pages 60-76

3. Best Student Papers

   1. A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem

      • Shi Li

      Pages 77-88

   2. Rice’s Theorem for μ-Limit Sets of Cellular Automata

      • Martin Delacourt

      Pages 89-100

   3. Fault-Tolerant Compact Routing Schemes for General Graphs

      • Shiri Chechik

      Pages 101-112

4. Best Papers

   1. Local Matching Dynamics in Social Networks

      • Martin Hoefer

      Pages 113-124

   2. Regular Languages of Words over Countable Linear Orderings

      • Olivier Carton, Thomas Colcombet, Gabriele Puppis

      Pages 125-136

   3. Algebraic Independence and Blackbox Identity Testing

      • Malte Beecken, Johannes Mittmann, Nitin Saxena

      Pages 137-148

5. Session B1: Foundations of Program Semantics

   1. A Fragment of ML Decidable by Visibly Pushdown Automata

      • David Hopkins, Andrzej S. Murawski, C. -H. Luke Ong

      Pages 149-161

   2. Krivine Machines and Higher-Order Schemes

      • S. Salvati, I. Walukiewicz

      Pages 162-173

   3. Relating Computational Effects by ⊤ ⊤-Lifting

      • Shin-ya Katsumata

      Pages 174-185

   4. Constructing Differential Categories and Deconstructing Categories of Games

      • Jim Laird, Giulio Manzonetto, Guy McCusker

      Pages 186-197

6. Session B2: Automata and Formal Languages

   1. Nondeterminism Is Essential in Small 2FAs with Few Reversals

      • Christos A. Kapoutsis

      Pages 198-209

   2. Isomorphism of Regular Trees and Words

      • Markus Lohrey, Christian Mathissen

      Pages 210-221

   3. On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids

      • Georg Zetzsche

      Pages 222-233

   4. The Cost of Traveling between Languages

      • Michael Benedikt, Gabriele Puppis, Cristian Riveros

      Pages 234-245

7. Session B3: Model Checking

   1. Emptiness and Universality Problems in Timed Automata with Positive Frequency

      • Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Amélie Stainer

      Pages 246-257

The two-volume set LNCS 6755 and LNCS 6756 constitutes the refereed proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, held in Zürich, Switzerland, in July 2011. The 114 revised full papers (68 papers for track A, 29 for track B, and 17 for track C) presented together with 4 invited talks, 3 best student papers, and 3 best papers were carefully reviewed and selected from a total of 398 submissions. The papers are grouped in three major tracks on algorithms, complexity and games; on logic, semantics, automata, and theory of programming; as well as on foundations of networked computation: models, algorithms and information management.

• computer science logic
• equilibria computation
• formal methods
• formal verification
• hybrid systems
• program semantics
• systems security
• algorithm analysis and problem complexity

• ICE-TCS, School of Computer Science, Reykjavik University, Reykjavik, Iceland

  Luca Aceto

• Fakultät für Informatik, Universität Wien, Wien, Austria

  Monika Henzinger

• Department of Applied Mathematics, Charles University, Praha 1, Czech Republic

  Jiří Sgall

Policies and ethics