37. ICALP 2010: Bordeaux, France - Part I

Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, Paul G. Spirakis (Eds.): Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II. Lecture Notes in Computer Science 6199 Springer 2010, ISBN 978-3-642-14161-4

Invited Talks

Pierre Fraigniaud:
Informative Labeling Schemes. 1
Jean Goubault-Larrecq:
Noetherian Spaces in Verification. 2-21
Joël Ouaknine, James Worrell:
Towards a Theory of Time-Bounded Verification. 22-37
Roger Wattenhofer:
Physical Algorithms. 38-51

Blaise Genest, Hugo Gimbert, Anca Muscholl, Igor Walukiewicz:
Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata. 52-63
Pierre Chambart, Philippe Schnoebelen:
Pumping and Counting on the Regular Post Embedding Problem. 64-75
Udi Boker, Orna Kupferman, Adin Rosenberg:
Alternation Removal in Büchi Automata. 76-87
Laurent Braud, Arnaud Carayol:
Linear Orders in the Pushdown Hierarchy. 88-99

Anna Blasiak, Robert D. Kleinberg:
The Serializability of Network Codes. 100-114
Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Morteza Zadimoghaddam:
How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange). 115-126
Petra Berenbrink, Jurek Czyzowicz, Robert Elsässer, Leszek Gasieniec:
Efficient Information Exchange in the Random Phone-Call Model. 127-138
Guy Even, Moti Medina:
An O(logn)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines. 139-150

Mai Gehrke, Serge Grigorieff, Jean-Eric Pin:
A Topological Approach to Recognition. 151-162
Norbert Blum:
On LR(k)-Parsers of Polynomial Size. 163-174
Georg Zetzsche:
On Erasing Productions in Random Context Grammars. 175-186

James Laird:
Game Semantics for Call-by-Value Polymorphism. 187-198
Martin Hofmann, Aleksandr Karbyshev, Helmut Seidl:
What Is a Pure Functional? 199-210
Roberto Giacobazzi, Francesco Ranzato:
Example-Guided Abstraction Simplification. 211-222
Annabelle McIver, Larissa Meinicke, Carroll Morgan:
Compositional Closure for Bayes Risk in Probabilistic Noninterference. 223-235

Paul Bunn, Rafail Ostrovsky:
Asynchronous Throughput-Optimal Routing in Malicious Networks. 236-248
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky:
Improved Fault Tolerance and Secure Computation on Sparse Networks. 249-260
Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg:
Sparse Reliable Graph Backbones. 261-272
Nikhil Bansal, Kamal Jain, Anna Kazeykina, Joseph Naor:
Approximation Algorithms for Diversified Search Ranking. 273-284

Ross Duncan, Simon Perdrix:
Rewriting Measurement-Based Quantum Computations with Generalised Flow. 285-296
Bob Coecke, Aleks Kissinger:
The Compositional Structure of Multipartite Quantum Entanglement. 297-308
Arend Rensink:
Compositionality in Graph Transformation. 309-320

Yijia Chen, Jörg Flum:
On p-Optimal Proof Systems and Logics for PTIME. 321-332

George B. Mertzios, Ignasi Sau, Mordechai Shalom, Shmuel Zaks:
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests. 333-344

Angelo Montanari, Gabriele Puppis, Pietro Sala:
Maximal Decidable Fragments of Halpern and Shoham's Modal Logic of Intervals. 345-356
Jerzy Marcinkowski, Jakub Michaliszyn, Emanuel Kieronski:
B and D Are Enough to Make the Halpern-Shoham Logic Undecidable. 357-368
Antonis Achilleos, Michael Lampis, Valia Mitsou:
Parameterized Modal Satisfiability. 369-380
Gaëlle Fontaine, Raul Andres Leal, Yde Venema:
Automata for Coalgebras: An Approach Using Predicate Liftings. 381-392

Jeremiah Blocki, Ryan Williams:
Resolving the Complexity of Some Data Privacy Problems. 393-404
T.-H. Hubert Chan, Elaine Shi, Dawn Song:
Private and Continual Release of Statistics. 405-417
Ning Chen, Xiaotie Deng:
Envy-Free Pricing in Multi-item Markets. 418-429
George Christodoulou, Katrina Ligett, Evangelia Pyrga:
Contention Resolution under Selfishness. 430-441

Ivan Lanese, Jorge A. Pérez, Davide Sangiorgi, Alan Schmitt:
On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi. 442-453
Daniel Hirschkoff, Damien Pous:
On Bisimilarity and Substitution in Presence of Replication. 454-465
Peter Habermehl, Roland Meyer, Harro Wimmel:
The Downward-Closure of Petri Net Languages. 466-477
Tomás Brázdil, Petr Jancar, Antonín Kucera:
Reachability Games on Extended Vector Addition Systems with States. 478-489

Andrea E. F. Clementi, Angelo Monti, Riccardo Silvestri:
Modelling Mobility: A Discrete Revolution. 490-501
Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Arnaud Labourel:
Tell Me Where I Am So I Can Meet You Sooner. 502-514
Jérémie Chalopin, Shantanu Das:
Rendezvous of Mobile Agents without Agreement on Local Orientation. 515-526

Hugo Gimbert, Youssouf Oualhadj:
Probabilistic Automata on Finite Words: Decidable and Undecidable Problems. 527-538
Tomás Brázdil, Javier Esparza, Stefan Kiefer, Michael Luttenberger:
Space-Efficient Scheduling of Stochastically Generated Tasks. 539-550
John Fearnley:
Exponential Lower Bounds for Policy Iteration. 551-562

Thomas Colcombet, Denis Kuperberg, Sylvain Lombardy:
Regular Temporal Cost Functions. 563-574
Stefan Göller, Christoph Haase, Joël Ouaknine, James Worrell:
Model Checking Succinct and Parametric One-Counter Automata. 575-586
Benedikt Bollig, Paul Gastin, Benjamin Monmege, Marc Zeitoun:
Pebble Weighted Automata and Transitive Closure Logics. 587-598
Krishnendu Chatterjee, Laurent Doyen:
Energy Parity Games. 599-610

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

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