FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science : 23rd Conference, Mumbai India, December 15-17, 2003, Proceedings

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.