Foundations of Software Technology and Theoretical Computer Science 18th Conference, Chennai, India, December 17-19, 1998 : Proceedings

th This volume contains the proceedings of the 18 FST&TCS conference (Fo- dations of Software Technology and Theoretical Computer Science), organized under the auspices of the Indian Association for Research in Computing Science (http://www. imsc. ernet. in/ iarcs). This year’s conference attracted 93 submissions from as many as 22 co- tries. Each submission was reviewed by at least three independent referees. The Programme Committee met on August 1 and 2, 1998, at Chennai and selected 28 papers for inclusion in the conference programme. We thank the Programme Committee members and the reviewers for their sincere e?orts. We are fortunate to have six invited speakers this year, providing for a very attractive programme: Rajeev Alur, Ken McMillan, Neil Immerman, John Reif, Erik Meineche Schmidt and Umesh Vazirani. The conference has two theme sessions: Model Checking (with invited talks by Alur and McMillan, and 4 c- tributedpapers),andQuantumComputation(withinvitedtalksbySchmidtand Vazirani). Moreover,the conference is preceded by a two-day workshop(Dec- ber 14–15, 1998) on Molecular Computing (organized by Kamala Krithivasan), and a two-day school (December 15–16, 1998) on Finite Model Theory (or- nized by Anuj Dawar and Anil Seth). The Molecular Computation Workshop includes talks by Natasha Jonoska, Kamala Krithivasan, Georghe Paun, John Reif,YasubumiSakakibara,RaniSiromoneyandK. G. Subramanian. Thespe- ers at the Finite Model Theory school include Anuj Dawar, Martin Grohe, Neil Immerman, Anil Seth, Wolfgang Thomas, Moshe Vardi and Victor Vianu.