Automata, Languages, and Programming

1. Front Matter

   PDF

2. EATCS Lecture

   1. Algorithms, Networks, and Social Phenomena

      • Jon Kleinberg

      Pages 1-3

3. Invited Talks

   1. Recent Advances for a Classical Scheduling Problem

      • Susanne Albers

      Pages 4-14

   2. Formalizing and Reasoning about Quality

      • Shaull Almagor, Udi Boker, Orna Kupferman

      Pages 15-27

   3. The Square Root Phenomenon in Planar Graphs

      • Dániel Marx

      Pages 28-28

   4. A Guided Tour in Random Intersection Graphs

      • Paul G. Spirakis, Sotiris Nikoletseas, Christoforos Raptopoulos

      Pages 29-35

   5. To Be Uncertain Is Uncomfortable, But to Be Certain Is Ridiculous

      • Peter Widmayer

      Pages 36-36

4. Track B – Logic, Semantics, Automata and Theory of Programming

   1. Decision Problems for Additive Regular Functions

      • Rajeev Alur, Mukund Raghothaman

      Pages 37-48

   2. Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs

      • Gilles Barthe, Federico Olmedo

      Pages 49-60

   3. A Maximal Entropy Stochastic Process for a Timed Automaton,

      • Nicolas Basset

      Pages 61-73

   4. Complexity of Two-Variable Logic on Finite Trees

      • Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieroński, Rastislav Lenhardt, Filip Mazowiecki et al.

      Pages 74-88

   5. Nondeterminism in the Presence of a Diverse or Unknown Future

      • Udi Boker, Denis Kuperberg, Orna Kupferman, Michał Skrzypczak

      Pages 89-100

   6. Coalgebraic Announcement Logics

      • Facundo Carreiro, Daniel Gorín, Lutz Schröder

      Pages 101-112

   7. Self-shuffling Words

      • Émilie Charlier, Teturo Kamae, Svetlana Puzynina, Luca Q. Zamboni

      Pages 113-124

   8. Block-Sorted Quantified Conjunctive Queries

      • Hubie Chen, Dániel Marx

      Pages 125-136

   9. From Security Protocols to Pushdown Automata

      • Rémy Chrétien, Véronique Cortier, Stéphanie Delaune

      Pages 137-149

   10. Efficient Separability of Regular Languages by Subsequences and Suffixes

       • Wojciech Czerwiński, Wim Martens, Tomáš Masopust

       Pages 150-161

   11. On the Complexity of Verifying Regular Properties on Flat Counter Systems,

       • Stéphane Demri, Amit Kumar Dhar, Arnaud Sangnier

       Pages 162-173

   12. Multiparty Compatibility in Communicating Automata: Characterisation and Synthesis of Global Session Types

       • Pierre-Malo Deniélou, Nobuko Yoshida

       Pages 174-186

   13. Component Reconfiguration in the Presence of Conflicts

       • Roberto Di Cosmo, Jacopo Mauro, Stefano Zacchiroli, Gianluigi Zavattaro

       Pages 187-198

This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, held in Riga, Latvia, in July 2013. The total of 124 revised full papers presented were carefully reviewed and selected from 422 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.

• algorithm analysis and problem complexity

• Department of Informatics, University of Bergen, Bergen, Norway

  Fedor V. Fomin

• Faculty of Computing, University of Latvia, Riga, Latvia

  Rūsiņš Freivalds

• Department of Computer Science, Wolfson Building, Parks Road, University of Oxford, Oxford, UK

  Marta Kwiatkowska

• Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

  David Peleg

Policies and ethics