| Contributed Papers |
| A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol Michael Backes, Birgit Pfitzmann 1 |
| Constructions of Sparse Asymmetric Connectors Andreas Baltz, Gerold Jaeger, Anand Srivastav 13 |
| A Separation Logic for Resource Distribution Nicolas Biri, Didier Galmiche 23 |
| An Equational Theory for Transactions Andrew P. Black, Vincent Cremet, Rachid Guerraoui, Martin Odersky 38 |
| Axioms for Regular Words Stephen L. Boom, Zoltan Esik 50 |
| 1-Bounded TWA Cannot Be Determinized Mikolaj Bojanczyk 62 |
| Reachability Analysis of Process Rewrite Systems Ahmed Bouajjani, Tayssir Touili 74 |
| Pushdown Games with Unboundedness and Regular Conditions Alexis-Julien Bouquet, Oliver Serre, Igor Walukiewicz 88 |
| Real-Time Model-Checking: Parameters Eveywhere Veronique Bruyere, Jean-Francois Raskin 100 |
| The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata Arnaud Carayol, Stefan Woehrle 112 |
| Deciding the Security of Protocols with Diffie-Hellman Exponentiation and Products in Exponents Yannick Chevalier, Ralf Kuesters, Michaeel Rusinowitch, Mathieu Turuani 124 |
| Subtyping Constraints in Quasi-lattices Emmanuel Coquery, Francois Fages 136 |
| An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case Nikhil R. Devanur, Vijay V. Vazirani 149 |
| Word Equations over Graph Products Volker Diekert, Markus Lohrey 156 |
| Analysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models Devdatt Dubhashi, Luigi Laura, Alessandro Panconesi 168 |
| Comparing Sequences with Segment Rearrangements Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp 183 |
| On Logically Defined Recognizable Tree Languages Zoltan Esik, Pascal Weil 195 |
| Randomized Time-Space Tradeoffs for Directed Graph Connectivity Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta 208 |
| Distance-Preserving Approximations of Polygonal Paths Joachim Gudmundsson, Giri Narasimhan, Michiel Smid 217 |
| Joint Separation of Geometric Clusters and the Extreme Irregularities of Regular Polyhedra Sumanta Guha 229 |
| On the Covering Steiner Problem Anupam Gupta, Aravind Srinivasan 244 |
| Minimality Results for the Spatial Logics D. Hirschkoff, E. Lozes, D. Sangiorgi 252 |
| Algorithms for Non-uniform Size Data Placement on Parallel Disks Srinivas Kashyap, Samir Khuller 265 |
| Efficient Algorithms for Abelian Group Isomorphism and Related Problems T. Kavitha 277 |
| Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees Jochen Koenemann, R. Ravi 289 |
| Model Checking and Satisfiability for Sabotage Modal Logic Christof Loeding, Philipp Rohde 302 |
| Merging and Sorting By Strip Moves Meena Mahajan, Raghavan Rama, Venkatesh Raman, S. Vijayakumar 314 |
| The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase Sebastian Maneth 326 |
| Distributed Games Swarup Mohalik, Igor Walukiewicz 338 |
| Maintenance of Multidimensional Histograms S. Muthukrishnan, Martin Strauss 352 |
| Tagging Makes Secrecy Decidable with Unbounded Nonces as Well R. Ramanujam, S.P. Suresh 363 |
| Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties Holger Spakowski, Mayur Thakur, Rahul Tripathi 375 |
| On the Greedy Superstring Conjecture Maik Weinard, Georg Schnitger 387 |
| Invited Papers |
| Reasoning about Infinite State Systems Using Boolean Methods Randal E. Bryant 399 |
| Stringent Relativization Jin-Yi Cai, Osamu Watanabe 408 |
| Component-Based Construction of Deadlock-Free Systems Gregor Goessler, Joseph Sifakis 420 |
| Moderately Hard Functions: From Complexity to Spam Fighting Moni Naor 434 |
| Zigzag Products, Expander Constructions, Connections, and Applications Avi Wigderson 443 |
| Author Index 445 |
| Contributed Papers |
| A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol Michael Backes, Birgit Pfitzmann 1 |
| Constructions of Sparse Asymmetric Connectors Andreas Baltz, Gerold Jaeger, Anand Srivastav 13 |
図書
