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

Over the past two decades, the Foundations of Software Technology and Th- retical Computer Science (FSTTCS) conferences have been providing an - nual forum in India for the presentation and publication of results in computer science from around the world. This volume contains the proceedings of the 23rd FSTTCS, organized under the aegis of the Indian Association for Research in Computing Science (IARCS). FSTTCS 2003 attracted over 160 submissions from 29 countries. After obt- ning521refereereportswithinaperiodofonemonth,theprogrammecommittee accepted33contributedpapers,themaximumthatcould?tintoatwo-and-ha- day programme. Unfortunately, many good papers had to be turned away. We thankalltheauthorsforsubmittingtheirpaperstoFSTTCS2003.Wethankthe reviewers for the tremendous support they provided to the conference through theirinformedandthoroughreviewsofthepapers.Wesincerelythankthem- bers of the programme committee for lending their names to the conference and for meeting the challenge arising out of the increased number of submissions this year. We are especially grateful to Kamal Lodaya who came down to Mumbai to assist us during the PC meeting. FSTTCS programmes have always featured highly eminent computer sci- tists as invited speakers. It is our great pleasure to thank the invited speakers of FSTTCS 2003, Randal Bryant, Moni Naor, Joseph Sifakis, Osamu Wat- abe and Avi Wigderson, who graciously agreed to speak at the conference and contribute to this volume. For several years now, topical workshops have been organized together with FSTTCS conferences. This year, the conference was preceded by a workshop on Advances in Model Checking, and was followed by a workshop on Algorithms for ProcessingMassiveDataSets.Wethanktheorganizersandspeakersforagreeing to come and share their expertise.

Includes supplementary material: sn.pub/extras

Klappentext

share their expertise.

Inhalt
Contributed Papers.- A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol.- Constructions of Sparse Asymmetric Connectors.- A Separation Logic for Resource Distribution.- An Equational Theory for Transactions.- Axioms for Regular Words.- 1-Bounded TWA Cannot Be Determinized.- Reachability Analysis of Process Rewrite Systems.- Pushdown Games with Unboundedness and Regular Conditions.- Real-Time Model-Checking: Parameters Everywhere.- The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata.- Deciding the Security of Protocols with Diffie-Hellman Exponentiation and Products in Exponents.- Subtyping Constraints in Quasi-lattices.- An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case.- Word Equations over Graph Products.- Analysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models.- Comparing Sequences with Segment Rearrangements.- On Logically Defined Recognizable Tree Languages.- Randomized Time-Space Tradeoffs for Directed Graph Connectivity.- Distance-Preserving Approximations of Polygonal Paths.- Joint Separation of Geometric Clusters and the Extreme Irregularities of Regular Polyhedra.- On the Covering Steiner Problem.- Minimality Results for the Spatial Logics.- Algorithms for Non-uniform Size Data Placement on Parallel Disks.- Efficient Algorithms for Abelian Group Isomorphism and Related Problems.- Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees.- Model Checking and Satisfiability for Sabotage Modal Logic.- Merging and Sorting By Strip Moves.- The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase.- Distributed Games.- Maintenance of Multidimensional Histograms.- Tagging Makes Secrecy Decidable with Unbounded Nonces as Well.- Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.- On the Greedy Superstring Conjecture.- Invited Papers.- Reasoning about Infinite State Systems Using Boolean Methods.- Stringent Relativization.- Component-Based Construction of Deadlock-Free Systems.- Moderately Hard Functions: From Complexity to Spam Fighting.- Zigzag Products, Expander Constructions, Connections, and Applications.