  Undecidability of various properties of first order term rewriting systems is
well-known. An undecidable property can be classified by the complexity of the
formula defining it. This gives rise to a hierarchy of distinct levels of
undecidability, starting from the arithmetical hierarchy classifying properties
using first order arithmetical formulas and continuing into the analytic
hierarchy, where also quantification over function variables is allowed.
  In this paper we consider properties of first order term rewriting systems
and classify them in this hierarchy. Weak and strong normalization for single
terms turn out to be Sigma-0-1-complete, while their uniform versions as well
as dependency pair problems with minimality flag are Pi-0-2-complete. We find
that confluence is Pi-0-2-complete both for single terms and uniform.
Unexpectedly weak confluence for ground terms turns out to be harder than weak
confluence for open terms. The former property is Pi-0-2-complete while the
latter is Sigma-0-1-complete (and thereby recursively enumerable).
  The most surprising result is on dependency pair problems without minimality
flag: we prove this to be Pi-1-1-complete, which means that this property
exceeds the arithmetical hierarchy and is essentially analytic.
