← All problems
Unverified

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 RR is terminating if and only if the dependency pair problem (DP(R),R)(DP(R),R) is terminating. \end{quote} A dependency pair problem is a pair (P,R)(P,R) of TRSs. Such a dependency pair problem is called terminating if it admits no infinite chain, that is, there is no P∪RP \cup R reduction containing infinitely many PP-steps, where PP-steps only occur at the root.

Can we use the dependency pair method to prove relative termination? Here for a pair (R,S)(R,S) of TRSs, RR is said to be terminating modulo SS if there is no R∪SR \cup S reduction containing infinitely many RR-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 ϕ\phi from pairs of TRSs to dependency pair problems, such that for every two TRSs R,SR,S the TRS RR is terminating modulo SS if and only if the dependency pair problem ϕ(R,S)\phi(R,S) 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).

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu