Abramsky / Gavoille / Kirchner Automata, Languages and Programming

37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II
Erscheinungsjahr 2010
ISBN: 978-3-642-14162-1
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 6199, 614 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Abramsky, Samson

Gavoille, Cyril

Kirchner, Claude

Meyer auf der Heide, Friedhelm

Spirakis, Paul

Inhaltsverzeichnis

Invited Talks.- Informative Labeling Schemes.- Noetherian Spaces in Verification.- Towards a Theory of Time-Bounded Verification.- Physical Algorithms.- Session 1-Track B. Automata.- Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata.- Pumping and Counting on the Regular Post Embedding Problem.- Alternation Removal in Büchi Automata.- Linear Orders in the Pushdown Hierarchy.- Session 1-Track C. Communication in Networks.- The Serializability of Network Codes.- How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange).- Efficient Information Exchange in the Random Phone-Call Model.- An O(logn)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines.- Session 2-Track B. Formal Languages.- A Topological Approach to Recognition.- On LR(k)-Parsers of Polynomial Size.- On Erasing Productions in Random Context Grammars.- Session 4-Track B. Semantics.- Game Semantics for Call-by-Value Polymorphism.- What Is a Pure Functional?.- Example-Guided Abstraction Simplification.- Compositional Closure for Bayes Risk in Probabilistic Noninterference.- Session 4-Track C. Fault Tolerance, Ranking.- Asynchronous Throughput-Optimal Routing in Malicious Networks.- Improved Fault Tolerance and Secure Computation on Sparse Networks.- Sparse Reliable Graph Backbones.- Approximation Algorithms for Diversified Search Ranking.- Session 5-Track B. Graphs, Categories and Quantum Information.- Rewriting Measurement-Based Quantum Computations with Generalised Flow.- The Compositional Structure of Multipartite Quantum Entanglement.- Compositionality in Graph Transformation.- Session 6-Track B. Best Paper Award.- On p-Optimal Proof Systems and Logics for PTIME.- Session 6-Track C. Best Paper Award.- Placing Regenerators in Optical Networksto Satisfy Multiple Sets of Requests.- Session 7-Track B. Logic.- Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals.- B and D Are Enough to Make the Halpern–Shoham Logic Undecidable.- Parameterized Modal Satisfiability.- Automata for Coalgebras: An Approach Using Predicate Liftings.- Session 7-Track C. Privacy, Selfishness.- Resolving the Complexity of Some Data Privacy Problems.- Private and Continual Release of Statistics.- Envy-Free Pricing in Multi-item Markets.- Contention Resolution under Selfishness.- Session 8-Track B. Concurrency.- On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi.- On Bisimilarity and Substitution in Presence of Replication.- The Downward-Closure of Petri Net Languages.- Reachability Games on Extended Vector Addition Systems with States.- Session 8-Track C. Mobile Agents.- Modelling Mobility: A Discrete Revolution.- Tell Me Where I Am So I Can Meet You Sooner.- Rendezvous of Mobile Agents without Agreement on Local Orientation.- Session 9-Track B. Probabilistic Computation.- Probabilistic Automata on Finite Words: Decidable and Undecidable Problems.- Space-Efficient Scheduling of Stochastically Generated Tasks.- Exponential Lower Bounds for Policy Iteration.- Session 10-Track B. Automata.- Regular Temporal Cost Functions.- Model Checking Succinct and Parametric One-Counter Automata.- Pebble Weighted Automata and Transitive Closure Logics.- Energy Parity Games.