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.
Author(s): Pierre Fraigniaud (auth.), Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, Paul G. Spirakis (eds.)
Series: Lecture Notes in Computer Science 6199 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 614
Tags: Algorithm Analysis and Problem Complexity; Computer Communication Networks; Computation by Abstract Devices; Software Engineering; Discrete Mathematics in Computer Science; Information Systems Applications (incl.Internet)
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 -
