Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II

Front Matter....Pages -
Nondeterministic Streaming String Transducers....Pages 1-20
An Introduction to Randomness Extractors....Pages 21-41
Invitation to Algorithmic Uses of Inclusion–Exclusion....Pages 42-59
On the Relation between Differential Privacy and Quantitative Information Flow....Pages 60-76
A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem....Pages 77-88
Rice’s Theorem for μ -Limit Sets of Cellular Automata....Pages 89-100
Fault-Tolerant Compact Routing Schemes for General Graphs....Pages 101-112
Local Matching Dynamics in Social Networks....Pages 113-124
Regular Languages of Words over Countable Linear Orderings....Pages 125-136
Algebraic Independence and Blackbox Identity Testing....Pages 137-148
A Fragment of ML Decidable by Visibly Pushdown Automata....Pages 149-161
Krivine Machines and Higher-Order Schemes....Pages 162-173
Relating Computational Effects by ⊤ ⊤-Lifting....Pages 174-185
Constructing Differential Categories and Deconstructing Categories of Games....Pages 186-197
Nondeterminism Is Essential in Small 2FAs with Few Reversals....Pages 198-209
Isomorphism of Regular Trees and Words....Pages 210-221
On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids....Pages 222-233
The Cost of Traveling between Languages....Pages 234-245
Emptiness and Universality Problems in Timed Automata with Positive Frequency....Pages 246-257
Büchi Automata Can Have Smaller Quotients....Pages 258-270
Automata-Based CSL Model Checking....Pages 271-282
A Progress Measure for Explicit-State Probabilistic Model-Checkers....Pages 283-294
Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation....Pages 295-306
On the Semantics of Markov Automata....Pages 307-318
Runtime Analysis of Probabilistic Programs with Unbounded Recursion....Pages 319-331
Approximating the Termination Value of One-Counter MDPs and Stochastic Games....Pages 332-343
Generic Expression Hardness Results for Primitive Positive Formula Comparison....Pages 344-355
Guarded Negation....Pages 356-367
Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates....Pages 368-379
Modular Markovian Logic....Pages 380-391
Programming with Infinitesimals: A While -Language for Hybrid System Modeling....Pages 392-403
Model Checking the Quantitative μ -Calculus on Linear Hybrid Systems....Pages 404-415
On Reachability for Hybrid Automata over Bounded Time....Pages 416-427
Deciding Robustness against Total Store Ordering....Pages 428-440
Multiply-Recursive Upper Bounds with Higman’s Lemma....Pages 441-452
Liveness-Preserving Atomicity Abstraction....Pages 453-465
On Stabilization in Herman’s Algorithm....Pages 466-477
Online Graph Exploration: New Results on Old and New Algorithms....Pages 478-489
Distance Oracles for Vertex-Labeled Graphs....Pages 490-501
Asymptotically Optimal Randomized Rumor Spreading....Pages 502-513
Fast Convergence for Consensus in Dynamic Networks....Pages 514-525
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem....Pages 526-538
Restoring Pure Equilibria to Weighted Congestion Games....Pages 539-551
Existence and Uniqueness of Equilibria for Flows over Time....Pages 552-563
Collusion in Atomic Splittable Routing Games....Pages 564-575
Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation....Pages 576-587
Adaptively Secure Non-interactive Threshold Cryptosystems....Pages 588-600
Content Search through Comparisons....Pages 601-612
Efficient Distributed Communication in Ad-Hoc Radio Networks....Pages 613-624
Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model....Pages 625-636
Convergence Time of Power-Control Dynamics....Pages 637-649
A New Approach for Analyzing Convergence Algorithms for Mobile Robots....Pages 650-661
Back Matter....Pages -