36. ICALP 2009: Rhodes, Greece - Part II

Track B: Invited Lectures

• Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger:
  A Survey of Stochastic Games with Limsup and Liminf Objectives. 1-15
  
• Georg Gottlob, Gianluigi Greco, Francesco Scarcello:
  Tractable Optimization Problems through Hypergraph-Based Structural Restrictions. 16-30
  

Track B: Contributed Papers

• Lucia Acciai, Michele Boreale:
  Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types. 31-42
  
• Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye:
  When Are Timed Automata Determinizable? 43-54
  
• Martin Beaudry, François Lemieux:
  Faithful Loops for Aperiodic E-Ordered Monoids. 55-66
  
• Achim Blumensath, Martin Otto, Mark Weyer:
  Boundedness of Monadic Second-Order Formulae over Finite Words. 67-78
  
• Manuel Bodirsky, Peter Jonsson, Timo von Oertzen:
  Semilinear Program Feasibility. 79-90
  
• Sylvie Boldo:
  Floats and Ropes: A Case Study for Formal Numerical Program Verification. 91-102
  
• Patricia Bouyer, Vojtech Forejt:
  Reachability in Stochastic Timed Games. 103-114
  
• Mário J. J. Branco, Jean-Éric Pin:
  Equations Defining the Polynomial Closure of a Lattice of Regular Languages. 115-126
  
• Philippe Chaput, Vincent Danos, Prakash Panangaden, Gordon D. Plotkin:
  Approximating Markov Processes by Averaging. 127-138
  
• Thomas Colcombet:
  The Theory of Stabilisation Monoids and Regular Cost Functions. 139-150
  
• Thomas Colcombet, Konrad Zdanowski:
  A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata. 151-162
  
• Ugo Dal Lago, Simone Martini:
  On Constructor Rewrite Systems and the Lambda-Calculus. 163-174
  
• Christian Dax, Felix Klaedtke, Martin Lange:
  On Regular Temporal Logics with Past, . 175-187
  
• Alain Finkel, Jean Goubault-Larrecq:
  Forward Analysis for WSTS, Part II: Complete WSTS. 188-199
  
• Vincent Gripon, Olivier Serre:
  Qualitative Concurrent Stochastic Games with Imperfect Information. 200-211
  
• Jean-Pierre Jouannaud, Vincent van Oostrom:
  Diagrammatic Confluence and Completion. 212-222
  
• Naoki Kobayashi, C.-H. Luke Ong:
  Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus. 223-234
  
• Lars Kuhtz, Bernd Finkbeiner:
  LTL Path Checking Is Efficiently Parallelizable. 235-246
  
• Paul-André Melliès, Nicolas Tabareau, Christine Tasson:
  An Explicit Formula for the Free Exponential Modality of Linear Logic. 247-260
  
• Jakub Michaliszyn:
  Decidability of the Guarded Fragment with the Transitive Closure. 261-272
  
• Pawel Parys, Igor Walukiewicz:
  Weak Alternating Timed Automata. 273-284
  
• Thomas Place, Luc Segoufin:
  A Decidable Characterization of Locally Testable Tree Languages. 285-296
  
• Michael Ummels, Dominik Wojtczak:
  The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games. 297-308
  

Track C: Invited Lecture

• Noam Nisan, Jason Bayer, Deepak Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal R. Varian, Dan Zigmond:
  Google's Auction for TV Ads. 309-327
  

Track C: Contributed Papers

• Kook Jin Ahn, Sudipto Guha:
  Graph Sparsification in the Semi-streaming Model. 328-338
  
• Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal:
  Sort Me If You Can: How to Sort Dynamic Data. 339-350
  
• Yossi Azar, Aleksander Madry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan:
  Maximum Bipartite Flow in Networks with Adaptive Channel Width. 351-362
  
• Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis:
  Mediated Population Protocols. 363-374
  
• Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi:
  Rumor Spreading in Social Networks. 375-386
  
• Andrea E. F. Clementi, Francesco Pasquale, Riccardo Silvestri:
  MANETS: High Mobility Can Make Up for Low Transmission Power. 387-398
  
• Colin Cooper, Alan M. Frieze, Tomasz Radzik:
  Multiple Random Walks and Interacting Particle Systems. 399-410
  
• Colin Cooper, David Ilcinkas, Ralf Klasing, Adrian Kosowski:
  Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies. 411-422
  
• Constantinos Daskalakis, Christos H. Papadimitriou:
  On a Network Generalization of the Minmax Theorem. 423-434
  
• Rocco De Nicola, Diego Latella, Michele Loreti, Mieke Massink:
  Rate-Based Transition Systems for Stochastic Process Calculi. 435-446
  
• Alexander Fanghänel, Thomas Keßelheim, Berthold Vöcking:
  Improved Algorithms for Latency Minimization in Wireless Networks. 447-458
  
• Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis:
  Efficient Methods for Selfish Network Design. 459-471
  
• Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik:
  Smoothed Analysis of Balancing Networks. 472-483
  
• Rachid Guerraoui, Eric Ruppert:
  Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures. 484-495
  
• Sudipto Guha, Kamesh Munagala:
  Multi-armed Bandits with Metric Switching Costs. 496-507
  
• Nitish Korula, Martin Pál:
  Algorithms for Secretary Problems on Graphs and Hypergraphs. 508-520
  
• Dariusz R. Kowalski, Andrzej Pelc:
  Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps. 521-533
  
• Maged H. Ibrahim, Aggelos Kiayias, Moti Yung, Hong-Sheng Zhou:
  Secure Function Collection with Sublinear Storage. 534-545
  
• Damon Mosk-Aoyama, Tim Roughgarden:
  Worst-Case Efficiency Analysis of Queueing Disciplines. 546-557
  
• Rosario Pugliese, Francesco Tiezzi, Nobuko Yoshida:
  On Observing Dynamic Prioritised Actions in SOC. 558-570
  
• Christian Scheideler, Stefan Schmid:
  A Distributed and Oblivious Heap. 571-582
  
• Li Zhang:
  Proportional Response Dynamics in the Fisher Market. 583-594