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