+612 9045 4394
Fst Tcs 2003: Foundations of Software Technology and Theoretical Computer Science : 23rd Conference, Mumbai India, December 15-17, 2003, Proceedings - Paritosh K. Pandya

Fst Tcs 2003: Foundations of Software Technology and Theoretical Computer Science

23rd Conference, Mumbai India, December 15-17, 2003, Proceedings

Paperback Published: 3rd December 2003
ISBN: 9783540206804
Number Of Pages: 454

Share This Book:


or 4 easy payments of $36.74 with Learn more
Ships in 5 to 9 business days

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.

A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocolp. 1
Constructions of Sparse Asymmetic Connectorsp. 13
A Separation Logic for Resource Distributionp. 23
An Equational Theory for Transactionsp. 38
Axioms for Regular Wordsp. 50
1-Bounded TWA Cannot Be Determinedp. 62
Reachability Analysis of Process Rewrite Systemsp. 74
Pushdown Games with Unboundedness and Regular Conditionsp. 88
Real-Time Model-Checking: Parameters Everywherep. 100
The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automatap. 112
Deciding the Security of Protocols with Diffie-Hellman Exponentiation and Products in Exponentsp. 124
Subtyping Constraints in Quasi-latticesp. 136
An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Casep. 149
Word Equations over Graph Productsp. 156
Analysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Modelsp. 168
Comparing Sequences with Segment Rearrangementsp. 183
On Logically Defined Recognizable Tree Languagesp. 195
Randomized Time-Space Tradeoffs for Directed Graph Connectivityp. 208
Distance-Preserving Approximations of Polygonal Pathsp. 217
Joint Separation of Geometric Clusters and the Extreme Irregularities of Regular Polyhedrap. 229
On the Covering Steiner Problemp. 244
Minimality Results for the Spatial Logicsp. 252
Algorithms for Non-uniform Size Data Placement on Parallel Disksp. 265
Efficient Algorithms for Abelian Group Isomorphism and Related Problemsp. 277
Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Treesp. 289
Model Checking and Satisfiability for Sabotage Modal Logicp. 302
Merging and Sorting By Strip Movesp. 314
The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increasep. 326
Distributed Gamesp. 338
Maintenance of Multidimensional Histogramsp. 352
Tagging Makes Secrecy Decidable with Unbounded Nonces as Wellp. 363
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Propertiesp. 375
On the Greedy Superstring Conjecturep. 387
Reasoning about Infinite State Systems Using Boolean Methodsp. 399
Stringent Relativizationp. 408
Component-Based Construction of Deadlock-Free Systemsp. 420
Moderately Hard Functions: From Complexity to Spam Fightingp. 434
Zigzag Products, Expander Constructions, Connections, and Applicationsp. 443
Author Indexp. 445
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540206804
ISBN-10: 3540206809
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 454
Published: 3rd December 2003
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 2.39
Weight (kg): 0.64