FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science

Invited Papers.- The Multicore Revolution.- Streaming Algorithms for Selection and Approximate Sorting.- Adventures in Bidirectional Programming.- Program Analysis Using Weighted Pushdown Systems.- The Complexity of Zero Knowledge.- Contributed Papers.- The Priority k-Median Problem.- "Rent-or-Buy" Scheduling and Cost Coloring Problems.- Order Scheduling Models: Hardness and Algorithms.- On Simulatability Soundness and Mapping Soundness of Symbolic Cryptography.- Key Substitution in the Symbolic Analysis of Cryptographic Protocols.- Symbolic Bisimulation for the Applied Pi Calculus.- Non-mitotic Sets.- Reductions to Graph Isomorphism.- Strong Reductions and Isomorphism of Complete Sets.- Probabilistic and Topological Semantics for Timed Automata.- A Theory for Game Theories.- An Incremental Bisimulation Algorithm.- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.- Communication Lower Bounds Via the Chromatic Number.- The Deduction Theorem for Strong Propositional Proof Systems.- Satisfiability of Algebraic Circuits over Sets of Natural Numbers.- Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems.- Synthesis of Safe Message-Passing Systems.- Automata and Logics for Timed Message Sequence Charts.- Propositional Dynamic Logic for Message-Passing Systems.- Better Algorithms and Bounds for Directed Maximum Leaf Problems.- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs.- Covering Graphs with Few Complete Bipartite Subgraphs.- Safely Composing Security Protocols.- Computationally Sound Typing for Non-interference: The Case of Deterministic Encryption.- Bounding Messages for Free in Security Protocols.- Triangulations of Line Segment Sets in the Plane.- ReconstructingConvex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections.- Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures.- Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space.- Stochastic Müller Games are PSPACE-Complete.- Solving Parity Games in Big Steps.- Efficient and Expressive Tree Filters.- Markov Decision Processes with Multiple Long-Run Average Objectives.- A Formal Investigation of Diff3.- Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem.- Undirected Graphs of Entanglement 2.- Acceleration in Convex Data-Flow Analysis.- Model Checking Almost All Paths Can Be Less Expensive Than Checking All Paths.- Closures and Modules Within Linear Logic Concurrent Constraint Programming.