FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science : 27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings

by Arvind, V.; Prasad, Sanjiva

• ISBN13: 9783540770497
• ISBN10: 3540770496
• Format: Paperback
• Copyright: 2007-12-20
• Publisher: Springer Verlag

Summary

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: The Challenges for Theory	p. 1
Streaming Algorithms for Selection and Approximate Sorting	p. 9
Adventures in Bidirectional Programming	p. 21
Program Analysis Using Weighted Pushdown Systems	p. 23
The Complexity of Zero Knowledge	p. 52
Contributed Papers
The Priority k-Median Problem	p. 71
"Rent-or-Buy" Scheduling and Cost Coloring Problems	p. 84
Order Scheduling Models: Hardness and Algorithms	p. 96
On Simulatability Soundness and Mapping Soundness of Symbolic Cryptography	p. 108
Key Substitution in the Symbolic Analysis of Cryptographic Protocols	p. 121
Symbolic Bisimulation for the Applied Pi Calculus	p. 133
Non-mitotic Sets	p. 146
Reductions to Graph Isomorphism	p. 158
Strong Reductions and Isomorphism of Complete Sets	p. 168
Probabilistic and Topological Semantics for Timed Automata	p. 179
A Theory for Game Theories	p. 192
An Incremental Bisimulation Algorithm	p. 204
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs	p. 216
Communication Lower Bounds Via the Chromatic Number	p. 228
The Deduction Theorem for Strong Propositional Proof Systems (Extended Abstract)	p. 241
Satisfiability of Algebraic Circuits over Sets of Natural Numbers	p. 253
Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems	p. 265
Synthesis of Safe Message-Passing Systems	p. 277
Automata and Logics for Timed Message Sequence Charts	p. 290
Propositional Dynamic Logic for Message-Passing Systems	p. 303
Better Algorithms and Bounds for Directed Maximum Leaf Problems	p. 316
Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs	p. 328
Covering Graphs with Few Complete Bipartite Subgraphs	p. 340
Safely Composing Security Protocols	p. 352
Computationally Sound Typing for Non-interference: The Case of Deterministic Encryption	p. 364
Bounding Messages for Free in Security Protocols	p. 376
Triangulations of Line Segment Sets in the Plane	p. 388
Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections (Extended Abstract)	p. 400
Finding a Rectilinear Shortest Path in R[superscript 2] Using Corridor Based Staircase Structures	p. 412
Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space	p. 424
Stochastic Muller Games are PSPACE-Complete	p. 436
Solving Parity Games in Big Steps	p. 449
Efficient and Expressive Tree Filters	p. 461
Markov Decision Processes with Multiple Long-Run Average Objectives	p. 473
A Formal Investigation of Diff3	p. 485
Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem	p. 497
Undirected Graphs of Entanglement 2	p. 508
Acceleration in Convex Data-Flow Analysis	p. 520
Model Checking Almost All Paths Can Be Less Expensive Than Checking All Paths	p. 532
Closures and Modules Within Linear Logic Concurrent Constraint Programming	p. 544
Author Index	p. 557
Table of Contents provided by Ingram. All Rights Reserved.