FST TCS 2000: Foundations of Software Technology and Theoretical Science 20th Conference, New Delhi, India, December13-15, 2000 Proceedings

The Foundations of SoftwareTechnology and Theoretical Computer Science c- ference (FST TCS) is a well-established annual event in the theoretical computer science community. The conference provides a forum for researchers to present interesting new results in several areas of theoretical computer science. The c- ference is now in its twentieth year and has continued to attract high-quality submissions and reputed invited speakers. This year'sconference attracted 141 submissions(of which 5 werewithdrawn) from over 25 countries. Each submission was reviewed by at least three referees, with most receiving more than four reviews. The Program Committee met in New Delhi on 5 and 6 August 2000, with many members participating electr- ically over the Internet. The discussions continued over the Internet for several days and we ?nally selected 36 papers for presentation at the conference and inclusion in the proceedings. We thank the Program Committee for their - perlative e?orts in ?nding top quality reviewers and working extremely hard to ensure the quality of the conference. We also thank all our reviewers for prov- ing detailed and informative feedback about the papers. Rich Gerber's START program greatly simpli?ed managing the submissions and the PC work. Wearegratefulto oursixinvited speakers, PeterBuneman, BernardChazelle, Allen Emerson, Martin Gr] otschel, Jos ́ e Meseguer, and Philip Wadler for agr- ing to speak at the conference and for providing written contributions that are included in the proceedings. With the main conference this year, there are two satellite workshops - on RecentAdvancesinProgrammingLanguages and onComputationalGeometry.