On the Complexity of Simplification Orderings Joachim Steinbach Fachbereich Informatik, Universitaet Kaiserslautern D-67663 Kaiserslautern, GERMANY E-mail: steinba@informatik.uni-kl.de Abstract Various methods for proving the termination of term rewriting systems have been suggested. Most of them are based on the notion of simplification ordering. In this paper, the theoretical time complexities (of the worst cases) of a collection of well-known simplification orderings will be presented. Keywords Term rewriting systems, termination, orderings, simplification orderings, complexity Source anonymous FTP server ftp.uni-kl.de [131.246.94.94] path: /reports_uni-kl/computer_science/SEKI/1993/papers/ file: Steinbach.SR-93-18.ps.Z