The two-volume set LNCS 6755 and LNCS 6756 constitutes the refereed proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, held in Zürich, Switzerland, in July 2011. The 114 revised full papers (68 papers for track A, 29 for track B, and 17 for track C) presented together with 4 invited talks, 3 best student papers, and 3 best papers were carefully reviewed and selected from a total of 398 submissions. The papers are grouped in three major tracks on algorithms, complexity and games; on logic, semantics, automata, and theory of programming; as well as on foundations of networked computation: models, algorithms and information management.
Author(s): Rajeev Alur, Jyotirmoy V. Deshmukh (auth.), Luca Aceto, Monika Henzinger, Jiří Sgall (eds.)
Series: Lecture Notes in Computer Science 6756
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 666
Tags: Logics and Meanings of Programs; Software Engineering; Mathematical Logic and Formal Languages; Computer Communication Networks; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices
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 -
