Arvind / Prasad FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science

27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings
2007
ISBN: 978-3-540-77050-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 4855, 560 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Arvind, V.

Prasad, Sanjiva

Inhaltsverzeichnis

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.