FST TCS 2003 : foundations of software technology and theoretical computer science : 23rd conference, Mumbai, India, December 15-17, 2003 : proceedings

This book constitutes the refereed proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2003, held in Mumbai, India in December 2003. The 23 revised full papers presented together with 4 invited papers and the abstract of an invited paper were carefully reviewed and selected from 160 submissions. A broad variety of current topics from the theory of computing are addressed, ranging from algorithmics and discrete mathematics to logics and programming theory. 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. 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. Paritosh K. Pandya, Jaikumar Radhakrishnan (eds.). Includes Bibliographical References And Index. Also Available Via The World Wide Web. Front Matter....Pages - A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol....Pages 1-12 Constructions of Sparse Asymmetric Connectors....Pages 13-22 A Separation Logic for Resource Distribution....Pages 23-37 An Equational Theory for Transactions....Pages 38-49 Axioms for Regular Words....Pages 50-61 1-Bounded TWA Cannot Be Determinized....Pages 62-73 Reachability Analysis of Process Rewrite Systems....Pages 74-87 Pushdown Games with Unboundedness and Regular Conditions....Pages 88-99 Real-Time Model-Checking: Parameters Everywhere....Pages 100-111 The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata....Pages 112-123 Deciding the Security of Protocols with Diffie-Hellman Exponentiation and Products in Exponents....Pages 124-135 Subtyping Constraints in Quasi-lattices....Pages 136-148 An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case....Pages 149-155 Word Equations over Graph Products....Pages 156-167 Analysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models....Pages 168-182 Comparing Sequences with Segment Rearrangements....Pages 183-194 On Logically Defined Recognizable Tree Languages....Pages 195-207 Randomized Time-Space Tradeoffs for Directed Graph Connectivity....Pages 208-216 Distance-Preserving Approximations of Polygonal Paths....Pages 217-228 Joint Separation of Geometric Clusters and the Extreme Irregularities of Regular Polyhedra....Pages 229-243 On the Covering Steiner Problem....Pages 244-251 Minimality Results for the Spatial Logics....Pages 252-264 Algorithms for Non-uniform Size Data Placement on Parallel Disks....Pages 265-276 Efficient Algorithms for Abelian Group Isomorphism and Related Problems....Pages 277-288 Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees....Pages 289-301 Model Checking and Satisfiability for Sabotage Modal Logic....Pages 302-313 Merging and Sorting By Strip Moves....Pages 314-325 The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase....Pages 326-337 Distributed Games....Pages 338-351 Maintenance of Multidimensional Histograms....Pages 352-362 Tagging Makes Secrecy Decidable with Unbounded Nonces as Well....Pages 363-374 Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties....Pages 375-386 On the Greedy Superstring Conjecture....Pages 387-398 Reasoning about Infinite State Systems Using Boolean Methods....Pages 399-407 Stringent Relativization....Pages 408-419 Component-Based Construction of Deadlock-Free Systems....Pages 420-433 Moderately Hard Functions: From Complexity to Spam Fighting....Pages 434-442 Zigzag Products, Expander Constructions, Connections, and Applications....Pages 443-443 Back Matter....Pages - Constitutes the refereed proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2003, held in Mumbai, India in December 2003. This book addresses topics from the theory of computing, which range from algorithmics and discrete mathematics to logics and programming theory.