FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

Contributed Papers

1. A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol

   • Michael Backes, Birgit Pfitzmann

   Pages 1-12

2. Constructions of Sparse Asymmetric Connectors

   • Andreas Baltz, Gerold Jäger, Anand Srivastav

   Pages 13-22

3. A Separation Logic for Resource Distribution

   • Nicolas Biri, Didier Galmiche

   Pages 23-37

4. An Equational Theory for Transactions

   • Andrew P. Black, Vincent Cremet, Rachid Guerraoui, Martin Odersky

   Pages 38-49

5. Axioms for Regular Words

   • Stephen L. Bloom, Zoltán Ésik

   Pages 50-61

6. 1-Bounded TWA Cannot Be Determinized

   • Mikołaj Bojañczyk

   Pages 62-73

7. Reachability Analysis of Process Rewrite Systems

   • Ahmed Bouajjani, Tayssir Touili

   Pages 74-87

8. Pushdown Games with Unboundedness and Regular Conditions

   • Alexis-Julien Bouquet, Oliver Serre, Igor Walukiewicz

   Pages 88-99

9. Real-Time Model-Checking: Parameters Everywhere

   • Véronique Bruyère, Jean-François Raskin

   Pages 100-111

10. The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata

    • Arnaud Carayol, Stefan Wöhrle

    Pages 112-123

11. Deciding the Security of Protocols with Diffie-Hellman Exponentiation and Products in Exponents

    • Yannick Chevalier, Ralf Küsters, Michaël Rusinowitch, Mathieu Turuani

    Pages 124-135

12. Subtyping Constraints in Quasi-lattices

    • Emmanuel Coquery, François Fages

    Pages 136-148

13. An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case

    • Nikhil R. Devanur, Vijay V. Vazirani

    Pages 149-155

14. Word Equations over Graph Products

    • Volker Diekert, Markus Lohrey

    Pages 156-167

15. Analysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models

    • Devdatt Dubhashi, Luigi Laura, Alessandro Panconesi

    Pages 168-182

16. Comparing Sequences with Segment Rearrangements

    • Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp

    Pages 183-194

17. On Logically Defined Recognizable Tree Languages

    • Zoltán Ésik, Pascal Weil

    Pages 195-207

18. Randomized Time-Space Tradeoffs for Directed Graph Connectivity

    • Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta

    Pages 208-216

19. Distance-Preserving Approximations of Polygonal Paths

    • Joachim Gudmundsson, Giri Narasimhan, Michiel Smid

    Pages 217-228