Foundations of Software Technology and Theoretical Computer Science 19th Conference, Chennai, India, December 13-15, 1999 Proceedings

th This volume contains the proceedings of the 19 FST&TCS conference (Foundations of Software Technology and Theoretical Computer Science), - ganized under the auspices of the Indian Association for Research in Computing Science (http: //www. imsc. ernet. in/ iarcs). This year's conference attracted 84 submissions from as many as 25 dieren t countries. Each submission was reviewed by at least three independent referees. th After a week-long e-mail discussion, the program committee met on the 7 th and 8 of August, 1999, in Chennai and selected 30 papers for inclusion in the conference program. We thank the program committee members and the reviewers for their sincere eorts. We are fortunate to have ve invited speakers this year, providing for a very attractive program: Mart n Abadi (Bell Labs - Lucent Technologies, Palo Alto, USA), Lila Kari (Univ. Western Ontario, Canada), Jean-Jacques L evy (INRIA, Paris, France), Micha Sharir, (Univ. TelAviv, Israel), andSeinosuke Toda (IEC, Tokyo, Japan). Moreover, theconferenceisprecededbyatwo-dayworkshop(- cember 11{12, 1999) on Data Structures and succeeded by a two-day workshop (December 16-17, 1999) on Foundations of Mobile Computation. The conference also features two joint sessions with the International Symposium on - tomata, Algorithms and Computation (December 16{18, 1999, Chennai): Monika Henzinger (Compaq Systems Research, Palo Alto, USA) is presenting a tutorial on Web algorithmics as the last event of FST&TCS and Kurt Mehlhorn (Max-Planck-Institut, Saarbru ]cken, Germany) is giving a talk on algorithm - gineering as the rst event of ISAAC.