LEADER 06531nam 22008415 450 001 9910483173803321 005 20230405224120.0 010 $a3-540-77050-X 024 7 $a10.1007/978-3-540-77050-3 035 $a(CKB)1000000000490597 035 $a(SSID)ssj0000317817 035 $a(PQKBManifestationID)11208043 035 $a(PQKBTitleCode)TC0000317817 035 $a(PQKBWorkID)10294858 035 $a(PQKB)10081450 035 $a(DE-He213)978-3-540-77050-3 035 $a(MiAaPQ)EBC6281915 035 $a(MiAaPQ)EBC337389 035 $a(MiAaPQ)EBC4975784 035 $a(Au-PeEL)EBL337389 035 $a(OCoLC)935267656 035 $a(PPN)123729289 035 $a(EXLCZ)991000000000490597 100 $a20100301d2007 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aFSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science $e27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings /$fedited by V. Arvind, Sanjiva Prasad 205 $a1st ed. 2007. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2007. 215 $a1 online resource (XIV, 560 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4855 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-77049-6 320 $aIncludes bibliographical references and index. 327 $aInvited 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 -- Reconstructing Convex 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. 330 $aThis 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 5 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. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4855 606 $aComputer science 606 $aSoftware engineering 606 $aCompilers (Computer programs) 606 $aMachine theory 606 $aAlgorithms 606 $aTheory of Computation 606 $aSoftware Engineering 606 $aComputer Science Logic and Foundations of Programming 606 $aCompilers and Interpreters 606 $aFormal Languages and Automata Theory 606 $aAlgorithms 615 0$aComputer science. 615 0$aSoftware engineering. 615 0$aCompilers (Computer programs) 615 0$aMachine theory. 615 0$aAlgorithms. 615 14$aTheory of Computation. 615 24$aSoftware Engineering. 615 24$aComputer Science Logic and Foundations of Programming. 615 24$aCompilers and Interpreters. 615 24$aFormal Languages and Automata Theory. 615 24$aAlgorithms. 676 $a005.1 702 $aArvind$b V$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aPrasad$b Sanjiva$4edt$4http://id.loc.gov/vocabulary/relators/edt 712 12$aConference on Foundations of Software Technology and Theoretical Computer Science 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910483173803321 996 $aFSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science$9772485 997 $aUNINA