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

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 -