Publisher Description

This book constitutes the refereed proceedings of the 27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007, held in New Delhi, India, in December 2007. The 40 revised full papers presented together with five invited papers were carefully reviewed. They provide original research results in fundamental aspects of computer science and reports from the frontline of software technology and theoretical computer science.

Table of Contents

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.

Long Description

Thisvolumecontainstheproceedingsofthe27thannualconferenceontheFo- dations of Software Technology and Theoretical Computer Science (FSTTCS 2007) held during December 12-14, 2007 at the India International Centre in New Delhi. The conference was organized under the auspices of the Indian - sociation for Research in Computing Science (IARCS). This year's conference attracted 135 submissions from 31 countries. Except for a few papers that were outside the scope of the conference, each subm- sion was assigned to at least three Programme Committee members, who, with the assistance of external expert researchers, ensured that each paper had at least three independent reviews. Given the high quality of the submissions, the Programme Committee decided to accept 40 papers. We thank all the expert reviewersfor their invaluablehelp. We are verygratefulto the PCmembers who put in enormous time and work in selecting the papers. Without their untiring e'orts the conference would not have been possible. The entire process of submission, refereeing, and the subsequent electronic PC meeting for selecting the papers for the conference program was greatly facilitated by the EasyChair conference management system; we would like to thank Andrei Voronkov and his team for this wonderful software. One of the highlights of FSTTCS is the high quality of the invited talks.

Details