FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science

This book constitutes the refereed proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2001, held in Bangalore, India in December 2001. The 23 revised full papers presented together with five invited papers were carefully reviewed and selected from 73 submissions. Among the issues addressed are randomization and derandomization, approximation, Kolmogorov complexity, pseudo-randomness, tree search, model checking, data structures, deterministic algorithms, formal verification, parallel algorithms, minimum-degree spanning trees, scheduling, Petri nets, equivalence logic, and rewriting.