Maurice Herlihy (auth.), V. Arvind, Sanjiva Prasad (eds.)3540770496, 9783540770497
The 40 revised full papers presented together with five invited papers were carefully reviewed and selected from 135 submissions. The papers provide original research results in fundamental aspects of computer science as well as reports from the frontline of software technology and theoretical computer science.
A broad variety of current topics from the theory of computing are addressed, ranging from software science, programming theory, systems design and analysis, formal methods, mathematical logic, mathematical foundations, discrete mathematics, combinatorial mathematics, complexity theory, and automata theory to theoretical computer science in general.
Table of contents :
Front Matter….Pages –
The Multicore Revolution….Pages 1-8
Streaming Algorithms for Selection and Approximate Sorting….Pages 9-20
Adventures in Bidirectional Programming….Pages 21-22
Program Analysis Using Weighted Pushdown Systems….Pages 23-51
The Complexity of Zero Knowledge….Pages 52-70
The Priority k -Median Problem….Pages 71-83
“Rent-or-Buy” Scheduling and Cost Coloring Problems….Pages 84-95
Order Scheduling Models: Hardness and Algorithms….Pages 96-107
On Simulatability Soundness and Mapping Soundness of Symbolic Cryptography….Pages 108-120
Key Substitution in the Symbolic Analysis of Cryptographic Protocols….Pages 121-132
Symbolic Bisimulation for the Applied Pi Calculus….Pages 133-145
Non-mitotic Sets….Pages 146-157
Reductions to Graph Isomorphism….Pages 158-167
Strong Reductions and Isomorphism of Complete Sets….Pages 168-178
Probabilistic and Topological Semantics for Timed Automata….Pages 179-191
A Theory for Game Theories….Pages 192-203
An Incremental Bisimulation Algorithm….Pages 204-215
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs….Pages 216-227
Communication Lower Bounds Via the Chromatic Number….Pages 228-240
The Deduction Theorem for Strong Propositional Proof Systems….Pages 241-252
Satisfiability of Algebraic Circuits over Sets of Natural Numbers….Pages 253-264
Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems….Pages 265-276
Synthesis of Safe Message-Passing Systems….Pages 277-289
Automata and Logics for Timed Message Sequence Charts….Pages 290-302
Propositional Dynamic Logic for Message-Passing Systems….Pages 303-315
Better Algorithms and Bounds for Directed Maximum Leaf Problems….Pages 316-327
Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs….Pages 328-339
Covering Graphs with Few Complete Bipartite Subgraphs….Pages 340-351
Safely Composing Security Protocols….Pages 352-363
Computationally Sound Typing for Non-interference: The Case of Deterministic Encryption….Pages 364-375
Bounding Messages for Free in Security Protocols….Pages 376-387
Triangulations of Line Segment Sets in the Plane….Pages 388-399
Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections….Pages 400-411
Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures….Pages 412-423
Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space….Pages 424-435
Stochastic Müller Games are PSPACE-Complete….Pages 436-448
Solving Parity Games in Big Steps….Pages 449-460
Efficient and Expressive Tree Filters….Pages 461-472
Markov Decision Processes with Multiple Long-Run Average Objectives….Pages 473-484
A Formal Investigation of Diff3….Pages 485-496
Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem….Pages 497-507
Undirected Graphs of Entanglement 2….Pages 508-519
Acceleration in Convex Data-Flow Analysis….Pages 520-531
Model Checking Almost All Paths Can Be Less Expensive Than Checking All Paths….Pages 532-543
Closures and Modules Within Linear Logic Concurrent Constraint Programming….Pages 544-556
Back Matter….Pages –
Reviews
There are no reviews yet.