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

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 -