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

Front Matter....Pages -
Informative Labeling Schemes....Pages 1-1
Noetherian Spaces in Verification....Pages 2-21
Towards a Theory of Time-Bounded Verification....Pages 22-37
Physical Algorithms....Pages 38-51
Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata....Pages 52-63
Pumping and Counting on the Regular Post Embedding Problem....Pages 64-75
Alternation Removal in Büchi Automata....Pages 76-87
Linear Orders in the Pushdown Hierarchy....Pages 88-99
The Serializability of Network Codes....Pages 100-114
How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)....Pages 115-126
Efficient Information Exchange in the Random Phone-Call Model....Pages 127-138
An O (log n )-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines....Pages 139-150
A Topological Approach to Recognition....Pages 151-162
On LR ( k )-Parsers of Polynomial Size....Pages 163-174
On Erasing Productions in Random Context Grammars....Pages 175-186
Game Semantics for Call-by-Value Polymorphism....Pages 187-198
What Is a Pure Functional?....Pages 199-210
Example-Guided Abstraction Simplification....Pages 211-222
Compositional Closure for Bayes Risk in Probabilistic Noninterference....Pages 223-235
Asynchronous Throughput-Optimal Routing in Malicious Networks....Pages 236-248
Improved Fault Tolerance and Secure Computation on Sparse Networks....Pages 249-260
Sparse Reliable Graph Backbones....Pages 261-272
Approximation Algorithms for Diversified Search Ranking....Pages 273-284
Rewriting Measurement-Based Quantum Computations with Generalised Flow....Pages 285-296
The Compositional Structure of Multipartite Quantum Entanglement....Pages 297-308
Compositionality in Graph Transformation....Pages 309-320
On p -Optimal Proof Systems and Logics for PTIME....Pages 321-332
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests....Pages 333-344
Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals....Pages 345-356
B and D Are Enough to Make the Halpern–Shoham Logic Undecidable....Pages 357-368
Parameterized Modal Satisfiability....Pages 369-380
Automata for Coalgebras: An Approach Using Predicate Liftings....Pages 381-392
Resolving the Complexity of Some Data Privacy Problems....Pages 393-404
Private and Continual Release of Statistics....Pages 405-417
Envy-Free Pricing in Multi-item Markets....Pages 418-429
Contention Resolution under Selfishness....Pages 430-441
On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi....Pages 442-453
On Bisimilarity and Substitution in Presence of Replication....Pages 454-465
The Downward-Closure of Petri Net Languages....Pages 466-477
Reachability Games on Extended Vector Addition Systems with States....Pages 478-489
Modelling Mobility: A Discrete Revolution....Pages 490-501
Tell Me Where I Am So I Can Meet You Sooner....Pages 502-514
Rendezvous of Mobile Agents without Agreement on Local Orientation....Pages 515-526
Probabilistic Automata on Finite Words: Decidable and Undecidable Problems....Pages 527-538
Space-Efficient Scheduling of Stochastically Generated Tasks....Pages 539-550
Exponential Lower Bounds for Policy Iteration....Pages 551-562
Regular Temporal Cost Functions....Pages 563-574
Model Checking Succinct and Parametric One-Counter Automata....Pages 575-586
Pebble Weighted Automata and Transitive Closure Logics....Pages 587-598
Energy Parity Games....Pages 599-610
Back Matter....Pages -