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

by Abramsky, Samson; Gavoille, Cyril; Kirchner, Claude; auf der Heide, Friedhelm Meyer; Spirakis, Paul G.

• ISBN13: 9783642141614
• ISBN10: 3642141617
• Format: Paperback
• Copyright: 2010-07-20
• Publisher: Springer-Verlag New York Inc

Summary

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 6198 contains 60 contributions of track A selected from 222 submissions as well as 2 invited talks.

Table of Contents

Invited Talks
Informative Labeling Schemes (Abstract)	p. 1
Noetherian Spaces in Verification	p. 2
Towards a Theory of Time-Bounded Verification	p. 22
Physical Algorithms	p. 38
Track B. Automata
Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata	p. 52
Pumping and Counting on the Regular Post Embedding Problem	p. 64
Alternation Removal in Büchi Automata	p. 76
Linear Orders in the Pushdown Hierarchy	p. 88
Track C. Communication in Networks
The Serializability of Network Codes	p. 100
How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)	p. 115
Efficient Information Exchange in the Random Phone-Call Model	p. 127
An O(log n)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines	p. 139
Track B. Formal Languages
A Topological Approach to Recognition	p. 151
On LR(k)-Parsers of polynomial Size (Extended Abstract)	p. 163
On Erasing Productions in Random Context Grammars	p. 175
Track B. Semantics
Game Semantics for Call-by-Value Polymorphism	p. 187
What is a Pure Functional?	p. 199
Example-Guided Abstraction Simplification	p. 211
Compositional Closure for Bayes Risk in Probabilistic Noninterference	p. 223
Track C. Fault Tolerance, Ranking
Asynchronous Throughput-Optimal Routing In Malicious Networks	p. 236
Improved Fault Tolerance and Secure Computation on Sparse Networks	p. 249
Sparse Reliable Graph Backbones	p. 261
Approximation Algorithms for Diversified Search Ranking	p. 273
Track B. Graphs Categories and Quantum Information
Rewriting Measurement-Based Quantum Computations with Generalised Flow	p. 285
The Compositional Structure of Multipartite Quantum Entanglement	p. 297
Compositionality in Graph Transformation	p. 309
Track B. Best Paper Award
On p-Optimal Proof Systems and Logics for PTIME	p. 321
Track C. Best Paper Award
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests	p. 333
Track B. Logic
Maximal Decidable Fragments of Halpern and Shoham's Modal Logic of Intervals	p. 345
B and D Are Enough to Make the Halpern-Shoham Logic Undecidable	p. 357
Parameterized Modal Satisfiability	p. 369
Automata for Coalgebras: An Approach Using Predicate Liftings	p. 381
Track C. Privacy, Selfishness
Resolving the Complexity of Some Data Privacy Problems	p. 393
Private and Continual Release of Statistics	p. 405
Envy-Free Pricing in Multi-item Markets	p. 418
Contention Resolution under Selfishness	p. 430
Track B. Concurrency
On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi	p. 442
On Bisimilarity and Substitution in Presence of Replication	p. 454
The Downward-Closure of Petri Net Languages	p. 466
Reachability Games on Extended Vector Addition Systems with State	p. 478
Track C. Mobile Agents
Modelling Mobility: A Discrete Revolution (Extended Abstract)	p. 490
Tell Me Where I Am So I Can Meet You Sooner: (Asynchronous Rendezvous with Location Information)	p. 502
Rendezvous of Mobile Agents without Agreement on Local Orientation	p. 515
Track B. Probabilistic Computation
Probabilistic Automata on Finite Words: Decidable and Undecidable Problems	p. 527
Space-Efficient Scheduling of Stochastically Generated Tasks	p. 539
Exponential Lower Bounds For Policy Iteration	p. 551
Track B. Automata
Regular Temporal Cost Functions	p. 563
Model Checking Succinct and Parametric One-Counter Automata	p. 575
Pebble Weighted Automata and Transitive Closure Logics	p. 587
Energy Parity Games	p. 599
Author Index	p. 611
Table of Contents provided by Ingram. All Rights Reserved.