Can we use the dependency pair method to prove relative termination?
The source page states the original problem together with its recorded qualifications and progress updates as follows.
The key of the success of the dependency pair method in proving termination is the following property from [Giesl and Zantema, 2010], stated in more recent terminology: \begin{quote} A TRS is terminating if and only if the dependency pair problem is terminating. \end{quote} A dependency pair problem is a pair of TRSs. Such a dependency pair problem is called terminating if it admits no infinite chain, that is, there is no reduction containing infinitely many -steps, where -steps only occur at the root.
Can we use the dependency pair method to prove relative termination? Here for a pair of TRSs, is said to be terminating modulo if there is no reduction containing infinitely many -steps. This is the same requirement as for termination of a dependency pair problem, except that the first TRS in a dependency pair problem may only be used for root steps. So, more precisely, the open problem is:
\begin{quote} Find a ``useful'' effectively computable function from pairs of TRSs to dependency pair problems, such that for every two TRSs the TRS is terminating modulo if and only if the dependency pair problem is terminating. \end{quote}
Here, useful'' means that the resulting dependency pair problem $\phi(R,S)$ should be easy'' (i.e., suitable for automated
termination analysis by existing tools).
