  The Termination Theorem by Podelski and Rybalchenko states that the reduction
relations which are terminating from any initial state are exactly the
reduction relations whose transitive closure, restricted to the accessible
states, is included in some finite union of well-founded relations. An
alternative statement of the theorem is that terminating reduction relations
are precisely those having a "disjunctively well-founded transition invariant".
From this result the same authors and Byron Cook designed an algorithm checking
a sufficient condition for termination for a while-if program. The algorithm
looks for a disjunctively well-founded transition invariant, made of
well-founded relations of height omega, and if it finds it, it deduces the
termination for the while-if program using the Termination Theorem.
  This raises an interesting question: What is the status of reduction
relations having a disjunctively well-founded transition invariant where each
relation has height omega? An answer to this question can lead to a
characterization of the set of while-if programs which the termination
algorithm can prove to be terminating. The goal of this work is to prove that
they are exactly the set of reduction relations having height omega^n for some
n < omega. Besides, if all the relations in the transition invariant are
primitive recursive and the reduction relation is the graph of the restriction
to some primitive recursive set of a primitive recursive map, then a final
state is computable by some primitive recursive map in the initial state.
  As a corollary we derive that the set of functions, having at least one
implementation in Podelski Rybalchenko while-if language with a well-founded
disjunctively transition invariant where each relation has height omega, is
exactly the set of primitive recursive functions.
