Automata, Languages and Programming : 36th Internatilonal Collogquium, ICALP 2009, Rhodes, greece, July 5-12, 2009, Proceedings, Part II

Annotation The two-volume set LNCS 5555 and LNCS 5556 constitutes the refereed proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, held in Rhodes, Greece, in July 2009. The 126 revised full papers (62 papers for track A, 24 for track B, and 22 for track C) presented were carefully reviewed and selected from a total of 370 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games; on logic, semantics, theory of programming, as well as on foundations of networked computation: models, algorithms and information management. LNCS 5556 contains 46 contributions of tracks B and C selected from 147 submissions as well as 2 invited lectures. This two-volume set lauches the new subline of Lecture Notes in Computer Science, entitled LNCS Advanced Research in Computing and Software Science (ARCoSS) Front Matter....Pages - A Survey of Stochastic Games with Limsup and Liminf Objectives....Pages 1-15 Tractable Optimization Problems through Hypergraph-Based Structural Restrictions....Pages 16-30 Deciding Safety Properties in Infinite-State Pi-Calculus via Behavioural Types....Pages 31-42 When Are Timed Automata Determinizable?....Pages 43-54 Faithful Loops for Aperiodic E-Ordered Monoids....Pages 55-66 Boundedness of Monadic Second-Order Formulae over Finite Words....Pages 67-78 Semilinear Program Feasibility....Pages 79-90 Floats and Ropes: A Case Study for Formal Numerical Program Verification....Pages 91-102 Reachability in Stochastic Timed Games....Pages 103-114 Equations Defining the Polynomial Closure of a Lattice of Regular Languages....Pages 115-126 Approximating Markov Processes by Averaging....Pages 127-138 The Theory of Stabilisation Monoids and Regular Cost Functions....Pages 139-150 A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata....Pages 151-162 On Constructor Rewrite Systems and the Lambda-Calculus....Pages 163-174 On Regular Temporal Logics with Past,....Pages 175-187 Forward Analysis for WSTS, Part II: Complete WSTS....Pages 188-199 Qualitative Concurrent Stochastic Games with Imperfect Information....Pages 200-211 Diagrammatic Confluence and Completion....Pages 212-222 Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus....Pages 223-234 LTL Path Checking Is Efficiently Parallelizable....Pages 235-246 An Explicit Formula for the Free Exponential Modality of Linear Logic....Pages 247-260 Decidability of the Guarded Fragment with the Transitive Closure....Pages 261-272 Weak Alternating Timed Automata....Pages 273-284 A Decidable Characterization of Locally Testable Tree Languages....Pages 285-296 The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games....Pages 297-308 Google’s Auction for TV Ads....Pages 309-327 Graph Sparsification in the Semi-streaming Model....Pages 328-338 Sort Me If You Can: How to Sort Dynamic Data....Pages 339-350 Maximum Bipartite Flow in Networks with Adaptive Channel Width....Pages 351-362 Mediated Population Protocols....Pages 363-374 Rumor Spreading in Social Networks....Pages 375-386 MANETS: High Mobility Can Make Up for Low Transmission Power....Pages 387-398 Multiple Random Walks and Interacting Particle Systems....Pages 399-410 Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies....Pages 411-422 On a Network Generalization of the Minmax Theorem....Pages 423-434 Rate-Based Transition Systems for Stochastic Process Calculi....Pages 435-446 Improved Algorithms for Latency Minimization in Wireless Networks....Pages 447-458 Efficient Methods for Selfish Network Design....Pages 459-471 Smoothed Analysis of Balancing Networks....Pages 472-483 Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures....Pages 484-495 Multi-armed Bandits with Metric Switching Costs....Pages 496-507 Algorithms for Secretary Problems on Graphs and Hypergraphs....Pages 508-520 Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps....Pages 521-533 Secure Function Collection with Sublinear Storage....Pages 534-545 Worst-Case Efficiency Analysis of Queueing Disciplines....Pages 546-557 On Observing Dynamic Prioritised Actions in SOC....Pages 558-570 A Distributed and Oblivious Heap....Pages 571-582 Proportional Response Dynamics in the Fisher Market....Pages 583-594 Back Matter....Pages - ICALP 2009, the 36th edition of the International Colloquium on Automata, Languages and Programming, was held on the island of Rhodes, July 6–10, 2009. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS) which ?rst took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, complexity and games) and track B (focusing on logic, automata, semantics and theory of programming), and of the recently introduced track C (in 2009 focusing on foundations of networked computation). In response to the call for papers, the Program Committee received 370 s- missions: 223 for track A, 84 for track B and 63 for track C. Out of these, 108 papers were selected for inclusion in the scienti?c program: 62 papers for track A, 24 for track B and 22 for track C. The selection was made by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high indeed, and many dese- ing papers could not be selected. ICALP 2009 consisted of ?ve invited lectures and the contributed papers.