Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5--12, 2009. Proceedings, Part II (Q1028779)

The articles of this volume will be reviewed individually. The preceding colloquium has been reviewed (see Zbl 1142.68001 and Zbl 1141.68001). For the first part of the proceedings of the present colloquium see Zbl 1166.68001. Indexed articles: \textit{Chatterjee, Krishnendu; Doyen, Laurent; Henzinger, Thomas A.}, A survey of stochastic games with limsup and liminf objectives, 1-15 [Zbl 1248.91015] \textit{Gottlob, Georg; Greco, Gianluigi; Scarcello, Francesco}, Tractable optimization problems through hypergraph-based structural restrictions, 16-30 [Zbl 1248.68246] \textit{Acciai, Lucia; Boreale, Michele}, Deciding safety properties in infinite-state pi-calculus via behavioural types, 31-42 [Zbl 1248.68346] \textit{Baier, Christel; Bertrand, Nathalie; Bouyer, Patricia; Brihaye, Thomas}, When are timed automata determinizable?, 43-54 [Zbl 1248.68284] \textit{Beaudry, Martin; Lemieux, François}, Faithful loops for aperiodic e-ordered monoids. (Extended abstract), 55-66 [Zbl 1248.68339] \textit{Blumensath, Achim; Otto, Martin; Weyer, Mark}, Boundedness of monadic second-order formulae over finite words, 67-78 [Zbl 1248.03018] \textit{Bodirsky, Manuel; Jonsson, Peter; von Oertzen, Timo}, Semilinear program feasibility, 79-90 [Zbl 1248.68236] \textit{Boldo, Sylvie}, Floats and ropes: a case study for formal numerical program verification, 91-102 [Zbl 1248.65045] \textit{Bouyer, Patricia; Forejt, Vojtěch}, Reachability in stochastic timed games, 103-114 [Zbl 1248.91014] \textit{Branco, Mário J. J.; Pin, Jean-Éric}, Equations defining the polynomial closure of a lattice of regular languages, 115-126 [Zbl 1248.68340] \textit{Chaput, Philippe; Danos, Vincent; Panangaden, Prakash; Plotkin, Gordon}, Approximating Markov processes by averaging, 127-138 [Zbl 1248.68322] \textit{Colcombet, Thomas}, The theory of stabilisation monoids and regular cost functions, 139-150 [Zbl 1248.68291] \textit{Colcombet, Thomas; Zdanowski, Konrad}, A tight lower bound for determinization of transition labeled Büchi automata, 151-162 [Zbl 1248.68292] \textit{Dal Lago, Ugo; Martini, Simone}, On constructor rewrite systems and the lambda-calculus, 163-174 [Zbl 1248.68275] \textit{Dax, Christian; Klaedtke, Felix; Lange, Martin}, On regular temporal logics with past, 175-187 [Zbl 1248.68326] \textit{Finkel, Alain; Goubault-Larrecq, Jean}, Forward analysis for WSTS. II: Complete WSTS, 188-199 [Zbl 1248.68352] \textit{Gripon, Vincent; Serre, Olivier}, Qualitative concurrent stochastic games with imperfect information, 200-211 [Zbl 1248.68353] \textit{Jouannaud, Jean-Pierre; van Oostrom, Vincent}, Diagrammatic confluence and completion, 212-222 [Zbl 1248.68277] \textit{Kobayashi, Naoki; Ong, C.-H. Luke}, Complexity of model checking recursion schemes for fragments of the modal mu-calculus, 223-234 [Zbl 1248.68334] \textit{Kuhtz, Lars; Finkbeiner, Bernd}, LTL path checking is efficiently parallelizable, 235-246 [Zbl 1248.68252] \textit{Melliès, Paul-André; Tabareau, Nicolas; Tasson, Christine}, An explicit formula for the free exponential modality of linear logic, 247-260 [Zbl 1248.03080] \textit{Michaliszyn, Jakub}, Decidability of the guarded fragment with the transitive closure, 261-272 [Zbl 1248.03020] \textit{Parys, Pawel; Walukiewicz, Igor}, Weak alternating timed automata, 273-284 [Zbl 1248.03058] \textit{Place, Thomas; Segoufin, Luc}, A decidable characterization of locally testable tree languages, 285-296 [Zbl 1248.68313] \textit{Ummels, Michael; Wojtczak, Dominik}, The complexity of Nash equilibria in simple stochastic multiplayer games, 297-308 [Zbl 1248.91016] \textit{Ahn, Kook Jin; Guha, Sudipto}, Graph sparsification in the semi-streaming model, 328-338 [Zbl 1248.68567] \textit{Anagnostopoulos, Aris; Kumar, Ravi; Mahdian, Mohammad; Upfal, Eli}, Sort me if you can: how to sort dynamic data, 339-350 [Zbl 1248.68178] \textit{Azar, Yossi; Mądry, Aleksander; Moscibroda, Thomas; Panigrahi, Debmalya; Srinivasan, Aravind}, Maximum bipartite flow in networks with adaptive channel width, 351-362 [Zbl 1248.90023] \textit{Chatzigiannakis, Ioannis; Michail, Othon; Spirakis, Paul G.}, Mediated population protocols, 363-374 [Zbl 1248.68081] \textit{Chierichetti, Flavio; Lattanzi, Silvio; Panconesi, Alessandro}, Rumor spreading in social networks, 375-386 [Zbl 1247.05227] \textit{Clementi, Andrea E. F.; Pasquale, Francesco; Silvestri, Riccardo}, MANETS: high mobility can make up for low transmission power, 387-398 [Zbl 1248.68108] \textit{Cooper, Colin; Frieze, Alan; Radzik, Tomasz}, Multiple random walks and interacting particle systems, 399-410 [Zbl 1247.05222] \textit{Cooper, Colin; Ilcinkas, David; Klasing, Ralf; Kosowski, Adrian}, Derandomizing random walks in undirected graphs using locally fair exploration strategies, 411-422 [Zbl 1247.05223] \textit{Daskalakis, Constantinos; Papadimitriou, Christos H.}, On a network generalization of the minmax theorem, 423-434 [Zbl 1248.91006] \textit{De Nicola, Rocco; Latella, Diego; Loreti, Michele; Massink, Mieke}, Rate-based transition systems for stochastic process calculi, 435-446 [Zbl 1248.68350] \textit{Fanghänel, Alexander; Keßelheim, Thomas; Vöcking, Berthold}, Improved algorithms for latency minimization in wireless networks, 447-458 [Zbl 1248.68113] \textit{Fotakis, Dimitris; Kaporis, Alexis C.; Spirakis, Paul G.}, Efficient methods for selfish network design, 459-471 [Zbl 1248.68061] \textit{Friedrich, Tobias; Sauerwald, Thomas; Vilenchik, Dan}, Smoothed analysis of balancing networks, 472-483 [Zbl 1248.68062] \textit{Guerraoui, Rachid; Ruppert, Eric}, Names trump malice: tiny mobile agents can tolerate Byzantine failures, 484-495 [Zbl 1248.68091] \textit{Guha, Sudipto; Munagala, Kamesh}, Multi-armed bandits with metric switching costs, 496-507 [Zbl 1248.91027] \textit{Korula, Nitish; Pál, Martin}, Algorithms for secretary problems on graphs and hypergraphs, 508-520 [Zbl 1248.68573] \textit{Kowalski, Dariusz R.; Pelc, Andrzej}, Leader election in ad hoc radio networks: a keen ear helps, 521-533 [Zbl 1248.68065] \textit{Ibrahim, Maged H.; Kiayias, Aggelos; Yung, Moti; Zhou, Hong-Sheng}, Secure function collection with sublinear storage, 534-545 [Zbl 1248.94072] \textit{Mosk-Aoyama, Damon; Roughgarden, Tim}, Worst-case efficiency analysis of queueing disciplines, 546-557 [Zbl 1248.90040] \textit{Pugliese, Rosario; Tiezzi, Francesco; Yoshida, Nobuko}, On observing dynamic prioritised actions in SOC, 558-570 [Zbl 1248.68099] \textit{Scheideler, Christian; Schmid, Stefan}, A distributed and oblivious heap, 571-582 [Zbl 1248.68174] \textit{Zhang, Li}, Proportional response dynamics in the Fisher market, 583-594 [Zbl 1248.91057]