Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II / Edition 1

Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II / Edition 1

by Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide
     
 

ISBN-10: 3642141617

ISBN-13: 9783642141614

Pub. Date: 06/30/2010

Publisher: Springer Berlin Heidelberg

The two-volume set LNCS 6198 and LNCS 6199 constitutes the refereed proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, held in Bordeaux, France, in July 2010.
The 106 revised full papers (60 papers for track A, 30 for track B, and 16 for track C) presented together with 6 invited talks were carefully reviewed and

…  See more details below

Overview

The two-volume set LNCS 6198 and LNCS 6199 constitutes the refereed proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, held in Bordeaux, France, in July 2010.
The 106 revised full papers (60 papers for track A, 30 for track B, and 16 for track C) presented together with 6 invited talks were carefully reviewed and selected from a total of 389 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. LNCS 6199 contains 46 contributions of track B and C selected from 167 submissions as well as 4 invited talks.

Product Details

ISBN-13:
9783642141614
Publisher:
Springer Berlin Heidelberg
Publication date:
06/30/2010
Series:
Lecture Notes in Computer Science / Theoretical Computer Science and General Issues Series, #6199
Edition description:
2010
Pages:
614
Product dimensions:
6.10(w) x 9.20(h) x 0.90(d)

Table of Contents

Invited Talks

Informative Labeling Schemes (Abstract) Pierre Fraigniaud Fraigniaud, Pierre 1

Noetherian Spaces in Verification Jean Goubault-Larrecq Goubault-Larrecq, Jean 2

Towards a Theory of Time-Bounded Verification James Worrell Worrell, James 22

Physical Algorithms Roger Wattenhofer Wattenhofer, Roger 38

Session 1 Track B. Automata

Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata Igor Walukiewicz Walukiewicz, Igor 52

Pumping and Counting on the Regular Post Embedding Problem Philippe Schnoebelen Schnoebelen, Philippe 64

Alternation Removal in Buchi Automata Adin Rosenberg Rosenberg, Adin 76

Linear Orders in the Pushdown Hierarchy Arnaud Carayol Carayol, Arnaud 88

Session 1 Track C. Communication in Networks

The Serializability of Network Codes Robert Kleinberg Kleinberg, Robert 100

How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange) Morteza Zadimoghaddam Zadimoghaddam, Morteza 115

Efficient Information Exchange in the Random Phone-Call Model Leszek Gasieniec Gasieniec, Leszek 127

An O(log n)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines Moti Medina Medina, Moti 139

Session 2 Track B. Formal Languages

A Topological Approach to Recognition Jean-Eric Pin Pin, Jean-Eric 151

On LR(k)-Parsers of polynomial Size (Extended Abstract) Norbert Blum Blum, Norbert 163

On Erasing Productions in Random Context Grammars Georg Zetzsche Zetzsche, Georg 175

Session 4 Track B. Semantics

Game Semantics for Call-by-Value Polymorphism James Laird Laird, James 187

What is a Pure Functional? Helmut Seidl Seidl, Helmut 199

Example-Guided Abstraction Simplification Francesco Ranzato Ranzato, Francesco 211

Compositional Closure for Bayes Risk in Probabilistic Noninterference Carroll Morgan Morgan, Carroll 223

Session 4 Track C. Fault Tolerance, Ranking

Asynchronous Throughput-Optimal Routing In Malicious Networks Rafail Ostrovsky Ostrovsky, Rafail 236

Improved Fault Tolerance and Secure Computation on Sparse Networks Rafail Ostrovsky Ostrovsky, Rafail 249

Sparse Reliable Graph Backbones David Peleg Peleg, David 261

Approximation Algorithms for Diversified Search Ranking Joseph (Seffi) Naor Naor, Joseph (Seffi) 273

Session 5 Track B. Graphs, Categories and Quantum Information

Rewriting Measurement-Based Quantum Computations with Generalised Flow Simon Perdrix Perdrix, Simon 285

The Compositional Structure of Multipartite Quantum Entanglement Aleks Kissinger Kissinger, Aleks 297

Compositionality in Graph Transformation Arend Rensink Rensink, Arend 309

Session 6 Track B. Best Paper Award

On p-Optimal Proof Systems and Logics for PTIME Jorg Flum Flum, Jorg 321

Session 6 Track C. Best Paper Award

Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests Shmuel Zaks Zaks, Shmuel 333

Session 7 Track B. Logic

Maximal Decidable Fragments of Halpern and Shoham's Modal Logic of Intervals Pietro Sala Sala, Pietro 345

B and D Are Enough to Make the Halpern-Shoham Logic Undecidable Emanuel Kieronski Kieronski, Emanuel 357

Parameterized Modal Satisfiability Valia Mitsou Mitsou, Valia 369

Automata for Coalgebras: An Approach Using Predicate Liftings Yde Venema Venema, Yde 381

Session 7 Track C. Privacy, Selfishness

Resolving the Complexity of Some Data Privacy Problems Ryan Williams Williams, Ryan 393

Private and Continual Release of Statistics Dawn Song Song, Dawn 405

Envy-Free Pricing in Multi-item Markets Xiaotie Deng Deng, Xiaotie 418

Contention Resolution under Selfishness Evangelia Pyrga Pyrga, Evangelia 430

Session 8 Track B. Concurrency

On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi Alan Schmitt Schmitt, Alan 442

On Bisimilarity and Substitution in Presence of Replication Damien Pous Pous, Damien 454

The Downward-Closure of Petri Net Languages Harro Wimmel Wimmel, Harro 466

Reachability Games on Extended Vector Addition Systems with States Antonin Kucera Kucera, Antonin 478

Session 8 Track C. Mobile Agents

Modelling Mobility: A Discrete Revolution (Extended Abstract) Riccardo Silvestri Silvestri, Riccardo 490

Tell Me Where I Am So I Can Meet You Sooner: (Asynchronous Rendezvous with Location Information) Arnaud Labourel Labourel, Arnaud 502

Rendezvous of Mobile Agents without Agreement on Local Orientation Shantanu Das Das, Shantanu 515

Session 9 Track B. Probabilistic Computation

Probabilistic Automata on Finite Words: Decidable and Undecidable Problems Youssouf Oualhadj Oualhadj, Youssouf 527

Space-Efficient Scheduling of Stochastically Generated Tasks Michael Luttenberger Luttenberger, Michael 539

Exponential Lower Bounds For Policy Iteration John Fearnley Fearnley, John 551

Session 10 Track B. Automata

Regular Temporal Cost Functions Sylvain Lombardy Lombardy, Sylvain 563

Model Checking Succinct and Parametric One-Counter Automata James Worrell Worrell, James 575

Pebble Weighted Automata and Transitive Closure Logics Marc Zeitoun Zeitoun, Marc 587

Energy Parity Games Laurent Doyen Doyen, Laurent 599

Author Index 611

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >