38. ICALP 2011: Zurich, Switzerland - Part II

Luca Aceto, Monika Henzinger, Jiri Sgall (Eds.): Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II. Lecture Notes in Computer Science 6756 Springer 2011, ISBN 978-3-642-22011-1

Invited Lectures

Rajeev Alur, Jyotirmoy V. Deshmukh:
Nondeterministic Streaming String Transducers. 1-20
Ronen Shaltiel:
An Introduction to Randomness Extractors. 21-41
Thore Husfeldt:
Invitation to Algorithmic Uses of Inclusion-Exclusion. 42-59
Mário S. Alvim, Miguel E. Andrés, Konstantinos Chatzikokolakis, Catuscia Palamidessi:
On the Relation between Differential Privacy and Quantitative Information Flow. 60-76

Shi Li:
A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem. 77-88
Martin Delacourt:
Rice's Theorem for μ-Limit Sets of Cellular Automata. 89-100
Shiri Chechik:
Fault-Tolerant Compact Routing Schemes for General Graphs. 101-112

Martin Hoefer:
Local Matching Dynamics in Social Networks. 113-124
Olivier Carton, Thomas Colcombet, Gabriele Puppis:
Regular Languages of Words over Countable Linear Orderings. 125-136
Malte Beecken, Johannes Mittmann, Nitin Saxena:
Algebraic Independence and Blackbox Identity Testing. 137-148

David Hopkins, Andrzej S. Murawski, C.-H. Luke Ong:
A Fragment of ML Decidable by Visibly Pushdown Automata. 149-161
Sylvain Salvati, Igor Walukiewicz:
Krivine Machines and Higher-Order Schemes. 162-173
Shin-ya Katsumata:
Relating Computational Effects by ⊤ ⊤-Lifting. 174-185
Jim Laird, Giulio Manzonetto, Guy McCusker:
Constructing Differential Categories and Deconstructing Categories of Games. 186-197

Christos A. Kapoutsis:
Nondeterminism Is Essential in Small 2FAs with Few Reversals. 198-209
Markus Lohrey, Christian Mathissen:
Isomorphism of Regular Trees and Words. 210-221
Georg Zetzsche:
On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids. 222-233
Michael Benedikt, Gabriele Puppis, Cristian Riveros:
The Cost of Traveling between Languages. 234-245

Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Amélie Stainer:
Emptiness and Universality Problems in Timed Automata with Positive Frequency. 246-257
Lorenzo Clemente:
Büchi Automata Can Have Smaller Quotients. 258-270
Lijun Zhang, David N. Jansen, Flemming Nielson, Holger Hermanns:
Automata-Based CSL Model Checking. 271-282
Xin Zhang, Franck van Breugel:
A Progress Measure for Explicit-State Probabilistic Model-Checkers. 283-294

Silvia Crafa, Francesco Ranzato:
Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation. 295-306
Yuxin Deng, Matthew Hennessy:
On the Semantics of Markov Automata. 307-318
Tomás Brázdil, Stefan Kiefer, Antonín Kucera, Ivana Hutarová Vareková:
Runtime Analysis of Probabilistic Programs with Unbounded Recursion. 319-331
Tomás Brázdil, Václav Brozek, Kousha Etessami, Antonín Kucera:
Approximating the Termination Value of One-Counter MDPs and Stochastic Games. 332-343

Simone Bova, Hubie Chen, Matthew Valeriote:
Generic Expression Hardness Results for Primitive Positive Formula Comparison. 344-355
Vince Bárány, Balder ten Cate, Luc Segoufin:
Guarded Negation. 356-367
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin:
Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates. 368-379
Luca Cardelli, Kim G. Larsen, Radu Mardare:
Modular Markovian Logic. 380-391

Kohei Suenaga, Ichiro Hasuo:
Programming with Infinitesimals: A While-Language for Hybrid System Modeling. 392-403
Diana Fischer, Lukasz Kaiser:
Model Checking the Quantitative μ-Calculus on Linear Hybrid Systems. 404-415
Thomas Brihaye, Laurent Doyen, Gilles Geeraerts, Joël Ouaknine, Jean-François Raskin, James Worrell:
On Reachability for Hybrid Automata over Bounded Time. 416-427

Ahmed Bouajjani, Roland Meyer, Eike Möhlmann:
Deciding Robustness against Total Store Ordering. 428-440
Sylvain Schmitz, Ph. Schnoebelen:
Multiply-Recursive Upper Bounds with Higman's Lemma. 441-452
Alexey Gotsman, Hongseok Yang:
Liveness-Preserving Atomicity Abstraction. 453-465
Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, James Worrell, Lijun Zhang:
On Stabilization in Herman's Algorithm. 466-477

Nicole Megow, Kurt Mehlhorn, Pascal Schweitzer:
Online Graph Exploration: New Results on Old and New Algorithms. 478-489
Danny Hermelin, Avivit Levy, Oren Weimann, Raphael Yuster:
Distance Oracles for Vertex-Labeled Graphs. 490-501
Benjamin Doerr, Mahmoud Fouz:
Asymptotically Optimal Randomized Rumor Spreading. 502-513
T.-H. Hubert Chan, Li Ning:
Fast Convergence for Consensus in Dynamic Networks. 514-525

Kook Jin Ahn, Sudipto Guha:
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem. 526-538
Konstantinos Kollias, Tim Roughgarden:
Restoring Pure Equilibria to Weighted Congestion Games. 539-551
Roberto Cominetti, José R. Correa, Omar Larré:
Existence and Uniqueness of Equilibria for Flows over Time. 552-563
Chien-Chung Huang:
Collusion in Atomic Splittable Routing Games. 564-575

Michael T. Goodrich, Michael Mitzenmacher:
Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. 576-587
Benoît Libert, Moti Yung:
Adaptively Secure Non-interactive Threshold Cryptosystems. 588-600
Amin Karbasi, Stratis Ioannidis, Laurent Massoulié:
Content Search through Comparisons. 601-612

Last update Fri May 25 08:16:30 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page