Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II

This two-volume set of LNCS 7391 and LNCS 7392 constitutes the refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and selected from 432 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation. Front Matter....Pages - On Multiple Keyword Sponsored Search Auctions with Budgets....Pages 1-12 A Theory Independent Curry-De Bruijn-Howard Correspondence....Pages 13-15 Standing on the Shoulders of a Giant....Pages 16-22 Session Types and Distributed Computing....Pages 23-23 Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations....Pages 24-26 Randomized Mechanisms for Multi-unit Auctions....Pages 27-29 Algebraic Synchronization Trees and Processes....Pages 30-41 Streaming Tree Transducers....Pages 42-53 Causal Graph Dynamics....Pages 54-66 Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers....Pages 67-78 Monadic Datalog Containment....Pages 79-91 A Machine-Independent Characterization of Timed Languages....Pages 92-103 Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets....Pages 104-115 Toward Model Theory with Data Values....Pages 116-127 Robust Reachability in Timed Automata: A Game-Based Approach....Pages 128-140 Minimizing Expected Termination Time in One-Counter Markov Decision Processes....Pages 141-152 Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata....Pages 153-164 A Saturation Method for Collapsible Pushdown Systems....Pages 165-176 Regular Languages Are Church-Rosser Congruential....Pages 177-188 Time and Parallelizability Results for Parity Games with Bounded Treewidth....Pages 189-200 Nominal Completion for Rewrite Systems with Binders....Pages 201-213 Discrete Generalised Polynomial Functors....Pages 214-226 Computing Game Metrics on Markov Decision Processes....Pages 227-238 Deciding First Order Properties of Matroids....Pages 239-250 Pebble Games with Algebraic Rules....Pages 251-262 Exponential Lower Bounds and Separation for Query Rewriting....Pages 263-274 Lattices of Logical Fragments over Words....Pages 275-286 On the Expressive Power of Cost Logics over Infinite Words....Pages 287-298 Coalgebraic Predicate Logic....Pages 299-311 Algorithmic Games for Full Ground References....Pages 312-324 Two-Level Game Semantics, Intersection Types, and Recursion Schemes....Pages 325-336 An Automata-Theoretic Model of Idealized Algol....Pages 337-350 Towards a Unified Theory of Operational and Axiomatic Semantics....Pages 351-363 Loader and Urzyczyn Are Logically Related....Pages 364-376 Languages of Profinite Words and the Limitedness Problem....Pages 377-389 The Complexity of Mean-Payoff Automaton Expression....Pages 390-402 On the Locality of Some NP-Complete Problems....Pages 403-415 Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs....Pages 416-427 Super-Fast Distributed Algorithms for Metric Facility Location....Pages 428-439 Preventing Unraveling in Social Networks: The Anchored k -Core Problem....Pages 440-451 Edge Fault Tolerance on Sparse Networks....Pages 452-463 Incentive Ratios of Fisher Markets....Pages 464-475 Computational Complexity of Traffic Hijacking under BGP and S-BGP....Pages 476-487 Efficiency-Revenue Trade-Offs in Auctions....Pages 488-499 Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports....Pages 500-512 A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs....Pages 513-524 Minimizing Rosenthal Potential in Multicast Games....Pages 525-536 Multiparty Proximity Testing with Dishonest Majority from Equality Testing....Pages 537-548 Anonymous Card Shuffling and Its Applications to Parallel Mixnets....Pages 549-560 Byzantine Agreement with a Rational Adversary....Pages 561-572 Random Hyperbolic Graphs: Degree Sequence and Clustering....Pages 573-585 Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks....Pages 586-597 Counting Arbitrary Subgraphs in Data Streams....Pages 598-609 k -Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth....Pages 610-622 Contention Issues in Congestion Games....Pages 623-635 Online Mechanism Design (Randomized Rounding on the Fly)....Pages 636-647 Online Packing with Gradually Improving Capacity Estimations and Applications to Network Lifetime Maximization....Pages 648-659 Distributed Algorithms for Network Diameter and Girth....Pages 660-672 Back Matter....Pages -