40th international colloquium on automata, languages and programming

摘要

In this special issue we collected selected papers from the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), which took place from the 8th to the 12th of July 2013 in Riga, Latvia. ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science. It is one of the most important conferences for the presentation of research on all aspects of theoretical computer science. ICALP 2013 had three tracks. Track A was devoted to Algorithms, Complexity and Games and saw the presentation of 71 papers. The theme for track B was Logic, Semantics, Automata and Theory of Programming; 33 papers were selected for this track. Track C focused on Foundations of Networked Computation: Models, Algorithms and Information Management and accepted 20 papers. Out of these 124 papers, 16 were selected for this special issue (8 for track A, 5 for track B and 3 for track C). Amongst these submissions, the first four contributions of this issue received best paper awards at ICALP 2013: 1. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. (Best paper for Track A.) 2. John Fearnley and Marcin Jurdzinski. Reachability in two-dock timed automata is PSPACE-complete. (Best paper for Track B.) 3. Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pajak and Przemyslaw Uznanski. Fast collaborative graph exploration. (Best paper for Track C.) 4. Nicolas Basset. A maximal entropy stochastic process for a timed automaton. (Best student paper for Track B.)