This book constitutes the refereed proceedings of the International Conference IFIP TCS 2000 held in Sendai, Japan in August 2000.The 32 revised full papers presented together with nine invited contributions were carefully reviewed and selected from a total of 70 submissions. The papers are organized in two tracks on algorithms, complexity, and models of computation and on logics, semantics, specification, and verification. The book is devoted to exploring new frontiers of theoretical informatics and addresses all current topics in theoretical computer science.